比赛链接：
https://ac.nowcoder.com/acm/contest/10662/
C.Stone Game
题意：
有 \(a1\) 堆有 1 个石子的石堆，\(a2\) 堆有两个石子的石堆，\(a3\) 堆有三个石子的石堆。
合并两个石堆 \(x\) 和 \(y\)，花费 \((x mod 3) * (y mod 3)\) 的代价，合并后的石堆总数为两个石堆的总数，问合并所有石堆最少花费多少价值。
思路：
首先要将 1 和 2 的石堆互相合并，花费最少，剩余的 1 或 2 的石堆单独合并成一堆，然后剩余的石堆与 3 合并就不花费代价了。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
vector <LL> a(4);
for (int i = 1; i <= 3; i ++ )
cin >> a[i];
LL x = min(a[1], a[2]);
a[1] -= x, a[2] -= x, a[3] += x;
cout << 2 * x + a[1] / 3 * 3 + (a[1] % 3 == 2) + a[2] / 3 * 6 + (a[2] % 3 == 2) * 4;
return 0;
}
D. Fight against involution
题意：
已知 \(n\) 个人每个人写的论文字数的范围 \([L_i, R_i]\)，为了拿高分，每个人肯定都尽可能写的多，即都写 \(R_i\) 个字，但是为了减少内卷，同时自己的分数又不会低，问每个人最少写的字数的总和为多少？
每个人的分数为比人的总数减去比自己字数多的人的个数。
思路：
为了保证分数，同一个分数的人要写同一个字数，同时要尽可能少，但不能少于比自己字数少的人。
所以按照 \(R_i\) 进行排序，对同一个分数的 \(L_i\) 求 max，即答案。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL n;
cin >> n;
vector<pair<LL, LL>> a(n);
for (int i = 0; i < n; i ++ )
cin >> a[i].second >> a[i].first;
sort(a.begin(), a.end());
LL ans = 0, now = a[0].second, p = 0;
for (int i = 1; i < n; i ++ ){
if (a[i].first != a[i - 1].first){
ans += (i - p) * now;
p = i;
}
now = max(now, a[i].second);
}
ans += (n - p) * now;
cout << ans << "\n";
return 0;
}
G.Xor Transformation
题意：
有一个数 \(X\)，想将它变成 \(Y（Y < X）\)，每次可以选择一个数 \(A（0 <= A < X）\)，使得 \(X = X XOR A\)，构造一个方法使得 \(X\) 不超过 5 次变成 \(Y\)。
思路：
2 步，先将 \(X\) 二进制下变成全是 1，然后转成 \(Y\)。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
LL x, y;
cin >> x >> y;
LL t = x, k = 0;
for (LL i = 1; t; i *= 2, t >>= 1 ){
if (t % 2 == 0){
k += i;
}
}
vector <LL> a;
a.push_back(k);
a.push_back((x ^ k) ^ y);
cout << a.size() << "\n";
for (int i = 0; i < a.size(); i ++ )
cout << a[i] << " \n"[i == a.size() - 1];
return 0;
}
J. Tree Constructer
题意：
给定一棵树，要求给每个点赋值，当两个点的权值按位或之后为 \(2^60 - 1\) 时，它们之间会有一条边，给出一个方案。
思路：
如果现在有一条链 \(x - y - z\)，那么 \(x\) 和 \(y\) 要匹配（即按位或之后满足条件），\(y\) 和 \(z\) 要匹配，但是 \(x\) 和 \(z\) 不能匹配，可以联想到二分图染色。对第一个点染为 1，相邻点之间颜色不同。
染完之后整个图变成二分图，记为黑和白，可以让所有黑的点的权值的第 59 位为 0，其它都为 1，白的点第 59 位为 1，其它为 0。这样子就满足了集合内没有连边的要求。
对于每个黑色点，按顺序，将第 \(i\) 个黑色点的第 \(i\) 位变成 0（产生一个锁），与它相邻的所有白色点的对应位都为 1（对应的钥匙），这样子就满足了全部的条件。
再考虑极限的情况，菊花图，如果中间的点是白色，那么黑色点的数量就是 99，超过了 60 位，所以要求黑色点的数量要比白色点的数量小，染色完的时候判断一下，进行 \(swap\) 就行。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int n;
cin >> n;
vector<vector<int>> G(n + 1);
for (int i = 1; i < n; i ++ ){
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
vector<int> color[2];
function<void(int, int, int)> dfs = [&](int u, int fa, int c){
color[c].push_back(u);
for (auto v : G[u]){
if (v == fa) continue;
dfs(v, u, c ^ 1);
}
};
dfs(1, 0, 1);
if (color[0].size() > color[1].size()) swap(color[0], color[1]);
vector<LL> f(n + 1);
vector<int> id(n + 1);
for (int i = 0; i < color[0].size(); i ++ ){
int u = color[0][i];
f[u] = (1LL << 59) - 1 - (1LL << i);
id[u] = i;
}
for (int i = 0; i < color[1].size(); i ++ ){
int u = color[1][i];
f[u] = (1LL << 59);
for (auto v : G[u])
f[u] += (1LL << id[v]);
id[u] = i;
}
for (int i = 1; i <= n; i ++ )
cout << f[i] << " \n"[i == n];
return 0;
}
L. Bit Sequence
题意：
定义 \(f(x)\) 表示 \(x\) 二进制状态下 1 的数量。
现在已知 \(L\)，求满足 \(x \in [0, L]\)，且 \(\forall i \in [0, m − 1], f(x + i) mod 2 = a_i\) 的 \(x\) 的数量。
思路：
容易想到数位 \(dp\)，有三维可以直接想到，枚举到哪一位、1 的数量的奇偶性、是否有上限。
因为 \(m\) 最多不超过 100，100 最多是 7 位，所以对于后面 7 位可以保留求解。但是有进位的情况会发生，即枚举到 \(i\)，加上 \(m\) 就超过了 128，这种情况下，从第 8 位开始的 1 的数量就会对答案造成影响，所以这个数量的奇偶性也要记录。总共四维。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e3 + 10;
LL dp[N][2][2][2], L;
int m, a[N], num[N];
int calc(int sum, int limit, int cnt){
int ans = 0, up = (limit ? (L % 128) : 127);
for (int i = 0; i <= up; i ++ ){
int f = 1;
for (int j = 0; j < m && f; j ++ ){
if (i + j < 128) f = ((__builtin_parity(i + j) ^ sum) == a[j]);
else f = ((__builtin_parity(i + j) ^ sum ^ cnt) == a[j]);
}
ans += f;
}
return ans;
}
LL dfs(int pos, int sum, int limit, int cnt){
if (dp[pos][sum][limit][cnt] != -1) return dp[pos][sum][limit][cnt];
if (pos <= 7) return dp[pos][sum][limit][cnt] = calc(sum, limit, cnt);
LL ans = 0;
int up = (limit ? num[pos] : 1);
for (int i = 0; i <= up; i ++ )
ans += dfs(pos - 1, sum ^ i, limit && (i == up), i & (!cnt));
return dp[pos][sum][limit][cnt] = ans;
}
void solve(){
memset(dp, -1, sizeof dp);
cin >> m >> L;
for (int i = 0; i < m; i ++ )
cin >> a[i];
int len = 0;
LL t = L;
while(t){
num[ ++ len] = t & 1;
t >>= 1;
}
cout << dfs(len, 0, 1, 0) << "\n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int T;
cin >> T;
while(T -- ){
solve();
}
return 0;
}
M.Cook Pancakes!
题意：
\(n\) 个煎饼，正反两面都要煎，一个锅最多可以煎 \(k\) 个，问最少煎几次。
思路：
正反两面都要煎，总共 \(2 * n\) 个饼，所以答案是 \(\lceil \frac{2n}{k} \rceil\)。
特殊情况，\(n > k\) 时，至少煎两次，二者取个 max 即可。
代码：
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int n, k;
cin >> n >> k;
if (k > n) cout << 2;
else cout << (2 * n + k - 1) / k;
return 0;
}