2022CCPC绵阳站VP题解报告(CGHMAE六题)

2022CCPC绵阳站VP题解报告

前言

• 队伍VP赛时 CGHME 五题，赛后A题。
• 赛时个人出了CHE，赛后补3题GMA。
• 题解按赛场过题人数排序。

Problem - C （签到思维）

注意到每次每个点的蝴蝶所在点的深度都会减少1，所以只需要在 1 号节点的所有孩子节点操作即可，答案就是1号节点的所有孩子的高度之和。

ac代码参考：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5 + 5, M = 2e5 + 5;int n, tot;
int head[N], ver[M], nxt[M], dep[N];inline void add(int x, int y){ver[++tot] = y; nxt[tot] = head[x]; head[x] = tot;
}void dfs(int x, int fa = 0){dep[x] = 1;for(int i = head[x]; i; i = nxt[i]){int y = ver[i];if(y == fa) continue;dfs(y, x);dep[x] = max(dep[x], dep[y] + 1);}
}void solve(){tot = 1;cin >> n;for(int i = 1; i < n; i++){int x, y;cin >> x >> y;add(x, y);add(y, x);}dfs(1);int ans = 0;for(int i = head[1]; i; i = nxt[i]){ans += dep[ver[i]];}cout << ans << '\n';
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);solve();return 0;
}

H (codeforces.com) （签到构造）

注意到 $k\le 100$，所以我们完全可以铺开来，只考虑单元每轮死亡到少个不必考虑复活的事，所以延对角线输出$2k$ 个点即可。

ac代码参考：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;void solve(){int k; cin >> k;cout << k * 2 << '\n';for(int i = 1; i <= 2 * k; i++){cout << i << ' ' << i << '\n';}
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);solve();return 0;
}

Problem - G （签到思维）

考虑相邻的两个数，其中较小的数一定无法存活至下一轮。因此每 一轮至少有一半(向下取整)的数字被删除，暴力模拟即可。

ac代码参考：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n,x;cin>>n;vector<int> a;for(int i=1;i<=n;i++) cin>>x,a.push_back(x);vector<int> b;int ans=0;while(a.size()!=1){b.clear();for(int i=0;i<a.size();i++){if(i==0){if(a[i]>a[i+1]) b.push_back(a[i]);}else if(i==a.size()-1){if(a[i]>a[i-1]) b.push_back(a[i]);}else{if(a[i]>a[i+1]&&a[i]>a[i-1]) b.push_back(a[i]);}}a=b;ans++;}cout<<ans<<'\n';
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);solve();return 0;
}

Problem - M （栈）

注意到如果一段相同的字符 $X$ 的左右两端点相邻 $Y$， 且 $Y$ 能赢 $X$，则将这一段 $X$ 全部换成 $Y$ 不会影响答案。同理，如果 $X$ 块位于序列的一端，且另一边与 $Y$ 相邻。则也可以将这一段 $X$ 全部换成 $Y$ 不会影响答案。那么，我们就可以用一个栈来不断维护并更新 $RPS$ 序列,时间复杂度 $O(|s|)$。

ac代码参考：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;void solve(){string s;cin >> s;stack<char> st;st.push(s[0]);for(int i = 1; i < s.length(); i++){while(!st.empty()){char pre = st.top();if(s[i] == 'R')if(pre == 'P') break;else if(s[i] == 'P')if(pre == 'S') break;else if(s[i] == 'S')if(pre == 'R') break;st.pop();}st.push(s[i]);}while(st.size() > 1) st.pop();cout<< st.top() <<'\n';
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T;cin >> T;while(T--) solve();return 0;
}

Problem - A （记忆化搜索）

注意到选取或禁用英雄时，一定会选择己方和对方剩余英雄中价值最大的。当某方选到 $k$ 个英雄后，它不会再做“选取英雄”操作，而是 尽可能地去做“禁用英雄”操作。所以双方轮流操作时能到达的”状态数”只有$O(n{k}^2)$个。

我们用 $dp(x,i,j)$ 表示当前双方总共操作 $x$ 轮，分别已经选取了 $i,j$ 个英雄时的答案。然后记忆化搜索即可。

ac代码参考：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 2e5 + 5;int n, m, a[N], b[N], f[N][11][11];
bool vis[N][11][11];int dfs (int x, int ca, int cb) {if (x >= 2 * n) return 0;if (vis[x][ca][cb])   return f[x][ca][cb];vis[x][ca][cb] = true;int aa = x / 2 - cb + ca + 1, bb = (x + 1) / 2 - ca + cb + 1, &t = f[x][ca][cb];t = dfs (x + 1, ca, cb); //不选if (x % 2 == 0) { //Aif (aa <= n && ca < m)  t = max (t, dfs (x + 1, ca + 1, cb) + a[aa]);}   else { //Bif (bb <= n && cb < m)  t = min (t, dfs (x + 1, ca, cb + 1) - b[bb]);}return t;
}void solve(){cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) cin >> b[i];sort (a + 1, a + n + 1, greater<int>());sort (b + 1, b + n + 1, greater<int>());cout << dfs (0, 0, 0) << '\n';
}int main () {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);solve();
}

