牛客周赛 Round 64(博弈论、思维、构造、LCA、换根DP)

牛客周赛 Round 64(博弈论、思维、构造、LCA、换根DP)

A. 小红的对错判断

根据题意判断即可。

#include<bits/stdc++.h>using namespace std;int main(){string s;cin >> s;string a = "YES", b = "yes";if(s.size() != 3) cout << "wrong answer" << endl;else{int flag = 0;for(int i = 0; i < 3; i++) flag += (a[i] == s[i] || b[i] == s[i]);if(flag == 3) cout << "accept" << endl;else cout << "wrong answer" << endl;}return 0;
}

B. 小红的幂表达

从大到小枚举底数，判断是否为整次幂。

#include<bits/stdc++.h>using namespace std;int main(){int n;cin >> n;cout << n << endl;for(int i = n; i >= 2; i--){int cnt = 0, x = n;while(1){if(x % i == 0) cnt++, x /= i;else break;}if(x == 1) cout << '=' << i << '^' << cnt << endl;}return 0;
}

C. 小红的前缀询问

维护每个元素出现的次数，边维护边统计其对答案的贡献。

#include<bits/stdc++.h>using namespace std;int main(){int n;cin >> n;map<int, int> v;long long res = 0;for(int i = 1; i <= n; i++){int x;cin >> x;res += v[x];v[x]++;cout << res << " ";}return 0;
}

D. 小红和小紫的博弈游戏（博弈论）

为了方便表示，把 2 * 2 的矩阵的四个元素定义为 1、2、3、4，如下图所示。

考虑一种情况：假设元素1 的值为 0。
这时，每次操作只能选择 (元素2，元素4) 或 (元素3，元素4)，最多的操作次数：
$X=min(value(元素2)+value(元素3)，value(元素4))$。
即，要么元素2和元素3拿完，剩下元素4；要么元素4 拿完，剩下元素2和元素3。
下面两个例子对应两个 ‘要么’ ：

例1：0 1 3 5
列2：0 6 8 3
分别对应四个元素的value

对于操作次数 X：

1. 当 X 为奇数时，先手必胜。（例2，操作3次）
2. 当 X 为偶数时，后手必胜。（例1，操作4次）

---

对于例1，给四个元素整体加 10，得到例3：

例3：10 11 13 15

这时，对于后手来说，肯定希望通过操作，使得==由’例3‘变为’例1‘==的情况。
是否可行呢？

---

显然可以，当先手选12时，后手选34；先手选13时，后手选24 …

每轮操作，后手都选先手没有操作的两个元素，即可实现使四个元素整体减一，直到出现==’例1’==，后手必胜。

综上，由特殊情况的后手必胜，得到了一般情况的后手必胜。

---

进一步思考，在上述情况的基础上，多一手操作，会怎么样？

显然，是先手必胜。

先手只需要第一步操作时，选择多出来的这一手操作，即可转化为 ‘先手’ 变 ’后手‘ 且出现 ’后手必胜的局面‘。

---

完。

---

code：

#include<bits/stdc++.h>using namespace std;int a[10];void rotate(){    // 逆时针旋转90°,看图int x = a[1];a[1] = a[2];a[2] = a[3];a[3] = a[4];a[4] = x;
}int main(){int ncase;cin >> ncase;while(ncase--){for(int i = 1; i <= 4; i++) cin >> a[i];int mn = a[1], mx = a[1];for(int i = 1; i <= 4; i++) mn = min(mn, a[i]);for(int i = 1; i <= 4; i++) a[i] -= mn;while(a[1] != 0) rotate();    // 让 0 在 1 的位置int cnt = min(a[4], a[2] + a[3]);if(cnt) cout << "kou" << endl;else cout << "yukari" << endl;}return 0;
}

E. 小红的字符串重排（思维、构造）

显然，出现最多的字符的个数 <= n / 2 时，有解。

一种排列思路：依次选择出现次数最多的字符与出现次数最少的字符换位置。

对于上述排列思路，会出现一个情况，如下：

a c c d d d e e e e

交换后，中间会剩下两个 d 还在原位，如何处理？

在剩下两个d时，此时交换操作的序列为：

a e
c e
c e
d e

取交换序列的前两次操作中的两个e与剩下的两个d 交换位置，结果为：

d d e e e e a c c d

证明这种方法一定可行：

• 在交换序列中，序列的长度等于“出现最多的字符的个数”。故而，可用作上述操作的字符的个数 = “出现最多的字符的个数”
• 出现次数最多的元素 <= n / 2，中间剩下的元素一定不是出现次数最多的字符。故而，中间剩下的元素的个数 <= “出现次数最多的元素”
• 综上，中间剩下的元素的个数<= 序列的长度 = 可用作交换的元素个数

#include<bits/stdc++.h>using namespace std;vector<int> v[30];
pair<int, int> a[30];
queue<pair<int, int> > qu; // 交换序列int main(){string s;cin >> s;int n = s.size();for(int i = 0; i < n; i++) v[s[i] - 'a'].push_back(i);for(int i = 0; i < 26; i++) a[i].first = v[i].size(), a[i].second = i;sort(a, a+26);if(a[25].first > n / 2) cout << -1 << endl;else{int i = 0, j = 25, x = 0, y = 0;while(i <= j){if(i != j){while(x < v[a[i].second].size() && y < v[a[j].second].size()){qu.push({v[a[i].second][x], v[a[j].second][y]}); // 少的放在前 x++;y++;}if(x == v[a[i].second].size()) i++, x = 0;if(y == v[a[j].second].size()) j--, y = 0;}else{for(int z = max(x, y); z < a[i].first; z++){pair<int, int> p = qu.front();qu.pop();qu.push(p);	qu.push({p.first, v[a[i].second][z]});}i++;}}int flag = 1;while(!qu.empty()){pair<int, int> p = qu.front();qu.pop();swap(s[p.first], s[p.second]);if(s[p.first] == s[p.second]) flag = 0;}if(flag) cout << s << endl;else cout << -1 << endl;}return 0;
}

