@Scarlet
        
        2017-01-23T04:44:53.000000Z
        字数 10941
        阅读 3982
    POI 2005 OI 解题报告
题意:求长度为的若干序列的公共子序列个数。 
听说是搜索好题QAQ
题意:不会概括
记录下每个玩具下次出现的位置,每次要删的话选一个最远的删掉
用堆维护这一过程
From hzwer
/*Author:Scarlet*/#include<bits/stdc++.h>#define maxn 500010using namespace std;typedef long long LL;#define G c=getchar()#define pa pair<int,int>#define mp make_pairinline int read(){int x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}int n,K,p,ans,a[maxn],nxt[maxn],last[maxn];bool m[maxn];priority_queue<pa,vector<pa> >q;int main(){n=read();K=read(),p=read();for(int i=1;i<=n;i++)last[i]=p+1;for(int i=1;i<=p;i++)a[i]=read();for(int i=p;i;i--)nxt[i]=last[a[i]],last[a[i]]=i;for(int i=1;i<=p;i++){if(m[a[i]]){q.push(mp(nxt[i],a[i]));continue;}if(K){ans++;q.push(mp(nxt[i],a[i]));m[a[i]]=1;K--;}else{while(m[q.top().second]==0)q.pop();m[q.top().second]=0;q.pop();ans++;q.push(mp(nxt[i],a[i]));m[a[i]]=1;}}printf("%d",ans);return 0;}
题意:求联通块个数
并查集后数
/*Author:Scarlet*/#include<cstdio>#define N 1000005using namespace std;inline int read(){int x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x;}int n,ans,fa[N],x,p,q;int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}int main(){n=read();for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=n;i++){x=read(),p=find(i),q=find(x);if(p!=q)fa[q]=i;}for(int i=1;i<=n;i++)if(fa[i]==i)ans++;printf("%d",ans);return 0;}
题意:环形轨道,车有一定的油,相邻城市有距离,每个城市能续命,问从多少个城市出发可以环绕所有城市
问题转化后就是环上每个点切开来后问最小子段和,单调队列可以直接艹。 
代码不是我写的所以不是很懂细节。
#include<bits/stdc++.h>#define maxn 2000100using namespace std;typedef long long LL;#define G c=getchar()inline LL read(){LL x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}struct rec{int x,y;}a[maxn];int b[maxn],sta[maxn],r[maxn],res,n;bool can[2][maxn];void work(int k){b[0]=0;for(int i=1;i<=n;i++)b[i]=b[i-1]+a[i].x-a[i].y;for(int i=1;i<=n;i++)b[n+i]=b[n+i-1]+a[i].x-a[i].y;int top=0;b[2*n+1]=-1000000000;for(int i=0;i<=(n<<1)+1;i++){while(top&&b[i]<b[sta[top]])r[sta[top--]]=i-1;sta[++top]=i;}for(int i=0;i<=n-1;i++)if(r[i]-i+1>=n)can[k][i+1]=1;}int main(){n=read();for(int i=1;i<=n;i++)a[i].x=read(),a[i].y=read(),res+=a[i].x-a[i].y;if(res<0){for(int i=1;i<=n;i++)printf("NIE\n");return 0;}work(0);for(int i=1;i<=n>>1;i++)swap(a[i],a[n+1-i]);int t=a[1].y;for(int i=1;i<=n-1;i++)a[i].y=a[i+1].y;a[n].y=t;work(1);for(int i=1;i<=n;i++)if(can[0][i]||can[1][n+1-i])printf("TAK\n");else printf("NIE\n");return 0;}
题意:种硬币凑成的最少硬币数
傻逼背包,倍增优化。
/*Author:Scarlet*/#include<bits/stdc++.h>#define M 20200using namespace std;#define G c=getchar()inline int read(){int x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}int n,k,b[220],c[220],f[M];int main(){n=read();for(int i=1;i<=n;i++)b[i]=read();for(int i=1;i<=n;i++)c[i]=read();k=read();memset(f,0x3f,sizeof f);f[0]=0;for(int i=1,j;i<=n;i++){for(j=1;j<=c[i];j<<=1){for(int k=::k;k>=b[i]*j;k--)f[k]=min(f[k],f[k-b[i]*j]+j);c[i]-=j;}if(!c[i]) continue;j=c[i];for(int k=::k;k>=b[i]*j;k--)f[k]=min(f[k],f[k-b[i]*j]+j);}printf("%d",f[k]);return 0;}
题意:求两个斐波那契进制数之和
两个性质:
1.对于
f[i]>=2的情况:
可以根据2*f[i]==f[i]+f[i-1]+f[i-2]=f[i+1]+f[i-2]
转化为f[i-2]++,f[i+1]++.2.对于
f[i]=1&&f[i+1]=1的情况:
根据f[i+2]=f[i]+f[i+1]转化为给f[i+2]++
之后玄学调整
/*Author:Scarlet*/#include<bits/stdc++.h>#define maxn 1000100using namespace std;typedef long long LL;#define G c=getchar()inline int read(){int x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}int a[maxn],b[maxn],c[maxn];void Up(int k){while(c[k]){c[k]=c[k-1]=0;c[k+1]++;k+=2;}}void trans(int i){if(c[i]<2)return;int k=i-2;if(i==2)k++;if(i>1)c[k]++;c[i+1]++;c[i]-=2;}int main(){int n=read();for(int i=1;i<=n;i++)a[i]=read();int m=read();for(int j=1;j<=m;j++)b[j]=read();int len=max(m,n);for(int i=len;i>=1;i--){c[i]+=a[i]+b[i];if(c[i]>=2){trans(i);trans(i+1);if(i==1)trans(1);}if(c[i])Up(i+1);if(c[i+1])Up(i+2);if(c[i+2])Up(i+3);}while(c[len+1])len++;if(c[len+2])len+=2;while(c[len+1])len++;printf("%d ",len);for(int i=1;i<=len;i++)printf("%d ",c[i]);return 0;}
题意:个选手,举行场比赛后,赢的最多的那个选手最少会赢多少场
十分明显的最大流模型:二分答案,源点向每场比赛连INF的边。每场比赛连向两个选手,容量为,表示每场只有一个人赢。每个选手连向汇点容量为的边,表示最多赢场。当流量为时答案可行。
实测ISAP的时间是dinic的4倍。不是很懂波兰人的出数据技巧。
/*Author:Scarlet*/#include<bits/stdc++.h>#define maxn 20010#define maxm 100010using namespace std;typedef long long LL;#define G c=getchar()inline int read(){int x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}#define AE(u,v,w) E[Si]=(Ed){v,w},nxt[Si]=idx[u],idx[u]=Si++#define Add(u,v,w) AE(u,v,w),AE(v,u,0)#define INF 1000000000struct Ed{int v,w;}E[maxm];int idx[maxn],nxt[maxm],Si,S,T,h[maxn],q[maxn],n,m,ans;bool bfs(){memset(h,-1,sizeof(h));q[0]=h[0]=0;for(int l=0,r=1;l<r;)for(int u=q[l++],i=idx[u];i+1;i=nxt[i])if(E[i].w&&h[E[i].v]==-1)h[E[i].v]=h[u]+1,q[r++]=E[i].v;return h[T]+1;}int dfs(int x,int f){if(x==T)return f;int ret=0,w;for(int i=idx[x];i+1;i=nxt[i])if(E[i].w&&h[E[i].v]==h[x]+1){w=dfs(E[i].v,min(f-ret,E[i].w));E[i].w-=w;E[i^1].w+=w;if((ret+=w)==f)return f;}if(!ret)h[x]=-1;return ret;}int dinic(){for(ans=0;bfs();)ans+=dfs(S,INF);return ans;}int e[maxn][2];void build(int x){memset(idx,-1,sizeof(idx)),Si=0;for(int i=1;i<=n;i++)Add(S,i,x);for(int i=1;i<=m;i++)Add(n+i,T,1),Add(e[i][0],n+i,1),Add(e[i][1],n+i,1);}int main(){n=read(),m=read();//这行前面写了int调了1h你敢信。S=0,T=n+m+1;for(int i=1;i<=m;i++)e[i][0]=read(),e[i][1]=read();int l=1,r=m,ans,mid;for(;l<=r;)mid=l+r>>1,build(mid),dinic()==m?r=mid-1,ans=mid:l=mid+1;printf("%d",ans);return 0;}
题意:见题目及样例
简单来说,先用扩展KMP求出每个后缀和原串的最长公共前缀,记为F[i]. 
然后转化问题:求最小的K,使相邻两个F值大于K的点距离不超过K。
然后用链表简单地XJB维护一下就好了。
一开始写了个sort,讲道理复杂度是的,而且sort常数挺小,但是为什么会跑得这么慢呢?
后来我发现计数排序就可以了,我好菜啊。 
观察了一下发现还是没上榜,原来跑得快的都是二分答案怼过去的。 
上不了榜了so sad
/*Author:Scarlet*/#include<bits/stdc++.h>#define maxn 1000010using namespace std;int n,k,p,F[maxn];char s[maxn],ch;void KMP(int n,char *a){int j=0,k=1;for(;1+j<n&&a[j]==a[1+j];j++);F[1]=j;for(int i=2,Len,L;i<n;i++){Len=k+F[k],L=F[i-k];if(L<Len-i)F[i]=L;else{for(j=max(0,Len-i);i+j<n&&a[j]==a[i+j];j++);F[k=i]=j;}}}int NXT[maxn],PRE[maxn];#define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++int idx[maxn],nxt[maxn],to[maxn],Si=1;int main(){scanf("%s",s);n=strlen(s);KMP(n,s);for(int i=0;i<=n;i++)NXT[i]=i+1,PRE[i]=i-1;F[0]=n;F[n]=n+1;for(int i=0;i<=n;i++)AE(F[i],i);int K=1,mx=1;for(;K<=n;K++){for(int i=idx[K-1],L,R;i;i=nxt[i])L=PRE[to[i]],R=NXT[to[i]],NXT[L]=R,PRE[R]=L,mx=max(mx,R-L);if(mx<=K)break;}printf("%d\n",K);}
题意:每次插入一个圆,判断集合内所有圆之交是否为空,是则退出,否则继续
找到了一个挺神的做法: 
考虑一个圆交,它的形状十分奇怪,但是一定是一个凸包。所以我们可以考虑维护这个圆交横坐标最大的点。显然这个点要么是某两个圆的交点,要么是某个圆圆心右边的点,就很好维护了,最后检查这个维护的这个点能否被圆集内的圆全都覆盖。
复杂度是常数较小的。在BZOJ随便交了一发Rank2,Rank1是陈老师比我高到不知道哪里去了。
/*Author:Scarlet*/#include<bits/stdc++.h>#define maxn 2010#define S(J) ((J)*(J))using namespace std;typedef long long LL;typedef double DB;#define G c=getchar()inline int read(){int x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}DB x[maxn],y[maxn],r[maxn];bool InC(DB X,DB Y,int w){return S(X-x[w])+S(Y-y[w])<=S(r[w])+0.00001;}void mx(DB&X,DB&Y,DB x,DB y){if(x>X)X=x,Y=y;}void mn(DB&X,DB&Y,DB x,DB y){if(x<X)X=x,Y=y;}void c2point(DB x1,DB y1,DB r1,DB x2,DB y2,DB r2,DB &rx1,DB &ry1,DB &rx2,DB &ry2){DB a,b,r;a=x2-x1;b=y2-y1;r=(a*a+b*b+r1*r1-r2*r2)/2;if(a==0&&b!=0){ry1=ry2=r/b;rx1=sqrt(r1*r1-ry1*ry1);rx2=-rx1;}else if(a!=0&&b==0){rx1=rx2=r/a;ry1=sqrt(r1*r1-rx1*rx2);ry2=-ry1;}else if(a!=0&&b!=0){DB delta;delta=b*b*r*r-(a*a+b*b)*(r*r-r1*r1*a*a);ry1=(b*r+sqrt(delta))/(a*a+b*b);ry2=(b*r-sqrt(delta))/(a*a+b*b);rx1=(r-b*ry1)/a;rx2=(r-b*ry2)/a;}rx1+=x1;ry1+=y1;rx2+=x1;ry2+=y1;}int main(){int n=read(),ans;for(int i=1;i<=n;i++)x[i]=read(),y[i]=read(),r[i]=read();DB MX=x[1]+r[1],MY=y[1];int f=0;for(int i=2;i<=n;i++){if(InC(MX,MY,i))continue;for(int j=1;j<i;j++){DB NX=-100000000,NY=-10000000,sx,sy,tx,ty;sx=sy=tx=ty=0;if(S(x[i]-x[j])+S(y[i]-y[j])>S(r[i]+r[j])){MX=NX,MY=NY;break;}//相离if(InC(x[j]+r[j],y[j],i))mx(NX,NY,x[j]+r[j],y[j]);if(InC(x[i]+r[i],y[i],j))mx(NX,NY,x[i]+r[i],y[i]);if(S(x[i]-x[j])+S(y[i]-y[j])>S(r[i]-r[j]))//相交{c2point(x[i],y[i],r[i],x[j],y[j],r[j],sx,sy,tx,ty);mx(NX,NY,sx,sy);mx(NX,NY,tx,ty);}if(MX>NX)MX=NX,MY=NY;}for(int j=1;j<=i;j++)if(!InC(MX,MY,j)){f=1;break;}if(f){ans=i;break;}}if(!f)puts("NIE");else printf("%d",ans);return 0;}
题意:个数站成两排(每个数最多出现两遍),一个操作可以交换一列中两个数,求使每行数不重复的最少操作数。
据说把每列看成一个点,把有相同数的点连边,那么会得到一个坨环+链。通过一些巧妙的思考,发现一个联通块中只有两个稳定状态。然后就每个联通块中枚举某处交不交换,dfs然后取min。
鈤狗了,在main上爆了5波OJ,两发没删注释,一发忘关文件,还小开数组WA了一发。
复健后总算自己写了一题w。
/*Author:Scarlet*/#include<bits/stdc++.h>#define maxn 50010using namespace std;typedef long long LL;#define G c=getchar()inline int read(){int x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}int vis[maxn<<1],st,num,cnt,sum,n,ans,t;int a[2][maxn],to[2][maxn],gg[maxn<<1];void dfs(int x){if(vis[x])return;sum++;vis[x]=1;if(a[st][x]==num)cnt++,num=a[!st][x],dfs(to[!st][x]);else num=a[st][x],dfs(to[st][x]);}int main(){n=read();memset(vis,-1,sizeof(vis));int tot=0;for(int i=0;i<2;i++)for(int j=1;j<=n;j++)a[i][j]=read(),gg[tot++]=a[i][j];sort(gg,gg+tot);tot=unique(gg,gg+tot)-gg;for(int i=0;i<2;i++)for(int j=1;j<=n;j++){a[i][j]=lower_bound(gg,gg+tot,a[i][j])-gg+1;if(vis[a[i][j]]==-1)vis[a[i][j]]=n*i+j-1;else to[i][j]=vis[a[i][j]]%n+1,to[vis[a[i][j]]/n][vis[a[i][j]]%n+1]=j;}memset(vis,0,sizeof(vis));vis[0]=1;for(int i=1;i<=n;i++)if(!vis[i]){cnt=sum=0;num=a[st=0][i];dfs(to[st][i]);num=a[st=1][i];dfs(to[st][i]);if(!vis[i])vis[i]=1,sum++;ans+=min(cnt,sum-cnt);}printf("%d",ans);return 0;}
题意:边长方格内的走一次的方格取数
离散化后按排序扫描,用树状数组加速dp,闭着眼睛过。
/*Author:Scarlet*/#include<bits/stdc++.h>#define maxn 100010using namespace std;typedef long long LL;#define G c=getchar()inline int read(){int x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}struct poi{int x,y,s;}q[maxn];inline bool cmp(const poi &a,const poi &b){return a.x==b.x?a.y<b.y:a.x<b.x;}int c[maxn],xg[maxn],yg[maxn],xc,yc;void add(int x,int v){for(;x<maxn;x+=x&-x)c[x]=max(c[x],v);}int ask(int x){int ret=0;for(;x;x-=x&-x)ret=max(ret,c[x]);return ret;}int main(){freopen("w.in","r",stdin);int n=read(),m=read(),k=read();for(int i=0;i<k;i++)xg[i]=read(),yg[i]=read(),q[i]=(poi){xg[i],yg[i],read()};sort(xg,xg+k);xc=unique(xg,xg+k)-xg;sort(yg,yg+k);yc=unique(yg,yg+k)-yg;for(int i=0;i<k;i++)q[i].x=lower_bound(xg,xg+xc,q[i].x)-xg+1,q[i].y=lower_bound(yg,yg+yc,q[i].y)-yg+1;sort(q,q+k,cmp);for(int i=0;i<k;i++){int w=ask(q[i].y)+q[i].s;add(q[i].y,w);}printf("%d\n",ask(maxn-1));return 0;}
Next:POI 2006