[关闭]
@Scarlet 2017-01-12T12:06:52.000000Z 字数 9897 阅读 493

POI 2003

POI 2003 OI 解题报告


Sequences without Stammers

题意:用最少的字符种数构造长度为的字符串使得没有连续重复子串

不是很懂,似乎>=5的情况下可以用三种字符无限构造。

贴一个poi的std:

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. using namespace std;
  6. int i,l,n;
  7. bool t[32769],c,d;
  8. int main()
  9. {
  10. scanf("%d",&n);
  11. for(l=1,c=0;l<=32768;t[l]=c,l*=2,c=!c)
  12. if (n==1) puts("1\na");
  13. if (n==2) puts("2d\nab");
  14. if (n==3) puts("2\baba");
  15. if (n>=4)
  16. {
  17. puts("3");
  18. for(c=0,d=1,i=1;i<=n;i++)
  19. {
  20. printf("%c",(c==d?'a':(c?'b':'c')));
  21. l=1+((i+1)^i);
  22. if(l>=65536)l>>=16;
  23. c=d;d^=t[l];
  24. }
  25. puts("");
  26. }
  27. return 0;
  28. }

Chocolate (Stage I)

题意:一块的巧克力,横切第刀需要的价格,竖切第刀需要的价格,求最小价值。

贪心,假设价值从大到小切是最优的。模拟即可。

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

Numerals of Przesmyks (Stage I) (0/100)


Printed-Circuit Boards (Stage I) (0/100)


Smugglers (Stage I)

题意:物品1通过一系列特技变化变成物品i,再变回物品1,试最小化特价代价+v[i]/2

