题解 【LGR-087】洛谷 7 月月赛 Div.2

题解 【LGR-087】洛谷 7 月月赛 Div.2

比赛链接。

A. P7724 远古档案馆（Ancient Archive）

细节题。一年前竟然 AC 乐。

考虑 $0$ 的数量，设其为 $cnt$：

• $cnt=0$，比对初始状态和目标状态是否相同即可。
• $cnt=1$，将两个状态分别连成环，去掉其中的 $0$，判断两个环是否可以通过旋转变成相同的即可。
• $cnt\ge 2$，一定可行。

int a[4], b[4], cnta, cntb;

void solve(){
	for(int i = 0; i < 4; ++ i){
		a[i] = rdi;
	}
	for(int i = 0; i < 4; ++ i){
		b[i] = rdi;
	}
	for(int i = 0; i < 4; ++ i){
		if(a[i]){
			++ cnta;
		}
		if(b[i]){
			++ cntb;
		}
	}
	if(cnta != cntb){
		puts("No");
		return;
	} else if(cnta <= 2){
		puts("Yes");
		return;
	} else if(cnta == 4){
		if(a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3]){
			puts("Yes");
			return;
		} else {
			puts("No");
			return;
		}
	} else {
		if(a[0] == 0){
			a[0] = a[1];
			a[1] = a[3];
			a[3] = a[2];
		} else if(a[1] == 0){
			a[1] = a[3];
			a[3] = a[2];
		} else if(a[3] == 0){
			a[3] = a[2];
		}
		if(b[0] == 0){
			b[0] = b[1];
			b[1] = b[3];
			b[3] = b[2];
		} else if(b[1] == 0){
			b[1] = b[3];
			b[3] = b[2];
		} else if(b[2] == 0){
			b[3] = b[2];
		}
		for(int i = 0; i < 3; ++ i){
			int tmp = a[0];
			a[0] = a[1];
			a[1] = a[2];
			a[2] = tmp;
			if(a[0] == b[0] && a[1] == b[1] && a[2] == b[2]){
				puts("Yes");
				return;
			}
			
		}
	}
	puts("No");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

B. P7725 珍珠帝王蟹（Crab King）

一年前打比赛的时候没做出来。

因为 + 3，+ 4 和 + 7 没什么不同，所以我们考虑对于所有操作分为四类：加正数、加负数、乘正数、乘负数，并相对求出各自的和、积，分别记为 $saa,sab,pma,pmb$。

因为乘数的绝对值 $\ge 2$，所以乘法一定比加法更优。

如果并没有“乘负数”的操作，答案即为 $saa\ast pma+sab$。

否则设“乘负数”操作中乘数的最大值为 $tmp$（因为都是负的，所以这个数的绝对值最小）：

• 若有奇数次“乘负数”操作，可以先用一次操作使“加负数”变为正的，再加上“加正数”，最后乘上剩余的乘数。答案：$(saa+sab\ast tmp)\ast pma\ast \frac{pmb}{tmp}$；
• 若有偶数次“乘负数”操作，可以先用一次操作使“加正数”变为负的，再加上“加负数”，最后乘上剩余的乘数。答案：$(sab+saa\ast tmp)\ast pma\ast \frac{pmb}{tmp}$。

const ll P = 998244353;
vector<int> ma, mb, aa, ab;
int n;

