poi2012 Tour de Byteotia
一眼题，不解释。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | #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。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #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不知哪写错了，求大神查错。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 | #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
强连通分量+最长路
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 | #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)解决。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | #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]}递增。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #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
裸扫一遍。。记下状态。注意一段中没有一个字母就不能算他为出现最少的字母= =！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #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。。。一样的题额。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #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(用置换中最小值换所有元素的代价；有全局最小值换置换中最小元素，用全局最小元素换所有元素，再将最小元素换回来),详见代码。。