【热烈庆祝ZOJ回归】
P1002：简单的DFS
#include <cstdio>
#include <cstring>
#include <algorithm>
][];
int N;
int input()
{
scanf("%d",&N);
;i<N;i++) scanf("%s",map[i]);
return N;
}
][];
,sizeof(disable)); }
int dfs(int cur)
{
)
][N-]>- || map[N-][N-]== : ;
int c = cur / N;
int r = cur % N;
)
);
);
for(int i=c;i<N && map[i][r]=='.';i++)
) disable[i][r]=cur;
for(int j=r;j<N && map[c][j]=='.';j++)
) disable[c][j]=cur;
res=std::max(res,dfs(cur+)+);
for(int i=c;i<N && map[i][r]=='.';i++)
;
for(int j=r;j<N && map[c][j]=='.';j++)
;
return res;
}
//cur=N*c+r
int main()
{
while(input())
{
init();
printf());
}
;
}Problem：ZOJ P1002
P1005：简单的DFSx2（Orz排行榜里那些28K的，我太弱所以用了1236K(￣▽￣")）
另外不要吐槽人家丑陋的代码٩(×̯×)۶
#include <cstdio>
#include <cstring>
#include <algorithm>
int A,B,N;
bool input()
{
return scanf("%d%d%d",&A,&B,&N)!=EOF;
}
][];
const char str_success[]="success";
const char str_pour[]="pour";
const char str_empty[]="empty";
const char str_fill[]="fill";
struct Cmd
{
const char* cmdType;
char v1,v2;
Cmd(const char* _cmd,char _v1,char _v2):
cmdType(_cmd),v1(_v1),v2(_v2) {}
void output()
{
if(cmdType==str_success) printf("%s\n",str_success);
else if(cmdType==str_pour) printf("%s %c %c\n",str_pour,v1,v2);
else if(cmdType==str_fill) printf("%s %c\n",str_fill,v1);
else printf("%s %c\n",str_empty,v1);
}
};
#include <stack>
std::stack<Cmd> dfsStack;
void init()
{
memset(ins,,sizeof(ins));
}
bool dfs(int a,int b)
{
ins[a][b]=true;
if(b==N)
{
dfsStack.push(Cmd(str_success,'a','a'));
return true;
}
][b] && dfs(,b))
{
dfsStack.push(Cmd(str_empty,'A','A'));
return true;
}
] && dfs(a,))
{
dfsStack.push(Cmd(str_empty,'B','B'));
return true;
}
if(a<A && !ins[A][b] && dfs(A,b))
{
dfsStack.push(Cmd(str_fill,'A','A'));
return true;
}
if(b<B && !ins[a][B] && dfs(a,B))
{
dfsStack.push(Cmd(str_fill,'B','B'));
return true;
}
int ra=A-a;
int rb=B-b;
if(a>=rb)
{
if(!ins[a-rb][B] && dfs(a-rb,B))
{
dfsStack.push(Cmd(str_pour,'A','B'));
return true;
}
}
else
{
][a+b] && dfs(,a+b))
{
dfsStack.push(Cmd(str_pour,'A','B'));
return true;
}
}
if(b>=ra)
{
if(!ins[A][b-ra] && dfs(A,b-ra))
{
dfsStack.push(Cmd(str_pour,'B','A'));
return true;
}
}
else
{
] && dfs(a+b,))
{
dfsStack.push(Cmd(str_pour,'B','A'));
return true;
}
}
return false;
}
void output()
{
while(!dfsStack.empty())
{
dfsStack.top().output();
dfsStack.pop();
}
}
int main()
{
while(input())
{
init();
dfs(,);
output();
}
;
}Problem：ZOJ P1005
P1025：贪心
#include <cstdio>
#include <cstring>
#include <algorithm>
;
int s[maxN];
int ans;
#include <utility>
typedef std::pair<int,int> Pr;
Pr st[maxN];
int N;
void input()
{
scanf("%d",&N);
;i<=N;i++)
scanf("%d%d",&st[i].first,&st[i].second);
}
int solve()
{
std::sort(st+,st+N+);
ans=;
;i<=N;i++)
{
bool ok=false;
;j<=ans && !ok;j++)
if(st[i].second>=s[j])
{
s[j]=st[i].second;
ok=true;
}
if(!ok)
s[++ans]=st[i].second;
}
return ans;
}
int main()
{
int cs; scanf("%d",&cs);
while(cs--)
{
input();
printf("%d\n",solve());
}
;
}Problem：ZOJ P1025
P1074：裸的最大子矩阵
#include <cstdio>
#include <cstring>
#include <algorithm>
;
int v[maxN][maxN];
int p[maxN][maxN]; //prefix
int N;
void input()
{
scanf("%d",&N);
;i<=N;i++)
;j<=N;j++)
scanf("%d",v[i]+j);
}
void init()
{
;j<=N;j++)
{
p[][j]=;
p[][j]=v[][j];
;i<=N;i++)
p[i][j]=p[i-][j]+v[i][j];
}
}
int solve()
{
int ans=0x90000000;
;u<=N;u++)
for(int d=u;d<=N;d++)
{
;
;j<=N;j++)
{
opt=opt<?(p[d][j]-p[u-][j]):opt+(p[d][j]-p[u-][j]);
ans=std::max(ans,opt);
}
}
return ans;
}
int main()
{
input();
init();
printf("%d\n",solve());
;
}Problem：ZOJ P1074
P1093：DAG最长路，DP或者SPFA都可以解决
（代码君已死）
P1107：记忆化搜索（直接DP比较难写）
#include <cstdio>
#include <cstring>
#include <algorithm>
;
int opt[maxN][maxN];
int val[maxN][maxN];
int N,K;
bool input()
{
scanf("%d%d",&N,&K);
) return false;
;i<N;i++)
;j<N;j++)
scanf("%d",val[i]+j);
return true;
}
void init()
{
memset(opt,,sizeof(opt));
}
int search(int hor,int ver)
{
if(opt[hor][ver]) return opt[hor][ver];
;u<=K && hor-u>=;u++)
if(val[hor-u][ver]>val[hor][ver])
opt[hor][ver]=std::max(opt[hor][ver],search(hor-u,ver));
;d<=K && hor+d<N;d++)
if(val[hor+d][ver]>val[hor][ver])
opt[hor][ver]=std::max(opt[hor][ver],search(hor+d,ver));
;l<=K && ver-l>=;l++)
if(val[hor][ver-l]>val[hor][ver])
opt[hor][ver]=std::max(opt[hor][ver],search(hor,ver-l));
;r<=K && ver+r<N;r++)
if(val[hor][ver+r]>val[hor][ver])
opt[hor][ver]=std::max(opt[hor][ver],search(hor,ver+r));
opt[hor][ver]+=val[hor][ver];
return opt[hor][ver];
}
int main()
{
while(input())
{
init();
printf(,));
}
;
}Problem：ZOJ P1107
P1108：LIS
#include <cstdio>
#include <cstring>
#include <algorithm>
;
struct Mouse
{
int weight;
int speed;
int idx;
bool operator < (const Mouse& other) const
{
return this->weight > other.weight;
}
};
Mouse ms[maxN];
;
void input()
{
while(scanf("%d%d",&ms[N].weight,&ms[N].speed)!=EOF)
{ ms[N].idx=N; N++; }
N--;
}
int dp[maxN];
int last[maxN];
void init()
{
;i<=N;i++) dp[i]=;
;i<=N;i++) last[i]=i;
}
void solve()
{
init();
,mxn=;
std::sort(ms+,ms+N+);
;i<=N;i++)
;j<i;j++)
if(ms[j].weight>ms[i].weight && ms[j].speed<ms[i].speed)
{
>dp[i])
{
dp[i]=dp[j]+;
last[i]=j;
if(dp[i]>mx)
{
mx=dp[i];
mxn=i;
}
}
}
printf("%d\n",mx);
while(last[mxn]!=mxn)
{
printf("%d\n",ms[mxn].idx);
mxn=last[mxn];
}
printf("%d\n",ms[mxn].idx);
}
int main()
{
input();
solve();
;
}Problem：ZOJ P1108
P1149：很裸的多重背包（一开始居然没发现，果然自己弱爆了……）
#include <cstdio>
#include <cstring>
#include <algorithm>
;
;
const char* success="Can be divided.";
const char* fail="Can't be divided.";
const char* tpl="Collection #%d:\n%s\n\n";
int dp[maxV];
int N;
int v[maxN];
void init()
{
memset(dp,,sizeof(dp));
N=;
}
];
;
bool proc()
{
;i<=;i++) scanf("%d",cnt+i);
bool end=true;
;i<=;i++) if(cnt[i]) { end=false; break; }
if(end) return false;
;
;i<=;i++) sum+=cnt[i]*i;
)
{
printf(tpl,++cs,fail);
return true;
}
sum>>=;
init();
;i<=;i++)
{
;
while(x<=cnt[i])
{
v[++N]=x*i;
cnt[i]-=x;
x<<=;
}
if(cnt[i]) v[++N]=cnt[i]*i;
}
;i<=N;i++)
for(int j=sum;j>=v[i];j--)
dp[j]=std::max(dp[j],dp[j-v[i]]+v[i]);
printf(tpl,++cs,dp[sum]==sum?success:fail);
return true;
}
int main()
{
while(proc());
;
}Problem：ZOJ P1149
由于只需判定可行性，所以此题的dp数组可以用bool代替，初值为dp[0]=true
#include <cstdio>
#include <cstring>
#include <algorithm>
;
;
const char* success="Can be divided.";
const char* fail="Can't be divided.";
const char* tpl="Collection #%d:\n%s\n\n";
bool dp[maxV];
int N;
int v[maxN];
void init()
{
memset(dp,,sizeof(dp));
N=;
}
];
;
bool proc()
{
;i<=;i++) scanf("%d",cnt+i);
bool end=true;
;i<=;i++) if(cnt[i]) { end=false; break; }
if(end) return false;
;
;i<=;i++) sum+=cnt[i]*i;
)
{
printf(tpl,++cs,fail);
return true;
}
sum>>=;
init();
;i<=;i++)
{
;
while(x<=cnt[i])
{
v[++N]=x*i;
cnt[i]-=x;
x<<=;
}
if(cnt[i]) v[++N]=cnt[i]*i;
}
dp[]=true;
;i<=N;i++)
for(int j=sum;j>=v[i];j--)
dp[j]|=dp[j-v[i]];
printf(tpl,++cs,dp[sum]?success:fail);
return true;
}
int main()
{
while(proc());
;
}Problem：ZOJ P1149（Optimized）
P1196：DP，dp[x][y]表示前x个餐馆处设置第y个depot，其之前部分的最小代价。代码中使用滚动数组压缩掉了第2维
#include <cstdio>
#include <cstring>
#include <algorithm>
;
;
const int inf=0x3f3f3f3f;
int dp[maxN];
int dist[maxN];
int N,K;
bool input()
{
scanf("%d%d",&N,&K);
if(!N) return false;
;i<=N;i++) scanf("%d",dist+i);
dist[N+]=inf;
dist[]=-inf;
return true;
}
int gap[maxN][maxN];
void initGap()
{
memset(gap,,sizeof(gap));
;i<N;i++)
;j<=N+;j++)
;k<j;k++)
gap[i][j]+=std::min(dist[j]-dist[k],dist[k]-dist[i]);
}
int solve()
{
memset(dp,0x3f,sizeof(dp));
for(int i=N;i;i--)
dp[i]=gap[][i];
;t<=K;t++)
{
for(int i=N;i>=t;i--)
;j>=;j--)
dp[i]=std::min(dp[i],dp[j]+gap[j][i]);
}
int ans=inf;
for(int i=K;i<=N;i++)
ans=std::min(ans,dp[i]+gap[i][N+]);
return ans;
}
;
int main()
{
while(input())
{
initGap();
printf("Chain %d\nTotal distance sum = %d\n\n",++cs,solve());
}
;
}Problem：ZOJ P1196
P1440：置换数+逆序对
如果代码中加一句#undef TEST，我们实际上就对val进行了离散化（比一般的排序+lower_bound要高效一些）
此外需要注意一下数据范围，逆序对数可能爆int
#include <cstdio>
#include <cstring>
#include <algorithm>
;
int val[maxN];
int pos[maxN];
bool vis[maxN];
int N;
void input()
{
scanf("%d",&N);
;i<=N;i++)
{
scanf("%d",val+i);
pos[i]=i;
}
}
inline bool cmp(int x,int y)
{
return val[x] < val[y];
}
inline void swap(int* x,int* y)
{
int t=*x; *x=*y; *y=t;
}
#define TEST
int getMinSwapCnt()
{
std::sort(pos+,pos+N+,cmp);
memset(vis,,sizeof(vis));
#ifndef TEST
;i<=N;i++) val[pos[i]]=i;
#endif
;
;i<=N;i++)
if(!vis[i])
{
#ifndef TEST
for(int j=i;!vis[j];j=val[j]) vis[j]=true;
#else
for(int j=i;!vis[j];j=pos[j]) vis[j]=true;
#endif
++res;
}
return N-res;
}
typedef long long int64;
int64 mergeSort_aux(int left,int right)
{
;
==right)
{
;
; }
}
;
int64 res=mergeSort_aux(left,mid)+mergeSort_aux(mid+,right);
;
int p=left;
while(i<=mid && j<=right)
{
if(val[i]<val[j]) pos[p++]=val[i++];
else
{
pos[p++]=val[j++];
res+=(mid+-i);
}
}
for(;i<=mid;i++) pos[p++]=val[i];
for(;j<=right;j++) pos[p++]=val[j];
memcpy(val+left,pos+left,(right-left+)*sizeof(int));
return res;
}
int64 getInvPairCnt()
{
,N);
}
#include <iostream>
int main()
{
input();
std::cout<<getMinSwapCnt()<<"\n";
std::cout<<getInvPairCnt()<<"\n";
;
}Problem：ZOJ P1440
P1985：单调栈
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
;
int h[maxN];
int l[maxN],r[maxN];
int s[maxN],p;
int N;
bool input()
{
scanf("%d",&N);
if(!N) return false;
;i<N;i++) scanf("%d",h+i);
return true;
}
typedef long long int64;
int64 solve()
{
p=-;
;i<N;i++)
{
&& h[s[p]]>=h[i];p--);
l[i]=(p==-)?:s[p]+;
s[++p]=i;
}
p=-;
;i--)
{
&& h[s[p]]>=h[i];p--);
r[i]=(p==-)?N:s[p];
s[++p]=i;
}
int64 ans();
;i<N;i++)
ans=std::max(ans,int64(h[i])*(r[i]-l[i]));
return ans;
}
int main()
{
while(input()) std::cout<<solve()<<"\n";
;
}Problem：ZOJ P1985
P2112：树套树或者平方分割均可
详见：http://www.cnblogs.com/Onlynagesha/p/5355133.html
template <class T>
struct SbtNode
{
typedef SbtNode<T> Node;
Node* lch;
Node* rch;
T val;
int lSize;
int rSize;
SbtNode(const T& _val):
lch(),rch(),val(_val),lSize(),rSize() {}
void assign(const T& _val)
{
lch=rch=;
val=_val;
lSize=rSize=;
}
};
template <class T,class Comp>
struct SizeBlcTree
{
,Left=,Right= };
typedef SbtNode<T> Node;
typedef SizeBlcTree<T,Comp> Sbt;
Node* root;
Comp cmp;
SizeBlcTree():root() {}
~SizeBlcTree() { clear(); }
void clear_aux(Node* _cur)
{
if(_cur->lch) clear_aux(_cur->lch);
if(_cur->rch) clear_aux(_cur->rch);
delete _cur;
}
void clear()
{
if(root) clear_aux(root);
root=;
}
Node* lRotate(Node* _cur)
{
Node* next=_cur->rch;
_cur->rch=next->lch;
next->lch=_cur;
_cur->rSize=next->lSize;
next->lSize+=(_cur->lSize+);
return next;
}
Node* rRotate(Node* _cur)
{
Node* next=_cur->lch;
_cur->lch=next->rch;
next->rch=_cur;
_cur->lSize=next->rSize;
next->rSize+=(_cur->rSize+);
return next;
}
Node* insert_aux(const T& _val,Node* _cur)
{
if(!_cur) return new Node(_val);
if(cmp(_val,_cur->val))
{
++_cur->lSize;
_cur->lch=insert_aux(_val,_cur->lch);
if(_cur->lch->lSize > _cur->rSize) return rRotate(_cur);
else if(_cur->lch->rSize > _cur->rSize)
{
_cur->lch=lRotate(_cur->lch);
return rRotate(_cur);
}
else return _cur;
}
else
{
++_cur->rSize;
_cur->rch=insert_aux(_val,_cur->rch);
if(_cur->rch->rSize > _cur->lSize) return lRotate(_cur);
else if(_cur->rch->lSize > _cur->lSize)
{
_cur->rch=rRotate(_cur->rch);
return lRotate(_cur);
}
else return _cur;
}
}
Sbt& operator << (const T& _val)
{
root=insert_aux(_val,root);
return *this;
}
Node* erase_aux(const T& _val,Node* _cur,bool& _found)
{
if(!_cur)
{
_found=false;
;
}
if(cmp(_val,_cur->val))
{
_cur->lch=erase_aux(_val,_cur->lch,_found);
if(_found) --_cur->lSize;
return _cur;
}
if(cmp(_cur->val,_val))
{
_cur->rch=erase_aux(_val,_cur->rch,_found);
if(_found) --_cur->rSize;
return _cur;
}
_found=true;
;
;
;
Node* res;
Node* &prev=res;
switch(status)
{
:
delete _cur;
;
:
res=_cur->lch;
delete _cur;
return res;
:
res=_cur->rch;
delete _cur;
return res;
:
prev=_cur;
if(prev->rch->lch)
{
--prev->rSize;
prev=prev->rch;
while(prev->lch->lch)
{
--prev->lSize;
prev=prev->lch;
}
_cur->val=prev->lch->val;
prev->lch=erase_aux(prev->lch->val,prev->lch,_found);
--prev->lSize;
}
else
{
_cur->val=_cur->rch->val;
_cur->rch=erase_aux(_cur->rch->val,_cur->rch,_found);
--_cur->rSize;
}
return _cur;
}
}
Sbt& operator >> (const T& _val)
{
bool found=false;
root=erase_aux(_val,root,found);
return *this;
}
int notMoreCount(const T& _val)
{
Node* cur=root;
;
while(cur)
{
if(cmp(_val,cur->val)) cur=cur->lch;
else
{
res+=(cur->lSize+);
cur=cur->rch;
}
}
return res;
}
int lessCount(const T& _val)
{
Node* cur=root;
;
while(cur)
{
if(cmp(cur->val,_val))
{
res+=(cur->lSize+);
cur=cur->rch;
}
else cur=cur->lch;
}
return res;
}
};
;
;
;
;
#include <functional>
#include <algorithm>
int unOrd[bktCount*bktSize];
using std::less;
SizeBlcTree<int,less<int> > all;
SizeBlcTree<int,less<int> > bucket[bktCount];
int N,K;
int cs;
#include <cstdio>
void init()
{
scanf("%d%d",&N,&K);
;i<N;i++)
{
scanf("%d",unOrd+i);
all<<unOrd[i];
bucket[i>>bktDigit] << unOrd[i];
}
}
inline void enumerate(int _rL,int _rR,int _val,int& _less,int& _notMore)
{
for(int i=_rL;i<=_rR;i++) if(unOrd[i]<=_val)
{
_notMore++;
if(unOrd[i]<_val) _less++;
}
}
int getAns(int _rL,int _rR,int _k)
{
int bktL = _rL>>bktDigit;
int bktR = _rR>>bktDigit;
int prevVal;
SbtNode<int> *cur=all.root;
while(cur)
{
;
;
if(bktL==bktR) enumerate(_rL,_rR,cur->val,less,notMore);
else
{
;i<bktR;i++)
{
notMore += bucket[i].notMoreCount(cur->val);
less += bucket[i].lessCount(cur->val);
}
enumerate(_rL,((bktL+)<<bktDigit)-,cur->val,less,notMore);
enumerate(bktR<<bktDigit,_rR,cur->val,less,notMore);
}
if(less<_k && notMore>=_k) return cur->val;
prevVal=cur->val;
if(less>=_k) cur=cur->lch;
else cur=cur->rch;
}
return prevVal;
}
void solve()
{
char cmd;
do cmd=getchar(); while(cmd==' ' || cmd=='\n');
if(cmd=='Q')
{
int rL,rR,k;
scanf("%d%d%d",&rL,&rR,&k);
printf(,rR-,k));
}
else
{
int pos,v;
scanf("%d%d",&pos,&v);
--pos;
all<<v;
bucket[pos>>bktDigit] >> unOrd[pos];
bucket[pos>>bktDigit] << (unOrd[pos]=v) ;
}
}
void reset()
{
all.clear();
int used=N>>bktDigit;
;i<=used;i++) bucket[i].clear();
}
int main()
{
scanf("%d",&cs);
while(cs--)
{
init();
while(K--) solve();
reset();
}
;
}Problem：ZOJ P2112
P2114：LCTdf好！！！
人生第一棵Link-cut-tree
#include <cstdio>
#include <cstring>
#include <algorithm>
,Right= };
struct SplayNode;
SplayNode* vir;
struct SplayNode
{
int dist;
int totDist;
bool isRoot;
SplayNode* parent;
SplayNode* child[];
void init()
{
dist=totDist=;
isRoot=true;
parent=child[]=child[]=vir;
}
void clear()
{
if(child[Left]!=vir) child[Left]->clear();
if(child[Right]!=vir) child[Right]->clear();
delete this;
}
void update()
{
this->totDist =
child[Left]->totDist+child[Right]->totDist+this->dist;
}
void rotate(int dir)
//If dir==Right then rotate clockwise, else rotate counter-clockwise
{
if(parent==parent->parent->child[Left])
parent->parent->child[Left]=this;
else if(parent==parent->parent->child[Right])
parent->parent->child[Right]=this;
parent->child[dir^]=this->child[dir];
child[dir]->parent=this->parent;
child[dir]=parent;
parent=parent->parent;
child[dir]->parent=this;
}
void zigzig(int dir)
{
parent->rotate(dir);
this->rotate(dir);
child[dir]->child[dir]->update();
child[dir]->update();
this->update();
}
void zigzag(int dir) //dir depends on first rotation
{
rotate(dir);
rotate(dir^);
child[Left]->update();
child[Right]->update();
this->update();
}
void zig(int dir)
{
rotate(dir);
child[dir]->update();
this->update();
}
void splay()
{
while(!isRoot)
{
;
;
;
if(!parent->isRoot)
{
if(parent->parent->isRoot) this->isRoot=true;
;
;
}
else
this->isRoot=true;
switch(status)
{
: zig(Right);
child[Right]->isRoot=false;
break;
: zig(Left);
child[Left]->isRoot=false;
break;
: zigzig(Right);
if(isRoot) child[Right]->child[Right]->isRoot=false;
break;
: zigzag(Left);
if(isRoot) child[Right]->isRoot=false;
break;
: zigzag(Right);
if(isRoot) child[Left]->isRoot=false;
break;
:zigzig(Left);
if(isRoot) child[Left]->child[Left]->isRoot=false;
break;
default:break;
}
}
}
};
int access(SplayNode* u)
{
SplayNode* v=vir;
;
while(u!=vir)
{
u->splay();
u->child[Right]->isRoot=true;
res=u->child[Right]->totDist;
u->child[Right]=v;
v->isRoot=false;
u->update();
v=u; u=u->parent;
}
return res + v->child[Right]->totDist;
}
inline int query(SplayNode* u,SplayNode* v)
{
access(u);
return access(v);
}
void initVir()
{
vir=new SplayNode;
vir->init();
}
;
SplayNode node[maxN];
int center[maxN];
int N,Q;
;
inline void link(int u,int v,int len)
{
access(node+u);
node[u].splay();
center[u]=v;
node[u].parent=node+v;
node[u].dist=len;
node[u].update();
}
inline void initNode()
{
;i<=N;i++) node[i].init();
;i<=N;i++) center[i]=i;
}
int getCenter(int x)
{
return center[x]==x ? x :
center[x]=getCenter(center[x]);
}
#define DEBUG
#undef DEBUG
#ifdef DEBUG
;
#endif
void solve()
{
lastRes=;
scanf("%d%d",&N,&Q);
initNode();
char cmd;
int v1,v2,len;
while(Q--)
{
do cmd=getchar(); while(cmd==' ' || cmd=='\n');
if(cmd=='Q')
{
scanf("%d%d",&v1,&v2);
if(getCenter(v1)==getCenter(v2))
printf("%d\n",lastRes=query(node+v1,node+v2));
else printf("Not connected.\n");
#ifdef DEBUG
printf("#%d query successful.\n",++qc);
#endif
}
else
{
scanf("%d%d%d",&v1,&v2,&len);
#ifndef DEBUG
v1=(v1-lastRes-)%N;
) v1+=N;
v2=(v2-lastRes-)%N;
) v2+=N;
#endif
link(getCenter(v1),getCenter(v2),len);
}
}
}
int main()
{
//freopen("/home/onlynagesha/Desktop/a.in","r",stdin);
//freopen("t.out","w",stdout);
initVir();
int X; scanf("%d",&X);
while(X--) solve();
;
}Problem：ZOJ P2114
P2334：左偏树+并查集
详见：http://www.cnblogs.com/Onlynagesha/p/5406403.html
#include <cstdio>
#include <cstring>
#include <algorithm>
template <class T>
struct HeapNode
{
typedef HeapNode<T> Node;
Node* lch;
Node* rch;
T val;
int dist;
HeapNode(),rch(),val(_val),dist() {}
void clear()
{
if(lch) lch->clear();
if(rch) rch->clear();
delete this;
}
};
template <class T,class Comp>
struct LeftistHeap
{
typedef HeapNode<T> Node;
typedef LeftistHeap<T,Comp> Heap;
Node* root;
Comp cmp;
LeftistHeap():root() {}
~LeftistHeap()
{
clear();
}
void clear()
{
if(root) root->clear();
root=;
}
Node* merge(Node* A,Node* B)
{
if(!A) return B;
if(!B) return A;
if(cmp(B->val,A->val)) std::swap(A,B);
A->rch=merge(B,A->rch);
if(!A->lch || A->rch->dist > A->lch->dist)
std::swap(A->lch,A->rch);
A->dist = (A->rch) ? A->rch->dist + : ;
return A;
}
void push(const T& _val)
{
Node* nNode=new Node(_val);
root=merge(root,nNode);
}
Heap& operator << (const T& _val)
{
push(_val);
return *this;
}
T top()
{
return root->val;
}
void pop()
{
Node* temp=root;
root=merge(temp->lch,temp->rch);
delete temp;
}
Heap& operator >> (T& _dest)
{
_dest=top();
pop();
return *this;
}
void merge(Heap& _other)
{
this->root=merge(this->root,_other.root);
_other.root=;
}
bool empty()
{
;
}
};
#include <functional>
;
int N,M;
int idx[maxN];
int father(int x)
{
return idx[x]==x ? x : idx[x]=father(idx[x]) ;
}
LeftistHeap<int,std::greater<int> > heap[maxN];
void init()
{
;i<maxN;i++) heap[i].clear();
;i<maxN;i++) idx[i]=i;
}
bool solve()
{
init();
if(scanf("%d",&N)==EOF) return false;
;i<=N;i++)
{
int s; scanf("%d",&s);
heap[i].push(s);
}
scanf("%d\n",&M);
while(M--)
{
int mk1,mk2;
scanf("%d%d",&mk1,&mk2);
int f1=father(mk1);
int f2=father(mk2);
if(f1==f2)
{
printf("-1\n");
continue;
}
int s1,s2;
heap[f1]>>s1;
heap[f2]>>s2;
if(f1<f2)
{
idx[f2]=f1;
heap[f1].merge(heap[f2]);
);
));
heap[f1] << (s1>>) << (s2>>);
}
else
{
idx[f1]=f2;
heap[f2].merge(heap[f1]);
);
));
heap[f2] << (s1>>) << (s2>>);
}
}
return true;
}
int main()
{
while(solve());
;
}Problem：ZOJ P2334
P2592：有一个非常神奇的性质
#include <cstdio>
int main()
{
int N,T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
;
;i<N;i++)
{
int v;
scanf("%d",&v);
tot+=v;
}
printf(?tot:);
}
;
}Problem：ZOJ P2592
然而偶的思路就有些繁琐了，而且套了个SBT模板（参考：http://www.cnblogs.com/Onlynagesha/p/5350398.html）
基本思想是维护前缀和序列，在序列“移动”过程中设立了一个offset变量，相当于给整棵树打了一个LazyTag
类似的思想可用于NOI2005“郁闷的出纳员”一题
template <class T>
struct SbtNode
{
typedef SbtNode<T> Node;
Node* lch;
Node* rch;
T val;
int lSize;
int rSize;
SbtNode(const T& _val):
lch(),rch(),val(_val),lSize(),rSize() {}
void assign(const T& _val)
{
lch=rch=;
val=_val;
lSize=rSize=;
}
};
template <class T,class Comp>
struct SizeBlcTree
{
,Left=,Right= };
typedef SbtNode<T> Node;
typedef SizeBlcTree<T,Comp> Sbt;
Node* root;
Comp cmp;
SizeBlcTree():root() {}
~SizeBlcTree() { clear(); }
void clear_aux(Node* _cur)
{
if(_cur->lch) clear_aux(_cur->lch);
if(_cur->rch) clear_aux(_cur->rch);
delete _cur;
}
void clear()
{
if(root) clear_aux(root);
root=;
}
Node* lRotate(Node* _cur)
{
Node* next=_cur->rch;
_cur->rch=next->lch;
next->lch=_cur;
_cur->rSize=next->lSize;
next->lSize+=(_cur->lSize+);
return next;
}
Node* rRotate(Node* _cur)
{
Node* next=_cur->lch;
_cur->lch=next->rch;
next->rch=_cur;
_cur->lSize=next->rSize;
next->rSize+=(_cur->rSize+);
return next;
}
Node* insert_aux(const T& _val,Node* _cur)
{
if(!_cur) return new Node(_val);
if(cmp(_val,_cur->val))
{
++_cur->lSize;
_cur->lch=insert_aux(_val,_cur->lch);
if(_cur->lch->lSize > _cur->rSize) return rRotate(_cur);
else if(_cur->lch->rSize > _cur->rSize)
{
_cur->lch=lRotate(_cur->lch);
return rRotate(_cur);
}
else return _cur;
}
else
{
++_cur->rSize;
_cur->rch=insert_aux(_val,_cur->rch);
if(_cur->rch->rSize > _cur->lSize) return lRotate(_cur);
else if(_cur->rch->lSize > _cur->lSize)
{
_cur->rch=rRotate(_cur->rch);
return lRotate(_cur);
}
else return _cur;
}
}
Sbt& operator << (const T& _val)
{
root=insert_aux(_val,root);
return *this;
}
Node* erase_aux(const T& _val,Node* _cur,bool& _found)
{
if(!_cur)
{
_found=false;
;
}
if(cmp(_val,_cur->val))
{
_cur->lch=erase_aux(_val,_cur->lch,_found);
if(_found) --_cur->lSize;
return _cur;
}
if(cmp(_cur->val,_val))
{
_cur->rch=erase_aux(_val,_cur->rch,_found);
if(_found) --_cur->rSize;
return _cur;
}
_found=true;
;
;
;
Node* res;
Node* &prev=res;
switch(status)
{
:
delete _cur;
;
:
res=_cur->lch;
delete _cur;
return res;
:
res=_cur->rch;
delete _cur;
return res;
:
prev=_cur;
if(prev->rch->lch)
{
--prev->rSize;
prev=prev->rch;
while(prev->lch->lch)
{
--prev->lSize;
prev=prev->lch;
}
_cur->val=prev->lch->val;
prev->lch=erase_aux(prev->lch->val,prev->lch,_found);
--prev->lSize;
}
else
{
_cur->val=_cur->rch->val;
_cur->rch=erase_aux(_cur->rch->val,_cur->rch,_found);
--_cur->rSize;
}
return _cur;
}
}
Sbt& operator >> (const T& _val)
{
bool found=false;
root=erase_aux(_val,root,found);
return *this;
}
T min()
{
Node* cur=root;
while(cur->lch) cur=cur->lch;
return cur->val;
}
};
;
int T,N;
int offset;
int arr[maxN];
int prefix[maxN];
#include <functional>
#include <cstdio>
#include <cstring>
#include <algorithm>
SizeBlcTree<int,std::less<int> > sbt;
void init()
{
offset=;
prefix[]=;
sbt.clear();
}
int solve()
{
init();
scanf("%d",&N);
;i<=N;i++)
{
scanf("%d",arr+i);
prefix[i]=prefix[i-]+arr[i];
sbt<<prefix[i];
}
? : ;
prefix[]=prefix[N];
;i<N;i++)
{
offset-=arr[i];
sbt>>prefix[i];
prefix[i]=prefix[i-]+arr[i];
sbt<<prefix[i];
) ++ans;
}
return ans;
}
int main()
{
scanf("%d",&T);
while(T--) printf("%d\n",solve());
;
}Another Solution to ZOJ P2592
P2652：只需分两种情况：改变第一行或不改变第一行。此后所有的状态都可以推导出来，无需再进行枚举
#include <cstdio>
#include <cstring>
#include <algorithm>
;
;
int mat[maxN][maxN];
int N,M;
bool input()
{
if(scanf("%d%d",&M,&N)==EOF) return false;
;i<=M;i++)
;j<=N;j++)
scanf("%d",mat[i]+j);
return true;
}
bool ch[maxN];
int check()
{
;
memset(ch,,sizeof(ch));
;i<=N;i++)
][i]<) { ch[i]=true; ++res; }
;i<=N;i++)
;j<=M;j++)
mat[j][i]=-mat[j][i];
;j<=M;j++)
{
;;
;i<=N;i++)
) ++c;
if(c==N) ++res;
else if(c) { res=inf; break; }
}
;i<=N;i++)
;j<=M;j++)
mat[j][i]=-mat[j][i];
return res;
}
int solve()
{
int ans=check();
;i<=N;i++) mat[][i]=-mat[][i];
ans=std::min(ans,+check());
:ans;
}
int main()
{
while(input())
printf("%d\n",solve());
;
}Problem：ZOJ P2652
P2671：线段树
#include <cstdio>
#include <cstring>
#include <algorithm>
;
int N,M,R;
);
struct Mat
{
][];
Mat() { memset(v,,sizeof(v)); }
Mat operator * (const Mat& u) const
{
Mat a;
;i<;i++)
;j<;j++)
{
;k<;k++)
a.v[i][j]+=this->v[i][k]*u.v[k][j];
a.v[i][j]%=R;
}
return a;
}
void read()
{
scanf(],v[]+,v[],v[]+);
}
void print()
{
) printf("\n");
printf(][],v[][],v[][],v[][]);
}
};
Mat mt[maxN];
struct SegTree
{
Mat* node;
int size;
SegTree(*size+]; }
~SegTree() { delete[] node; }
template <class RAIter>
void init_aux(RAIter begin,int len,int cur)
{
) {
node[cur]=*begin; return;
}
);
init_aux(begin,len>>,cur+);
init_aux(begin+(len>>),(len+)>>,rt);
node[cur]=node[cur+]*node[rt];
}
template <class RAIter>
void init(RAIter begin)
{
init_aux(begin,size,);
}
Mat ask_aux(int rl,int rr,int nl,int nr,int cur)
{
if(rl<=nl && rr>=nr) return node[cur];
;
);
);
else if(rl>=mid) return ask_aux(rl,rr,mid,nr,rt);
)*ask_aux(rl,rr,mid,nr,rt);
}
Mat ask(int l,int r)
{
,size,);
}
};
bool input()
{
if(scanf("%d%d%d",&R,&N,&M)==EOF) return false;
;i<=N;i++)
mt[i].read();
return true;
}
void proc()
{
SegTree tree(N);
tree.init(mt+);
int l,r;
Mat ans;
while(M--)
{
scanf("%d%d",&l,&r);
ans=tree.ask(l-,r);
ans.print();
}
}
int main()
{
);
while(input())
proc();
;
}Problem：ZOJ P2671
P2688：很有意思的题目，题解参考：http://blog.csdn.net/axuan_k/article/details/47447281
#include <cstdio>
#include <cstring>
#include <algorithm>
;
;
double v[maxK][maxN];
int N;
bool input()
{
scanf("%d",&N);
if(!N) return false;
];
;f<=N;f++)
{
;i<;i++)
scanf("%lf",a+i);
;b<;b++)
{
v[b][f]=0.0;
,j=b;i<;i++,j>>=)
{
) v[b][f]+=a[i];
else v[b][f]-=a[i];
}
}
}
return true;
}
double solve()
{
double mx,mn;
double ans(-1e100);
;b<;b++)
{
mx=-1e100; mn=1e100;
;i<=N;i++)
{
mx=std::max(mx,v[b][i]);
mn=std::min(mn,v[b][i]);
}
ans=std::max(ans,mx-mn);
}
return ans;
}
int main()
{
while(input())
printf("%.2lf\n",solve());
;
}Problem：ZOJ P2688
P3164：背包问题的加强版，输入及其恶心，代码也很丑……(/= _ =)/~┴┴
#include <cstdio>
#include <cstring>
#include <algorithm>
;
int N,D;
int K[maxN],E[maxN],P[maxN];
int G;
int inGrp[maxN];
char buf[maxN];
void procGrp(int idx)
{
;
;;i++)
{
if(buf[i]=='\n' || buf[i]=='\0')
{
if(v) inGrp[v]=idx;
break;
}
else if(buf[i]==' ')
{ inGrp[v]=idx; v=; }
else
{ v*=; v+=(buf[i]-'); }
}
}
bool input()
{
if(scanf("%d%d",&N,&D)==EOF)
return false;
;i<=N;i++)
{
scanf("%d%d%d",K+i,E+i,P+i);
if(!K[i]) K[i]=D/P[i];
}
scanf("%d",&G);
memset(inGrp,-,sizeof(inGrp));
fgets(buf,maxN,stdin);
;i<G;i++)
{
fgets(buf,maxN,stdin);
procGrp(i);
}
return true;
}
][maxN];
int dp[maxN];
int solve()
{
memset(grpOpt,0xc0,sizeof(grpOpt));
;i<;i++) grpOpt[i][]=;
memset(dp,]=;
;i<=N;i++)
)
{
int& grp=inGrp[i];
;j<=K[i] && j*P[i]<=D;j++)
grpOpt[grp][j*P[i]]=std::max
(grpOpt[grp][j*P[i]],j*E[i]);
}
;i<=N;i++)
)
{
int k=K[i];
;j<=k;j<<=)
{
k-=j;
for(int v=D;v>=P[i]*j;v--)
dp[v]=std::max(dp[v],dp[v-P[i]*j]+E[i]*j);
}
if(k) for(int v=D;v>=P[i]*k;v--)
dp[v]=std::max(dp[v],dp[v-P[i]*k]+E[i]*k);
}
;i<G;i++)
for(int v=D;v;v--)
for(int w=v;w;w--)
dp[v]=std::max(dp[v],dp[v-w]+grpOpt[i][w]);
return dp[D];
}
int main()
{
while(input())
{
int ans=solve();
) printf("i'm sorry...\n");
else printf("%d\n",ans);
}
;
}Problem：ZOJ P3164
P3195：LCA
预处理每个点到根节点的距离dist
记三个点为v1，v2，v3，两两配对的LCA分别为u1，u2，u3，那么ans=dist(v1)+dist(v2)+dist(v3)-dist(u1)-dist(u2)-dist(u3)
毫不夸张的说这是我写过的最恶心的代码(￣﹏￣)
map和多余的qv*数组都可以省下
1 #include <cstdio>
2 #include <cstring>
3 #include <algorithm>
4 #include <utility>
5 #include <map>
6
7 typedef std::pair<int,int> Pr;
8
9 std::map <Pr,int> lca;
10
11 const int maxQ=420005;
12 const int maxN=50005;
13 const int __maxN=70005;
14
15 Pr query[maxQ]; // first=to // second=next
16 int qHead[maxN];
17 int qCnt;
18
19 struct Edge
20 {
21 int to;
22 int weight;
23 int next;
24
25 void assign(int t,int w,int n)
26 {
27 to=t; weight=w; next=n;
28 }
29 };
30
31 Edge edge[maxN*2];
32 int eHead[maxN];
33 int eCnt;
34
35 void initL()
36 {
37 lca.clear();
38 qCnt = eCnt = 0;
39 memset(eHead,-1,sizeof(eHead));
40 memset(qHead,-1,sizeof(qHead));
41 }
42
43 inline void addEdge(int v1,int v2,int w)
44 {
45 edge[eCnt].assign(v2,w,eHead[v1]);
46 eHead[v1]=eCnt++;
47 edge[eCnt].assign(v1,w,eHead[v2]);
48 eHead[v2]=eCnt++;
49 }
50
51 inline void addQuery(int v1,int v2)
52 {
53 query[qCnt].first=v2;
54 query[qCnt].second=qHead[v1];
55 qHead[v1]=qCnt++;
56 query[qCnt].first=v1;
57 query[qCnt].second=qHead[v2];
58 qHead[v2]=qCnt++;
59 }
60
61 int N,Q;
62 int qv1[__maxN],qv2[__maxN],qv3[__maxN];
63
64 bool input()
65 {
66 if(scanf("%d",&N)==EOF) return false;
67 initL();
68 int v1,v2,w;
69 for(int i=1;i<N;i++)
70 {
71 scanf("%d%d%d",&v1,&v2,&w);
72 addEdge(v1,v2,w);
73 }
74 scanf("%d",&Q);
75 for(int i=1;i<=Q;i++)
76 {
77 scanf("%d%d%d",qv1+i,qv2+i,qv3+i);
78 addQuery(qv1[i],qv2[i]);
79 addQuery(qv2[i],qv3[i]);
80 addQuery(qv1[i],qv3[i]);
81 }
82 return true;
83 }
84
85 bool vis[maxN];
86 int dist[maxN];
87
88 void initV()
89 {
90 memset(vis,0,sizeof(vis));
91 }
92
93 void build(int cur,int len)
94 {
95 vis[cur]=true;
96 dist[cur]=len;
97 for(int e=eHead[cur];e>-1;e=edge[e].next)
98 if(!vis[edge[e].to])
99 build(edge[e].to,len+edge[e].weight);
100 }
101
102 int setn[maxN];
103
104 void initS()
105 {
106 for(int i=1;i<=N;i++) setn[i]=i;
107 memset(vis,0,sizeof(vis));
108 }
109
110 int find(int x) { return setn[x]==x?x:setn[x]=find(setn[x]); }
111
112 void dfs(int cur)
113 {
114 vis[cur]=true;
115 for(int e=eHead[cur];e>-1;e=edge[e].next)
116 if(!vis[edge[e].to])
117 {
118 dfs(edge[e].to);
119 setn[edge[e].to]=cur;
120 }
121 for(int q=qHead[cur];q>-1;q=query[q].second)
122 if(vis[query[q].first])
123 {
124 int anc=setn[find(query[q].first)];
125 lca[Pr(cur,query[q].first)]=anc;
126 lca[Pr(query[q].first,cur)]=anc;
127 }
128 }
129
130 void solve_aux()
131 {
132 for(int i=1;i<=Q;i++)
133 {
134 int lca1=lca[Pr(qv1[i],qv2[i])];
135 int lca2=lca[Pr(qv2[i],qv3[i])];
136 int lca3=lca[Pr(qv1[i],qv3[i])];
137 printf("%d\n",dist[qv1[i]]+dist[qv2[i]]+dist[qv3[i]]-
138 dist[lca1]-dist[lca2]-dist[lca3]);
139 }
140 }
141
142 int flag=0;
143 void solve()
144 {
145 if(flag++) printf("\n");
146 initV();
147 build(0,0);
148 initS();
149 dfs(0);
150 solve_aux();
151 }
152
153 int main()
154 {
155 while(input()) solve();
156 return 0;
157 }A Very Nasty Solution to ZOJ P3195
P3197：区间覆盖问题，贪心思想很简单，但是代码并不好写(´･ω･｀)
最后参（chao）考（xi）了这位的代码才AC掉：http://blog.csdn.net/zhangwenjun32/article/details/4149683
此题很重要
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
typedef std::pair<int,int> Pr;
;
Pr rg[maxN];
int N;
void input()
{
scanf("%d",&N);
;i<=N;i++)
scanf("%d%d",&rg[i].first,&rg[i].second);
}
int solve()
{
std::sort(rg+,rg+N+);
),end();
);
);
while(end<N)
{
int tp=-maxN;
begin=end+;
for(;cur<=N && rg[cur].first<=begin;cur++)
tp=std::max(tp,rg[cur].second);
++ans; end=tp;
}
return ans;
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
input();
printf("%d\n",solve());
}
;
}Problem：ZOJ P3197
P3201：树形DP
因为很久没写树形DP了所以卡了很久……
#include <cstdio>
#include <cstring>
#include <algorithm>
int N,M;
;
int lch[maxN];
int rch[maxN];
int adjList[maxN][maxN];
int head[maxN];
bool vis[maxN];
int dpQueue[maxN];
int dp[maxN][maxN];
int dpa[maxN][maxN];
int qp;
int val[maxN];
void init()
{
memset(lch,-,sizeof(lch));
memset(rch,-,sizeof(rch));
memset(head,,sizeof(head));
memset(vis,,sizeof(vis));
;i<maxN;i++) dp[i][]=dpa[i][]=;
qp=;
}
bool input()
{
if(scanf("%d%d",&N,&M)==EOF) return false;
init();
;i<=N;i++) scanf("%d",val+i);
int v1,v2;
;i<N;i++)
{
scanf("%d%d",&v1,&v2);
++v1; ++v2;
adjList[v1][head[v1]++]=v2;
adjList[v2][head[v2]++]=v1;
}
return true;
}
void build(int cur)
{
vis[cur]=true;
int next,i;
int last;
;i<head[cur];i++)
{
next=adjList[cur][i];
if(!vis[next])
{
last=lch[cur]=next;
build(next);
break;
}
}
if(i==head[cur]) return;
for(;i<head[cur];i++)
{
next=adjList[cur][i];
if(!vis[next])
{
build(next);
last=rch[last]=next;
}
}
}
void dfs(int cur)
{
) dfs(rch[cur]);
) dfs(lch[cur]);
dpQueue[qp++]=cur;
}
const int minf=0xf0000000;
int solve_aux()
{
int ans=minf;
;i<qp;i++)
{
;
int cur=dpQueue[i];
) status|=;
) status|=;
int lc,rc;
switch(status)
{
:
dp[cur][]=dpa[cur][]=val[cur];
;j<=M;j++) dp[cur][j]=dpa[cur][j]=minf;
break;
:
rc=rch[cur];
dp[cur][]=val[cur];
;j<=M;j++) dp[cur][j]=minf;
;j<=M;j++)
dpa[cur][j]=std::max(dpa[rc][j],dpa[rc][j-]+val[cur]);
break;
:
lc=lch[cur];
;j<=M;j++)
dp[cur][j]=dpa[cur][j]=dpa[lc][j-]+val[cur];
break;
:
lc=lch[cur]; rc=rch[cur];
;j<=M;j++)
dp[cur][j]=dpa[lc][j-]+val[cur];
;j<=M;j++)
{
dpa[cur][j]=minf;
;k<=j;k++)
dpa[cur][j]=std::max(dpa[cur][j],dpa[rc][j-k]+dp[cur][k]);
}
break;
}
ans=std::max(ans,dp[cur][M]);
}
return ans;
}
int solve()
{
build();
dfs();
return solve_aux();
}
int main()
{
while(input()) printf("%d\n",solve());
;
}Problem：ZOJ P3201
P3224：分段讨论
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
typedef long long Lint;
;
;
using std::cin;
using std::cout;
Lint ex[maxN][maxL];
int N;
Lint A,B;
Lint v[maxN];
Lint r[maxN*maxL];
int cnt;
bool input()
{
if(!(cin>>N)) return false;
cin>>A>>B;
;i<N;i++) cin>>v[i];
return true;
}
void initExp()
{
cnt=;
;i<N;i++)
{
ex[i][]=1LL;
;;j++)
{
ex[i][j]=ex[i][j-]*v[i];
if(ex[i][j]<=B) r[cnt++]=ex[i][j];
else break;
}
}
r[cnt++]=B+;
std::sort(r,r+cnt);
cnt=std::unique(r,r+cnt)-r;
}
Lint gcd(Lint a,Lint b)
{
return b ? gcd(b,a%b) : a;
}
Lint solve_aux(Lint X)
{
Lint ans(0LL);
;i<cnt-;i++)
{
bool ok=true;
;j<N;j++) if(r[i]<v[j])
{ ok=false; break; }
if(!ok) continue;
Lint lcm=1LL;
;j<N;j++)
{
Lint k=0LL;
while(r[i]>=ex[j][k]) k++;
k--;
lcm=lcm*k/gcd(lcm,k);
}
Lint L=r[i],R=r[i+]-;
if(L>X) break;
if(R>=X)
{
R=X; ok=false;
}
if(L%lcm) L+=(lcm-L%lcm);
if(R%lcm) R-=R%lcm;
ans+=(R-L)/lcm+1LL;
if(!ok) break;
}
return ans;
}
Lint solve()
{
initExp();
return solve_aux(B)
-solve_aux(A-);
}
int main()
{
while(input())
cout<<solve()<<"\n";
;
}Problem：ZOJ P3224
P3231：最小费用流
易证：如果若干个整数的和为定值，那么它们的方差最小时，任意两个数的差不会超过1
于是此题可以转换成有上下界的最小费用流问题
建图方法：对于有流量下界的弧，建两条边：一条流量为其下界，费用为cost-inf；一条流量为上、下界之差，费用为cost（cost为该弧的费用）
对于本题，建立源点与每个节点连边（费用为0，流量为该节点原有的苹果数），树上的边视为双向边建立两条弧（流量为inf，费用为搬运一个苹果的成本），再将每个节点与汇点连边（若苹果总数tot能被N整除，每条边的流量为tot/N，费用为0；否则，按有流量下界的方法建两条边，流量分别为tot/N和1，费用分别为-inf和0）
#include <cstdio>
#include <cstring>
#include <algorithm>
struct Edge
{
int to;
int next;
int capacity;
int cost;
void assign(int t,int n,int ca,int co)
{
to=t; next=n;
capacity=ca;
cost=co;
}
};
;
;
;
;
;
Edge edgeList[maxE];
int head[maxN];
;
void init()
{
memset(head,-,sizeof(head));
edgeCnt=;
}
inline void addEdge(int from,int to,int ca,int co)
{
edgeList[edgeCnt].assign(to,head[from],ca,co);
head[from]=edgeCnt++;
edgeList[edgeCnt].assign(,-co);
head[to]=edgeCnt++;
}
int N;
int ave;
int apple[maxN];
bool exactDiv;
bool input()
{
if(scanf("%d",&N)==EOF) return false;
init();
;i<=N;i++) scanf("%d",apple+i);
; exactDiv=false;
;i<=N;i++) tot+=apple[i];
) exactDiv=true;
;i<=N;i++) addEdge(src,i,apple[i],);
int v1,v2,l;
;i<N;i++)
{
scanf("%d%d%d",&v1,&v2,&l);
++v1; ++v2;
addEdge(v1,v2,inf,l);
addEdge(v2,v1,inf,l);
}
ave=tot/N;
;i<=N;i++)
addEdge(i,sink,ave,);
;i<=N;i++)
{
addEdge(i,sink,ave,-inf);
addEdge(i,sink,,);
}
return true;
}
#include <queue>
const int distInf=0x3f3f3f3f;
std::queue<int> bfsq;
int dist[maxN];
int prev[maxN];
int prevEdge[maxN];
bool inq[maxN];
bool spfa()
{
memset(dist,0x3f,sizeof(dist));
memset(inq,,sizeof(inq));
dist[src]=;
bfsq.push(src);
while(!bfsq.empty())
{
int cur=bfsq.front();
bfsq.pop();
inq[cur]=false;
int t;
;e=edgeList[e].next)
if(edgeList[e].capacity)
{
t=edgeList[e].to;
if(dist[t] > dist[cur] + edgeList[e].cost)
{
dist[t] = dist[cur] + edgeList[e].cost;
prev[t] = cur;
prevEdge[t] = e;
if(!inq[t])
{
inq[t]=true;
bfsq.push(t);
}
}
}
}
return dist[sink]<distInf;
}
int minCostFlow()
{
;
while(spfa())
{
int flow=inf;
int e;
for(int v=sink;v>src;v=prev[v])
{
int e=prevEdge[v];
flow=std::min(flow,edgeList[e].capacity);
}
for(int v=sink;v>src;v=prev[v])
{
e=prevEdge[v];
ans+=flow*edgeList[e].cost;
edgeList[e].capacity-=flow;
edgeList[e^].capacity+=flow;
}
}
return exactDiv ? ans : ans+N*ave*inf;
}
int main()
{
while(input()) printf("%d\n",minCostFlow());
;
}Problem：ZOJ P3231
P3264：背包问题
#include <cstdio>
#include <cstring>
#include <algorithm>
;
;
int totW,N;
int w1[maxN],w2[maxN],v1[maxN],v2[maxN];
int rel[maxN];
bool input()
{
if(scanf("%d%d",&totW,&N)==EOF)
return false;
totW/=;
;i<=N;i++)
{
scanf("%d%d%d%d%d",w1+i,v1+i,w2+i,v2+i,rel+i);
w1[i]/=; w2[i]/=;
}
return true;
}
int dp[maxW];
int solve()
{
memset(dp,,sizeof(dp));
;i<=N;i++)
{
int j,mn,mx,mv;
switch(rel[i])
{
:
for(j=totW;j>=w1[i]+w2[i];j--)
dp[j]=std::max(dp[j],dp[j-w1[i]-w2[i]]+v1[i]+v2[i]);
break;
:
if(w1[i]<w2[i])
{
mx=w2[i]; mn=w1[i];
mv=;
}
else
{
mx=w1[i]; mn=w2[i];
mv=;
}
for(j=totW;j>=mn;j--)
{
if(j>=mx) dp[j]=std::max(dp[j],
std::max(dp[j-w1[i]]+v1[i],dp[j-w2[i]]+v2[i]));
else dp[j]=std::max(dp[j],
(mv==)?dp[j-w1[i]]+v1[i]:dp[j-w2[i]]+v2[i]);
}
break;
:
for(j=totW;j>=w1[i]+w2[i];j--)
dp[j]=std::max(dp[j],
std::max(dp[j-w1[i]]+v1[i],dp[j-w1[i]-w2[i]]+v1[i]+v2[i]));
for(;j>=w1[i];j--)
dp[j]=std::max(dp[j],dp[j-w1[i]]+v1[i]);
break;
}
}
return dp[totW];
}
int main()
{
while(input()) printf("%d\n",solve());
;
}Problem：ZOJ P3264
P3279：树状数组+二分
#include <cstdio>
#include <cstring>
#include <algorithm>
;
int bit[maxN];
int pref[maxN];
int cnt[maxN];
int N,Q;
inline int lb(int x)
{
return x & -x;
}
bool input()
{
if(scanf("%d",&N)==EOF) return false;
]=;
;i<=N;i++)
{
scanf("%d",&v);
cnt[i]=v;
pref[i]=pref[i-]+v;
}
;i<=N;i++)
bit[i]=pref[i]-pref[i-lb(i)];
return true;
}
void solve()
{
scanf("%d",&Q);
char cmd;
int ans;
int left,right,mid;
int a,b;
while(Q--)
{
do cmd=getchar(); while(cmd==' ' || cmd=='\n');
if(cmd=='q')
{
scanf("%d",&a);
left=; right=N;
while(left<right)
{
mid=(left+right)>>;
ans=;
for(int i=mid;i;i-=lb(i)) ans+=bit[i];
;
else right=mid;
}
printf("%d\n",left);
}
else
{
scanf("%d%d",&a,&b);
for(int i=a;i<=N;i+=lb(i))
bit[i]+=(b-cnt[a]);
cnt[a]=b;
}
}
}
int main()
{
while(input()) solve();
;
}Problem：ZOJ P3279
P3280：和2688一个套路
#include <cstdio>
#include <cstring>
#include <algorithm>
;
];
int val[maxN];
];
int N,M;
bool input()
{
if(scanf("%d%d",&N,&M)==EOF) return false;
;i<N;i++)
;j<M;j++)
scanf("%d",dim[i]+j);
;i<M;i++)
scanf("%d",wgt+i);
return true;
}
void setVal(int b)
{
;i<N;i++)
{
val[i]=;
,k=b;j<M;j++,k>>=)
{
) val[i]+=wgt[j]*dim[i][j];
else val[i]-=wgt[j]*dim[i][j];
}
}
}
const int inf=0x70000000;
int solve()
{
int ans=-inf;
;b<(<<M);b++)
{
setVal(b);
int mx=-inf,mn=inf;
;i<N;i++)
{
mx=std::max(mx,val[i]);
mn=std::min(mn,val[i]);
}
ans=std::max(ans,mx-mn);
}
return ans;
}
int main()
{
while(input())
printf("%d\n",solve());
;
}Problem：ZOJ P3280
P3281：先用spfa求出每个点到起点的距离，然后进行dfs
此题最恶心的地方在于读数据
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
typedef std::string Str;
;
;
const char* linkTag="Link:";
std::map<Str,int> mp;
char buf[bufLen];
int dist[maxM];
int depth[maxM];
int vis[maxM];
int N,M;
int curIdx;
std::queue<int> que;
struct Edge
{
int to,next;
void assign(int t,int n) { to=t; next=n; }
};
Edge elist[][maxM];
][maxM];
];
void addEdge(int type,int from,int to)
{
)
{
elist[][ecnt[]].assign(to,head[][from]);
head[][]++;
elist[][ecnt[]].assign(][to]);
head[][to]=ecnt[]++;
}
)
{
elist[][ecnt[]].assign(to,head[][from]);
head[][]++;
elist[][ecnt[]].assign(][to]);
head[][to]=ecnt[]++;
}
} //child=0,father=1,linkTo=2,linkFrom=3
void init()
{
memset(head,-,sizeof(head));
memset(ecnt,,sizeof(ecnt));
mp.clear();
curIdx=;
}
bool input()
{
if(scanf("%d%d",&N,&M)==EOF) return false;
N*=M;
scanf("%d",&M);
fgets(buf,bufLen,stdin); //filter '\n'
return true;
}
int readBuf(int pos,int& st,bool& isLink)
{
isLink=true;
;i<;i++) if(buf[pos+i]!=linkTag[i]) isLink=false;
;
for(;buf[pos]!=' ' && buf[pos]!='\n' && buf[pos]!='\0';pos++);
; ;
return pos;
}
inline int check(const Str& s)
{
if(mp.count(s)) return mp[s];
mp.insert(std::map<Str,int>::value_type(s,++curIdx));
return curIdx;
}
inline int move(int n)
{
for(;buf[n]==' ';n++);
return n;
}
void procBuf()
{
Str tp;
),next();
);
int ci,ni;
bool isLink;
next=readBuf(pos,st,isLink);
tp.assign(buf,next);
ci=check(tp);
while(st)
{
pos=move(next);
next=readBuf(pos,st,isLink);
if(isLink)
{
tp.assign(buf+pos+,next-pos-);
ni=check(tp);
addEdge(,ci,ni);
}
else
{
tp.assign(buf+pos,next-pos);
ni=check(tp);
addEdge(,ci,ni);
}
}
}
void link()
{
;i<=M;i++)
{
fgets(buf,bufLen,stdin);
procBuf();
}
}
inline void slack(int from,int to,int len)
{
dist[to]=dist[from]+len;
if(!vis[to])
{
vis[to]=;
que.push(to);
}
}
void spfa()
{
que.push();
memset(vis,,sizeof(vis));
memset(dist,0x3f,sizeof(dist));
dist[]=;
while(!que.empty())
{
int cur=que.front();
que.pop();
vis[cur]=;
][cur];e!=-;e=elist[][e].next)
{
][e].to;
)
slack(cur,to,);
}
][cur];e!=-;e=elist[][e].next)
{
][e].to;
)
slack(cur,to,);
}
][cur];e!=-;e=elist[][e].next)
{
][e].to;
)
slack(cur,to,);
}
}
}
int dfs(int cur,int step)
{
int ans=depth[cur];
][cur];e!=-;e=elist[][e].next)
{
][e].to;
<vis[to] && step++dist[to]<=N)
{
vis[to]=step+;
ans=std::max(ans,dfs(to,step+));
}
}
][cur];e!=-;e=elist[][e].next)
{
][e].to;
<vis[to] && step++dist[to]<=N)
{
vis[to]=step+;
ans=std::max(ans,dfs(to,step+));
}
}
][cur];e!=-;e=elist[][e].next)
{
][e].to;
<vis[to] && step++dist[to]<=N)
{
vis[to]=step+;
ans=std::max(ans,dfs(to,step+));
}
}
return ans;
}
void calcDepth()
{
depth[]=;
que.push();
while(!que.empty())
{
int cur=que.front();
que.pop();
][cur];e!=-;e=elist[][e].next)
{
][e].to;
depth[to]=depth[cur]+;
que.push(to);
}
}
}
int solve()
{
memset(vis,0x3f,sizeof(vis));
vis[]=;
calcDepth();
,);
}
int main()
{
while(input())
{
init();
link();
spfa();
printf("%d\n",solve());
}
;
}Problem：ZOJ P3281
P3283：有三个要点：
（1）B很大而C很小，所以求a[i]的B次幂无需快速幂算法，直接求循环节即可
（2）通过dp将求和转化为求方案数
dp[x][n]表示对于前x个数，取若干个，其B次幂的乘积取余等于n的方案总数，初始时dp[0][1]=1
注意题目要求不能包含空集，所以dp[N][1]要减1
（3）高精度取余（其实很简单）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
;
typedef long long int64;
int N,C;
];
];
];
bool input()
{
) return false;
scanf("%s",B);
scanf("%d",&C);
;i<=N;i++)
scanf("%d",A+i);
return true;
}
int Bmod(int x)
{
;
;B[i]!='\0';i++)
res=(*res+(B[i]-'))%x;
return res;
}
void getAs()
{
],vis[];
int len,first;
cyc[]=;
;i<=N;i++)
{
memset(vis,-,sizeof(vis));
vis[]=; len=;
while(len)
{
cyc[len]=cyc[len-]*A[i]%C;
)
{
first=vis[cyc[len]];
break;
}
vis[cyc[len]]=len;
len++;
}
As[i]=cyc[first+Bmod(len-first)];
}
}
int64 dp[][];
int64 solve()
{
getAs();
memset(dp,,sizeof(dp));
dp[][]=;
;i<N;i++)
;j<C;j++)
{
dp[i+][j]+=dp[i][j];
dp[i+][j*As[i+]%C]+=dp[i][j];
}
--dp[N][];
int64 res();
;i<C;i++)
{
res+=i*dp[N][i];
res%=D;
}
return res;
}
int main()
{
while(input())
std::cout<<solve()<<"\n";
;
}Problem：ZOJ P3283
P3284：维护整行（列）的修改量，可以看成是LazyTag思想的一种体现
#include <cstdio>
#include <cstring>
#include <algorithm>
;
int mat[maxN][maxN];
int deltaR[maxN];
int deltaC[maxN];
int R,C,Q;
bool input()
{
if(scanf("%d%d",&R,&C)==EOF) return false;
;i<=R;i++)
;j<=C;j++)
scanf("%d",mat[i]+j);
return true;
}
void proc()
{
memset(deltaR,,sizeof(deltaR));
memset(deltaC,,sizeof(deltaC));
scanf("%d",&Q);
while(Q--)
{
int cmd; scanf("%d",&cmd);
)
{
int r,c;
scanf("%d%d",&r,&c);
printf("%d\n",mat[r][c]+deltaR[r]+deltaC[c]);
}
else
{
int r1,c1,r2,c2,k;
scanf("%d%d%d%d%d",&r1,&c1,&r2,&c2,&k);
)
{
if(r1==r2) for(int i=c1;i<=c2;i++) mat[r1][i]+=k;
else
{
for(int i=c1;i<=C;i++) mat[r1][i]+=k;
;i<r2;i++) deltaR[i]+=k;
;i<=c2;i++) mat[r2][i]+=k;
}
}
else
{
if(c1==c2) for(int i=r1;i<=r2;i++) mat[i][c1]+=k;
else
{
for(int i=r1;i<=R;i++) mat[i][c1]+=k;
;i<c2;i++) deltaC[i]+=k;
;i<=r2;i++) mat[i][c2]+=k;
}
}
}
}
}
);
int main()
{
while(input())
{
printf("Case %d\n",++cs);
proc();
}
;
}Problem：ZOJ P3284
P3297：顺序扫描（此题数据特别坑，必须检查合法性）
#include <cstdio>
#include <cstring>
#include <algorithm>
;
;
int N,K;
int C[maxN],A[maxK],B[maxK];
bool input()
{
if(scanf("%d%d",&N,&K)==EOF) return false;
;i<=N;i++) scanf("%d",C+i);
;i<=K;i++) scanf("%d%d",A+i,B+i);
return true;
}
;
int okCnt;
int cnt[maxK];
int head,tail;
int exc;
void init()
{
okCnt=; head=tail=; exc=;
memset(cnt,,sizeof(cnt));
;i<=K;i++)
&& B[i]>=) ++okCnt;
}
bool check()
{
;i<=K;i++)
{
if(A[i]>B[i]) return false;
) return false;
}
return true;
}
int moveHead()
{
++head; int& cur=C[head];
;
++cnt[cur];
if(cnt[cur]==A[cur])
;
)
{
--okCnt;
exc=cur;
;
}
;
}
int moveTail()
{
++tail; int& cur=C[tail];
--cnt[cur];
if(cnt[cur]==B[cur])
{
++okCnt;
; ; }
}
)
{
--okCnt;
) ;
}
;
}
int solve()
{
init();
;
int ans=inf;
;
while(st)
{
if(okCnt==K) ans=std::min(ans,head-tail);
) st=moveHead();
else st=moveTail();
}
:ans;
}
int main()
{
while(input()) printf("%d\n",solve());
;
}Problem：ZOJ P3297
————To be continued————