@Scarlet
2017-01-23T12:44:53.000000Z
字数 10941
阅读 3447
POI
2005
OI
解题报告
题意:求长度为的若干序列的公共子序列个数。
听说是搜索好题QAQ
题意:不会概括
记录下每个玩具下次出现的位置,每次要删的话选一个最远的删掉
用堆维护这一过程
From hzwer
/*
Author:Scarlet
*/
#include<bits/stdc++.h>
#define maxn 500010
using namespace std;
typedef long long LL;
#define G c=getchar()
#define pa pair<int,int>
#define mp make_pair
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,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 1000005
using 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 2000100
using 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 20200
using 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 1000100
using 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 100010
using 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 1000000000
struct 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 1000010
using 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 50010
using 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 100010
using 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