嘛,一看就是一道最短路。是找一个经过1和v[i]的有向最小环,事实上求出正反边的最短路取个min就好了。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 5010
  6. #define maxm 200010
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline int read()
  11. {
  12. int x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. int n,m;
  18. #define AE(u,v,w,idx) E[Si]=(Ed){u,v,w},nxt[Si]=idx[u],idx[u]=Si++
  19. struct Ed{int u,v,w;}E[maxm];
  20. int a[maxn],i1[maxn],i2[maxn],nxt[maxm],Si=1,q[maxm],d[maxn],e[maxn],v[maxn],ans;
  21. queue<int>Q;
  22. int main()
  23. {
  24. n=read();
  25. for(int i=1;i<=n;i++)a[i]=read();
  26. m=read();
  27. for(int u,v,w;m--;)u=read(),v=read(),w=read(),AE(u,v,w,i1),AE(v,u,w,i2);
  28. memset(d,63,sizeof(d));Q.push(1);d[1]=0;v[1]=1;
  29. for(;!Q.empty();)
  30. {
  31. int u=Q.front();Q.pop();v[u]=0;
  32. for(int i=i1[u];i;i=nxt[i])
  33. if(d[u]+E[i].w<d[E[i].v])
  34. {
  35. d[E[i].v]=d[u]+E[i].w;
  36. if(!v[E[i].v])
  37. v[E[i].v]=1,Q.push(E[i].v);
  38. }
  39. }
  40. memset(e,63,sizeof(e));Q.push(1);e[1]=0;v[1]=1;
  41. for(;!Q.empty();)
  42. {
  43. int u=Q.front();Q.pop();v[u]=0;
  44. for(int i=i2[u];i;i=nxt[i])
  45. if(e[u]+E[i].w<e[E[i].v])
  46. {
  47. e[E[i].v]=e[u]+E[i].w;
  48. if(!v[E[i].v])
  49. v[E[i].v]=1,Q.push(E[i].v);
  50. }
  51. }
  52. ans=1e9;
  53. for(int i=1;i<=n;i++)
  54. ans=min(ans,d[i]+e[i]+a[i]/2);
  55. printf("%d\n",ans);
  56. return 0;
  57. }

Mastermind II (Stage II - day 0) (0/100)


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


Trinomial (Stage II - day 1)

题意:计算次项系数对取模

在lbn187的帮助下拿到了伪std。
可还是不知道是怎么回事,好神啊,为什么求就行了呢?
不是很懂啊

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<stdio.h>
  5. int f[3]={1,1,2};long long n,m,t;
  6. int C(int n,int m){return m>n?0:f[n]*f[m]*f[n-m]%3;}
  7. int L(long long n,long long m){return m?C(n%3,m%3)*L(n/3,m/3)%3:1;}
  8. int main()
  9. {
  10. for(scanf("%lld",&t);t--;)
  11. {
  12. scanf("%lld%lld",&n,&m);
  13. printf("%d\n",L(2*n,m)*(m%2+1)%3);
  14. }
  15. }

Tiles (Stage II - day 2)

题意:一个字符串同时是它的循环节,求的最多不同字符数。

时,答案是
否则为

证明?分类讨论,找出最小循环节即可。

为了能顺理成章的出题提高自己的姿势水平还是简单写一下吧。

证明:
假设这是一个从开始的无限长度的字符串

因为都是循环节,所以

也就是说,事实上是一个以最小循环节的字符串,这个最小循环节内的字符可以随意钦点,所以答案是
但上述情况是建立在足够长的前提下的。

好比一辆电梯每次只能移动层,这个电梯最终能到达的楼层与总层数直接相关。好在我们有个定理:当时,电梯可以在任意层停止。

那么原题也是同理,当,最小循环节就是,也就是答案。否则通过手算得到答案为

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 501
  6. using namespace std;
  7. typedef long long LL;
  8. #define G c=getchar()
  9. inline int read()
  10. {
  11. int x=0,f=1;char G;
  12. while(c>57||c<48){if(c=='-')f=-1;G;}
  13. while(c>47&&c<58)x=x*10+c-48,G;
  14. return x*f;
  15. }
  16. const int MAXN = 510;
  17. struct HugeInt
  18. {
  19. int len, s[MAXN];
  20. HugeInt ()
  21. {
  22. memset(s, 0, sizeof(s));
  23. len = 1;
  24. }
  25. HugeInt (int num) { *this = num; }
  26. HugeInt (const char *num) { *this = num; }
  27. HugeInt operator = (const int num)
  28. {
  29. char s[MAXN];
  30. sprintf(s, "%d", num);
  31. *this = s;
  32. return *this;
  33. }
  34. HugeInt operator = (const char *num)
  35. {
  36. if(len==1&&num[0]==0)return *this;
  37. for(int i = 0; num[i] == '0'; num++) ; //去前导0
  38. len = strlen(num);
  39. for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
  40. return *this;
  41. }
  42. HugeInt operator + (const HugeInt &b) const //+
  43. {
  44. HugeInt c;
  45. c.len = 0;
  46. for(int i = 0, g = 0; g || i < max(len, b.len); i++)
  47. {
  48. int x = g;
  49. if(i < len) x += s[i];
  50. if(i < b.len) x += b.s[i];
  51. c.s[c.len++] = x % 10;
  52. g = x / 10;
  53. }
  54. return c;
  55. }
  56. HugeInt operator += (const HugeInt &b)
  57. {
  58. *this = *this + b;
  59. return *this;
  60. }
  61. void clean()
  62. {
  63. while(len > 1 && !s[len-1]) len--;
  64. }
  65. HugeInt operator * (const HugeInt &b) //*
  66. {
  67. HugeInt c;
  68. c.len = len + b.len;
  69. for(int i = 0; i < len; i++)
  70. {
  71. for(int j = 0; j < b.len; j++)
  72. {
  73. c.s[i+j] += s[i] * b.s[j];
  74. }
  75. }
  76. for(int i = 0; i < c.len; i++)
  77. {
  78. c.s[i+1] += c.s[i]/10;
  79. c.s[i] %= 10;
  80. }
  81. c.clean();
  82. return c;
  83. }
  84. HugeInt operator *= (const HugeInt &b)
  85. {
  86. *this = *this * b;
  87. return *this;
  88. }
  89. HugeInt operator - (const HugeInt &b)
  90. {
  91. HugeInt c;
  92. c.len = 0;
  93. for(int i = 0, g = 0; i < len; i++)
  94. {
  95. int x = s[i] - g;
  96. if(i < b.len) x -= b.s[i];
  97. if(x >= 0) g = 0;
  98. else
  99. {
  100. g = 1;
  101. x += 10;
  102. }
  103. c.s[c.len++] = x;
  104. }
  105. c.clean();
  106. return c;
  107. }
  108. HugeInt operator -= (const HugeInt &b)
  109. {
  110. *this = *this - b;
  111. return *this;
  112. }
  113. HugeInt operator / (const HugeInt &b)
  114. {
  115. HugeInt c, f = 0;
  116. for(int i = len-1; i >= 0; i--)
  117. {
  118. f = f*10;
  119. f.s[0] = s[i];
  120. while(f >= b)
  121. {
  122. f -= b;
  123. c.s[i]++;
  124. }
  125. }
  126. c.len = len;
  127. c.clean();
  128. return c;
  129. }
  130. HugeInt operator /= (const HugeInt &b)
  131. {
  132. *this = *this / b;
  133. return *this;
  134. }
  135. HugeInt operator % (const HugeInt &b)
  136. {
  137. HugeInt r = *this / b;
  138. r = *this - r*b;
  139. return r;
  140. }
  141. HugeInt operator %= (const HugeInt &b)
  142. {
  143. *this = *this % b;
  144. return *this;
  145. }
  146. bool operator < (const HugeInt &b)
  147. {
  148. if(len != b.len) return len < b.len;
  149. for(int i = len-1; i >= 0; i--)
  150. {
  151. if(s[i] != b.s[i]) return s[i] < b.s[i];
  152. }
  153. return false;
  154. }
  155. bool operator > (const HugeInt &b)
  156. {
  157. if(len != b.len) return len > b.len;
  158. for(int i = len-1; i >= 0; i--)
  159. {
  160. if(s[i] != b.s[i]) return s[i] > b.s[i];
  161. }
  162. return false;
  163. }
  164. bool operator == (const HugeInt &b)
  165. {
  166. return !(*this > b) && !(*this < b);
  167. }
  168. bool operator != (const HugeInt &b)
  169. {
  170. return !(*this == b);
  171. }
  172. bool operator <= (const HugeInt &b)
  173. {
  174. return *this < b || *this == b;
  175. }
  176. bool operator >= (const HugeInt &b)
  177. {
  178. return *this > b || *this == b;
  179. }
  180. string str() const
  181. {
  182. string res = "";
  183. for(int i = 0; i < len; i++) res = char(s[i]+'0') + res;
  184. return res;
  185. }
  186. };
  187. istream& operator >> (istream &in, HugeInt &x)
  188. {
  189. string s;
  190. in >> s;
  191. x = s.c_str();
  192. return in;
  193. }
  194. ostream& operator << (ostream &out, const HugeInt &x)
  195. {
  196. out << x.str();
  197. return out;
  198. }
  199. HugeInt Pow(HugeInt x,int y)
  200. {
  201. HugeInt r=1;
  202. for(;y;y>>=1,x=x*x)if(y&1)r=r*x;
  203. return r;
  204. }
  205. HugeInt factorial(int x)
  206. {
  207. HugeInt a=1;
  208. for(int i=2;i<=x;i++)
  209. a*=i;
  210. return a;
  211. }
  212. HugeInt k,l,d,n,g;
  213. HugeInt gcd(HugeInt a,HugeInt b)
  214. {
  215. return (b.len==1&&b.s[0]==0)?a:gcd(b,a%b);
  216. }
  217. int main()
  218. {
  219. cin>>n>>k>>l;d=gcd(k,l);
  220. g=k+l-gcd(k,l);
  221. if(n<=g)cout<<k+l-n<<endl;
  222. else cout<<d<<endl;
  223. return 0;
  224. }

板子贴贴没希望了。


Connections (Stage II - day 2)

题意:求图中第短路

Too difficult,大概是A*特技。


Treasure (Stage III - day 1) (0/100)


Sums (Stage III - day 1)

题意:给定个数,每次询问一个数能否表示成这个数之和,一数可以多次使用

这是一个(我现在才会做的)经典问题。表示个数中最小的数,那么只要考虑意义下每个被表示数中最小的数,用f[i]表示。
是个环状背包,所以需要在环上跑两遍。
差点被main卡常。QAQ

  1. /*
  2. Author:Scarlet
  3. */
  4. #pragma GCC optimize ("O2")
  5. #include<bits/stdc++.h>
  6. #define maxn 50010
  7. using namespace std;
  8. typedef long long LL;
  9. #define G c=getchar()
  10. inline int read()
  11. {
  12. int x=0,f=1;char G;
  13. while(c>57||c<48){if(c=='-')f=-1;G;}
  14. while(c>47&&c<58)x=x*10+c-48,G;
  15. return x*f;
  16. }
  17. int m,i,w,j,st,p,q,n,f[maxn],a[maxn/10],mn=maxn;
  18. bool vis[maxn],cnt;
  19. int main()
  20. {
  21. n=read();
  22. for(i=1;i<=n;i++)a[i]=read(),mn=min(mn,a[i]);
  23. for(i=1;i<mn;i++)f[i]=2000000000;
  24. for(i=1,w,j;i<=n;i++)
  25. for(w=a[i]%mn,j=1;j<=2;j++,cnt^=1)
  26. for(st=0;vis[st]==cnt&&st<mn;st++)
  27. for(p=st,q=st+w>=mn?st+w-mn:st+w;vis[p]==cnt;vis[p]=cnt^1,p=q,q=q+w>=mn?q+w-mn:q+w)
  28. if(f[p]+a[i]<f[q])f[q]=f[p]+a[i];
  29. m=read();
  30. for(;m--;)
  31. {
  32. i=read();
  33. if(i>=f[i%mn])puts("TAK");
  34. else puts("NIE");
  35. }
  36. return 0;
  37. }

Monkeys (Stage III - day 2)

题意:有只猴子,第一只尾巴抓住树枝,每一只猴子可能双手抓住其他猴子的尾巴,即二叉树结构,现在每秒都有猴子松开某只手,求各个猴子落地时间

看到题目第一眼认识到删边不可做,加边可做,于是就把询问倒过来,看猴子什么时候上树。

因为猴子是“一块一块”上去的,所以应该是使用并查集,当加入到1所在集合中就更新整组答案。这里采用dfs搜索联通块。

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. #define maxn 400010
  6. using namespace std;
  7. typedef long long LL;
  8. #define G c=getchar()
  9. inline int read()
  10. {
  11. int x=0,f=1;char G;
  12. while(c>57||c<48){if(c=='-')f=-1;G;}
  13. while(c>47&&c<58)x=x*10+c-48,G;
  14. return x*f;
  15. }
  16. int fa[maxn],a[maxn],n,m;
  17. int gf(int x){return x==fa[x]?x:fa[x]=gf(fa[x]);}
  18. #define AE(u,v) to[Si]=v,nxt[Si]=idx[u],idx[u]=Si++
  19. int idx[maxn],nxt[maxn],to[maxn],Si=1;
  20. void dfs(int x,int fa,int z)
  21. {
  22. a[x]=z;
  23. for(int i=idx[x];i;i=nxt[i])if(to[i]!=fa)dfs(to[i],x,z);
  24. }
  25. void uni(int x,int y,int z){
  26. int p=gf(x),q=gf(y);
  27. if(y<0||p==q)return;
  28. if(p==gf(1))dfs(y,x,z);else if(q==gf(1))dfs(x,y,z);else AE(x,y),AE(y,x);
  29. fa[p]=q;
  30. }
  31. int c[maxn][2],q[maxn][2],b[maxn][2];
  32. int main()
  33. {
  34. n=read(),m=read();a[1]=-1;
  35. for(int i=1;i<=n;i++)c[i][0]=read(),c[i][1]=read(),fa[i]=i;
  36. for(int i=1;i<=m;i++)q[i][0]=read(),q[i][1]=read()-1,b[q[i][0]][q[i][1]]=1;
  37. for(int i=1;i<=n;i++)for(int j=0;j<2;j++)if(!b[i][j])uni(i,c[i][j],-1);
  38. for(int i=m;i>=1;i--)uni(q[i][0],c[q[i][0]][q[i][1]],i-1);
  39. for(int i=1;i<=n;i++)printf("%d\n",a[i]);
  40. return 0;
  41. }

Shuffle (Stage III - day 2)

题意:给定和置换,求一个置换使得

要做这个题首先我们需要知道是什么
想象一个长度为的循环,如果我们将这个循环求次方,我们将会得到个长度为的循环
那么现在我们将分解成循环,假如现在我们得到了一个长度为的循环,那么由之前的结论可以得到
容易证明存在一个最小的满足这个是所有合法的的约数,且这个满足对于的任意一个质因子中的次数等于中的次数加上中的次数
于是我们找到这个最小的,将个长度为的循环合并成一个循环即可

From PoPoQQQ

  1. /*
  2. Author:Scarlet
  3. */
  4. #include<bits/stdc++.h>
  5. typedef long long LL;
  6. #define maxn 1000010
  7. using namespace std;
  8. int a[maxn],v[maxn],n,top,k,ans[maxn];
  9. vector<int>*st[maxn];
  10. #define G c=getchar()
  11. inline int read()
  12. {
  13. int x=0,f=1;char G;
  14. while(c>57||c<48){if(c=='-')f=-1;G;}
  15. while(c>47&&c<58){x=x*10+c-48;G;}
  16. return x*f;
  17. }
  18. void getC(int x,vector<int> *vec)
  19. {
  20. for(;;)
  21. {
  22. if(v[x])return;
  23. vec->push_back(x);
  24. v[x]=1;x=a[x];
  25. }
  26. }
  27. int cmp(vector<int>*v1,vector<int>*v2){return v1->size()<v2->size();}
  28. int L(int x)
  29. {
  30. int k=::k,re=1;
  31. for(int i=2;i*i<=x;i++)
  32. if(x%i==0)
  33. {
  34. while(x%i==0)x/=i,re*=i;
  35. while(k%i==0)k/=i,re*=i;
  36. }
  37. if(x-1)
  38. for(re*=x;k%x==0;)
  39. k/=x,re*=x;
  40. return re;
  41. }
  42. int main()
  43. {
  44. n=read();k=read();
  45. for(int i=1;i<=n;i++)
  46. a[i]=read();
  47. for(int i=1;i<=n;i++)
  48. if(!v[i])
  49. getC(i,st[++top]=new vector<int>);
  50. sort(st+1,st+top+1,cmp);
  51. for(int i=1;i<=top;)
  52. {
  53. static int a[maxn];
  54. int l=L(st[i]->size()),tmp=__gcd(l,k);
  55. for(int j=0;j<tmp;j++)
  56. for(int k=0;k<(signed)st[i+j]->size();k++)
  57. a[(j+(long long)k*::k)%l]=(*st[i+j])[k];
  58. for(int j=0;j<l;j++)
  59. ans[a[j]]=a[(j+1)%l];
  60. i+=tmp;
  61. }
  62. for(int i=1;i<=n;i++)
  63. printf("%d\n",ans[i]);
  64. }

Next POI 2005

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