Loading... ## Problem A. A+B Problem (I) I don't know I need to say what. But I know there are many teams using `BigInteger`. They get `Time Limit Exceeded` and some people get `Wrong Answer` or `Runtime Error` because they didn't deal negative numbers well. However, $-10^{18} \leq a,b \leq 10^{18}$, which means $-2 \times 10^{18} \leq a + b \leq 2 * 10^{18}$. That's ok for `long long`. ```cpp #include <bits/stdc++.h> using namespace std; int main() { long long a, b; scanf("%lld%lld", &a, &b); printf("%lld\n", a + b); return 0; } ``` ## Problem B. A+B Problem (II) 题目里已经写的很清楚了，在每次输出以后你需要使用`fflush(stdout);`或`System.out.flush();`让系统收到你的输出，否则会导致`TIME LIMIT`。 ```cpp #include <bits/stdc++.h> using namespace std; int main() { long long a, b; while (scanf("%lld%lld", &a, &b)==2){ if (a == -1 && b == -1) return 0; printf("%lld\n", a + b); fflush(stdout); } } ``` ## Problem C. 又到了白色相簿的季节 答案：`251463` 就是测测评测机压力嘛~大家暴力枚举下嘛~ ## Problem D. 31点 ### 方法1： （这是出题人想要的方案）考虑这个游戏的实质就是1-6的选数博弈问题，但是由于每个数字有限，所以会存在一些特殊情况，如$(n,m)=(5,5),(1,1),(1,2)$，只要把这些情况考虑清楚即可，其他时候无脑拼7。完整的情况如下图所示（包括$n=2$的）： - 先手拿 5 - 假如后手拿 5，先手接着拿 2，后手再拿 5 先手继续 2…… - 假如后手拿非 5 的，先手就在下一次拿取中抢占关键点 3、10、17、24、31，抢到之后后手拿 X 先手就拿 7-X - 先手拿1： <img src="https://image.mlwly.cn/2019/05/14/5cda0a762739e.jpg" alt="e61190ef76c6a7eff48bd97bf3faaf51f3de6639.jpg" /> - 先手拿2： <img src="https://image.mlwly.cn/2019/05/14/5cda0a865a201.jpg" alt="b21c8701a18b87d6e36bdd42090828381f30fd46.jpg" /> 对应的程序实现如下： ```cpp #include <bits/stdc++.h> using namespace std; int num[7]={0,4,4,4,4,4,4}; int sum=0; void play() { while (sum!=31) { int x=31-sum; x%=7; assert(num[x]); printf("%d\n",x); num[x]--; sum+=x; fflush(stdout); scanf("%d",&x); if (x<=0) return; num[x]--; sum+=x; } } int main() { int n,m; scanf("%d%d",&n,&m); num[n]--; num[m]--; sum=n+m; if ((n==5&&m!=5)||(n==1&&m>=3)) { play(); return 0; } if (n==5&&m==5) { while (1) { printf("2\n"); fflush(stdout); num[2]--; sum+=2; int x; scanf("%d",&x); if (x<=0) return 0; num[x]--; sum+=x; if (x!=5) { play(); break; } } } if (n==1) { bool flag=(m==2); while (1) { printf("6\n"); fflush(stdout); num[6]--; sum+=6; int x; scanf("%d",&x); if (x<=0) return 0; num[x]--; sum+=x; if (x>=3) { play(); break; } if (x==2) { if (flag) { play(); break; } flag=true; continue; } } } return 0; } ``` ### 方法2： 不过验题人发现，这题步数很少，直接暴力搜索，把所有情况搜到，找到所有的必胜情况即可，为了代码的美观，可以使用状压等技巧 ```cpp #include<stdio.h> #include<string.h> int state[5*5*5*5*5*5]; int nextplay[5*5*5*5*5*5]; int go(int nowstate){ if(state[nowstate])return state[nowstate]; int a[7],sum=0; for(int i=1,temp=nowstate;i<=6;i++){ a[i]=temp%5; sum+=a[i]*i; temp/=5; } if(sum==31)return state[nowstate]=-1; if(sum>31)return state[nowstate]=1; for(int i=1,temp=1;i<=6;i++){ if(a[i]<4&&go(nowstate+temp)==-1){ nextplay[nowstate]=i; return state[nowstate]=1; } temp*=5; } return state[nowstate]=-1; } int w[7]; int main() { w[1]=1; for(int i=2;i<=6;i++) w[i]=w[i-1]*5; int nowstate=0; int n,m; scanf("%d",&n); nowstate+=w[n]; int x; while(~scanf("%d",&x)){ nowstate+=w[x]; go(nowstate); printf("%d\n",nextplay[nowstate]); fflush(stdout); nowstate+=w[nextplay[nowstate]]; } return 0; } ``` ## Problem E. 管道设计 很显然，你可以用三个水龙头将其设计为$1:1$的输出，如下图所示 <img src="https://image.mlwly.cn/2019/12/21/75e7760430bac.png" alt="" /> 找到$c+d \leq 2^n$的最小的$n$，使用$1:1$的输出分配建立一颗深度为$n$的二叉树，其最底层有$2^n$个叶子节点，我们将其中$c$个叶子节点连向$-1$，$d$个连向$-2$，剩余的回流，最后形成的就是$c:d$的了。 为了减少输出，我们需要把相同输出的$1:1$输出进行合并或简化。 ```cpp #include <bits/stdc++.h> using namespace std; // The main idea for the solution works in two stages: // - first: we construct a 1:1 splitter from the c:d splitter as follows // // | // /----|----\ // / / \ \ // c c d d // | / \ | // \-/| |\-/ // d c // | | // // To see that this acts as a 1:1 splitter, consider just the // output of the second layer. It produces for outputs with ratios // c^2:c*d:d*c:d^2. The middle two are equal, and if we lead the // the outer two back to the root, effectively all input is thus split // in half. // // - next: We construct the desired ratio by building a binary tree (using // the above 1:1 splitter) that sends: // a/2^n to output A // b/2^n to output B // (2^n-a-b)/2^n back to the root. // this is done by repeatedly splitting the unused leaves in half, // sending output to A, B or the root in each layer to the maximum // extent possible. Again, this works because the output is forced to // have the right ratio, and anything that doesn't is simply // reprocessed. int main() { long long a, b, c, d; cin >> c >> d >> a >> b; long long denom = a+b; long long pow2 = 1; while (pow2 < denom) pow2 *= 2; long long feedback = pow2-denom; vector<pair<int, int>> splitters; queue<int> endpoints; // Setup initial 50-50 split splitters.push_back({1,2}); splitters.push_back({0,-5}); splitters.push_back({-5,0}); endpoints.push(2*1+1); endpoints.push(2*2); long long cur = pow2/2; while (a != 0 || b != 0 || feedback != 0) { queue<int> nextendpoints; while (a >= cur) { a -= cur; int ep = endpoints.front(); endpoints.pop(); // Patch output of selected endpoint to -1 int idx = ep/2; if (ep % 2 == 1) splitters[idx].second = -1; else splitters[idx].first = -1; } while (b >= cur) { b -= cur; int ep = endpoints.front(); endpoints.pop(); // Patch output of selected endpoint to -2 int idx = ep/2; if (ep % 2 == 1) splitters[idx].second = -2; else splitters[idx].first = -2; } while (feedback >= cur) { feedback -= cur; int ep = endpoints.front(); endpoints.pop(); // Patch output of selected endpoint to 0 int idx = ep/2; if (ep % 2 == 1) splitters[idx].second = 0; else splitters[idx].first = 0; } // Further split remaining endpoints (there will be at most 2!) while (!endpoints.empty()) { int ep = endpoints.front(); endpoints.pop(); int nidx = splitters.size(); // Patch output of selected endpoint to nidx int idx = ep/2; if (ep % 2 == 1) splitters[idx].second = nidx; else splitters[idx].first = nidx; // Create new 50-50 splitter splitters.push_back({nidx+1,nidx+2}); splitters.push_back({nidx, -5}); splitters.push_back({-5, nidx}); nextendpoints.push(2*(nidx+1)+1); nextendpoints.push(2*(nidx+2)); } // Do bookkeeping endpoints.swap(nextendpoints); cur /= 2; } // Output all splitters cout << splitters.size() << endl; for (auto s : splitters) { cout << s.first << " " << s.second << endl; } } ``` ~~我觉得上面那个写的有点长，我们还是看下一个吧~~ ```c #include <stdio.h> typedef long long ll; #define prt( x, y ) printf("%lld %lld\n",(x),(y)) void connect( ll a, ll x, ll y ) { prt( 3*a+1, 3*a+2 ); prt( 3*a, x < 0 ? x : 3*x ); prt( y < 0 ? y : 3*y, 3*a ); } int main() { ll x[3], s, N = 2, B[3] = {0,0,1}, C[6], D; scanf( "%lld %lld", x+1, x ); scanf( "%lld %lld", x+1, x ); s = x[0]+x[1]-1; while( s >>= 1 ) N <<= 1; x[2] = N-x[0]-x[1]; printf( "%d\n", 3*(__builtin_popcountll(x[0])+__builtin_popcountll(x[1])+__builtin_popcountll(x[2])-1) ); for( ll k = N>>1; B[1] < B[2]; k >>= 1 ) { B[0] = B[1]; B[1] = B[2]; D = 0; for( ll i = 0; i < 3; ++i ) { if( x[i] >= k ) { x[i] -= k; C[D++] = i-2; } } while( D < 2*(B[1]-B[0]) ) C[D++] = B[2]++; for( ll i = 0; i < B[1]-B[0]; ++i ) connect( B[0]+i, C[2*i], C[2*i+1] ); } } ``` Last modification：December 21st, 2019 at 09:53 pm © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
