推蒟蒻 $\color{green}{blog}$

原题链接qaq~

原题大 E 是有 $n$ 条大新闻，每条大新闻形如 $u$ 扣了 $v$ 一滴血，每个人有 3 滴血，如果一个人的血量为 $0$， 那么之后所有有关他的大新闻都失效。

这时候出了一个外挂er，他可以在某一时刻开挂，突然扣一个人一滴血（这个人可以是死人）。定义 $f[k]$ 为“在某一位置突然扣了某个人一滴血后，导致最后有 $k$ 人存活的方案数”，求 $f[0…m]$ 的异或和。

预处理

首先我们有一个非常显然的结论：对于一个人来说，如果某一段时间他既没有去砍别人也没有被别人砍，那么他在这段时间里的任何时刻，被砍一刀导致的结果都是 等价的 。

然后我们继续分析，一个人在 3 滴血时被砍和在 2 滴血时被砍，导致的结果也是一样的——他们都会在本应还有 1 滴血的时候暴毙。

这样一来，其实我们可以把任何一个人的存活时间分成 几个区间 ，每个区间内被砍导致的结果都等价。我们整区间整区间地统计，这会使我们的代码优化很多。

先放预处理部分的瑇码~

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
N = read();
M = read();
for (register int i = 1; i <= M; i++)
	HP[i] = 3;//HP 数组存血量
for (register int i = 1; i <= N; i++)
{
	int x, y;
	x = read();
	y = read();
	q[i].u = x;
	q[i].v = y;//q 数组用来存每条大新闻
	if (HP[x] && HP[y])//如果这条新闻是有效的
	{
		HP[y]--;
		if (HP[y] == 0)
		{
			die[y] = i;//die 数组存每个人是什么时候死的
		}
	}
	if (HP[x] == 1)
	{
		v[x].push_back(MP(lst[x], i - 1));//v 存每个人的等价区间们
		//lst 存每个人的上一步行动是在什么时候
		v[x].push_back(MP(i, i));
		lst[x] = i + 1;
	}
}
int remain = 0;//如果没有开挂，本应有 remain 人存活
for (register int i = 1; i <= M; i++)
{
	if (HP[i])
		remain++;
	if (lst[i] != N + 1)//处理一些还未封闭的等价区间
		v[i].push_back(MP(lst[i], N));
	if (die[i] == 0)
		die[i] = N + 5;//如果一直不死，就给他赋一个无限晚的死亡时间
}

获取答案

然后我们要做的就是枚举每一个人，枚举他的每个等价区间，再把答案累计上去。

你会想，可这 $n^2$ 难道不会 T 飞🐎？

事实证明是不会的，由于每人的区间个数之和是一个定值，这个 $n^2$ 必然是跑不满的水 $n^2$ 。

如果在某个等价区间里，这个人已经死了，那么鞭一刀尸体不会影响答案，$f[remain]+=\texttt{区间长度}$ 。

否则，专门写一个函数 check 判断会留下几个人，函数里可以直接暴力一个一个大新闻地跑。然后 $f[check()]+=\texttt{区间长度}$ 。

然后我们就有一份 AC 瑇码辣！!1

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
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
const int MAX = 1e5 + 7;
const int MOD = 1e9 + 7;
void print(bool a)
{
	cout << (a ? "YES" : "NO") << endl;
}
struct atk
{
	int u, v;
} q[MAX];
#define PII pair<int, int>
#define MP make_pair
vector<PII> v[MAX];
int read()
{
	int num = 0, bj = 1;
	char ch = getchar();
	while (!isdigit(ch))
	{
		if (ch == '-')
		{
			bj = -1;
		}
		ch = getchar();
	}
	while (isdigit(ch))
	{
		num = num * 10 + ch - '0';
		ch = getchar();
	}
	return bj * num;
}
int lst[MAX];
int die[MAX], HP[MAX];
int ans[MAX];
int N, M;
inline int check(int pos, int v)//在 pos 号大新闻后，v 被砍了一刀
{
	for (register int i = 1; i <= M; i++)
		HP[i] = 3;
	for (register int i = 1; i <= pos; i++)
		if (HP[q[i].u] && HP[q[i].v])
			HP[q[i].v]--;
	if (HP[v])//开挂砍一刀
		HP[v]--;
	for (register int i = pos + 1; i <= N; i++)
		(HP[q[i].u] && HP[q[i].v])
			HP[q[i].v]--;
	int tmp = 0;
	for (register int i = 1; i <= M; i++)
		tmp += (HP[i] > 0);//统计存活人数
	return tmp;
}
signed main()
{
	...//预处理部分，在此不再重复
	
	for (register int i = 1; i <= M; i++)//枚举人
	{
		for (auto u : v[i])//枚举等价区间
		{
			if (u.first > u.second)
			//若区间不合法则跳过（推测应该是在造区间的时候造了一些没用的区间）
				continue;
			if (die[i] <= u.first)//若是鞭尸
				ans[remain] += u.second - u.first + 1;
			else
				ans[check(u.second, i)] += u.second - u.first + 1;
		}
	}
	for (register int i = 0; i <= M; i++)
		printf("%d ", ans[i]);
	return 0;
}

最后更新： 2021年05月04日 18:46

原始链接： https://quest233.github.io/2021/05/04/%E6%B5%85%E8%B0%88%E4%B8%80%E7%B1%BB%E4%BC%98%E5%8C%96%E5%90%8E%E7%9A%84%E6%9A%B4%E5%8A%9B%E2%80%94%E2%80%94%E3%80%8CMCOI-05%E3%80%8D%E8%BF%BD%E6%9D%80-%E9%A2%98%E8%A7%A3/