A. Two Towers
题意：有两个积木塔，由红色/蓝色积木组成，你每次可以将一个塔的塔顶放到另一个塔上，问任意次操作后能否使得两座塔都是红蓝相间。
可以将一个塔全部转移到另一个塔上，那么操作相当于把“大塔”从中间分开两半。如果“大塔”中红红/蓝蓝的数量超过 \(1\)，则不可行，否则从那里分开即可。
By tourist
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, m;
cin >> n >> m;
string a;
string b;
cin >> a >> b;
reverse(b.begin(), b.end());
a += b;
int cnt = 0;
for (int i = 0; i < n + m - 1; i++) {
cnt += (a[i] == a[i + 1]);
}
cout << (cnt <= 1 ? "YES" : "NO") << '\n';
}
return 0;
}
B. Ideal Point
题意：数轴上有若干条线段，问能否删去若干条，使 \(x\) 成为被覆盖最多的点（严格最多）。
容易发现，只要有两个线段，一个左端点在 \(x\)，一个右端点在 \(x\)，那么只要保留这两条就行。如果不存在这种情况，一定不可行，因为要想 \(x\) 覆盖比 \(x+1\) 更多，就必然要存在一个线段右端点为 \(x\)；要想 \(x\) 覆盖比 \(x-1\) 更多，就必然要存在一个线段左端点为 \(x\)。
By tourist
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n, k;
cin >> n >> k;
vector<int> l(n), r(n);
for (int i = 0; i < n; i++) {
cin >> l[i] >> r[i];
}
bool L = false;
bool R = false;
for (int i = 0; i < n; i++) {
L |= (l[i] == k);
R |= (r[i] == k);
}
cout << (L && R ? "YES" : "NO") << '\n';
}
return 0;
}
C. Tea Tasting
题意：有 \(n\) 杯茶和 \(n\) 个人，第 \(i\) 杯茶有 \(a_i\) 单位的茶水，第 \(i\) 个人对每杯茶最多和 \(b_i\) 单位。初始第 \(i\) 个人站在第 \(i\) 杯茶前，每人喝一次，然后 \(n\) 个人往左平移一位（第一个人结束），继续重复上面步骤。问每个人最后分别喝到了多少茶。
我们可以从左到右扫每杯茶，看这杯茶对后面的人造成的贡献。首先可以预处理前缀和，二分查找这杯茶到第几个人被喝完，这样，这个人之前的人每人都能“喝饱”；最后一个人喝掉剩下的茶。区间修改可以在差分数组上改两位，最后求前缀和即可。
By jiangly
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n), b(n);
for (int i = 0; i < n; i++)
std::cin >> a[i];
for (int i = 0; i < n; i++)
std::cin >> b[i];
std::vector<i64> s(n + 1);
for (int i = 0; i < n; i++)
s[i + 1] = s[i] + b[i];
std::vector<int> d(n);
std::vector<i64> ans(n);
for (int i = 0; i < n; i++) {
int j = std::lower_bound(s.begin() + i, s.end(), a[i] + s[i]) - s.begin() - 1;
if (j > i) {
d[i]++;
if (j < n)
d[j]--;
}
if (j < n)
ans[j] += a[i] - (s[j] - s[i]);
}
for (int i = 1; i < n; i++)
d[i] += d[i - 1];
for (int i = 0; i < n; i++) {
ans[i] += 1LL * d[i] * b[i];
std::cout << ans[i] << " \n"[i == n - 1];
}
}
D. Triangle Coloring
题意：有 \(6n\) 个点，其中 \(\{1,2,3\},\{4,5,6\},\cdots,\{6n-2,6n-1,6n\}\) 分别形成三角形。边有边权。你需要将 \(3n\) 个点染成黑色，\(3n\) 个点染成白色，定义一种方案的权值为，所有两端异色的边的权值和。求让权值和最大化的方案数，对 \(998244353\) 取模。
题目的大体理解是要尽可能多的异色边，所以可以先考虑最多情况。容易发现，一个三角形内最多只能有两个异色边，且让每个三角形都有两个是可以做到的（在 \(2n\) 个三角形中，\(n\) 个黑黑白，\(n\) 个白白黑）。于是，最优解一定是每个三角形选较大的那两条边。
对于三角形内的方案数，如果较小的两条边不同，那么只有一种方案；如果三条边相同，则有三种方案；如果较小的两条边相同，较大的不同，则有两种。
由于要在 \(2n\) 个三角形中选出 \(n\) 个染黑黑白，剩余白白黑，所以需要再乘一个 \(\binom{2n}{n}\) 的组合数。
By tourist
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
Mint ans = 1;
for (int i = 0; i < n; i += 3) {
vector<int> a(3);
for (int j = 0; j < 3; j++) {
cin >> a[j];
}
sort(a.begin(), a.end());
if (a[0] < a[1]) {
ans *= 1;
}
if (a[0] == a[1] && a[1] < a[2]) {
ans *= 2;
}
if (a[0] == a[1] && a[1] == a[2]) {
ans *= 3;
}
}
for (int i = n / 6 + 1; i <= n / 3; i++) {
ans *= i;
}
for (int i = 1; i <= n / 6; i++) {
ans /= i;
}
cout << ans << '\n';
return 0;
}
E. Explosions?
题意：有 \(n\) 个怪物，第 \(i\) 个有 \(a_i\) 滴血，每次普通攻击花费 \(1\) 能量，可以让一个怪物减 \(1\) 滴血。在若干次普通攻击后，可以发一个大招，消耗 \(x\) 能量，选择某个怪物（设为 \(i\)）减 \(x\) 滴血，如果杀死，则相邻怪物减 \(a_i-1\) 滴血；如果继续杀死相邻怪物，则有传递性（如杀死 \(i+1\)，\(i+2\) 怪物会减 \(a_{i+1}-1\) 滴血）。你必须通过这一个大招杀掉所有剩下的怪物。问总的最小能量消耗。
显然要让普通攻击尽可能少，且把阵型优化成能够连续杀完的形态。可以考虑 DP：记 \(f[0][i]\) 表示如果大招对 \(i\) 用，要想把左边都连续干掉，需要提前处理的普通攻击次数；\(f[1][i]\) 为右边，同理。
以左边为例，\(f[0][1]\) 显然为 \(0\)，直接干掉就行了；每次考虑下一个新的怪物时，如果上一个怪物血量更高，则需要减少到 \(a_i-1\)（为了保证连续），而这可能会导致上上一个血量需要继续减少，似乎很难考虑。
但是，我们发现，对于一个连续段，要减少只能统一减少，所以可以维护当前的连续段信息。具体地，维护一个栈，元素形如 \(\{l,r,lx,rx\}\) 表示这一个连续段的左右端点和左右端点的值。
当加入一个怪物时，可以新建一个连续段 \(\{i,i,a_i,a_i\}\)，然后从栈顶开始依次处理段之间的影响。容易发现，影响时自顶向下的，且一个段影响下一个段后，这两个段必然合并。这便是复杂度保证的关键。
细节上，需要注意血量到 \(0\) 就不需要继续处理了，而前面处理的过程中可能会把血量减到负数，从而多花一些操作。只需要处理结束后“恢复”这些操作即可（操作数减一个等差数列）。
By cxm1024
int a[300010], f[2][300010];
void Solve(int test) {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
struct node {int l, r, lx, rx;};
for (int tt = 0; tt <= 1; tt++) {
stack<node> st;
int now = 0;
for (int i = 1; i <= n; i++) {
st.push({i, i, a[i], a[i]});
while (st.size() > 1) {
node tmp = st.top(); st.pop();
if (tmp.lx <= st.top().rx) {
now += (st.top().rx - tmp.lx + 1) * (st.top().r - st.top().l + 1);
st.top().lx -= st.top().rx - tmp.lx + 1, st.top().r = tmp.r, st.top().rx = tmp.rx;
}
else {st.push(tmp);break;}
}
if (st.top().lx < 0) {
now -= (-st.top().lx) * (-st.top().lx + 1) / 2;
st.top().l += (-st.top().lx), st.top().lx = 0;
}
f[tt][i] = now;
}
reverse(a + 1, a + n + 1);
}
reverse(f[1] + 1, f[1] + n + 1);
int ans = 1e18;
for (int i = 1; i <= n; i++)
ans = min(ans, a[i] + f[0][i] + f[1][i]);
cout << ans << endl;
}
F. Blocking Chips
题意：有一颗树，有若干个点为黑色且放了棋子，其他点为白色。你可以依次操作每个棋子，将它移动一步到白色点，并将该点染成黑色。操作完最后一个棋子后返回第一个棋子循环操作。问最多操作次数。
容易发现，棋子走后就无法回头，所以相当于对于每个棋子，选出一条以该棋子为端点的路径。
这种最大化的问题，看上去就非常像二分答案。考虑二分操作次数，那么前面若干个棋子会走 \(x+1\) 步，后面会走 \(x\) 步。预先存储下来，判断可行性。
略微思考一下性质，容易发现一个棋子要尽可能往子树内走，这样能给上面的棋子留下更多空间。于是可以考虑 DP：\(f[i]\) 表示 \(i\) 的子树能往下走的最远深度（如果需要往上走，就是负数）。
那么，对于一个有棋子的点，假设需要走 \(x\) 步，考虑所有儿子。只要有一个儿子需要往上走，就不合法；否则如果有一个儿子能供这个点往下走 \(x\) 步，\(f[i]=0\)（这个子树不需要往上走，也不允许往下走）；否则就必须往上走 \(x\) 步，\(f[i]=-x\)。
对于一个没有棋子的点，考虑所有儿子。如果有两个儿子需要往上走，就不合法；如果有一个儿子需要往上走，条件允许的话可以“拐个弯”再往下走（即通过别的子树的空地，内部解决问题，不需要往上走）。否则就必须要往上走。
看起来很多情况，但其实很多都可以统一写法：使用 \(neg\) 表示当前考虑这些儿子，需要走的量（不可能有两个往上走，一旦出现立刻无解）。对于棋子来说，初始为 \(-x\)；对于空地，初始为 \(1\)。如果一个儿子的 DP 值为负数（需要往上走），且当前的 \(neg\le 0\)（表示已经需要占用这个节点）则无解。否则，将 \(neg\) 设为该 DP 值 \(-1\)（因为已经往这个节点走了一格）。同时，记录儿子允许空地的最大值 \(max\)，遍历完后，如果 \(neg\le max\) 则可以内部解决，\(f[i]=0\)，否则必须往上走，\(f[i]=neg\)。
By jiangly
void solve() {
int n;
std::cin >> n;
std::vector<std::vector<int>> adj(n);
for (int i = 1; i < n; i++) {
int u, v;
std::cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
int k;
std::cin >> k;
std::vector<int> a(k);
for (int i = 0; i < k; i++) {
std::cin >> a[i];
a[i]--;
}
int lo = 0, hi = n;
while (lo < hi) {
int x = (lo + hi + 1) / 2;
std::vector<int> f(n, -1);
for (int i = 0; i < k; i++) {
f[a[i]] = x / k + (i < x % k);
}
std::vector<int> dp(n);
bool ok = true;
auto dfs = [&](auto self, int x, int p) -> void {
int neg = -f[x], max = 0;
for (auto y : adj[x]) {
if (y == p) {
continue;
}
self(self, y, x);
if (dp[y] < 0) {
if (neg <= 0) {
ok = false;
}
neg = dp[y] + 1;
} else {
max = std::max(max, dp[y]);
}
}
if (neg <= 0) {
if (neg + max >= 0) {
dp[x] = 0;
} else {
dp[x] = neg;
}
} else {
dp[x] = max + 1;
}
// std::cerr << "dp[" << x << "] = " << dp[x] << "\n";
};
dfs(dfs, 0, -1);
// std::cerr << "x = " << x << "\n";
if (ok && dp[0] >= 0) {
lo = x;
} else {
hi = x - 1;
}
}
std::cout << lo << "\n";
}
这种统一写法的方式非常值得学习，我赛时的代码就是直接分类讨论情况，又难写又不好调试。写代码之前要三思而后行。
标签：std,143,int,cin,++,vector,棋子,EDU,CFR From： https://www.cnblogs.com/cxm1024/p/17168444.html