@Scarlet
2017-01-12T20:07:00.000000Z
字数 3034
阅读 3331
POI 2004 OI 解题报告
题意：的跳棋，一个子能向右移动一格，或跳过一段连续的棋子，先到m即负，求必胜的起手方案
巨难的博弈。
1. 若，则只能移动最后一枚棋子，。
2. 若谁移动后所有棋子都在，则胜。故可转化模型：两个空格之间作为楼梯，与间作为地面，连续棋子数B作为石子数，则成为经典问题（见论文）。
结论：该游戏Sg函数为奇数格棋子数的Xor和。 优化：对于转化后连续的奇数个等价于个，连续偶数个等价于个。
可行策略：
奇数楼梯i：
偶数楼梯i：
Too difficult.
#include<bits/stdc++.h>#define N 1001000#define G c=getchar()inline int read(){int x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}int n,m,i,now,tot,top,ans,sum,a[N],b[N];int main(){m=read(),n=read();a[n+1]=m-1;for(int i=1;i<=n;i++)a[i]=read();if(a[n]>=m-1){for(int i=n;i&&a[i]-a[i-1]==1;i--)sum++;return printf("%d",sum+1),0;}for(int i=n;i;i--,now++)if(a[i+1]-a[i]!=1){b[top++]=now;now=0;if(a[i+1]-a[i]>2)top+=2-((a[i+1]-a[i])&1);}b[top]=now;for(int i=1;i<=top;i++)if(i&1)ans^=b[i];for(int i=1;i<=top;i++)if( (i&1)&&(b[i]^ans)<b[i] || !(i&1)&&(b[i-1]^ans)>b[i-1]&&((b[i-1]^ans)<=b[i]+b[i-1]))sum++;printf("%d",sum);}
题意：
题意：个人过桥，最多两个人同时过，两人过桥取最慢速度，求最短时间
输入的过桥时间是升序的。考虑贪心，观察样例得知有两种情况会比较优：最快的人与当前人一起去，最快的人回来；两快的过去，然后一个回来，然后两个最慢的过去，另一个再回来。
这样就能贪心了
/*Author:Scarlet*/#include<bits/stdc++.h>#define maxn 100010using namespace std;#define G c=getchar()inline int read(){int x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}int n,a[maxn],f[maxn];int main(){n=read();for(int i=1;i<=n;i++)a[i]=read();if(n<=2)return printf("%d",a[n]),0;for(int i=n-1;i>=2;i--){f[i]=f[i+1]+a[1]+a[i+1];if(i<=n-2)f[i]=min(f[i],f[i+2]+a[i+2]+a[1]+a[2]*2);}printf("%d",f[2]+a[2]);}
题意：个人过桥，不能超过总载重，多人过桥取最慢速度，求最短时间
状压dp，f[S]表示状态为的人在对岸的最短时间。
每次变化都是转移，所以只要枚举状态的子集就行了。
/*Author:Scarlet*/#include<bits/stdc++.h>#define maxn 20#define G c=getchar()inline int read(){int x=0,f=1;char G;while(c>57||c<48){if(c=='-')f=-1;G;}while(c>47&&c<58)x=x*10+c-48,G;return x*f;}using namespace std;int t[maxn],w[maxn],f[1<<16],T[1<<16],s[1<<16];int bin[maxn],W,n;int main(){memset(f,63,sizeof(f));bin[0]=1;for(int i=1;i<maxn;i++)bin[i]=bin[i-1]<<1;W=read(),n=read();for(int i=0;i<n;i++)t[i]=read(),w[i]=read();for(int i=0;i<bin[n];i++)for(int j=0;j<n;j++)if(i&bin[j])T[i]=max(T[i],t[j]),s[i]+=w[j];f[0]=0;for(int i=1;i<bin[n];i++)for(int j=i;j;j=i&(j-1))if(s[j]<=W)f[i]=min(f[i],T[j]+f[i^j]);printf("%d",f[bin[n]-1]);}