poi2012 Tour de Byteotia
一眼题,不解释。。
#include<cstdio> int n,m,k,ans=0; int fa[1000001]; struct re{ int u,v; } a[2000001]; re b[2000001]; int getfa(int x){return fa[x]==x? x:fa[x]=getfa(fa[x]);} int main(){ //freopen("tou1a.in","r",stdin); scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=n;i++) fa[i]=i; for (int i=1;i<=m;i++){ scanf("%d%d",&a[i].u,&a[i].v); if (a[i].u<=k||a[i].v<=k) continue; int fx=getfa(a[i].u); int fy=getfa(a[i].v); if (fx!=fy){ fa[fx]=fy; } } for (int i=1;i<=m;i++){ if (a[i].u>k&&a[i].v>k) continue; int fx=getfa(a[i].u); int fy=getfa(a[i].v); if (fx==fy){ ans++; b[ans].u=a[i].u; b[ans].v=a[i].v; } else fa[fx]=fy; } printf("%d\n",ans); for (int i=1;i<=ans;i++) printf("%d %d\n",b[i].u,b[i].v); }
poi2012 well
二分答案+单调队列。。main过了,bzoj无限tle。。。
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; int q[1000011]; int n,maxi=0; int ansx,ansk; ll m; int a[1000011]; ll sum[1000011]; ll c[1000011],f[1000011],fr[1000011],fl[1000011],g[1000011]; inline ll min(ll a,ll b){return a<b? a:b;} inline bool check(int xx){ ll x=xx; int h=0,t=1; c[1]=a[1]; q[t]=1; f[1]=0; sum[1]=a[1]; for (int i=2;i<=n;i++){ sum[i]=sum[i-1]+a[i]; c[i]=min(c[i-1]+x,a[i]); while (h<t&&c[q[t]]+x*q[t]>=c[i]+x*i) t--; int j=q[t]; //printf("i=%d j=%d\n",i,j); if (h==t){ f[i]=sum[i]-(c[i]+c[i]+(i-1)*x)*i/2;} else { f[i]=sum[i]-sum[j]-(c[i]+c[i]+(i-j-1)*x)*(i-j)/2+f[j];} q[++t]=i; } //for (int i=1;i<=n;i++) printf("f[%d]=%I64d ",i,f[i]); //printf("\n"); //for (int i=1;i<=n;i++) printf("c[%d]=%I64d\n",i,c[i]); h=0; t=1; q[1]=1; fl[1]=a[1]; for (int i=2;i<=n;i++){ while (h+1<t&&c[q[h+2]]+q[h+2]*x<=i*x) h++; int j=q[h+1]; if (c[q[h+1]]+q[h+1]*x>i*x){fl[i]=sum[i]-(i-1)*x*i/2;} else {fl[i]=sum[i]-sum[j]-(i-j-1)*x*(i-j)/2+f[j];} while (h<t&&c[q[t]]+q[t]*x>=c[i]+i*x) t--; q[++t]=i; } //for (int i=1;i<=n;i++) printf("fl[%d]=%I64d ",i,fl[i]); //printf("\n"); h=0; t=1; c[n]=a[n]; q[t]=n; g[n]=0; sum[n]=a[n]; for (int i=n-1;i>=1;i--){ sum[i]=sum[i+1]+a[i]; c[i]=min(c[i+1]+x,a[i]); while (h<t&&c[q[t]]-x*q[t]>=c[i]-x*i) t--; int j=q[t]; if (h==t){ g[i]=sum[i]-(c[i]+c[i]+(n-i)*x)*(n-i+1)/2;} else { g[i]=sum[i]-sum[j]-(c[i]+c[i]+(j-i-1)*x)*(j-i)/2+g[j];} q[++t]=i; } //for (int i=1;i<=n;i++) printf("g[%d]=%I64d ",i,g[i]); //printf("\n"); h=0; t=1; q[1]=n; fr[n]=a[n]; ll ans=fr[n]+fl[n]-a[n]; for (int i=n-1;i>=1;i--){ while (h+1<t&&c[q[h+2]]-q[h+2]*x<=-i*x) h++; int j=q[h+1]; if (c[q[h+1]]-q[h+1]*x>-i*x){fr[i]=sum[i]-(n-i)*x*(n-i+1)/2;} else {fr[i]=sum[i]-sum[j]-(j-i-1)*x*(j-i)/2+g[j];} while (h<t&&c[q[t]]-q[t]*x>=c[i]-i*x) t--; q[++t]=i; ans=min(ans,fl[i]+fr[i]-a[i]); } //printf("ans=%I64d\n",ans); if (ans>m) return false; if (x<ansx){ ansx=x; for (int i=1;i<=n;i++){ if (fr[i]+fl[i]-a[i]<=m){ ansk=i; break; } } } return true; } inline void half(int l,int r){ while (l!=r){ int mm=(l+r)/2; //printf("%I64d\n",mm); if (check(mm)) r=mm; else l=mm+1; } } int main(){ //freopen("stu.in","r",stdin); //freopen("stu.out","w",stdout); scanf("%d%lld",&n,&m); ansx=1000000000; ansk=1000000000; for (int i=1;i<=n;i++){ scanf("%d",&a[i]); maxi=max(maxi,a[i]); } //printf("%d\n",maxi); if (maxi>20000000) maxi=20000000; half(0,maxi+1); if (ansx==1000000000) half(20000001,100000000); printf("%d %d\n",ansk,ansx); //printf("%d\n",check(1076)); }
poi2012 rendezvous
基圈上的外向树求lca。。。先预处理所有的环长,以及外向树内的lca,对每个询问,在一棵树上就直接求,在一个环上就先到根,再判断从哪个方向走,如果不在一个环上输出-1 -1。。。
另:lca不知哪写错了,求大神查错。。。
#include<cstdio> #include<cmath> #include<cstring> int can[500001]; int ansx=0,ansy=0,n,p=0,ss=0,m,sum=0; int d[500001],pos[500001],fa[500001]; int f[500001][20],root[500001]; int dis[500001],kind[500001],head[500001],next[1000001]; struct re{ int u,v; } a[1000001]; inline int max(int a,int b){return a>b? a:b;} inline int min(int a,int b){return a<b? a:b;} void getlca(int x,int y){ ansx=0; ansy=0; if (x==y) return; //printf("fu\n"); if (dis[x]>dis[y]){ int xx=dis[x]-dis[y]; ansx=xx; int k=int(log2(n)); while (k>=0){ if (xx>=(1<<k)){ x=f[x][k]; xx-=(1<<k); } k--; } }else{ int xx=dis[y]-dis[x]; ansy=xx; //printf("%d\n",xx); int k=int(log2(n)); while (k>=0){ if (xx>=(1<<k)){ y=f[y][k]; xx-=1<<k; } k--; } } //printf("f2\n"); if (x==y) return; //printf("ansx=%d ansy=%d\n",ansx,ansy); //printf("x\n"); int k=int(log2(n)); while (k>=0){ //printf("%d %d %d %d %d\n",k,ansx,ansy,f[x][k],f[y][k]); if (f[x][k]!=f[y][k]&&f[x][k]!=0&&f[y][k]!=0){ ansx+=1<<k; ansy+=1<<k; x=f[x][k]; y=f[y][k]; } k--; } ansx++; ansy++; } void get(int x,int y){ if (root[x]==root[y]){ //printf("e\n"); getlca(x,y); return; } if (kind[root[x]]!=kind[root[y]]) return; ansx=dis[x]; ansy=dis[y]; x=root[x]; y=root[y]; int t=kind[x]; int len=d[t]; int lx=pos[y]-pos[x]; if (lx<0) lx+=len; int rx=pos[x]-pos[y]; if (rx<0) rx+=len; //printf("len=%d px=%d py=%d\n",len,pos[x],pos[y]); //printf("ax=%d ay=%d tx=%d ty=%d\n",ansx,ansy,lx,rx); if (max(lx+ansx,ansy)<max(ansx,rx+ansy)){ //printf("a1\n"); ansx+=lx; return; } if (max(lx+ansx,ansy)>max(ansx,rx+ansy)){ //printf("a2\n"); ansy+=rx; return; } //printf("f1 %d %d\n",ansx,rx+ansy); //printf("f2 %d %d\n",ansx+lx,ansy); if (min(lx+ansx,ansy)<min(ansx,rx+ansy)){ //printf("b1\n"); ansx+=lx; return; } if (min(lx+ansx,ansy)>min(ansx,rx+ansy)){ //printf("b2\n"); ansy+=rx; return; } //printf("s\n"); ansx+=lx; } void done(int i){ root[i]=i; kind[i]=++ss; d[ss]++; pos[i]=++p; int j=fa[i]; while (j!=i){ //printf("j=%d %d\n",j,i); root[j]=j; kind[j]=ss; d[ss]++; pos[j]=++p; j=fa[j]; } } void dfs(int i,int x){ can[i]=x; int k=fa[i]; if (can[k]==x){ done(k); return; } if (can[k]) return; can[k]=x; dfs(k,x); } void dfs2(int i){ can[i]=1; //printf("ii=%d\n",i); int x=int(log2(n)); f[i][0]=fa[i]; for (int j=1;j<=x;j++){ f[i][j]=f[f[i][j-1]][j-1]; } for (int j=head[i];j;j=next[j]){ int k=a[j].v; if (root[k]||can[k]) continue; root[k]=root[i]; dis[k]=dis[i]+1; dfs2(k); } } void build(int u,int v){ a[++sum].u=u; a[sum].v=v; next[sum]=head[u]; head[u]=sum; } int main(){ //freopen("ran3c.in","r",stdin); //freopen("ran.out","w",stdout); scanf("%d%d",&n,&m); int x,y; for (int i=1;i<=n;i++){ scanf("%d",&x); build(x,i); build(i,x); fa[i]=x; } for (int i=1;i<=n;i++){ if (!can[i]) dfs(i,i); //printf("%d\n",can[i]); } //printf("d\n"); memset(can,0,sizeof(can)); for (int i=1;i<=n;i++){ if (root[i]) dfs2(i); } //for (int i=1;i<=n;i++) printf("i=%d root=%d dis=%d pos=%d kind=%d\n",i,root[i],dis[i],pos[i],kind[i]); for (int i=1;i<=m;i++){ scanf("%d%d",&x,&y); ansx=-1; ansy=-1; get(x,y); printf("%d %d\n",ansx,ansy); } }
poi2012 festival
强连通分量+最长路
#include<cstdio> #include<cstring> const int maxi=100000000; int ft[610][610]; bool f[100001],can[100001]; int head[100001],next[200001],d[100001]; int dfn[100001],low[100001],sta[100001],g[100001]; int top=0,s=0,sum=0,ss=0,n,m1,m2,ans=0; struct re{ int u,v,w; } a[200001]; inline int min(int a,int b){return a<b? a:b;} inline int max(int a,int b){return a>b? a:b;} inline int abs(int x){return x>=0? x:-x;} void done(int i){ ++s; while (sta[top]!=i){ g[sta[top]]=s; can[sta[top]]=false; top--; } g[i]=s; can[i]=false; top--; } void dfs(int i){ dfn[i]=low[i]=++ss; sta[++top]=i; f[i]=false; for (int j=head[i];j;j=next[j]){ int k=a[j].v; if (can[k]){ if (f[k]) dfs(k); low[i]=min(low[i],min(low[k],dfn[k])); } } if (low[i]==dfn[i]) done(i); } void build(int u,int v,int w){ a[++sum].u=u; a[sum].v=v; a[sum].w=w; next[sum]=head[u]; head[u]=sum; } int main(){ //freopen("fes11a.in","r",stdin); scanf("%d%d%d",&n,&m1,&m2); int u,v; for (int i=1;i<=m1;i++){ scanf("%d%d",&u,&v); build(v,u,1); build(u,v,-1); } for (int i=1;i<=m2;i++){ scanf("%d%d",&u,&v); build(v,u,0); } memset(f,true,sizeof(f)); memset(can,true,sizeof(can)); for (int i=1;i<=n;i++){ if (f[i])dfs(i); } //for (int i=1;i<=n;i++) printf("g[%d]=%d\n",i,g[i]); for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ ft[i][j]=-maxi; } } //printf("%d\n",ft[1][1]); for (int i=1;i<=n;i++) ft[i][i]=0; for (int i=1;i<=sum;i++){ if (g[a[i].u]==g[a[i].v]){ ft[a[i].u][a[i].v]=max(ft[a[i].u][a[i].v],a[i].w); } } /*for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ printf("f[%d][%d]=%d ",i,j,ft[i][j]); } printf("\n"); }*/ for (int k=1;k<=n;k++){ for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ //if (i==j) printf("i=%d j=%d k=%d f2=%d f3=%d\n",i,j,k,ft[i][k],ft[k][j]); ft[i][j]=max(ft[i][j],ft[i][k]+ft[k][j]); } } } /*for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ printf("f[%d][%d]=%d ",i,j,ft[i][j]); } printf("\n"); }*/ for (int i=1;i<=n;i++){ if (ft[i][i]>0){ printf("NIE\n"); return 0; } } for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ if (g[i]==g[j]) d[g[i]]=max(d[g[i]],abs(ft[i][j])); } } for (int i=1;i<=s;i++){ ans+=d[i]+1; } printf("%d\n",ans); }
poi2012 distance
暴力水过。。就是d(a,b)=c[a]+c[b]-c[gcd(a,b)];c[i]表示i的质因子数。然后对每个a[i]暴力枚举gcd(),求一个b使c[a]+c[b]-2*c[gcd()]最小。。这个可以预处理后O(1)解决。。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxi=1000000000; int n,m=0,tot=0; bool ss[1000051]; int prime[1000051]; int f[1000051],g[1000051]; int a[1000051],c[1000051]; int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&a[i]); m=max(m,a[i]); } memset(ss,true,sizeof(ss)); for (int i=2;i<=m;i++){ if (ss[i]){ prime[++tot]=i; c[i]=1; } for (int j=1;j<=tot&&prime[j]*i<=m;j++){ int k=i*prime[j]; ss[k]=false; c[k]=c[i]+1; if (i%prime[j]==0) break; } } //for (int i=1;i<=tot;i++) printf("prime[%d]=%d\n",i,prime[i]); //for (int i=1;i<=m;i++) printf("c[%d]=%d\n",i,c[i]); c[0]=maxi; for (int i=1;i<=n;i++){ for (int j=1;j*j<=a[i];j++){ if (a[i]%j!=0) continue; int k=a[i]/j; //printf("i=%d j=%d k=%d\n",i,j,k); if (c[a[i]]<c[a[f[j]]]){g[j]=f[j]; f[j]=i;} else if (c[a[i]]<c[a[g[j]]]) g[j]=i; //printf("g=%d f=%d\n",g[j],f[j]); if (j==k) continue; if (c[a[i]]<c[a[f[k]]]){g[k]=f[k]; f[k]=i;} else if (c[a[i]]<c[a[g[k]]]) g[k]=i; } //if (i%10000==0) printf("i=%d\n",i); } //for (int i=1;i<=m;i++) printf("i=%d f=%d g=%d\n",i,f[i],g[i]); for (int i=1;i<=n;i++){ int h=maxi,d=0; for (int j=1;j*j<=a[i];j++){ if (a[i]%j!=0) continue; int k=a[i]/j,x; if (f[j]==i) x=g[j]; else x=f[j]; //printf("i=%d x=%d j=%d k=%d h=%d\n",i,x,j,k,h[i]); if (h>c[a[i]]+c[a[x]]-2*c[j]||(h==c[a[i]]+c[a[x]]-2*c[j]&&x<d)){ h=c[a[i]]+c[a[x]]-2*c[j]; d=x; } if (j==k) continue; if (f[k]==i) x=g[k]; else x=f[k]; if (h>c[a[i]]+c[a[x]]-2*c[k]||(h==c[a[i]]+c[a[x]]-2*c[k]&&x<d)){ h=c[a[i]]+c[a[x]]-2*c[k]; d=x; } } //if (i%10000==0) printf("%d\n",i); printf("%d\n",d); } }
1109: [POI2007]堆积木Klo
树状数组维护序列,使{a[i]-i}不增,且{a[i]}递增。。。
#include<cstdio> #include<algorithm> using namespace std; const int maxi=~0u>>1; int n,ans(0); int f[200001],t[1000001]; struct re{ int n,h; }a[200001]; int lowbit(int x){return x&(-x);} bool cmp(re a,re b){return a.n==b.n? a.h<b.h:a.n>b.n;} void change(int x,int c){ while (x<=n){ t[x]=max(t[x],c); //printf("x=%d t[x]=%d\n",x,t[x]); x+=lowbit(x); } } int ques(int x){ int ans=0; while (x){ ans=max(ans,t[x]); //printf("%d t[x]=%d\n",x,t[x]); x-=lowbit(x); } //printf("ans=%d\n",ans); return ans; } int main(){ scanf("%d",&n); for (int i=1;i<=n;i++){ scanf("%d",&a[i].h); a[i].n=a[i].h-i; //printf("a[%d]=%d\n",i,a[i].n); } sort(a+1,a+n+1,cmp); for (int i=1;i<=n;i++){ //printf("i=%d n=%d h=%d\n",i,a[i].n,a[i].h); if (a[i].n>0) continue; int x; if (a[i].h-1>0){ //printf("%d\n",a[i].h); x=ques(a[i].h-1); }else x=0; //printf("x=%d\n",x); f[i]=x+1; //printf("f=%d\n",f[i]); ans=max(ans,f[i]); //printf("f[%d]=%d\n",i,f[i]); change(a[i].h,f[i]); } printf("%d\n",ans); }
2213: [Poi2011]Difference
裸扫一遍。。记下状态。注意一段中没有一个字母就不能算他为出现最少的字母= =!
#include<cstdio> int n,ans=0; char st[1000002]; int f[41][41],g[41][41]; int max(int a,int b){return a>b? a:b;} int main(){ scanf("%d",&n); scanf("%s",st); for (int i=0;i<n;i++){ int y=st[i]-'a'; for (int j=0;j<26;j++){ f[j][y]++; f[y][j]--; if (!g[y][j]) g[y][j]=1; if (g[y][j]==2){g[y][j]=1;f[y][j]++;} if (f[y][j]<=-1){f[y][j]=-1;g[y][j]=2;} if (g[y][j]) ans=max(ans,f[y][j]); if (g[j][y]) ans=max(ans,f[j][y]); //printf("f[%c][%c]=%d f[%c][%c]=%d ",j+'a',y+'a',f[j][y],y+'a',j+'a',f[y][j]); } //printf("\n"); } printf("%d\n",ans); }
两道水
2793: [Poi2012]Vouchers:暴力加小优化,据说是O(mlogm)的。
2091: [Poi2010]The Minima Game:之前做的USACO10的taking turns。。。一样的题额。。
#include<cstdio> #include<cstring> typedef long long ll; int m,n; ll x,maxi=0,tot=0,sum=0; ll d[1000001]; ll ans[1000001]; bool c[1000001],f[1000001]; ll max(ll a,ll b){return a>b? a:b;} int main(){ scanf("%d",&m); memset(f,true,sizeof(f)); for (int i=1;i<=m;i++){ scanf("%lld",&x); c[x]=true; maxi=max(maxi,x); } scanf("%d",&n); for (int i=1;i<=maxi;i++){ d[i]=i; } for (int i=1;i<=n;i++){ scanf("%lld",&x); int s=x; long long y=d[x]; while (s){ if (y>maxi) break; if (f[y]){ tot++; d[x]=y; f[y]=false; //printf("y=%d\n",y); if (c[y]) ans[++sum]=tot; s--; } y+=x; } //printf("s=%d tot=%d\n",s,tot); tot+=s; } printf("%lld\n",sum); for (int i=1;i<=sum;i++){ printf("%lld\n",ans[i]); } }
1510: [POI2006]Kra-The Disks
水题一道不解释,前缀和暴力裸过。。就是不知为什么,poi原数据我总有一个跑不对= =。详见程序
1119: [POI2009]SLO
也不算什么难题。。求出所有的置换,再在每个置换中讨论,ans=min(用置换中最小值换所有元素的代价;有全局最小值换置换中最小元素,用全局最小元素换所有元素,再将最小元素换回来),详见代码。。