本文最后编辑于
题目大意：A就不写题意了。
解法：分票，down全给一台，剩下的全给一台，所以答案就是n-down的数量。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include <bits/stdc++.h> using namespace std;int T, n, a[55 ], n1, n2;int main () cin >> T; while (T--){ cin >> n, n1 = n2 = 0 ; for (int i = 1 ; i <= n; i++){ cin >> a[i]; if (a[i] == 1 ) n1++; if (a[i] == 2 ) n2++; if (a[i] == 3 ) n1++; } cout << n1 << endl; } return 0 ; }
题目大意：B还挺好玩，构造两个数，第一个数a位，第二个数b位，他们的gcd是c位。
解法：有很多种构造方法，我用的是三个数2,3,5；用2的次幂来构造gcd，用gcd×3的次幂构造第一个数，gcd×5的次幂来构造第二个数。
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 #include <bits/stdc++.h> using namespace std;int T, a, b, c;int cal (long long x) int ret = 0 ; while (x) ret += 1 , x /= 10 ; return ret; } int main () cin >> T; while (T--){ cin >> a >> b >> c; long long base = 5 , n, m; while (cal (base) < c) base *= 5 ; n = m = base; while (cal (n) < a) n *= 2 ; while (cal (m) < b) m *= 3 ; cout << n << ' ' << m << endl; } return 0 ; }
题目大意：有一堆牌，牌的种类最多50种，每次操作抽出某种牌最靠近牌堆顶的一张，输出这张是从顶往下数第几张，然后把这张牌放在牌堆顶。
解法：由于种类很少，所以直接模拟就ok，只要处理某一个种类的牌第一次抽是第几张就好了，剩下的情况因为种类过少所以一定存在某一种类会抽很多次，当某一种类被抽过一次之后他就一直在顶上那个范围了，所以硬爆其实也没多少。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;int n, q, x, num;int a[300005 ], color[105 ], st[105 ], v[105 ];int main () for (int i = 0 ; i <= 100 ; i ++) color[i] = 1e9 ; cin >> n >> q; for (int i = 1 ; i <= n; i ++) cin >> a[i], color[a[i]] = min (color[a[i]], i), st[a[i]] = color[a[i]]; for (int i = 1 ; i <= q; i ++){ cin >> x; if (!v[x]){ num = 0 , v[x] = 1 ; for (int j = 1 ; j <= 50 ; j++) if (v[j] && st[j] > st[x]) num++; color[x] += num; } for (int j = 1 ; j <= 50 ; j++) if (j != x && v[j] && color[j] < color[x]) color[j]++; cout << color[x] << ' ' , color[x] = 1 ; } return 0 ; }
题目大意：D题需要构造一个代价最小的序列，一个序列的代价是满足如下条件：(si=sj且si+1=sj+1且i!=j)的(i,j)点对数。
解法：由于题意要求，有影响的只跟相邻两字母组成的二元组出现次数有关，手玩一下字符集比较小的情况，发现这样的二元组共有n×n种，而且这n×n个二元组可以不产生代价的出现在同一个序列中，比如字符集为3的情况，可以构造aabacbbc，这样是最优的情况，而最优序列显然是这样的一个序列重复出现。得到这样的猜测之后直接写个暴力dfs搜一下，发现所有的字符集都可以这样搜出来，那么我们这个做法就没有任何问题了。直接搜一个最优串，让这个串不停地重复出现就得到了答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <bits/stdc++.h> using namespace std;int n, k, num[30 ], a[200005 ], w[200005 ], mx, fl;bool vis[30 ][30 ];void dfs (int x, int y) if (fl) return ; w[y] = x; if (y == k * k){ fl = 1 ; return ; } for (int i = 0 ; i < k; i++) if (!vis[x][i] && !fl) vis[x][i] = 1 , dfs (i, y + 1 ), vis[x][i] = 0 ; } int main () cin >> n >> k; dfs (0 , 0 ); for (int i = 1 ; i <= n; i++) cout << (char )('a' + w[i % (k * k)]); return 0 ; }
题目大意：一张图n行m列，有w个白色格子和n*m-w个黑色格子，黑色格子无法操作，白色格子可以涂成蓝色或者红色，然后如果有两个蓝色的格子竖着放在一起，那么他们两个上就可以放一个2×1的钻石，如果两个红色的格子横着放在一起，他们两个上边就可以放一个1×2的钻石，最后问所有的红蓝染色方案中，每个方案都按最大的放钻石方案放钻石，能放的钻石和是多少(任意方案都是最优的放置数量，要求的是所有方案的放置数量之和)。
解法：观察题面，可以将问题从 每个方案的数量和 转化为 求每个钻石所存在的方案数，然后找到所有能放的钻石，把每个钻石的方案数加起来。有了这个之后下来就解决最优放置的问题，实际上只要对于一排(或者一列)连续的白色格子，我们在这一排(或者一列)通过染色放置的钻石是最优的情况，那么剩下的点染什么色放什么钻石是剩下的点要考虑的事情，而每一种染色方案都一定可以得到一个对于那个方案的最优解，那样的解是无法影响我当前这连续的一排(或一列)格子的放置方案，所以这个题目就又被拆分成如下情况：当前有一排(或一列)连续的白色格子共k个，那么这k个格子对答案产生的贡献就是cal(k)*(2^(w-k))，我们只要分行和列分别讨论就可以得到结果。
接下来来解决这个cal(k)，这个东西咋整呢？因为k值和cal(k)是一一对应的，就可以把他当成一个数列，目测他是一个很有规律的东西，可以直接爆它的前几项，然后去OEIS一下，我们就得到这样一个数列：a(n) = ((3*n+1)*2^n - (-1)^n)/9 ，然后就可以做啦！
不过OEIS实际上还是有点偏移我们之前分析出来的情况，如果从头开始重新考虑，对于连续的k个白色方块，我们可以放置钻石的位置实际上只有k-1个，而我在最后k的位置上放置钻石的方案数实际上是只跟1k-2这些格子合法放置有关的，而之前在放置1k-2这么多个格子的钻石的时候，我们是算过一部分和当前这两个格子有关的方案数的，于是dp[k]=dp[k-2]+(2^(w-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 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 #include <bits/stdc++.h> #define mo 998244353 using namespace std;long long a[300005 ], ans, inv9, num;int n, m;string s[300005 ]; long long qpow (long long x, long long y) long long ret = 1 ; while (y){ if (y & 1 ) ret *= x, ret %= mo; x *= x, x %= mo, y >>= 1 ; } return ret; } int main () inv9 = qpow (9 , mo - 2 ); for (long long i = 1 ; i <= 300000 ; i++){ a[i] = (((3 * i + 1 ) * qpow (2LL , i) % mo - qpow (-1LL , i) + mo) % mo * inv9 % mo); a[i] = (a[i] + mo) % mo; } cin >> n >> m; for (int i = 1 ; i <= n; i++) cin >> s[i]; for (int i = 1 ; i <= n; i++) for (int j = 0 ; j < m; j++) num += s[i][j] == 'o' ; for (int i = 1 ; i <= n; i++){ int pro = 0 ; for (int j = 0 ; j < m; j++){ if (s[i][j] == 'o' ) pro++; if (s[i][j] == '*' || j == m - 1 ){ if (pro){ ans += a[pro - 1 ] * qpow (2 , num - pro) % mo, ans %= mo; } pro = 0 ; } } } for (int j = 0 ; j < m; j++){ int pro = 0 ; for (int i = 1 ; i <= n; i++){ if (s[i][j] == 'o' ) pro++; if (s[i][j] == '*' || i == n){ if (pro){ ans += a[pro - 1 ] * qpow (2 , num - pro) % mo, ans %= mo; } pro = 0 ; } } } cout << ans << endl; return 0 ; }
题目大意：给了一个字典，有几个串，最后要使用这给出的几个串拼一个长为m的串，这样一个串具有以下三个属性(s，X，Y)，其中s是长为m的字符串，然后将这个长为m的串使用两种方式划分开，每一种方式划分出来的子串都要是字典中存在的串，第一种划分方式成为X，第二种划分方式成为Y。如果说两个串的三个属性中有任何一个不同，那么就说这两个串是不同的，最终要求出的是所有不同的串的数量。
解法：首先提一下，一张图的邻接矩阵自乘k步之后，i行j列表示的数就是从i点经过k步走到j点的方案数。
通过这样的性质，我们重新回来看这道题目，一个字符串具有三个属性，s，X，Y，第一个属性最好处理，只要字符不一样就好了，接下来我们来处理剩下的两个属性。我们将每一个不同的字符串都当做一个点，比如说字符串这三个aa，aaa，aab，现在我们将其看做三个点，当某一个串可以组成另一个串时，就在他们之间连一条边，比如点aa向点aaa连边，点aa向点aab连边，但是aaa显然不能组成aab，所以点aab和aaa之间是没有边的；而空字符串要向所有的单个字母构成的字符串连边。在我们将整个字符串问题转化为图的问题之后，就可以通过矩阵自乘来得到相应长度的方案。之后我们再回来看这个题目的两个属性，显然最后字符串结束的时候，也就是字符串的后缀一定是某一个字典串，故而我们可以通过字典树也就是trie树来简化图中的点的情况，我们只需要有用的字符串(因为如果我们构造出了某一个无法被字典树识别的子串，那么显然这个串也无法构成字典里的任何一个串或者被字典里的串构成)。如果我们只看属性X，那么用字典树中的ncnt个节点建图，将空字符串作为root点，且只给字典串中的结尾部分赋值为1，那么这样一个图的邻接矩阵自乘m步之后，矩阵中root行root列就是长为m的串，所有的划分的方案数。如果再添加第二个属性Y，无非就是将这两个属性分开来算，当两个属性同时满足的时候才赋值1，否则赋值0，整张图的点数就是ncnt*ncnt(每一个为了解决X属性的串都要对应一个解决Y属性的串)。
其实前边说了很多都是为了解释为什么矩阵快速幂在字典树上跑的正确性，真正到这个题，就是看当前满足X属性的串x和满足Y属性的串y，这样的二元组(x，y)如何向下转移。为了满足s属性，我们枚举下一个字符d，而在x串后接字符d组成的新串我们设它为dx，同理，y对应的就是dy，假如dx和dy都是完整的字典串(意味着划分到这里就划了一下，下个字符开始就是新的一个字典串了)，那么可以直接向(root,root)也就是情况x串和y串可以通过下一个字符d转移到答案；同理假如dx是一个字典串，那么可以向(root,dy)转移(即x这里划分划了一下，但是Y没有划分开)；假如dy是一个字典串，那么可以向(dx,root)转移；当然也可以继续向下转移(dx,dy)，也就是在这里X和Y都没有划分。
在得到这样的初始矩阵之后只需要自乘m步最后输出root行root列的答案就好了。
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 61 62 #include <bits/stdc++.h> #define mo 998244353 using namespace std;int n, m, num[55 ], ch[55 ][55 ], ncnt, cnt, rt;map<pair<int , int >, int > tu; string s; struct Mat { int a[305 ][305 ]; }ans; Mat operator * (const Mat &x, const Mat &y){ Mat ret; memset (ret.a, 0 , sizeof for (int i = 1 ; i <= cnt; i++) for (int k = 1 ; k <= cnt; k++) for (int j = 1 ; j <= cnt; j++) ret.a[i][j] += 1ll * x.a[i][k] * y.a[k][j] % mo, ret.a[i][j] %= mo; return ret; } Mat qpow (Mat x, int y) { Mat ret; for (int i = 1 ; i <= cnt; i++) for (int j = 1 ; j <= cnt; j++) ret.a[i][j] = (i == j); while (y){ if (y & 1 ) ret = ret * x; x = x * x, y >>= 1 ; } return ret; } int dfs (int x, int y) if (tu[{x, y}]) return tu[{x, y}]; tu[{x, y}] = ++cnt; int pro = cnt; for (int i = 0 ; i < 26 ; i++) if (ch[x][i] && ch[y][i]){ int dx = ch[x][i], dy = ch[y][i]; ans.a[pro][dfs (0 , 0 )] += num[dx] * num[dy]; ans.a[pro][dfs (dx, 0 )] += num[dy]; ans.a[pro][dfs (0 , dy)] += num[dx]; ans.a[pro][dfs (dx, dy)] += 1 ; } return pro; } int main () cin >> n >> m; for (int i = 1 ; i <= n; i++){ cin >> s, rt = 0 ; for (auto j: s){ if (!ch[rt][j - 'a' ]) ch[rt][j - 'a' ] = ++ncnt; rt = ch[rt][j - 'a' ]; } ++num[rt]; } dfs (0 , 0 ), ans = qpow (ans, m), cout << ans.a[1 ][1 ] << endl; return 0 ; }
题目大意：nim游戏，n堆石子，每堆最多m个，q组询问，每次询问得到石子数目区间在[l,r]的石子堆共k堆，然后询问这k堆石子堆每堆石子数目都减去l的之后的k堆石子做nim游戏的答案，询问互相独立，当前做的操作不会影响别的询问(这里并没有按照原来的语言描述题面，换了数学意义等价的描述方式)。
解法：观察题面，发现每次实际上就是找一个区间，然后对区间的每一个数做差之后进行异或求异或和，那实际上通过O3优化，avx2指令集优化以及使用GUNC++17(64)，4e10的数据也会被优化的飞快，所以暴力就过了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #pragma GCC optimize("O3" ) #pragma GCC target("avx2" ) #include <bits/stdc++.h> using namespace std;int n, m, a[200005 ], ans, l, r, x, ii;int main () scanf ("%d%d" , &n, &m), a[n + 1 ] = 1 << 30 ; for (int i = 1 ; i <= n; ++i) scanf ("%d" , &a[i]); sort (a + 1 , a + n + 1 ), scanf ("%d" , &m); while (m--){ scanf ("%d%d" , &l, &r), x = l; r = upper_bound (a + 1 , a + n + 1 , r) - a; l = upper_bound (a + 1 , a + n + 1 , l) - a; for (ii = l; ii < r; ++ii) ans ^= a[ii] - x; putchar ("AB" [ans == 0 ]), ans = 0 ; } return 0 ; }
非暴力解(感谢队友RRRR_wys)：
按位拆开，每一位都是互相不影响的。f[i][k] 表示从i开始向后延申2^k长度的区间的答案，实际上每个位置异或的数字范围是[0,2^k-1]，然后考虑用f[i][k-1]和f[i+1<<k-1][k-1]合并答案的时候，相当于后边这个区间整体值加上2^(k-1)，其他的低位不变，所以只用考虑 k-1 位的贡献，询问也同样的方式考虑，就得到结果。
这里并没有写这个做法（跑
就没有代码了。
总结 现场被队友hack了，掉分了(气呼呼
个人对这场构造题(B，D)的评价还是比较高的，不过现场没有看F题，之后补题的时候感觉有点。。。套路了？G可能出题人都没想到4e10也能跑过吧，有点偏离主旨了。
不过怎么说呢？指令集优化也是算法！
总的来说相比上一场，代码量就会有一部分提升。还行吧。