# Codeforces Round 928 (Div. 4)
<https://codeforces.com/contest/1926>
# ABCD太简单略了
# E
首先，**只有奇数本身和其2、4、8、16……倍存在首先被遍历的可能性**，即首先遍历全部奇数，然后是奇数的2倍，然后是4倍，然后是8倍……这个容易推出，不做证明。
可以用筛法得到奇数本身、*2、*4、*8……等序列（可分别称为1序列、2序列、4序列、8序列……），但是仅能用于研究，打表处理不了1e9的规模，结果如：
```
2： 1 / 2
4： 1 3 / 2 / 4
9: 1 3 5 7 9 / 2 6 / 4 / 8
19: 1 3 5 7 9 11 13 15 17 19 / 2 6 10 14 18 / 4 12 / 8 / 16
20: 1 3 5 7 9 11 13 15 17 19 / 2 6 10 14 18 / 4 12 20 / 8 / 16
```
这个序列有分形的特性：
- 4的2及之后序列同构于2的所有序列
- 9的2及之后序列同构于4的所有序列
- 9的4及之后序列同构于2的所有序列
- 19的2及之后序列同构于9的所有序列
- ……
因此我们可以找到 $\text O(\log n)$ 的**规律**：
- 1序列长度 $l_1 = \lceil n/2\rceil$
- 2序列长度 $l_2 = \lceil (n-l_1)/2\rceil$
- 4序列长度 $l_4 = \lceil (n-l_1-l_2)/2\rceil$
- $2^m$序列长度 $l_{2^m} = \lceil (n-\sum_{i=0}^{m-1}l_{2^i})/2\rceil$
- ……
假设查询位置为$k$，那么有如下结论：
- ①从$k$中依次减去可全部经过的序列的长度，只剩下减不动的长度$k'$。比如 9 的$l_1=5$，$l_2=2$，假设$k=7$，则$k'=7-5=2$，意味着查询 $k$ 落在了 9 的$2$序列的第$2$个元素上
- ②因为分形的规律，$2^m$序列的第$k'$个元素，一定是正奇数序列的第$k'$个元素的$2^m$倍，具体数字即为 $2^m\cdot(2k'-1)$，其中$k'\ge1$
```cpp
int main() {
//ios_base::sync_with_stdio(false);
int qwq; INI(qwq);
F0(t, qwq) {
int n, m;
INI(n); INI(m);
int p = 1;
F0(i, 32) {
int len = n - n / 2;
if (m <= len) {
printf("%d\n", p * (2 * m - 1));
break;
}
p *= 2;
m -= len;
n -= len;
}
}
return 0;
}
```
------
# F
首先找到存在冲突的黑块（中心块）以及可以尝试删除的块（中心块及其四角块）。考虑枚举+回溯法，删除某些块，判断是否解开局面，返回解的代价，并筛选最优解。
另外还有一个特性：在此棋盘上，奇格（x+y为奇数）和偶格（x+y为偶数）是互不干扰的，奇格的冲突只能由奇格解开，偶格的冲突只能由偶格解开。这个特性可以作为剪枝的依据，分别在奇偶两个图层上找解，然后将代价相加即可。
本题DFS相当难写（虽然原理不变），在此放一份tourist使用位压缩+枚举的代码：
```cpp
/**
* author: tourist
* created: 19.02.2024 09:34:20
**/
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int tt;
cin >> tt;
while (tt--) {
int n = 7;
vector<string> s(n);
for (int i = 0; i < n; i++) {
cin >> s[i];
}
int ans = 0;
for (int p = 0; p < 2; p++) { // 处理奇偶图层
// 构建冲突格集bad
int64_t bad = 0;
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if ((i + j) % 2 != p) { // 处理奇偶图层
continue;
}
if (s[i][j] == 'B' && s[i - 1][j - 1] == 'B' && s[i - 1][j + 1] == 'B' && s[i + 1][j - 1] == 'B' && s[i + 1][j + 1] == 'B') {
bad |= int64_t(1) << (i * n + j);
}
}
}
// 构建棋盘每一格(i,j)的解开格集kill[i][j]
vector<vector<int64_t>> kill(n, vector<int64_t>(n));
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < n - 1; j++) {
kill[i][j] |= int64_t(1) << (i * n + j);
kill[i][j] |= int64_t(1) << ((i - 1) * n + (j - 1));
kill[i][j] |= int64_t(1) << ((i - 1) * n + (j + 1));
kill[i][j] |= int64_t(1) << ((i + 1) * n + (j - 1));
kill[i][j] |= int64_t(1) << ((i + 1) * n + (j + 1));
}
}
int best = n * n + 1;
// 7*7的棋盘上，值得删除的格必然在5*5范围内，而其中单论奇格或偶格的话最多13个
// 因此将删除格集t从0遍历到2^14，枚举所有的删除情况，即可找到解
for (int t = 0; t < (1 << 13); t++) {
int at = 0;
int64_t done = 0;
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < n - 1; j++) {
if ((i + j) % 2 != p) { // 处理奇偶图层
continue;
}
if ((t >> at) & 1) { // 判断第at个奇格(偶格)是否包含在删除格集t中？
done |= kill[i][j]; // done代表本轮枚举的删除格集t可以解开的所有位置
}
at += 1;
}
}
// 若本轮枚举的解开位置done包含了原局面的冲突格集bad，则是一个有效解
if ((done & bad) == bad) {
best = min(best, __builtin_popcount(t));
}
}
ans += best; // 在奇格和偶格中分别有一个best，将这两个加到ans里
}
cout << ans << '\n';
}
return 0;
}
```
> 奇偶特性：
>
> 
------
# G
首先可以知道，当派对音乐完成传播后，整棵树上的每个节点要么是安静的，要么是扰民的，即睡眠节点必为安静态，派对节点必为扰民态，中立节点将根据是否被传播音乐而呈现为扰民态或安静态。
由于是树，比图具有更好的性质，因此我们直接尝试从叶子节点开始，自底向上判断每个节点的情况：
- 对睡眠节点
- 其一定向上传递为安静态
- 断开其与所有扰民态子节点的边
- 对派对节点
- 其一定向上传递为扰民态
- 断开其与所有安静态子节点的边
- 对中立节点
- 忽略中立态子节点
- 若安静态和睡眠态子节点个数不同，则向上传递占优状态。断开与非占优状态的子节点的边。*验证可知断开非占优状态的边一定不比断开占优状态的边差*。
- 若安静态和睡眠态子节点个数相同，则向上传递中立态。断开与任一状态子节点的边。*验证可知选择哪一个都不影响传播全部完成后最终断开的边的条数*。
- 无子节点和一个子节点的情况都可以归约到此通用方法
- 上文所说的“验证”都是指：判断当前节点的父节点分别是扰民和安静时，与父节点的边是否需要断开，以及最终断开的边的条数是否最优。
综合来看，这个算法可以被归为贪心法。除此之外还有人用DP做，基本思路也是这样枚举各类情况，但让搜索空间更大。
```cpp
// -------------- HEAD ----------------
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
#define _CRT_SECURE_NO_WARNINGS
//#undef DEBUG
#ifdef DEBUG
#define ___LOG_PREFIX ">>> LOG: "
#define LOG(x) {std::cout << ___LOG_PREFIX << x << endl;}
#define LOGF printf(___LOG_PREFIX);printf
#else
#define LOG (void)
#define LOGF (void)
#endif
#define INI(x) scanf("%d", &(x))
#define IND(x) scanf("%lf", &(x))
#define INLL(x) scanf("%lld", &(x))
#define INS_BUF(x,buf) \
{ \
char ___##x[buf]; \
scanf("%s", ___##x); \
x = ___##x; \
}
#define INS(x) INS_BUF(x, 10000)
#define F0(i,n) for(int i=0;i<n;++i)
#define F1(i,n) for(int i=1;i<=n;++i)
#define F0R(i,n) for(int i=n-1;i>=0;--i)
#define F1R(i,n) for(int i=n;i>0;--i)
#define FE(i,c) for(auto &i:c)
#define fill0(c) memset(c,0,sizeof(c))
#define mp make_pair
#define mt make_tuple
#define endl "\n"
// -------------- GLOBAL ----------------
struct TreeNode {
vector<int>* c = NULL;
int p = 0;
char ch = 0;
int status = 0; // -1: 安静 0: 中立 1: 扰民
};
TreeNode tree[200000];
// -------------- FUNC ----------------
void addChild(int p, int c) {
tree[c].p = p;
if (tree[p].c == NULL)
tree[p].c = new vector<int>();
tree[p].c->push_back(c);
}
void init(int n) {
F0(i, 200000) {
if (tree[i].c != NULL)
delete tree[i].c;
}
fill0(tree);
}
int postOrder(int node) {
if (tree[node].c == NULL) {
return 0;
}
int removed = 0;
FE(c, *tree[node].c) {
removed += postOrder(c);
}
if (tree[node].status != 0) {
FE(c, *tree[node].c) {
if (tree[c].status == -tree[node].status)
removed++;
}
}
else {
int s = 0, p = 0;
FE(c, *tree[node].c) {
if (tree[c].status == -1)
s++;
else if (tree[c].status == 1)
p++;
}
if (s > p) {
removed += p;
tree[node].status = -1;
}
else if (s < p) {
removed += s;
tree[node].status = 1;
}
else {
removed += s;
tree[node].status = 0;
}
}
return removed;
}
// -------------- MAIN ----------------
int main() {
//ios_base::sync_with_stdio(false);
int qwq; INI(qwq);
F0(t, qwq) {
int n;
INI(n);
init(n);
F1(i, n - 1) {
int t;
INI(t);
addChild(t, i + 1);
}
getchar();
F1(i, n) {
tree[i].ch = getchar();
if (tree[i].ch == 'P') tree[i].status = 1;
else if (tree[i].ch == 'S') tree[i].status = -1;
}
printf("%d\n", postOrder(1));
}
return 0;
}
```
![]()