mydcwfy's Blog

LOJ3897 「NOIP2022」喵了个喵

Posted on
Symbols count in article: 3.5k Reading time ≈ 8 mins.

题意：有 $m$ 张卡牌分为 $k$ 种，每种都是偶数张，你需要顺次把 $m$ 张放进 $n$ 个栈，如果存在一个栈相邻两个种类相同，那么立刻消去。同时你可以选择两个栈，他们的底部卡牌种类需要相同，然后消去这两张卡牌。要求放完 $m$ 张卡牌过后 $n$ 个栈都是空的。请给出一个构造方案。$m\leq 2\times 10 ^ 6$，$n\leq 300$，$k = 2n - 2$ 或者 $k = 2n - 1$。

首先考虑 $k = 2n - 2$ 的做法。容易发现我们只需要空出一个栈，剩下的每个栈都放不同种类的卡牌，新来一张如果是对应卡牌是在底部的话就放在空栈，在顶部的话就直接可以消去。容易发现这样是一定能消完的。

现在考虑多一种怎么做。首先一个关键点是我们还是得留出一个空栈，否则底部的 $n - 1$ 种都没法消。那么现在问题在于这 $n - 1$ 个栈已经放了 $2n - 2$ 种类，并且又来了一种新的。

首先如果他的下一张卡牌是在底部的话，我们直接在这个栈上面放上一个新来的，然后把底部消去即可。同时如果下一张卡牌也是新来的种类的话，我们直接把这两张都放在空栈即可消去。

上面两种特殊情况提示我们考虑后面卡牌中第一次出现底部种类或者是新来种类的卡牌，注意到中间一定全部是顶部种类。

如果后面第一次出现是新来种类的话，由于中间全是顶部种类，没必要留空栈，于是我们把新来的种类放在空栈等待消去，其他的顶部种类直接消 / 放即可。

如果后面第一次出现是底部种类的话，我们直接把新来的种类放在这个栈上面是不好的，因为后面可能出现这个栈的顶部种类无法消去。

  1. 如果这个顶部种类在这段区间中出现了偶数次，我们就把它全部扔在空栈，其他的种类正常消 / 放没有影响。
  2. 如果这个顶部种类在这段区间中出现了奇数次，我们必须把这个栈让开，否则消不掉。注意到这个栈最后会变成空栈，这恰好符合我们的构造。于是我们把新来的种类放在空栈，然后其他的正常消 / 放，最后来的底部种类就会把这个栈变成空栈（因为这个栈的顶部种类已经被消了）。这样我们重新把这个栈看作空栈即可。

实现的时候会出现一些问题，主要是因为 $O(nm)$ 的时间比较卡，我们用一个队列维护（没有填满并且没有被钦定为是空栈）的栈，由于这些填入造成的修改都是 $O(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
78
79
80
81
82
83
84
85
86
void work()
{
	read(n, m, k);
	int em = n; // empty stack
	opt.clear();
	while (!add.empty()) add.pop();
	for (int i = 1; i <= k; ++ i) id[i] = 0, ins[i] = dn[i] = false;
	for (int i = 1; i <= n; ++ i) a[i].clear();
	for (int i = 1; i < n; ++ i) add.push(i), add.push(i);
	for (int i = 1; i <= m; ++ i) read(c[i]);
	auto insert = [&](int x) {
		if (ins[x]) {
			if (dn[x]) {
				opt.push_back({1, em});
				opt.push_back({2, id[x], em});
				a[id[x]].pop_front();
				ins[x] = dn[x] = false;
				if (a[id[x]].size()) dn[a[id[x]].front()] = true;
			} else opt.push_back({1, id[x]}), a[id[x]].pop_back(), ins[x] = dn[x] = false;
			add.push(id[x]), id[x] = 0;
			return;
		}
		if (add.size()) {
			int t = add.front();
			add.pop();
			dn[x] = !a[id[x] = t].size(), ins[x] = true, a[t].push_back(x);
			opt.push_back({1, t});
			return;
		}
	};
	for (int i = 1, x; i <= m; ++ i)
	{
		/*std::cout << i << ' ' << c[i] << " Deque\n";
		for (int j = 1; j <= n; ++ j, puts(""))
			for (int x : a[j]) printf("%d ", x);
		fflush(stdout);*/
		if (ins[x = c[i]] || add.size()) {
			insert(x);
			continue;
		}
		int j = i + 1, flag = 0, t, uc;
		while (j <= m && !dn[c[j]] && c[j] != x) ++ j;
		if (c[j] == x) {
			opt.push_back({1, em});
			for (int k = i + 1; k < j; ++ k) insert(c[k]);
			opt.push_back({1, em});
			i = j;
			continue;
		}
		t = id[c[j]], uc = a[t].back();
		for (int k = i; k < j; ++ k) flag ^= (c[k] == uc);
		if (flag) {
			// std::cout << "Flag1 " << i << ' ' << j << '\n';
			opt.push_back({1, em});
			int ls = -1;
			for (int k = i; k < j; ++ k)
				if (c[k] == uc) ls = k;
			for (int k = i + 1; k < j; ++ k)
				if (c[k] == uc) {
					if (k == ls) opt.push_back({1, t});
					else opt.push_back({1, em});
				} else insert(c[k]);
			opt.push_back({1, t});
			ins[x] = dn[x] = true, id[x] = em;
			ins[c[j]] = ins[uc] = dn[c[j]] = dn[uc] = false, id[c[j]] = id[uc] = 0;
			add.push(em), a[t].clear(), a[em].push_back(x);
			em = t;
			i = j;
		} else {
			// std::cout << "Flag0 " << i << ' ' << j << '\n';
			opt.push_back({1, t});
			for (int k = i + 1; k < j; ++ k)
				if (c[k] == uc) opt.push_back({1, em});
				else insert(c[k]);
			opt.push_back({1, em}), opt.push_back({2, t, em});
			dn[x] = false, ins[x] = true, dn[uc] = true, id[uc] = id[x] = t;
			a[t].pop_front(), a[t].push_back(x);
			ins[c[j]] = false, id[c[j]] = 0;
			i = j;
		}
	}
    write(opt.size(), '\n');
    for (auto p : opt)
        if (p.op == 1) write('1', ' ', p.u, '\n');
        else write('2', ' ', p.u, ' ', p.v, '\n');
}