老师让我们打这套题练练手。感觉这套题还是挺有意思的，比国内某些比赛不知道高到哪里去。最后我拿了284/300，貌似比赛是IOI赛制啊，强行被当成OI赛制做了，不然我T3可能还能多骗点。
T1.sculpture
题目大意：把N个数分成A~B段，使各段和最后或起来最小。（数据组1：N<=100，1<=A<=B<=N；数据组2：N<=2000，A=1<=B<=N）
思路：直接把最后答案从最高位开始按位贪心，能取0就取0，否则取1，判断能否取0可以dp，求是否能分成A~B段使得每一段的和二进制下各位都不超过当前答案（答案一开始二进制全是1），若l~r的和为s，则(s|ans)==ans表示l~r可取成一段，具体DP可以把数据分成两类，1<=A<=B<=N的情况可以用f[i][j]表示1~i能否取成j段，可以O(N^3)DP，A=1时只要贪心使取的段最少，f[i]表示1~i最少取几段，可以O(N^2)DP。最后复杂度再多上外面算答案的log，还是能很科学地通过该题。
#include<cstdio> #include<cstring> #include<iostream> using namespace std; #define ll long long inline int read() { int x=0;char c; while((c=getchar())<'0'||c>'9'); for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0'; return x; } #define MN 2000 #define MN2 100 #define MK 40 int n,l,r,a[MN+5]; ll ans=(1LL<<MK+1)-1; int f[MN+5],f2[MN2+5][MN2+5]; bool check() { int i,j;ll s; memset(f,42,sizeof(f)); for(i=f[0]=0;i<n;++i)for(s=a[j=i+1];j<=n;s+=a[++j]) if((s|ans)==ans&&f[i]+1<f[j])f[j]=f[i]+1; return f[n]>r; } bool check2() { int i,j,k;ll s; memset(f2,0,sizeof(f2));f2[0][0]=1; for(i=0;i<n;++i)for(j=0;j<=i;++j)if(f2[i][j]) for(s=a[k=i+1];k<=n;s+=a[++k])if((s|ans)==ans)f2[k][j+1]=1; for(i=l;i<=r;++i)if(f2[n][i])return 0; return 1; } int main() { freopen("sculpture.in","r",stdin); freopen("sculpture.out","w",stdout); n=read();l=read();r=read(); for(int i=1;i<=n;++i)a[i]=read(); for(int i=MK;i>=0;--i) { ans^=1LL<<i; if(l<2?check():check2())ans^=1LL<<i; } cout<<ans; fclose(stdin);fclose(stdout);return 0; }
T2.skyscraper
题目大意：N栋楼，有M个人分布在这些楼中，每个人有自己的行走能力Pi，现在第0号人想通知第1号人，每个被通知过的人可以用1s从自己所在的第k栋楼走到第k-Pi栋或k+Pi栋，也可以0s通知第k楼里所有人，问最少几s第1号人能收到通知，无解输出-1。（N,M<=30000）
思路：考虑直接bfs，用在第i栋楼到达一个能力为j的人表示一个状态，f[i][j]可以拓展到f[i+j][j]或f[i-j][j]，第一次到达某一栋楼时可以把整栋里的人对应状态全部加入队列。复杂度看上去是O(N^2)，实际上可能被拓展的状态只有O(N*M^0.5)，证明：一个在i栋楼能力为j的人拓展出的状态只可能是f[k][j]其中i和k模j同余，或者拓展其他人，对每个人只考虑自己，要最大化状态数，必然使第一个人拓展f[i][1]，i%1=0，第二第三个人分别拓展f[i][2],f[j][2]，i%2=0,j%2=1……也就是说，要新拓展出n个状态，第i次需要i个人，设最后状态数最多为kn，则k(k+1)/2=m，故k约为M^0.5。N^2的内存肯定开不下，Hash一下就好了。
#include<cstdio> inline int read() { int x=0;char c; while((c=getchar())<'0'||c>'9'); for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0'; return x; } #define MN 30000 #define MQ 7500000 #define MOD 9875321 struct MyMap { int h[MOD],en,nx[MQ+5],t[MQ+5],z[MQ+5]; int&operator[](int x) { for(int i=h[x%MOD];i;i=nx[i])if(t[i]==x)return z[i]; nx[++en]=h[x%MOD];t[en]=x;h[x%MOD]=en;return z[en]; } }mp; inline int H(int x,int y){return x*30011+y;} struct edge{int nx,t;}e[MN+5]; int h[MN+5],en,d[MN+5],u[MN+5],q[MQ+5],qp[MQ+5],qn; inline void ins(int x,int y){e[++en]=(edge){h[x],y};h[x]=en;} void init(int x) { for(int i=h[x];i;i=e[i].nx)if(!u[e[i].t]) u[e[i].t]=1,q[++qn]=x,qp[qn]=e[i].t,mp[H(x,e[i].t)]=d[x]; for(int i=h[x];i;i=e[i].nx)u[e[i].t]=0; } int main() { freopen("skyscraper.in","r",stdin); freopen("skyscraper.out","w",stdout); int n,m,i,j,b,s,t; n=read();m=read(); for(i=0;i<m;++i) { b=read();ins(b,read()); if(!i)s=b;if(i==1)t=b; } for(i=d[s]=1,init(s);!d[t]&&i<=qn;++i) { int&x=mp[H(q[i],qp[i])]; if((b=q[i]+qp[i])<n) { if(!d[b])d[b]=x+1,init(b); int&y=mp[H(b,qp[i])]; if(!y)y=x+1,q[++qn]=b,qp[qn]=qp[i]; } if((b=q[i]-qp[i])>=0) { if(!d[b])d[b]=x+1,init(b); int&y=mp[H(b,qp[i])]; if(!y)y=x+1,q[++qn]=b,qp[qn]=qp[i]; } } printf("%d",d[t]-1); fclose(stdin);fclose(stdout);return 0; }
T3.bridge
题目大意：一条河隔开了两岸，两岸各有一排楼，现在给出N条路线，分别是从一栋楼走到另一栋楼（可能过河可能不过），现在要求建K座桥，选定建桥位置使得路线总长最小，求出最小值。（N<=100,000，1<=K<=2）。
思路：不过河的直接加入答案。过河的都当做一条线段，问题变成选K个点使各条线段到最近点距离的和最小。K=1时，选取的点位置即为所有端点的中位数，这是个比较显然的结论，这里不多做说明。K=2时，考虑每条线段最后会选择哪个点作为最近点，可以发现，会选择离它中点最近的点，我们把每条线段按他们的中点位置排序，这样肯定前面一部分选择一座桥，后面的选择另一座桥，而只选一座桥的话就是他们的中位数，我们枚举这个分界点，然后用权值线段树或平衡树维护左右两半的中位数和答案。复杂度O(nlogn)。
这里先贴一个我做这套时写的骗分，K=2时，猜想可能跟K=1时有类似的结论，就是选的第一座桥大约是第n/3大，第二座桥第2n/3大，设定一个搜索半径把n/3和2n/3周围都枚举一下，可以得到一个较优解，这份代码得分是84/100。
#include<cstdio> #include<algorithm> #include<iostream> using namespace std; #define ll long long inline int read() { int x=0;char c; while((c=getchar())<'0'||c>'9'); for(;c>='0'&&c<='9';c=getchar())x=x*10+c-'0'; return x; } #define MN 100000 inline int get(){for(char c;c=getchar();)if(c>='A'&&c<='B')return c-'A';} ll ans=1LL<<60,s=0; int a[MN+5],b[MN+5],c[MN*2+5],cnt; inline int z(int x){return x<0?-x:x;} void cal(int x,int y) { ll p=0;int i; for(i=0;i<cnt;++i) p+=min(z(a[i]-x)+z(b[i]-x), z(a[i]-y)+z(b[i]-y)); if(p<ans)ans=p; } int main() { freopen("bridge.in","r",stdin); freopen("bridge.out","w",stdout); int k,n,i,j,x;ll p=0; k=read();n=read(); while(n--) { x=get();c[cnt]=a[cnt]=read(); if(x==get())s+=z(a[cnt]-read()); else ++s,b[cnt++]=read(); } for(i=0;i<cnt;++i)c[i+cnt]=b[i];n=cnt<<1; sort(c,c+n); if(k==1) { for(i=1;i<n;++i)p+=c[i]-c[0]; if(p<ans)ans=p; for(i=1;i<n;++i) { p=p+(ll)((i<<1)-n)*(c[i]-c[i-1]); if(p<ans)ans=p; } } else { p=cnt<=1000?200:10; for(i=-p;i<=p;++i)if(n/3+i>=0&&n/3+i<n) for(j=-p;j<=p;++j)if(n*2/3+j>=0&&n*2/3+j<n) cal(c[n/3+i],c[n*2/3+j]); for(i=-p;i<=p;++i)for(j=-p;j<=p;++j) cal((c[n-1]-c[0])/3+i,(c[n-1]-c[0])*2/3+j); } cout<<ans+s; }
正解
#include<cstdio> #include<algorithm> using namespace std; #define ll long long char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } inline char get(){while((C=*S++)!='A'&&C!='B');return C-'A';} #define MN 100000 #define N 262144 ll ans=1LL<<60,s=0,t[4][N*2]; int c[MN*2+5],cn; struct li{int l,r;}l[MN+5]; bool cmp(li a,li b){return a.l+a.r<b.l+b.r;} inline int z(int x){return x<0?-x:x;} void inc(ll*t,int k,int x){for(k+=N;k;k>>=1)t[k]+=x;} int find(int x) { for(int l=1,r=cn,mid;;) { if(c[mid=l+r>>1]==x)return mid; if(c[mid]<x)l=mid+1; else r=mid-1; } } ll query(int p) { int k=t[p][1]+1>>1,i,x=0;ll r=0; for(i=1;i<N;) if(k<=t[p][i<<1])x-=t[p][(i<<1)+1],r+=t[p+1][(i<<1)+1],i<<=1; else x+=t[p][i<<1],k-=t[p][i<<1],r-=t[p+1][i<<1],i=(i<<1)+1; return r+(ll)x*c[i-N]; } int main() { fread(B,1,1<<26,stdin); int k,n,i,cnt=0; k=read();n=read(); while(n--) { i=get();l[cnt].l=read(); if(i==get())s+=z(l[cnt].l-read()); else ++s,c[++cn]=l[cnt].l,c[++cn]=l[cnt++].r=read(); } sort(c+1,c+cn+1);sort(l,l+cnt,cmp); for(c[n=0]=-1,i=1;i<=cn;++i)if(c[i]!=c[i-1])c[++n]=c[i];cn=n; for(i=0;i<cnt;++i) { l[i].l=find(l[i].l);inc(t[2],l[i].l,1);inc(t[3],l[i].l,c[l[i].l]); l[i].r=find(l[i].r);inc(t[2],l[i].r,1);inc(t[3],l[i].r,c[l[i].r]); } if(k<2)return printf("%lld",query(2)+s),0; for(i=0;i<cnt;++i) { inc(t[0],l[i].l,1);inc(t[0],l[i].r,1); inc(t[1],l[i].l,c[l[i].l]);inc(t[1],l[i].r,c[l[i].r]); inc(t[2],l[i].l,-1);inc(t[2],l[i].r,-1); inc(t[3],l[i].l,-c[l[i].l]);inc(t[3],l[i].r,-c[l[i].r]); ans=min(ans,query(0)+query(2)); } printf("%lld",ans+s); }