[关闭]
@Scarlet 2017-01-12T12:07:00.000000Z 字数 3034 阅读 3176

POI 2004

POI 2004 OI 解题报告


Game (Stage I) (0/100)

题意:的跳棋,一个子能向右移动一格,或跳过一段连续的棋子,先到m即负,求必胜的起手方案

巨难的博弈。
1. 若,则只能移动最后一枚棋子,
2. 若谁移动后所有棋子都在,则胜。故可转化模型:两个空格之间作为楼梯,间作为地面,连续棋子数B作为石子数,则成为经典问题(见论文)。 
结论:该游戏Sg函数为奇数格棋子数的Xor和。 优化:对于转化后连续的奇数个等价于,连续偶数个等价于。 
可行策略:
奇数楼梯i: 
偶数楼梯i:

Too difficult.

  1. #include<bits/stdc++.h>
  2. #define N 1001000
  3. #define G c=getchar()
  4. inline int read()
  5. {
  6. int x=0,f=1;char G;
  7. while(c>57||c<48){if(c=='-')f=-1;G;}
  8. while(c>47&&c<58)x=x*10+c-48,G;
  9. return x*f;
  10. }
  11. int n,m,i,now,tot,top,ans,sum,a[N],b[N];
  12. int main()
  13. {
  14. m=read(),n=read();a[n+1]=m-1;
  15. for(int i=1;i<=n;i++)a[i]=read();
  16. if(a[n]>=m-1)
  17. {
  18. for(int i=n;i&&a[i]-a[i-1]==1;i--)sum++;
  19. return printf("%d",sum+1),0;
  20. }
  21. for(int i=n;i;i--,now++)
  22. if(a[i+1]-a[i]!=1)
  23. {
  24. b[top++]=now;now=0;
  25. if(a[i+1]-a[i]>2)top+=2-((a[i+1]-a[i])&1);
  26. }
  27. b[top]=now;
  28. for(int i=1;i<=top;i++)
  29. if(i&1)ans^=b[i];
  30. for(int i=1;i<=top;i++)
  31. 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]))
  32. sum++;
  33. printf("%d",sum);
  34. }

Strings (Stage I) (0/100)

题意:


Spies (Stage I) (0/100)


The Competition (Stage I) (0/100)


The Bridge (Stage II - day 0) (0/100)

题意:个人过桥,最多两个人同时过,两人过桥取最慢速度,求最短时间

输入的过桥时间是升序的。考虑贪心,观察样例得知有两种情况会比较优:最快的人与当前人一起去,最快的人回来;两快的过去,然后一个回来,然后两个最慢的过去,另一个再回来。
这样就能贪心了

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 100010
  6. using namespace std;
  7. #define G c=getchar()
  8. inline int read()
  9. {
  10. int x=0,f=1;char G;
  11. while(c>57||c<48){if(c=='-')f=-1;G;}
  12. while(c>47&&c<58)x=x*10+c-48,G;
  13. return x*f;
  14. }
  15. int n,a[maxn],f[maxn];
  16. int main()
  17. {
  18. n=read();
  19. for(int i=1;i<=n;i++)a[i]=read();
  20. if(n<=2)return printf("%d",a[n]),0;
  21. for(int i=n-1;i>=2;i--)
  22. {
  23. f[i]=f[i+1]+a[1]+a[i+1];
  24. if(i<=n-2)f[i]=min(f[i],f[i+2]+a[i+2]+a[1]+a[2]*2);
  25. }
  26. printf("%d",f[2]+a[2]);
  27. }

Gates (Stage II - day 1) (0/100)


Cave (Stage II - day 1) (0/100)


Passage (Stage II - day 2) (0/100)

题意:个人过桥,不能超过总载重,多人过桥取最慢速度,求最短时间

状压dp,f[S]表示状态为的人在对岸的最短时间。
每次变化都是转移,所以只要枚举状态的子集就行了。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 20
  6. #define G c=getchar()
  7. inline int read()
  8. {
  9. int x=0,f=1;char G;
  10. while(c>57||c<48){if(c=='-')f=-1;G;}
  11. while(c>47&&c<58)x=x*10+c-48,G;
  12. return x*f;
  13. }
  14. using namespace std;
  15. int t[maxn],w[maxn],f[1<<16],T[1<<16],s[1<<16];
  16. int bin[maxn],W,n;
  17. int main()
  18. {
  19. memset(f,63,sizeof(f));
  20. bin[0]=1;for(int i=1;i<maxn;i++)bin[i]=bin[i-1]<<1;
  21. W=read(),n=read();
  22. for(int i=0;i<n;i++)
  23. t[i]=read(),w[i]=read();
  24. for(int i=0;i<bin[n];i++)
  25. for(int j=0;j<n;j++)
  26. if(i&bin[j])
  27. T[i]=max(T[i],t[j]),s[i]+=w[j];
  28. f[0]=0;
  29. for(int i=1;i<bin[n];i++)
  30. for(int j=i;j;j=i&(j-1))
  31. if(s[j]<=W)f[i]=min(f[i],T[j]+f[i^j]);
  32. printf("%d",f[bin[n]-1]);
  33. }

The Tournament (Stage II - day 2) (0/100)


Guesswork (Stage III - day 0) (0/100)


East-West (Stage III - day 1) (0/100)


The Islands (Stage III - day 1) (0/100)


C-algae (Stage III - day 2) (0/100)


Maximal Orders of Permutations (Stage III - day 2) (0/100)


添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注