F&G. 小红的树上路径查询（LCA、换根DP）

结论1：在无向图中，对于一个任意一个点 x，到路径(u，v)的距离为：$(dist(u,x)+dist(v,x)-dist(u,v))/2$，其中 $dist(u,v)$ 表示点u 到点v 的距离。

结论2：在树上，$dist(u,v)=deep(u)+deep(v)-deep(LCA(u,v))\ast 2$，其中 $deep(x)$ 表示x的深度，$LCA(u,v)$ 表示 u 和 v的最近公共祖先。

---

结论1证明：如下图，对于x到路径(u，v) 有两种情况$x_1$和 $x_2$，通过黑线和蓝线的关系，可得到$x_1$和$x_2$ 满足结论1。

结论2证明：如下图，通过黑线和蓝线的关系，结论2得证。

---

推广结论1，一个无向图G中，n个点到路径(u，v)的距离$X=\sum (dist(u,x)+dist(v,x)-dist(u,v))/2，x\in 图G的点集$

化简上述公式，$X=(\sum dist(u,x)+\sum dist(v,x)-n\ast dist(u,v))/2，x\in 图G的点集$。

对于任一点u，预处理 $\sum dist(u,x)，x\in 图G的点集$，即所有点到点 u 的距离和。即可快速求出 X。($dist(u,v)$ 通过结论2 可以方便求出)

---

设$DP(u)$ = $\sum dist(u,x)$，现在考虑$DP(u)$ 如何维护，如下左图：

可以把点分为两类，一类为 u 为根的子树内的点，一类为 u 为根的子树外的点。

• 对于 u为根的子树内的点，设 $sum(u)$ 表示子树内的点到 u 的距离和
  • 对于叶子节点， $sum(u)=0$
  • 对于非叶子节点，$sum(u)=\sum (sum(x)+sz(x))，x\in u的son$
  • 对于 u 的孩子结点x，以 x为根的子树，通过边$(x,u)$ 到点 u，共有$sz(x)$个点需要走这条边。
• 对于 u 为根的子树外的点，设$dp(u)$ 表示子树外的点到 u 的距离和
  • 显然，dp(1) = 0，根节点没有子树外的结点。
  • 考虑换根，如何通过 fu 到 u，需要考虑两类点，如下右图。
    • 对于第 1 部分的点，需要通过边 (fu, u) 到点u，共有 sz(1) - sz(fu) 个点需要走这条边。
      故而，第一部分点的贡献为：$dp(fu)+sz(1)-sz(fu)$
    • 对于第 2 部分的点，需要通过边 (fu, u) 到点u，共有 sz(fu) - sz(u) 个点需要走这条边。
      故而，第二部分点的贡献为：$sum(fu)-sum(u)+sz(fu)-sz(u)$
  • 综上，$dp(u)=dp(fu)+sz(1)-sz(fu)+sum(fu)-sum(u)+sz(fu)-sz(u)$
• 综上，$DP(u)=sum(u)+dp(u)$
  

#include<bits/stdc++.h>
#define ll long long
using namespace std;const int maxn = 1e5 + 5;vector<int> mp[maxn];ll sz[maxn], sum[maxn]; // sz[x] = 以 X 为根的子树的大小；sum[x] = 以 x 为根的子树中，子树内的点到 x 的距离和 
ll deep[maxn], f[maxn][20]; // dis[x] 表示根结点 x 的深度, f[x][i] 表示 x 向上 2^i 个祖先 
void dfs(int fa, int u){deep[u] = deep[fa] + 1;f[u][0] = fa;for(int i = 1; i < 20; i++) f[u][i] = f[f[u][i-1]][i-1]; 	sz[u] = 1;for(auto v : mp[u]){if(v == fa) continue;dfs(u, v);sz[u] += sz[v];sum[u] += sum[v] + sz[v];}
}ll dp[maxn];	// 注意数据范围，int不行
void dfs2(int fa, int u){for(auto v : mp[u]){if(v == fa) continue;dp[v] = dp[u] + sz[1] - sz[v] + sum[u] - sum[v] - sz[v];	// 转移dp，维护子树外的点的贡献dfs2(u, v);}dp[u] += sum[u]; // 加上子树内的点的贡献
}// lca
int lca(int u, int v){if(deep[u] < deep[v]) swap(u, v);int d = deep[u] - deep[v];for(int i = 0; (1<<i) <= d; i++) if((1<<i) & d) u = f[u][i];if(u == v) return u;for(int i = 19; i >= 0; i--){if(f[u][i] != f[v][i]){u = f[u][i];v = f[v][i];}}return f[u][0];
}// 得到 u 到 v 的距离 
ll get_dist(int u, int v){return deep[u] + deep[v] - deep[lca(u, v)] * 2;
}int main(){int n, q;cin >> n >> q;int u, v; for(int i = 1; i < n; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}dfs(0, 1);dfs2(0, 1); while(q--){cin >> u >> v;ll res = (dp[u] +  + dp[v] - 1ll * get_dist(u, v) * n) / 2;cout << res << endl;}return 0;
}