2022CCPC绵阳站VP题解报告

前言

• 队伍VP赛时 CGHME 五题。
• 赛时个人出了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) { //A
        if (aa <= n && ca < m)  t = max (t, dfs (x + 1, ca + 1, cb) + a[aa]);
    }   
    else { //B
        if (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;
}