2018-07-07
早上复习NewTrain...
NewTrain3 bzoj2342 双倍回文
题解:
这题不算难 就是manacher+数据结构
令一个位置i代表i与i+1之间的那个位置(对称轴)
对于一个位置i 我们找最小的j 满足j+1到i组成了一个题目中说的w^r 也就是双倍回文串的第二部分
这个怎么找呢
预处理f[i]表示以位置i为对称轴的回文串的最长长度的一半(就是向一边的最长长度) 那么只要满足下面两个条件
1.i \leq f[j]+j 2.i- \frac{f[i]} 2 \leq j
维护一个堆和一个set 堆中存储pair{f[j]+j,j} set中存储j
我们把i向右移动1的时候
把堆中堆顶弹出 直到堆顶的元素的f[j]+j>=i
同时 每弹出一个元素 就把它在set中对应的序号erase掉
弹出完后 我们要寻找最小的j满足第二个条件 只要在set中二分即可
最后再把i给压入堆和set中
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=2000100;
int n;
string ss;
int f[maxn],p[maxn];
char tmp[maxn];
void doit(){
tmp[0]='$';
tmp[1]='#';
for(int i=0;i<n;i++){
tmp[2*i+2]=ss[i];
tmp[2*i+3]='#';
}
n=2*(n+1);
tmp[n]='\0';
int mx=0,id=0;
for(int i=1;i<n;i++){
if(i<mx)
p[i]=min(p[2*id-i],mx-i);
else p[i]=1;
while(tmp[i+p[i]]==tmp[i-p[i]]) p[i]++;
if(mx<i+p[i]){
mx=i+p[i];
id=i;
}
}
n=ss.size();
ss=' '+ss;
for(int i=1;i<=n;i++)
f[i]=(p[i*2+1]-1)/2;
}
int main(){
#ifdef LZT
freopen("in","r",stdin);
#endif
scanf("%d",&n);
cin>>ss;
doit();
set<int> s;
s.clear();
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
s.insert(1);
pq.push(make_pair(f[1]+1,1));
int ans=0;/*
for(int i=1;i<=n;i++)
cout<<f[i]<<' ';
cout<<endl;*/
for(int i=2;i<=n;i++){
while(!pq.empty()){
pair<int,int> nw=pq.top();
if(nw.first<i){
pq.pop();
s.erase(nw.second);
continue;
}
break;
}/*
for(set<int>::iterator it=s.begin();it!=s.end();it++){
cout<<*it<<' ';
}
cout<<endl;*/
int wnt=i-f[i]/2;
//cout<<i<<' '<<wnt<<endl;
set<int>::iterator it=s.lower_bound(wnt);
if(it==s.end()){
pq.push(make_pair(f[i]+i,i));
s.insert(i);
continue;
}
int j=*it;
ans=max(ans,(i-j)*4);
pq.push(make_pair(f[i]+i,i));
s.insert(i);
}
printf("%d\n",ans);
return 0;
}
Review:
1.一开始我把i- \frac {f[i]} 2写成了i- \frac {f[i]+1} 2
细节上要注意
- manacher的时候先把字符串变形
我一开始是这么写的
string tmp;
tmp.clear();
tmp=tmp+"$#";
for(int i=0;i<n;i++)
tmp=tmp+ss[i]+'#';
n=2*(n+1);
tmp[n]='\0';
但是这样会超时 可能在string后面加一个字符的复杂度与字符串长度有关
所以得改成这样
tmp[0]='$';
tmp[1]='#';
for(int i=0;i<n;i++){
tmp[2*i+2]=ss[i];
tmp[2*i+3]='#';
}
n=2*(n+1);
tmp[n]='\0';
这样就不超时啦
NewTrain3 bzoj2301 Problem b
题解:
基础的数论题
感觉莫比乌斯反演的题都是什么gcd 什么统计满足要求数对的个数等等
但是我还是不会使用莫比乌斯反演...%>_<%
先把a c 减1之后 a b c d都除以k
用容斥原理把x∈(a,b) y∈(c,d) 变成 calc(b,d)-calc(a,d)-calc(b,c)-calc(a,c)
要计算\sum_{x=1}^{n} \sum_{y=1}^{m} [gcd(x,y)==1]
我们令f[i]表示1 \leq x \leq n, 1 \leq y \leq m, gcd(x,y)=i的(x,y)的数量 令g[i]表示1 \leq x \leq n, 1 \leq y \leq m, i|gcd(x,y)的(x,y)的数量
那么g[i]=[\frac n i] \times [\frac m i]
并且有g[n]=\sum_{n|d} f[d]
所以用莫比乌斯反演得到f[n]=\sum_{n|d} {g[n]\times μ(\frac d n)}
我们要求f[1] 只要求\sum_{i=1}^{min(n,m)} {μ(i) \times \frac n i \times \frac m i}
我们发现\frac n i \times \frac m i的取值只有2\sqrt n+2\sqrt m种 因此可以预处理μ的前缀和 然后枚举每种取值累加即可
与当前的i取值相同的最大的i的值可以用min(n/(n/i),m/(m/i))算出 加上1就是下一个取值的最小的i
坑点: 自然溢出!!! 一开始用longlong发现会变成负的 于是用int自然溢出...
Code:
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int miu[50050];
int pr[50050],cnt;
bool isp[50050];
int n,a,b,c,d,k;
vector<int> pos;
ll calc(int N,int M){
ll ret=0;
int t=min(N,M),last;
for(int i=1;i<=t;i=last+1){
last=min(N/(N/i),M/(M/i));
ret=ret+(N/i)*(M/i)*(miu[last]-miu[i-1]);
}
return ret;
}
int main(){
#ifdef LZT
freopen("in","r",stdin);
#endif
n=read();
miu[1]=1;
memset(isp,1,sizeof(isp));
isp[1]=0;
for(int i=2;i<=50000;i++){
if(isp[i]){
pr[++cnt]=i;
miu[i]=-1;
}
for(int j=1;j<=cnt && i*pr[j]<=50000;j++){
isp[i*pr[j]]=0;
if(i%pr[j]!=0) miu[i*pr[j]]=miu[i]*-1;
if(i%pr[j]==0){
miu[i*pr[j]]=0;
break;
}
}
}
for(int i=1;i<=50000;i++)
miu[i]+=miu[i-1];
while(n--){
a=read(),b=read(),c=read(),d=read(),k=read();
a--;c--;
a/=k;b/=k;c/=k;d/=k;
// cout<<a<<' '<<b<<' '<<c<<' '<<d<<endl;
ll ans=calc(b,d)-calc(b,c)-calc(a,d)+calc(a,c);
printf("%d\n",ans);
}
return 0;
}
Review:
关于枚举每种取值我原来的写法是这样的
pos.clear();
for(int i=1;i<=sqrt(N);i++) pos.push_back(i);
for(int i=N/(int)(sqrt(N))-1;i>=1;i--) pos.push_back(N/(i+1)+1);
for(int i=1;i<=sqrt(M);i++) pos.push_back(i);
for(int i=M/(int)(sqrt(M))-1;i>=1;i--) pos.push_back(M/(i+1)+1);
pos.push_back(min(N,M)+1);
sort(pos.begin(),pos.end());
pos.erase(unique(pos.begin(),pos.end()),pos.end());
for(int i=0;i<pos.size()-1;i++){
int nw=pos[i],nxt=pos[i+1];
ll res=(N/nw)*(M/nw);
ret=ret+res*(miu[nxt-1]-miu[nw-1]);
}
这样会超时(vector比较慢??)
按理说复杂度是O(n\sqrt n logn)不会超时的啊...
于是改成了
int t=min(N,M),last;
for(int i=1;i<=t;i=last+1){
last=min(N/(N/i),M/(M/i));
ret=ret+(N/i)*(M/i)*(miu[last]-miu[i-1]);
}
这样去掉一个log就不超时了
枚举权值的时候经常用
下午开了一场TJOI2014 Day1
没仔细想 就上课了
晚上做了一下
第二题比较可做 我好像做烦了...
bzoj5155 [Tjoi2014]电源插排
题解:
我的做法:
首先用大根堆维护每一个连续的段的长度和段的起始点 用set维护每一个人的位置和他的编号
每次来一个人 就把堆顶元素取出 然后找到这一段的中心位置nw给这个人 记录下来 然后把堆顶元素弹出 然后把这一段去掉nw之后分成的两段压进堆里 再把(nw,k)压进set中
如果一个人走掉 找到这个人的位置nw 就把在set中找到这个位置的前驱(如果没有就是1) 和后继(如果没有就是n) 分别记为l,r 然后把(l,nw-1),(nw+1,r)合并成一段 处理好压进堆中 原来的两端从堆中删掉(记录一个map表示删除次数来完成删除) 再把set中对应的元素erase掉
现在我们就完成了对数据的处理
问题变成 m次操作 在一个位置上+1 在一个位置上-1 查询区间和
离散化之后用基础数据结构维护一下即可
网上的做法:
这题显然是一道线段树的题啦！不过却有许多细节要注意。
首先，将一个人的占据视为阻隔，那么一个区间需要维护几个值：
此区间内最大区间的长度
此区间内最大区间的起始位置
从左向右扩展的最大长度
从右向左扩展的最大长度
此区间内被占据的个数
那么，合并区间的方法就显而易见了，人的进入就相当于单点修改。
但由于区间有 1e9 那么大，所以必须动态开点，以编号为下标储存。
另外每个人的坐标无序，用 Hash 处理即可。
一个人插入的位置就是当前根节点的②值、加上①值除以2，
同时用一个数组记录，以便其离开时查找。
那么总时间复杂度就是优美的 O(QlogN) 。
---分割线---
感觉还是我的做法比较通俗易懂...
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int n,m;
set<pair<int,int> > pos;
priority_queue<pair<int,int> > pq;
map<pair<int,int>,int> app;
map<int,int> res;
map<int,int> M;
struct query{
int opt;
int a,b;
};
query ord[100100];
vector<int> pp;
int calc(int x){
return (int)(lower_bound(pp.begin(),pp.end(),x)-pp.begin())+1;
}
#define lowbit(x) (x&-x)
int a[1000100];
void add(int pos,int val){
while(pos<=1000000){
a[pos]+=val;
pos=pos+lowbit(pos);
}
}
int sum(int pos){
int ret=0;
while(pos){
ret+=a[pos];
pos-=lowbit(pos);
}
return ret;
}
int main(){
#ifdef LZT
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif
n=read(),m=read();
pq.push(make_pair(n,1));
for(int i=1;i<=m;i++){
int k=read();
if(k==0){
int l=read(),r=read();
ord[i].opt=1;
ord[i].a=l;
ord[i].b=r;
}
else if(M[k]==0){
while(app[pq.top()]){
app[pq.top()]--;
pq.pop();
}
int nw=pq.top().first;
int ind=pq.top().second;
pq.pop();
res[k]=ind+nw/2;
M[k]=1;
if(res[k]>ind) pq.push(make_pair(res[k]-ind,ind));
if(res[k]<ind+nw-1) pq.push(make_pair(ind+nw-1-res[k],res[k]+1));
pos.insert(make_pair(res[k],k));
ord[i].opt=2;
ord[i].a=res[k];
ord[i].b=1;
}
else{
set<pair<int,int> >::iterator it=pos.find(make_pair(res[k],k));
int l=res[k],r=res[k];
ord[i].opt=2;
ord[i].a=res[k];
ord[i].b=-1;
M[k]=0;
if(it!=pos.begin()){
it--;
l=(*it).first+1;
it++;
}
else l=1;
app[make_pair(res[k]-l,l)]++;
it++;
if(it!=pos.end())
r=(*it).first-1;
else r=n;
it--;
pos.erase(it);
app[make_pair(r-res[k],res[k]+1)]++;
pq.push(make_pair(r-l+1,l));
res[k]=0;
}
}
for(int i=1;i<=m;i++){
if(ord[i].opt==2)
pp.push_back(ord[i].a);
else{
pp.push_back(ord[i].a);
pp.push_back(ord[i].b);
}
}
sort(pp.begin(),pp.end());
pp.erase(unique(pp.begin(),pp.end()),pp.end());
for(int i=1;i<=m;i++){
if(ord[i].opt==2)
ord[i].a=calc(ord[i].a);
else{
ord[i].a=calc(ord[i].a);
ord[i].b=calc(ord[i].b);
}
}
for(int i=1;i<=m;i++){
if(ord[i].opt==1)
printf("%d\n",sum(ord[i].b)-sum(ord[i].a-1));
else
add(ord[i].a,ord[i].b);
}
return 0;
}
Review:
这题一开始一直RE
问题出在人的序号比较大 记录每个人的位置的时候应该用map我忘记了 使用的数组...
所以要离散化的题目注意 是不是所有该离散的值都离散了 不要漏了
bzoj5156 [Tjoi2014]拼图
题解:
暴力dfs枚举每个碎片放在什么位置
竟然就过了...
据说正解是舞蹈链 完全没听说过
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
inline int get(){
char c=getchar();
while(c!='0' && c!='1') c=getchar();
return c-'0';
}
int n;
int mp[20][5][5];
int l[20],r[20],s[20];
int ans;
int gr[5][5];
int res[5][5];
void dfs(int nw){
if(ans==2) return;
if(nw==n+1){
ans++;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
res[i][j]=gr[i][j];
return;
}
int nwx,nwy;
for(int i=1;i<=l[nw];i++)
for(int j=1;j<=r[nw];j++)
if(mp[nw][i][j]==1){
nwx=i;nwy=j;
break;
}
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
if(gr[i][j]==0){
bool ok=1;
for(int a=1;a<=l[nw];a++)
for(int b=1;b<=r[nw];b++)
if(mp[nw][a][b]==1)
if(gr[a-nwx+i][b-nwy+j] || a-nwx+i>4 || b-nwy+j>4 || a-nwx+i<1 || b-nwy+j<1){
ok=0;
break;
}
if(!ok) continue;
for(int a=1;a<=l[nw];a++)
for(int b=1;b<=r[nw];b++)
if(mp[nw][a][b]==1)
gr[a-nwx+i][b-nwy+j]=nw;
dfs(nw+1);
if(ans==2) return;
for(int a=1;a<=l[nw];a++)
for(int b=1;b<=r[nw];b++)
if(mp[nw][a][b]==1)
gr[a-nwx+i][b-nwy+j]=0;
}
}
int main(){
#ifdef LZT
freopen("in","r",stdin);
#endif
while(scanf("%d",&n)!=EOF){
memset(mp,0,sizeof(mp));
memset(gr,0,sizeof(gr));
memset(res,0,sizeof(res));
int sum=0;
for(int i=1;i<=n;i++){
s[i]=0;
l[i]=read(),r[i]=read();
for(int j=1;j<=l[i];j++)
for(int k=1;k<=r[i];k++){
mp[i][j][k]=get();
if(mp[i][j][k]==1) s[i]++;
}
sum+=s[i];
}
ans=0;
if(sum!=16){
puts("No solution");
continue;
}
dfs(1);
if(ans==0){
puts("No solution");
continue;
}
else if(ans==1){
puts("Yes, only one!");
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++)
cout<<res[i][j];
cout<<endl;
}
}
else{
puts("Yes, many!");
continue;
}
}
return 0;
}
Review:
暴力出奇迹!!!
剩下还有一题 匹配 据说是一个基础的费用流题 但是连费用流都没写过的蒟蒻我只好先学习费用流...
bzoj5154 [Tjoi2014]匹配
题解:
首先第一问就是一个最大费用最大流
然后第二问 裸的方法是把每一条最大流里存在的边删掉 然后再跑一遍最大费用最大流 这样的复杂度是O(n^5) 显然不行
我们发现如果一条边(x,y)可以被替换 我们就可以找到另一种从x到y的方式使得这条路径上的cost与原来的cost相同
所以我们只需把(x,y)的反向边先设成满流 然后从x到y再増广一次 如果能够增广并且cost与(x,y)的cost相同 那么这条边不一定存在 否则一定存在 最后再把(x,y)的反向边的流量调回去就可以了
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
ll x=0,f=1;char c=getchar();
while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0' && c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
int n;
int a[100][100];
struct Edge{
int fr,to,cap,flow,cost;
};
struct MCMF{
int m;
vector<Edge> edges;
vector<int> G[300];
int vis[300],d[300],pre[300],a[300];
void addedge(int fr,int to,int cap,int cost){
edges.push_back((Edge){fr,to,cap,0,cost});
edges.push_back((Edge){to,fr,0,0,-cost});
m=edges.size();
G[fr].push_back(m-2);
G[to].push_back(m-1);
}
bool spfa(int s,int t){
for(int i=1;i<=n;i++) d[i]=-1e9;
d[s]=0;
vis[s]=1;
queue<int> Q;
Q.push(s);
a[s]=1e9;
while(!Q.empty()){
int u=Q.front();Q.pop();
vis[u]=0;
for(int i=0;i<G[u].size();i++){
Edge &e=edges[G[u][i]];
if(e.cap>e.flow && d[e.to]<d[u]+e.cost){
d[e.to]=d[u]+e.cost;
pre[e.to]=G[u][i];
a[e.to]=min(a[u],e.cap-e.flow);
if(!vis[e.to]) Q.push(e.to),vis[e.to]=1;
}
}
}
if(d[t]==-1e9) return 0;
return 1;
}
void doit(int s,int t,int &flow,int &cost){
flow+=a[t];
cost+=a[t]*d[t];
int nw=t;
while(nw!=s){
edges[pre[nw]].flow+=a[t];
edges[pre[nw]^1].flow-=a[t];
nw=edges[pre[nw]].fr;
}
}
int calc(int s,int t){
int flow=0,cost=0;
while(spfa(s,t)) doit(s,t,flow,cost);
return cost;
}
void work(){
int nwn=(n-2)/2;
for(int i=0;i<m;i++){
if(edges[i].flow<edges[i].cap && edges[i].cap) continue;
if(edges[i].fr>=1 && edges[i].fr<=nwn && edges[i].to>nwn && edges[i].to<=2*nwn){
edges[i^1].flow=edges[i^1].cap;
//cout<<edges[i].fr<<' '<<edges[i].to-nwn<<endl;
if(spfa(edges[i].fr,edges[i].to) && d[edges[i].to]!=edges[i].cost){
printf("%d %d\n",edges[i].fr,edges[i].to-nwn);
}
edges[i^1].flow=-edges[i].flow;
}
}
}
} gr;
int main(){
#ifdef LZT
freopen("in","r",stdin);
#endif
n=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
a[i][j]=read();
gr.addedge(i,j+n,1,a[i][j]);
}
int s=n*2+1,t=n*2+2;
for(int i=1;i<=n;i++)
gr.addedge(s,i,1,0);
for(int i=n+1;i<=n+n;i++)
gr.addedge(i,t,1,0);
n=t;
printf("%d\n",gr.calc(s,t));
gr.work();
return 0;
}
Review:
网络流当图变得很少的时候往往可以通过一些简单的操作或性质去完成新的问题 不需要重新跑一遍
