本文最后编辑于
题目大意：A没啥好说的。
解法：就硬找。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include <bits/stdc++.h> using namespace std;long long n, T;int main () cin >> T; while (T--){ cin >> n; while (1 ){ long long pro = n, ret = 0 ; while (pro) ret += (pro % 10 ), pro /= 10 ; if (__gcd(n, ret) > 1 ){ cout << n << endl; break ; } else n++; } } return 0 ; }
题目大意：有一些1×2^？的块，平放，放进一个盒子，给了盒子的宽，求盒子的高。
解法：贪心，能放多大就放多大的块，完了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <bits/stdc++.h> using namespace std;int n, T, m, ans, a;map <int , int > num; int main () scanf ("%d" , &T); while (T--){ scanf ("%d%d" , &n, &m); for (int i = 1 ; i <= n; i++) scanf ("%d" , &a), num[a]++; while (n){ ans++; int pro = 1 , ret = m; while (pro <= m) pro <<= 1 ; pro >>= 1 ; while (ret && n && pro){ if (num[pro]) ret -= pro, num[pro]--, n--; while ((pro > ret || !num[pro]) && pro) pro >>= 1 ; } } printf ("%d\n" , ans), ans = 0 ; } return 0 ; }
题目大意：给n块平行的平面镜，假如有一束强度为k的光射向镜子，将沿着射入方向穿过镜子并额外向反向反射出一束强度为k-1的光，当光强度降为0就消失了。假如某束光的前进方向没有镜子，就是射向外界的。问当一束强度为k的光从最左侧射入，求最终射向外界的光的总数。
解法：观察题面，n和k都比较小，而且实际上由于光不可能从镜子中间出现，只能从左右射入，所以最为关键的信息就是连续的一段镜子的数目以及光的强度和从左向射入还是从右向射入。所以我们可以直接枚举光强，f[i][j][k]表示从最右边到第i块镜子这么连续的一段镜子区间，j是光强，k是射入方向，同理s[i][j][k]是从最左边到第i块镜子这样连续的区间，j是光强，k是射入方向，之后就转移一下就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include <bits/stdc++.h> #define mo 1000000007 using namespace std;long long T, n, m, f[1005 ][1005 ][2 ], s[1005 ][1005 ][2 ]; int main () cin >> T; while (T--){ cin >> n >> m; for (int i = 0 ; i <= n; i ++) for (int j = 0 ; j <= m; j ++) f[i][j][0 ] = f[i][j][1 ] = 0 , s[i][j][0 ] = s[i][j][1 ] = 0 ; for (int i = 1 ; i <= n; i ++) f[i][1 ][0 ] = f[i][1 ][1 ] = 1 ; for (int i = 1 ; i <= m; i ++) f[0 ][i][0 ] = s[0 ][i][0 ] = 1 ; for (int i = 1 ; i <= n; i ++){ s[i][1 ][0 ] = (s[i - 1 ][1 ][0 ] + f[i][1 ][0 ]) % mo; s[i][1 ][1 ] = (s[i - 1 ][1 ][1 ] + f[i][1 ][1 ]) % mo; } for (int k = 2 ; k <= m; k ++) for (int i = 1 ; i <= n; i ++){ f[i][k][0 ] = 1 + (f[i][k][0 ] + s[i + 1 ][k - 1 ][1 ] - s[1 ][k - 1 ][1 ]) % mo; f[i][k][1 ] = 1 + (f[i][k][1 ] + s[n - 1 ][k - 1 ][0 ] + mo) % mo; if (i > 1 ) f[i][k][1 ] = (f[i][k][1 ] - s[i - 2 ][k - 1 ][0 ] + mo) % mo; s[i][k][0 ] = (s[i - 1 ][k][0 ] + f[i][k][0 ]) % mo; s[i][k][1 ] = (s[i - 1 ][k][1 ] + f[i][k][1 ]) % mo; } cout << f[1 ][m][1 ] << endl; } return 0 ; }
题目大意：有两种操作方式，分别是给当前数加上一个数和给当前一个数乘以一个数（这里这个数字可能是小数，所以所有操作的结果都向上取整），每个操作方式都有一个可以执行的次数。初始状态是0。最终要求的是1~m中的每个数字，都是最少可以使用前几个操作方式组成（具体细节还挺复杂，题面有更详细的描述）。
解法：继续暴力，先说加法，观察加法我们发现实际上假如某一个数字之前已经被组成了，那么他接下来很多次操作实际上所组成的数字在模加数的一一下都是相同的，就可以使用这一性质对加法进行优化，使其达到Om的级别。再说乘法，假如当前我们某个数字x乘以现在操作的一个数字p，发现结果的数字y在之前的操作中已经被得到过了，那么y也一定会在这次操作中不断的乘以p，所以到这一步我们就可以直接退出循环，直到当前的数字是y时，再用y和p去乘，这样每个乘法操作也是Om级别的（因为所有m个数字，每个数字最多会被标记1次，而每个数字扫到一个已经被标记过的数字就会结束循环，总数是2m）。
应该还有dp的写法，但是一开始没往这里想，是从纯暴力改对的，显得代码比较长。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 #pragma GCC optimize("O3" ) #include <bits/stdc++.h> using namespace std;long long n, m, a, c, ans[400005 ], now[400005 ], ret[400005 ], mx = 0 ;long long b;int main () scanf ("%lld%lld" , &n, &m); memset (ans, -1 , sizeof 0 ] = 0 ; for (long long i = 1 ; i <= n; i++){ scanf ("%lld%lld%lld" , &a, &b, &c); double pro = b / 100000.0 ; long long bb = b / 100000 ; bb = bb * 100000 ; if (a == 1 ){ memset (ret, 0 , sizeof memset (now, 0 , sizeof for (long long j = 0 ; j <= m; j++) now[j] = (ans[j] != -1 ); long long prov; if (bb < b) prov = bb / 100000 + 1 ; else prov = bb / 100000 ; for (long long j = 0 ; j <= m; j++){ if (!now[j]){ if (ret[j % prov]) ans[j] = i; } else ret[j % prov]++; if (j - c * prov >= 0 ){ if (now[j - c * prov]) ret[j % prov]--; } } } else { memset (now, 0 , sizeof for (long long j = 0 ; j <= m; j++) now[j] = (ans[j] != -1 ); for (long long j = 1 ; j <= m; j++) if (now[j]){ long long cc = j * b; mx = max (mx, j); long long last = -1 ; for (long long k = 1 ; k <= c; k++){ long long pwp; long long ccc = cc / 100000 ; if (ccc * 100000 < cc) pwp = ccc + 1 ; else pwp = ccc; if (pwp > m) break ; if (last == pwp) break ; if (ans[pwp] != -1 ) break ; last = pwp; if (ans[pwp] == -1 ){ ans[pwp] = i; } cc = pwp * b; } } } } for (long long i = 1 ; i <= m; i++) printf ("%lld " , ans[i]); return 0 ; }
题目大意：朴素的交互题，有n个点，任两个点i,j之间通过有向边相连，但是我们不知道边的方向，现在题目一开始给定了每个点的入度，要求出可以互相到达的一对入度差最大的点。我们每次可以向程序询问一对点是否可以互相到达，如果程序回复我们可以到达，那么我们再也无法进行询问。
解法：首先，由于两点要可以互相到达，那么显然入度拉满的点或者出度拉满的点都不行。所以我们把所有这样的点都删掉（有的点会因为删掉了别的点之后变成当前图中入度拉满或者出度拉满的点，这个也是需要处理的），在删掉所有点之后，我们大胆猜测，如果从一个入度很大的点（意味着出度很小）都能到一个入度很小的点（出度很大），那么这两个点反过来应该会更容易到达，因为反过来就是从一个出度很大到一个入度很大的点，于是我们就这样贪心的求一下，发现它居然过了hhhh。
之后我看题解有的dalao好像都没有询问就得出了答案，但是我懒了一下没有看他们怎么做的orz太强啦！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #include <bits/stdc++.h> using namespace std;int n, a, num[505 ], up, cnt;pair<int , int > p[505 ]; pair<int , pair<int , int >> pp[505 *505 ]; char s[50 ];int main () cin >> n; for (int i = 1 ; i <= n; i++) cin >> a, p[i] = {a, i}, num[a]++; while (cnt <= up){ up += num[cnt], cnt++; } sort (p + 1 , p + 1 + n), cnt = 0 ; for (int i = 1 ; i <= n; i++) if (p[i].first > up){ for (int j = n; j > i; j--) if (p[j].first > up){ pp[++cnt] = {p[i].first - p[j].first, {p[j].second, p[i].second}}; } } sort (pp + 1 , pp + 1 + cnt); for (int i = 1 ; i <= cnt; i++){ cout << '?' << ' ' << pp[i].second.first << ' ' << pp[i].second.second << endl, cout.flush (); cin >> s; if (s[0 ] == 'Y' ){ cout << '!' << ' ' << pp[i].second.first << ' ' << pp[i].second.second << endl, cout.flush (); return 0 ; } } cout << "! 0 0" << endl, cout.flush (); return 0 ; }
题目大意：给一棵树，树上有些点有礼物，每次操作是选一个点，然后将这个点上的礼物任选数量转化到这个点的第k个祖先上。假如一个点没有第k个祖先或者这个点没有礼物，就不能选这个点。对于一个给定的根，两个人轮流操作是显然会有一个人必胜的，最后要求以每一个点为根的情况下谁必胜。
解法：首先观察题目，k不超过20，对于一个链，这就是一个阶梯模k意义下的阶梯nim游戏（阶梯nim游戏就是只考虑偶数台阶上的石子异或起来的结果），再将链扩展到树上，发现对于给定根的问题，也是满足阶梯nim游戏的特性的（以根到某个点的距离在模k意义下的情况来考虑），dp[x][i]表示x的所有儿子中距离x的距离%2k==i的点上的礼物的异或和。那么接下来我们所需要做的就是换根的时候怎么做。考虑到两个点x，y的转移，假如当前x是y的儿子，要将y的结果转化到x上，也就是x所在的整颗子树所有点距离根长度都-1，与此同时除了这棵子树之外所有的点长度都+1。再回到一开始我们阶梯nim要取偶数台阶，那就给长度%2k，这样k2k-1都是偶数台阶，0k-1都是奇数台阶，所以到最后我们只需要通过XOR的性质以及最开始dp的定义，在转移的时候消除一下影响就好了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include <bits/stdc++.h> using namespace std;int n, k, a[200005 ], b, c, dp[200005 ][40 ], ans[200005 ], pro[50 ];vector<int > tu[200005 ]; void dfs1 (int x, int y) dp[x][0 ] = a[x]; for (int i : tu[x]) if (i != y){ dfs1 (i, x); for (int j = 0 ; j < 2 * k; j++) dp[x][(j + 1 ) % (2 * k)] ^= dp[i][j]; } } void dfs2 (int x, int y) if (x != y) for (int i = 0 ; i < 2 * k; i++) dp[x][(i + 1 ) % (2 * k)] ^= pro[i]; int t = 0 ; for (int i = k; i < 2 * k; i++) t ^= dp[x][i]; ans[x] = (t != 0 ); for (int i : tu[x]) if (i != y){ for (int j = 0 ; j < 2 * k; j++) pro[j] = dp[x][j] ^ dp[i][(j - 1 + 2 * k) % (2 * k)]; dfs2 (i, x); } } int main () cin >> n >> k; for (int i = 1 ; i < n; i++) cin >> b >> c, tu[b].push_back (c), tu[c].push_back (b); for (int i = 1 ; i <= n; i++) cin >> a[i]; dfs1 (1 , 1 ), dfs2 (1 , 1 ); for (int i = 1 ; i <= n; i++) cout << ans[i] << ' ' ; return 0 ; }
总结 感觉前4道题都挺暴力的吧，可能由于个人做题比较少，E题和F题会比较令人耳目一新？F题是真的妙啊妙！