3166: [Heoi2013]Alo
这题大意是给你一个序列，求一个最优区间[l,r],使其中的次大值xor上区间中任意另一个数，使xor和最大（对不起，我又语死了）
这题其实暴力能a= =
但是写暴力太没节操了（- -b）
网上似乎没有除暴力以外的题解= =我来写一篇吧= =
我的大致想法就是用线段树维护i前面第二个比他大的值f[i]（这里可以用权值线段树），然后用函数式trie找(f[i]+1,i)上与a[i]的最大xor。。
貌似很基础的样子= =也很暴力= =
有更优解请告诉我= =
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 | #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=3000010;struct re{ int l,r,lc,rc,ms,mf;} t[N];int root[N],col[N],a[N],b[N],c[N],d[N];int tr[N][2];int n,sum=0,num=0,tot=0,ans=0;inline void inse(int pp,int i,int x){ root[i]=++sum; int pos=root[i]; col[pos]=i; for (int j=30;j>=0;j--){ int y=(x>>j)&1; tr[pos][y^1]=tr[pp][y^1]; tr[pos][y]=++sum; col[sum]=i; pos=tr[pos][y]; pp=tr[pp][y]; }}inline int ques(int l,int r,int x){ int pos=root[r]; int ans=0; for (int j=30;j>=0;j--){ int z=(x>>j)&1; if (col[tr[pos][z^1]]>=l){ ans+=1<<j; pos=tr[pos][z^1]; }else pos=tr[pos][z]; } return ans;}inline int buildtree(int l,int r){ int x=++num; t[x].l=l; t[x].r=r; t[x].mf=t[x].ms=0; if (l==r){ t[x].lc=t[x].rc=0; return x; } int mm=(l+r)/2; t[x].lc=buildtree(l,mm); t[x].rc=buildtree(mm+1,r); return x;}inline void renew(int c,int x){ if (t[x].mf<c){ t[x].ms=t[x].mf; t[x].mf=c; return; } if (t[x].mf==c) return; if (t[x].ms<c) t[x].ms=c;}inline void down(int x){ int l=t[x].lc,r=t[x].rc; renew(t[x].ms,l); renew(t[x].mf,l); renew(t[x].ms,r); renew(t[x].mf,r);}inline int query(int x,int pos){ if (t[x].l==t[x].r) return t[x].ms; down(x); int mm=(t[x].l+t[x].r)/2; if (pos<=mm) return query(t[x].lc,pos); return query(t[x].rc,pos);}inline void add(int x,int l,int r,int c){ if (t[x].l==0) return; if (l<=t[x].l&&t[x].r<=r){ t[x].ms=t[x].mf; t[x].mf=c; return; } down(x); int mm=(t[x].l+t[x].r)/2; if (l<=mm) add(t[x].lc,l,r,c); if (mm<r) add(t[x].rc,l,r,c);}inline void calc(){ memset(col,0,sizeof(col)); memset(tr,0,sizeof(tr)); sum=0; tot=0; inse(0,0,0); for (int i=1;i<=n;i++){ b[++tot]=a[i]; inse(root[i-1],i,a[i]); } std::sort(b+1,b+n+1); for (int i=1;i<=n;i++){ c[i]=lower_bound(b+1,b+n+1,a[i])-b; } num=0; int ro=buildtree(1,n); for (int i=1;i<=n;i++){ int x; x=query(ro,c[i]); x++; ans=max(ans,ques(x,i,a[i])); if (c[i]>1) add(ro,1,c[i]-1,i); }}inline void read(int &T){ int ch=getchar(); while (ch<'0'||ch>'9'){ ch=getchar(); } T=0; while (ch>='0'&&ch<='9'){ T=T*10+ch-'0'; ch=getchar(); }}int main(){ scanf("%d",&n); num=0; for (int i=1;i<=n;i++){ scanf("%d",&d[i]); a[i]=d[i]; } calc(); for (int i=1;i<=n;i++) a[i]=d[n-i+1]; calc(); printf("%d\n",ans);} |
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原数据我总有一个跑不对= =。详见程序