很祭的一次比赛，啥也不会。 \(0 pts\) 给你一颗树，树根为 1 ，初始所有点都是白色，每次询问给出一个点集，若把点集中的点全部染成黑色，问至少需要翻转多少个节点才能使整棵树全为白点。无解输出 -1。询问之间相互独立 翻转的定义为：将节点 u 及其子树中所有节点颜色翻转。 赛时不会，想到了时间复杂度 \(O(n * m)\) 的树上 DP，以为是正解（时间复杂度想假了 \(n\) 按 \(log\large{n}\) 算的），打完才发现时间复杂度不对，之后就只想着怎么在这个基础上优化了，一直在思考把 \(n\) 变成 \(log \large{n}\)，本地跑大样例从 \(36s\) 卡常优化到了 \(1.9s\)，但时间复杂度没变，大概调了一个多小时急了，直接交了，想着能拿个 \(30pts\)，特殊性质也没想，结果捆绑测试实际得分 \(0pts\)。 以后模拟赛不能一个思路耗死，不能太高估自己，像这个题，性质也没那么难想，但自己完全就是没想着会有什么性质，一直在优化自己的 dp，看来以后要及时否定自己多换思路。 注：下文“染黑某个点”等说法皆指染黑以该点为根的子树。 我们枚举每个被染黑的点，设为 \(u\)，由于 \(u\) 已经被染黑了，所以我们肯定要把它染回来，如果 \(u\) 的父亲节点 \(fa\) 也为黑点，那么我们在进行将 \(fa\) 染为白点的操作后，自然也一起把 \(u\) 染白了； 计算答案 \(ans\) 时，那么我们只需遍历每个被染黑的点，若它的父亲节点不是黑点，则需要染一次，\(ans++\)，再遍历它的子节点，若子节点是白点，则还需染子节点一次，\(ans++\)。 这便是我们的思想，不过较容易发现，时间复杂度为 \(O(Q n m)\)，（\(Q\) 为询问的次数），会 \(T\) 掉。 时间复杂度多的那个 \(n\) 是枚举每个黑点的儿子节点导致的，所以我们考虑能不能不枚举每个儿子，我们可以预处理出来的时每个节点儿子的数量，这些数量是不会变化的，“别管黑儿子还是白儿子都是儿子”。 所以在枚举每个黑点的时候，我们可以直接加上该点儿子的数量。但这样就多加了黑儿子啊，按照我们的思路只加白儿子，但别忘了，黑儿子是被染黑的点，所以我们枚举所有黑点时总会枚举到这些多加的黑儿子，那么我们枚举时，判断枚举点的父亲节点是否为黑，若为父亲节点为白，则加一次操作，否则把减去一次操作，这样就把多加的黑儿子减去了。 成功优化到 \(O(Q n)\) 了！ 怀特有一个长度为 \(n\) 的正整数数列 \(A\) ，现在他在研究一种数列划分方法。 划分是将这个这个数列分成 \(k\) 个非空连续段，每段的价值为这段所有数的总和对给定的怀特数 \(p\) 取模后的值。 使得这 \(k\) 段的价值总和最小的划分方法就被成为怀特划分法。 布莱克现在有一个长度为 \(n\) 的序列 \(A\)，但是由于他的 dp 不好，所以 \(A\) 序列只会出现 1,−1 这两个数，虽然他也不知道这有什么用，但是需要 dp 的时候这样会变简单吧 为了给以后的 dp 做更多准备，现在他想求出一个布莱克序列 \(B\) ，布莱克序列 \(B\) 满足以下几个限制 给定一个序列，求是否是布莱克序列。 其实赛时基本想到正解了，但由于在 T2 卡的时间过长，所以 T3 根本没敢仔细想即使是已经出现正解的思路，只是在最后半小时打完了 T3 和 T4 的暴力。 构造。我们先将 \(b_i\) 赋值为 \(i\)，并求 \(∑_{i=1}^n b_i * a_i\) 的和记为 \(sum\)，求一个 \(s\) 数组为 \(a\) 数组的前缀。 若 \(sum=0\) 直接输出即可 \(sum>0\) 时 \(sum<0\) 时，与上述相反操作即可。 给你一颗树，边长均为1，初始所有点都是黑色，有以下两种操作： 对于每一个操作 G，输出一个整数，表示最远的两个黑点的距离。
题目列表：
A.White and Black
题意：
赛时分析：
正解：
思想：
再枚举 \(u\) 的子节点 \(son\)，如果 \(son\) 为白色，那么在把 \(u\) 染回来的操作中，\(son\) 点便被染黑了，所以还需要再染一次 \(son\) 点。暴力代码
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, Q, m, in[N];
int color[N], fa[N];
map<pair<int, int>, int>son;
signed main(){
// freopen("in.in", "r", stdin); freopen("a.out", "w", stdout);
scanf("%d%d", &n, &Q);
for(int i=2; i<=n; i++){
scanf("%d", &fa[i]);
son[mp(fa[i], ++son[mp(fa[i], 0)])] = i;
}
while(Q--)
{
scanf("%d", &m);
for(register int i=1; i<=m; i++){
scanf("%d", &in[i]);
color[in[i]] = 1;
}
int ans = 0;
for(int i=1; i<=m; i++){
if(!color[fa[in[i]]]) ans++;
for(int j=1; j<=son[mp(in[i], 0)]; j++){
if(!color[son[mp(in[i], j)]]) ans++;
}
}
printf("%d\n", ans);
for(register int i=1; i<=m; i++) color[in[i]] = 0;
}
return 0;
}
考虑优化：
最终代码：
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, Q, m, in[N];
int color[N], fa[N], son[N];
signed main(){
// freopen("in.in", "r", stdin); freopen("a.out", "w", stdout);
scanf("%d%d", &n, &Q);
for(int i=2; i<=n; i++){
scanf("%d", &fa[i]);
son[fa[i]]++;
}
while(Q--)
{
scanf("%d", &m);
for(register int i=1; i<=m; i++){
scanf("%d", &in[i]);
color[in[i]] = 1;
}
int ans = 0;
for(int i=1; i<=m; i++){
if(!color[fa[in[i]]]) ans++;
else ans--;
ans += son[in[i]];
}
printf("%d\n", ans);
for(register int i=1; i<=m; i++) color[in[i]] = 0;
}
return 0;
}
White and White
题意：
Black and Black
题意：
赛时分析：
正解：
code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 10;
int n, a[N]; ll b[N], sum;
ll s[N];
inline void print(){
puts("Yes");
for(int i=1; i<=n; i++) printf("%lld ", b[i]);
}
int main(){
// freopen("in.in", "r", stdin); freopen("out.out", "w", stdout);
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
s[i] = s[i-1] + a[i];
b[i] = i; sum += i * a[i];
}
if(sum == 0) print();
else if(sum < 0){
for(int i=n; i>=1; i--){
if(s[n] - s[i-1] > 0){
for(int j=i; j<=n; j++){
b[j] += -sum;
}
print();
return 0;
}
}
for(int i=1; i<=n; i++){
if(s[i] - s[0] < 0){
for(int j=1; j<=i; j++){
b[j] += sum;
}
print();return 0;
}
}
puts("No");
}
else{
for(int i=n; i>=1; i--){
if(s[n] - s[i-1] < 0){
for(int j=i; j<=n; j++)
b[j] += sum;
print();
return 0;
}
}
for(int i=1; i<=n; i++){
if(s[i] - s[0] > 0){
for(int j=1; j<=i; j++)
b[j] -= sum;
print();
return 0;
}
}
puts("No");
}
return 0;
}
Black and White
题意：
C u 将点 \(u\) 的颜色反转，即黑变白，白变黑；G 询问距离最远的两个黑点的距离；还不会...