Problem - E (图论上的DP，根号分治优化)

​ 对于这个问题，其实我们不必管 $a_i$，我们只要求出点权为 $1$ 转移的最小代价最后乘以权值即可，这么转换后我们不难想到一个暴力的 $DP$ 做法，令 $f(i,j)$ 表示第 $j$ 号点，在第 $i$ 天后的所有操作中所需的最小代价。那么转移就明显了，第 $i$ 天需要转移 $b_i$，那么 f ( i , b i ) = min ⁡ ( b i , y ) ∈ e d g e { w ( b i , y ) + f ( i + 1 , y ) } f(i,b_i) = \min_{(b_i,y)\in edge}\{w(b_i,y) + f(i + 1, y)\} f(i,bi​)=min(bi​,y)∈edge​{w(bi​,y)+f(i+1,y)} 其中 $w(x,y)$ 为边权。

​ 但是，像上述 $DP$ 解法，时间和空间上都会超出限制，我们考虑怎么优化。由于每一天我们只会更新某一个 $j$ 的值，所以我们可以直接省略 $f$ 的第一维。此外，状态的转移是图的邻域问题，我们可以考虑一个常用的套路：根号分治。我们选取一个阈值 $B$，对所有的点按度数的大小分为两类：

• 对于度数小于 $B$ 的点 $j$，我们只需要枚举来更新 $f(j)$ 的的值。
• 对于度数大于 $B$ 的点 $j$，我们考虑维护一个 $multiset$，对所有连向 $j$ 的边 $(x,j)$，将 $f(x)+w(x,j)$ 放入集合。每次我们只需要从集合中取出最小值更新 $f(j)$，再枚举所有连接的度数大于 $B$ 的点，更新多重集即可。

对于度数小于 $B$ 的点，我们转移的复杂度是 $O(B)$ 的，对于度数大于 $B$ 的点最多有 $\frac{2m}{B}$ 个，每次转移的复杂度是 $O(\frac{m}{B}\log n)$ 的。当 $B=\sqrt{2m\log n}$ 时，总的复杂度为 $O(q\sqrt{m\log n})$。

ac代码参考：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int N = 1e5 + 5, M = 2e5 + 5;
const int mod = 998244353;int n, m, q, tot, tb;
ll a[N], b[N], f[N], deg[N], edge[M], eb[M];
int head[N], ver[M], nxt[M];
int hb[N], vb[M], nb[M];
multiset<ll> se[N];inline void add(int x, int y, ll z){ver[++tot] = y; edge[tot] = z;nxt[tot] = head[x]; head[x] = tot;
}
inline void addb(int x, int y, ll z){vb[++tb] = y; eb[tb] = z;nb[tb] = hb[x]; hb[x] = tb;
}void solve(){tot = tb = 1;cin >> n >> m >> q;int SQ = sqrt(2ll * m * log2(n));for(int i = 1; i <= n; i ++) cin >> a[i];for(int i = 1; i <= m; i++){int x, y, z;cin >> x >> y >> z;add(x, y, z); add(y, x, z);deg[x] ++; deg[y] ++;}for(int x = 1; x <= n; x++) if(deg[x] > SQ)for(int i = head[x]; i; i = nxt[i]){int y = ver[i], z = edge[i];se[x].insert(z + f[y]);if(deg[y] > SQ) addb(y, x, z);}for(int i = 1; i <= q; i ++) cin >> b[i];for(int j = q; j; j--){int x = b[j];if(deg[x] <= SQ){ll cost = 1e18;for(int i = head[x]; i; i = nxt[i])cost = min(cost, edge[i] + f[ver[i]]);for(int i = head[x]; i; i = nxt[i]){int y = ver[i], z = edge[i];if(deg[ver[i]] > SQ){se[y].erase(se[y].find(z + f[x]));se[y].insert(cost + z);}}f[x] = cost;}else {for(int i = hb[x]; i; i = nb[i])se[vb[i]].erase(se[vb[i]].find(f[x] + eb[i]));f[x] = *se[x].begin();for(int i = hb[x]; i; i = nb[i])se[vb[i]].insert(f[x] + eb[i]);}}ll ans = 0;for(int i = 1; i <= n; i++){ans = (ans + f[i] * a[i]) % mod;}cout << ans << '\n';
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);solve();return 0;
}