void solve(){
	n = rdi;
	ll pma = 1, tmp = 1, pmb = 1, saa = 0, sab = 0;
	for(int i = 1; i <= n; ++ i){
		char ch;
		cin >> ch;
		int a = rdi;
		if(ch == '+'){
			if(a > 0){
				aa.push_back(a);
				saa += a;
			} else {
				a = -a;
				ab.push_back(a);
				sab += a;
			}
		} else {
			if(a > 0){
				ma.push_back(a);
				pma = pma * a % P;
			} else {
				a = -a;
				mb.push_back(a);
			}
		}
	}
	if(mb.size() == 0){
		writen((saa % P * pma % P - sab % P + P) % P);
		return;
	}
	sort(mb.begin(), mb.end());
	tmp = mb[0];
	for(int i = 1; i < mb.size(); ++ i){
		pmb = pmb * mb[i] % P;
	}
	if(mb.size() & 1){
		writen((sab % P * tmp % P + saa % P) % P * pma % P * pmb % P);
	} else {
		writen((saa % P * tmp % P + sab % P) % P * pma % P * pmb % P);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

C. P7726 天体探测仪（Astral Detector）

有点困难。

首先考虑 $1$ 的可能位置。可以查询第 $\lceil \frac{n}{2}\rceil$ 层的 $1$ 的个数，若有 $k$ 个 $1$，$1$ 的位置即为 $k$ 或 $n-k+1$。这里我们任取其一即可，后面会解释为什么。

然后考虑 $2$。$1$ 的位置把原区间 $[1,n]$ 分成了两个子区间 $[1,po{s}_1-1],[po{s}_1+1,n]$。对于区间 $[l,r]$，我们查询第 $r-l+1,r-l+2$ 层，若前者有 $2$，后者没有 $2$，则 $2$ 可以处于区间 $[l,r]$ 中。那么把 $[l,r]$ 替换为 $[1,po{s}_1-1],[po{s}_1+1,n]$，查询即可。若两个区间均可，也是任取其一都行。然后按照查询 $1$ 的位置一样查询 $2$ 的位置。

其它数同理，只不过是要查询更多的区间。这里可以使用链表维护每个数的位置、它后面的数。

为什么对于多个可行的答案任选其一都可以呢？因为整个解法我们只考虑了各个区间的长度，对于多个可行的答案，其实他们分成的每个区间的长度所形成的集合是相同的，所以任选其一都可以。

const int N = 1010;
int n, cnt[N][N];

struct Link{
	int pos, nxt;
} lnk[N];

void solve(){
	n = rdi;
	for(int i = 1; i <= n; ++ i){
		for(int j = i; j <= n; ++ j){
			++ cnt[i][rdi];
		}
	}
	lnk[0].pos = 0;
	lnk[n+1].pos = n+1;
	lnk[0].nxt = n+1;
	for(int i = 1; i <= n; ++ i){
		for(int j = 0; j <= n; j = lnk[j].nxt){
			int len = lnk[lnk[j].nxt].pos - lnk[j].pos - 1;
			if(cnt[len][i] && !cnt[len+1][i]){
				lnk[i].pos = lnk[j].pos + cnt[len+1>>1][i];
				lnk[i].nxt = lnk[j].nxt;
				lnk[j].nxt = i;
				break;
			}
		}
	}
	for(int i = lnk[0].nxt; i <= n; i = lnk[i].nxt){
		write(i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

D. P7727 风暴之眼（Eye of the Storm）

考虑树形 DP。设四个状态：

• 初态不等于终态，可改变，需要父亲的颜色传递到自己
• 初态不等于终态，可改变，只需子树的颜色传递到自己
• 初态等于终态，不可改变
• 初态等于终态，可改变，需要保证周围所有点不会出现终态以外的颜色。

则可以列出转移方程：

$$f_{x,0}=\prod _{y\in So{n}_x}(f_{y,0}[a_x=a_y],f_{y,2}[a_x\ne a_y])$$

$$f_{x,1}=\prod _{y\in So{n}_x}(f_{y,0}+f_{y,1}+f_{y,2})-f_{x,0}$$

$$f_{x,2}=\prod _{y\in So{n}_x}(f_{y,0}[a_x=a_y]+f_{y,1}+f_{y,2}+f_{y,3})$$

$$f_{x,3}=[a_{fa}=a_x]\prod _{y\in So{n}_x}(f_{y,2}+f_{y,3})[a_x=a_y]$$

const ll P = 998244353;
const int N = 2e5 + 10;
vector<int> G[N];
int n, a[N];
ll f[N][4];

void dfs(int x, int fa){
	f[x][0] = f[x][1] = f[x][2] = 1;
	f[x][3] = (a[fa] == a[x] ? 1 : 0);
	for(int i = 0; i < G[x].size(); ++ i){
		int y = G[x][i];
		if(y == fa){
			continue;
		}
		dfs(y, x);
		f[x][0] = f[x][0] * (a[x] == a[y] ? f[y][0] : f[y][2]) % P;
		f[x][1] = f[x][1] * (f[y][0] + f[y][1] + f[y][2]) % P;
		f[x][2] = f[x][2] * ((a[x] == a[y] ? f[y][0] : 0) + f[y][1] + f[y][2] + f[y][3]) % P;
		f[x][3] = f[x][3] * (a[x] == a[y] ? f[y][2] + f[y][3] : 0) % P;
	}
	f[x][1] = (f[x][1] - f[x][0] + P) % P;
}

void solve(){
	n = rdi;
	for(int i = 1; i <= n; ++ i){
		a[i] = rdi;
	}
	for(int i = 1; i < n; ++ i){
		int x = rdi;
		int y = rdi;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	a[0] = a[1];
	dfs(1, 0);
	printf("%lld\n", (f[1][1] + f[1][2] + f[1][3]) % P);
	return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39