Loading... （结果最后还是补了E题 # A. Prof. Slim ## 题意 给定一个数列，可以任意交换两个数的符号，求是否能得到递增序列。 ## 做法 显然把符号全部放到最左边然后判断即可。 代码略。 # B. Dorms War ## 题意 给定一个字符串和一个字符表$\mathbb C$，每时刻**所有**在$\mathbb C$中的字符都会吞噬它左侧相邻的字符（如果没有则不吞噬）。求最多能够执行多少次操作。 ## 分析 考虑每个特殊字符$c_i$和左侧最近特殊字符$c_j$的距离$dis$，拿这个去维护$ans$： * 如果它小于$ans$显然无事发生，这是因为当它吞噬到$c_j$时等价于替代了$c_j$； * 如果它大于$ans$，那么拿这个去更新答案即可。 ## 代码 ```cpp int t; int main() { cin >> t; while (t--) { int n, m; string str; set<char> spe; spe.clear(); cin >> n >> str >> m; FOR(i, 1, m) { char ch; cin >> ch; spe.insert(ch); } int ans = 0, last = 0; FOR(i, 0, n - 1) if (spe.find(str[i]) != spe.end()) { int dis = i - last; if (dis > ans) ans = dis; last = i; } cout << ans << endl; } return 0; } ``` # C. Where is the Pizza? ## 题意 给定$n$的两个全排列$A$，$B$，同时给出序列$C$使得$c_i=a_i$或$c_i=b_i$。同时$C$的某些位置已经被标明了数字。求有多少种使得$C$也是$n$的全排列的合法方案。 ## 分析 考虑$A$、$B$组成的一个二部图。相同数字所在位置会连边。那么我们跑dfs遍历所有连通块，对于每个**所有位置都没被标明过数字**的连通块，它显然有两种放置数字的方式。乘法原理记录结果即可。 ## 代码 ```cpp int t; #define N 100005 #define M 1000000007 int a[N], b[N], c[N], pa[N], pb[N]; bool vis[N]; ll fac[N]; int n; bool dfs(int p) { vis[p] = true; bool ans = true; if (c[p]) ans = false; if (!vis[pb[a[p]]]) ans &= dfs(pb[a[p]]); if (!vis[pa[b[p]]]) ans &= dfs(pa[b[p]]); return ans; } int main() { fac[0] = 1; FOR(i, 1, 100000) fac[i] = fac[i - 1] * 2 % M; cin.sync_with_stdio(0); cin.tie(nullptr); cin >> t; while (t--) { int n; cin >> n; FOR(i, 1, n) { cin >> a[i]; pa[a[i]] = i; } FOR(i, 1, n) { cin >> b[i]; pb[b[i]] = i; } FOR(i, 1, n) { cin >> c[i]; if (a[i] == b[i]) c[i] = a[i]; vis[i] = false; } ll ans = 0; FOR(i, 1, n) if (!vis[i] && dfs(i)) ans++; cout << fac[ans] << endl; } return 0; } ``` # D. Very Suspicious ## 题意 给一个正六边形密铺的蜂窝图，可以画$n$条无限长的对角线，求问最多能得到多少个正三角形？ ## 分析 只能说这个题在思考思路上需要一点灵感。相比于考虑哪些格子会被如何分割，不如考虑线之间的相交关系： 容易发现只可能有三种角度的直线，分别称为$a$，$b$，$c$。由于直线是无限长的，所以每条直线和其他所有类型直线都会相交，而每两条直线相交的交点，都会产生**两个三角形**。如果三条直线交于一点，我们会发现这个规律也满足。 那么答案很明显就是$2(ab+bc+ac)$。预处理即可。 ## 代码 ```cpp #define N 1000000 ll ans[N]; int main() { ll a = 1, b = 0, c = 0; for (int i = 2; ans[i] < 1000000000; i++) { if (i % 3 == 1) a++; else if (i % 3 == 2) b++; else c++; ans[i] = 2 * (a * b + b * c + a * c); } int t; cin >> t; while (t--) { int n; cin >> n; cout<<lower_bound(ans, ans + N, n) - ans<<endl; } return 0; } ``` # E. Hemose on the Tree 食言了，还是决定补一下这个题。 ## 题意 给定$2^p$个点和$2^p-1$条边，构成一棵树。现在需要把$[1,2^{(p+1)}-1]$这些数字分配给所有点和边，然后选定根节点$root$，要求从根节点出发，结束于任意点或者边的所有路径的异或和的最大值最小。求一种具体方案。 ## 分析 涉及到异或肯定要考虑异或的性质。注意到给定数字构成了$000...001$到$111...111$的一个全排列，当我们取出$2^p$即$100...000$之后，剩下的数字就能两两配对：$x$和$2^p+x$，那么这两个数和$2^p$异或起来结果恰好是$0$，这样我们非常容易构造一个最大值为$2^p$的方案： 只要任选一个根节点，把$2^p$放在根节点上，然后进行dfs，对于每个当前节点和所有出边： * 如果到当前节点为路径和为$2^p$，那么在边上放$2^p+x$，在这条边连到的点上放$x$； * 否则在边上放$x$，在这条边连到的点上放$2^p+x$。 容易证明这样做中途任意位置异或和都不会超过$2^p$，并且每组“边-点”都可以被消掉——任意时刻到任意被访问过的点处，路径总和要么是$2^p$，要么是$0$。 那么结果有没有可能存在更小的结果呢？答案是否定的。 因为如果更小的答案存在，那么意味着它最高位是$0$，我们令他为$x$，同样可以找到$2^p+x$和它配对。考虑这两数之间的路径： * 如果路径上异或和为$0$，那么当$x$和$2^p+x$异或起来将会得到$2^p$，矛盾； * 如果路径上异或和不为$0$，那么记这个数字为$y$，从而经过$2^p+x$时我们将会得到$2^p\otimes y$。我们要让它小于$2^p$，由于这是独立的一位，就意味着前面的路径异或和$y$就必须包含$2^p$也就是$y>2^p$，矛盾。 由此得证，答案就是$2^p$。 ## 代码 ```cpp #include <bits/stdc++.h> using namespace std; #define mp(x, y) make_pair(x, y) #define pb(x) push_back(x) #define FOR(x, y, z) for (int x = y; x <= z; x++) #define endl '\n' #define umax(x, y) x = max(x, y) #define umin(x, y) x = min(x, y) typedef long long ll; typedef pair<int, int> pii; int t, p; #define N 300005 int vp[N], ve[N]; // value of point, value of edge vector<pii> nxt[N]; // fi:next node, se:no of edge int use; void dfs(int now, int fa, bool sum) { for (auto v : nxt[now]) { int ed = v.second; int ver = v.first; if (ver == fa) continue; ++use; if (sum) { ve[ed] = (1 << p) + use; vp[ver] = use; dfs(ver, now, false); } else { ve[ed] = use; vp[ver] = (1 << p) + use; dfs(ver, now, true); } } } int main() { cin >> t; while (t--) { cin >> p; int n = 1 << p; FOR(i, 1, n) nxt[i].clear(); FOR(i, 1, n - 1) { int x, y; cin >> x >> y; nxt[x].emplace_back(y, i); nxt[y].emplace_back(x, i); } cout << 1 << endl; use = 0; vp[1] = 1 << p; dfs(1, -1, true); FOR(i, 1, n) cout << vp[i] << ' '; cout << endl; FOR(i, 1, n - 1) cout << ve[i] << ' '; cout << endl; } return 0; } ``` © 允许规范转载 打赏 赞赏作者 赞 如果觉得我的文章对你有用，请随意赞赏