首页 > 代码库 > APIO2015简要题解
APIO2015简要题解
最近老师把apio的题目拿出来了，然后由于我实在是菜，分数还没三位数......
----------------我是分割线
1.巴厘岛的雕塑
N个数，分成连续的A-B个组，让每个组的和或起来最小，求最小值。
对于Task1 n<=100
由于涉及到位运算，所以很容易想到按二进制位来做。要让答案最小，显然要从二进制高位到低位判断，能取0就取0。
所以我们考虑一个n^3 dp 用 f[i][j] 表示在当前的值之下，前i个分j组能否符合条件，用x表示当前判断的数字。
f[i][j]|=f[k][j-1] (k=[0,i-1] , s[k+1..i] or x=x)
很显然如果满足第k+1到第i个数的和或上x等于x，那么这个数字和没有一个二进制位比x大。
那么就先把所有位设成1，从高位开始，把它设成0，进行dp。如果在f[n][A..B]中有一个true，那么就可以分，不然就把这一位改回1。这样一直做下去就可以得到答案。
复杂度n^3logAi
对于Task 2 n<=2000, A=1
n的范围扩大了，但是A＝1很关键，这意味着我不考虑分组是否大等A了，只要<=B即可（显然这样我们就要让分组最小）。
那么我们改良一下dp，用f[i]表示前i个数，满足条件的情况下，至少分几组。
f[i]=min(f[j])+1;(j=[0,i-1],s[j+1..i] or x=x)
最后的答案和B比较一下即可,这样就dp变成了n^2了，其他过程不变。
复杂度n^2logAi。
附很丑的代码
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } bool f[105][105]; int f2[2005]; int n; ll ans; ll s[2005]; int a,b; bool check(ll x) { memset(f,0,sizeof(f)); f[0][0]=1; for(int i=1;i<=n;i++) for(int k=1;k<=i;k++) for(int j=0;j<i;j++) { if(((s[i]-s[j])|x)==x) f[i][k]|=f[j][k-1]; } for(int i=a;i<=b;i++) if(f[n][i]) return true; return false; } bool check2(ll x) { f2[0]=0;ll nown=0; for(int i=1;i<=n;i++) { f2[i]=n+1; for(int j=0;j<i;j++) { if(((s[i]-s[j])|x)==x) f2[i]=min(f2[i],f2[j]+1); } } if(f2[n]<=b) return true; return false; } int main() { freopen("sculpture.in","r",stdin); freopen("sculpture.out","w",stdout); n=read();a=read();b=read(); for(int i=1;i<=n;i++) s[i]=read(); for(int i=1;i<=n;i++) s[i]+=s[i-1]; if(n<=100) { ans=(ll)1<<50;--ans; for(int i=49;i>=0;--i) { ans-=(ll)1<<i; if(!check(ans)) ans+=(ll)1<<i; } } else { ans=(ll)1<<50;--ans; for(int i=49;i>=0;--i) { ans-=(ll)1<<i; if(!check2(ans)) ans+=(ll)1<<i; } } printf("%I64d\n",ans); return 0; }
2.雅加达的摩天楼
有n个点m只doge（0-m-1)，每只doge给定初始位置和跳跃力，每次跳跃，位置为b,跳跃力为p的doge可以跳到b+p或者b-p。
现在doge0有信息要传到doge1 求最少的跳跃数。n,m<=30000
网上有其他的最短路的做法，但是我们仔细分析分析，是可以暴力的.....
设一个状态(b,p)表示现在信息传到了在b点跳跃力为p的doge上。从出题人卡代码的角度上，显然要状态数最多，只要加上了判重，那么状态数就最多是
30000+2*15000+3*10000+....
也就是说每个跳跃力状态数最多只有n种，但是对于跳跃力p,每个能增加的状态数辆只有n/p....
那么这样数量最多的时候， doge跳跃力从1,2,2,3,3,3,一直到k, k*(k-1)/2=m，状态数最多n＊k，大约七百多万....
所以直接bfs，到达一个没到过的点时候把那里的doge全部入队，加上哈希判重即可。（map跑太慢了，听了一个大佬的建议手写了一个在这道题理论上o(1)的哈希表...)
附上好丑好丑的代码
#include<iostream> #include<cstdio> #include<queue> #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int n,m,cnt=0,cnt2=0; int head[30005]; bool has[30005]; int front[9875322]; int hx[7300001]; int next[7300001]; struct edge{ int m,next; }e[30005]; int q[3][7300001]; int top,tail; inline void push(int b,int p,int f) { q[0][++top]=b; q[1][top]=p; q[2][top]=f; } inline void ins(int x,int y) { e[++cnt].next=head[x]; head[x]=cnt; e[cnt].m=y; } void rel(int num,int f)//释放所有doge { has[num]=1; for(int i=head[num];i;i=e[i].next) push(num,e[i].m,f); } inline void insw(int h,int b) { next[++cnt2]=front[h]; front[h]=cnt2; hx[cnt2]=b; } bool check(int hash,int b) { for(int i=front[hash];i;i=next[i]) if(hx[i]==b) return false; insw(hash,b); return true; } inline void get(int&b,int&p,int&f) { b=q[0][++tail]; p=q[1][tail]; f=q[2][tail]; } inline void add(int b,int p,int f) { int hash=(b<<15)+p;hash%=9875321; if(check(hash,b)) { push(b,p,f); if(!has[b]) rel(b,f); } } int main() { freopen("skyscraper.in","r",stdin); freopen("skyscraper.out","w",stdout); n=read();m=read();int from,to; for(register int i=1;i<=m;++i) { q[0][i]=read();q[1][i]=read(); ins(q[0][i],q[1][i]); }from=q[0][1];to=q[0][2]; rel(from,0); if(from==to) return 0*puts("0"); register int b,p,f; while(top!=tail) { get(b,p,f); if(b+p==to||b-p==to) {printf("%d\n",f+1);return 0;} if(b>=p) add(b-p,p,f+1); if(b+p<n) add(b+p,p,f+1); } puts("-1"); return 0; }
3.巴邻旁之桥
从前有条河，河旁住着人....
有n个人，每个人有要从一个坐标到另一个坐标，这些位置可能在河的两边。现在你要在河的某些位置修建垂直于河的k座桥，让所有人的路径长之和最短。
对于Task 1 k=1,n<=100000
不过河的人直接统计答案。
剩下的人，很显然，只修一座桥的情况下，一定要修在坐标的中位数那里。（设桥修在x，每个坐标产生的距离为|pos-x|，脑补一下就知道了）。
对于Task 2 k=2 n<=100000
这下预算高了一点 要修两座桥了，对于每一个人(x,y)，肯定走离x，y的中点(x+y)/2更近的桥。
那么一定会存在一个分割点，使得左边的人走左边的桥，右边的人走右边的桥，距离和最短。这样的话，两边的桥就按照Task1修在中位数就可以了。
那么就要考虑枚举分割点。从一段中删掉或者插入一个点，我们发现由于每次都选在中位数，实际上产生影响的只有被操作的那个点。所以我们用两个权值线段树（或者平衡树），维护左右两段的中位数即可啦。
复杂度nlogn
附上最丑的代码
#include<iostream> #include<cstdio> #include<algorithm> #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘) f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘; ch=getchar();} return x*f; } int T1[800005],T2[800005]; inline ll myabs(ll x) { return x<0?-x:x; } struct gg{ int l,r,mid,idl,idr; }home[200005]; int n,cnt=0; char c1,c2; ll s[200005]; ll ext=0,ans=0,ans2=0,minn,num; int solve1() { int a,b; for(int i=1;i<=n;i++) { scanf("%c",&c1);a=read(); scanf("%c",&c2);b=read(); if(c1==c2) ext+=myabs(a-b); else { s[++cnt]=a; s[++cnt]=b; ++ext; } } sort(s+1,s+cnt+1); ll mid=s[(cnt+1)/2]; for(int i=1;i<=cnt;i++) ans+=myabs(mid-s[i]); printf("%lld",ans+ext); return 0; } ll query(int*T,int x,int l,int r,int rk) { if(l==r) return s[l]; if(T[x<<1]>=rk) return query(T,x<<1,l,(l+r)>>1,rk); else return query(T,x*2+1,(l+r)/2+1,r,rk-T[x<<1]); } void ins(int*T,int x,int p,int l,int r,int ad) { if(l!=r) { int mid=(l+r)>>1; if(x<=mid) ins(T,x,p<<1,l,mid,ad); else ins(T,x,(p<<1)+1,mid+1,r,ad); } T[p]+=ad; } bool cmp(gg x,gg y){return x.mid<y.mid;} int main() { freopen("bridge.in","r",stdin); freopen("bridge.out","w",stdout); int type=read();n=read(); if(type==1) return 0*solve1(); int a,b; for(int i=1;i<=n;i++) { scanf("%c",&c1);a=read(); scanf("%c",&c2);b=read(); //cout<<c1<<" "<<c2<<endl; if(c1==c2) ext+=myabs(a-b); else { home[++cnt].l=min(a,b); home[cnt].r=max(a,b); home[cnt].mid=(a+b)/2; s[++num]=a; s[++num]=b; ++ext; } } sort(s+1,s+num+1); for(int i=1;i<=cnt;i++) { home[i].idl=lower_bound(s+1,s+num+1,home[i].l)-s; home[i].idr=lower_bound(s+1,s+num+1,home[i].r)-s; } sort(home+1,home+cnt+1,cmp); if(cnt<=2) { ans=0; for(int i=1;i<=cnt;i++) ans+=home[i].r-home[i].l; printf("%lld\n",ans+ext);return 0; } for(int i=1;i<=cnt;i++) ins(T2,home[i].idl,1,1,num,1),ins(T2,home[i].idr,1,1,num,1); ans=ans2=0; ll pos=query(T2,1,1,num,cnt+1); for(int i=1;i<=cnt;i++) ans2+=myabs((ll)home[i].r-pos)+myabs((ll)home[i].l-pos); minn=ans+ans2; ll pos1,pos2=pos; for(int i=1;i<=cnt;i++) { ans2-=myabs((ll)home[i].l-pos2)+myabs((ll)home[i].r-pos2); ins(T1,home[i].idl,1,1,num,1); ins(T2,home[i].idl,1,1,num,-1); ins(T1,home[i].idr,1,1,num,1); ins(T2,home[i].idr,1,1,num,-1); pos1=query(T1,1,1,num,i); pos2=query(T2,1,1,num,cnt-i+1); ans+=myabs((ll)home[i].l-pos1)+myabs((ll)home[i].r-pos1); if(ans+ans2<minn) minn=ans+ans2; } printf("%I64d\n",minn+ext); return 0; }
好的就是这样，理解了题目做法后都就不难写了.....
有什么错误请您指出 谢谢咯 ??
APIO2015简要题解