前言

作为一名退役 OIer，借着此比赛来复健。

大部分题目都是口胡（没啥好写的），spj题手写了代码，A了。

难度不算特别高，但是赛场上拿到高分略有压力（退役了可以瞎bb）。

个人认为应该要拿到 300+ 的分数，但是感觉 AH 成绩普遍不好？

spj 题（尤其是构造题）一定要多重视啊，我当年没赶上这个好时代啊～

种花

洛谷标签为绿，pass

签到题，如果出事了建议去 pj 组历练。

懒得讨论。

喵了个喵

貌似是照应《羊了个羊》。是一道很有意思的 cf 类型题，大概会是 div1 中决定 rank 在 100 内还是外的分界线的难度。

此题在官方数据范围的指引下难度降了很多。首先 \(k=2n-2\) 十分容易，只需要维持一个空栈即可，其他每个栈至多两张卡牌。上层卡牌利用方法 1，下层卡牌利用方法 2 即可。

然后思考如何解决 \(k=2n-1\)。上面的策略在遇到连续 \(2n-1\) 个不同卡牌时，就不能维持一个空栈。首先在茫茫之中要明确一个原则：所有的栈中至多 \(2n-1\) 个卡牌，更进一步，不存在两个相同卡牌，否则将会把问题带向深渊，愈加复杂。

当遇到这种不可调和的情况时，仔细思考发现可以分 3 类情况讨论。首先先定义：栈中放入卡牌 \(X\) 后，所有栈有 \(2n-1\) 张不同卡牌，放 \(X\) 前有 \(2n-2\) 张卡牌，也就是说有 \(n-1\) 个栈，每个栈有两张卡牌。下层的卡牌集合记为 \(\{A\}\)，上层为 \(\{B\}\)。

牌 \(X\) 之后，必然还会遇到一次 \(X\)。在 \(X\) 之前，我们可能会遇到 \(A\) 或 \(B\)。

第一种情况：在两次 \(X\) 之间全是 \(B\)。那么 \(X\) 放空栈即可，对后续操作不会有影响。

假如在两次 \(X\) 之间含有 \(A\)，且第一个 \(A\) 在栈 \(i\) 中，栈 \(i\) 中还有一个上层卡牌 \(B_0\)，第二种情况是：\(B_0\) 不在 \(X\) 到 \(A\) 之间，那么就把 \(X\) 放到第 \(i\) 个栈顶，然后后面正常操作，直到遇到 \(A\)，此时空栈仍然是空栈，利用其消去 \(A\)，那么仍然存在空栈并且其它栈元素均不超过 2，可以继续。

那么当 \(B_0\) 出现在 \(X\) 和 \(A\) 之间，采用上面的方法会导致栈中已有的 \(B_0\) 无法消去，于是为第三种情况。那么就把 \(X\) 放到空栈里，当操作到 \(B_0\) 时，\(i\) 栈仅剩一个元素 \(A\)，如果之后再次遇到 \(B_0\)，就放到 \(X\) 顶上，这样遇到了 \(A\) 以后，直接放在 \(i\) 栈即可消去 \(A\)，此时 \(i\) 栈变成了空栈，并且其它栈元素均不超过 2。

复杂度 \(\mathcal O(n+m)\)。

#include <bits/stdc++.h>
const int N = 305, M = 2e6 + 5;
int T, n, m, k, a[N], b[N], c[N * 2], cur, s[M];
std::stack<int> s1, s2;
struct step { int x, y, z; };
std::vector<step> ans;
void opt_1(int x) {
	ans.push_back({1, x, 0});
}
void opt_2(int x, int y) {
	ans.push_back({2, x, y});
}
bool solve(int x) {
	if (c[x]) {
		if (c[x] < 0) {
			int u = -c[x];
			opt_1(u); b[u] = 0;
			s2.push(u);
		}
		else {
			int u = c[x];
			opt_1(cur); opt_2(u, cur);
			a[u] = b[u];
			if (b[u]) {
				c[b[u]] *= -1;
				b[u] = 0;
				s2.push(u);
			}
			else s1.push(u);
		}
		c[x] = 0;
	}
	else if (!s1.empty()) {
		int u = s1.top(); s1.pop();
		opt_1(u);
		a[u] = x; c[x] = u; // 第一层 +
	}
	else if (!s2.empty()) {
		int u = s2.top(); s2.pop();
		opt_1(u);
		b[u] = x; c[x] = -u; // 第二层 -
	}
	else return false;
	return true;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &n, &m, &k);
		for (int i = 1; i <= m; i++)
			scanf("%d", &s[i]);
		while (!s1.empty()) s1.pop();
		while (!s2.empty()) s2.pop();
		ans.clear();
		cur = n;
		for (int i = 1; i < n; i++)
			s1.push(i), s2.push(i);
		for (int i = 1; i <= m; i++)
			if (!solve(s[i])) {
				int j = i + 1;
				while (s[j] != s[i] && c[s[j]] < 0) j++;
				if (s[j] == s[i]) {
					opt_1(cur);
					for (int k = i + 1; k < j; k++)
						solve(s[k]);
					opt_1(cur);
				}
				else {
					int u = c[s[j]], p = 0;
					for (int k = i + 1; k < j; k++)
						if (c[s[k]] == -u) { p = k; break; }
					if (p) {
						opt_1(cur);
						c[a[cur] = s[i]] = cur;
						for (int k = i + 1; k < p; k++)
							solve(s[k]);
						opt_1(u);
						b[u] = c[s[p]] = 0; s2.push(cur);
						for (int k = p + 1; k < j; k++)
							solve(s[k]);
						opt_1(u);
						a[u] = c[s[j]] = 0;
						cur = u;
					}
					else {
						opt_1(u);
						for (int k = i + 1; k < j; k++)
							solve(s[k]);
						opt_1(cur); opt_2(u, cur);
						c[s[j]] = 0;
						c[a[u] = b[u]] = u;
						c[b[u] = s[i]] = -u;
					}
				}
				i = j;
			}
		printf("%lu\n", ans.size());
		for (step o : ans)
			if (o.x == 1) printf("1 %d\n", o.y);
			else printf("2 %d %d\n", o.y, o.z);
	}
	return 0;
}

建造军营

此题很裸，直接 缩点 + DP 计个数即可。没什么好说的。

比赛

看了眼数据范围 + 时限，直接分块。细节没想好，想起来了就补。

好像可以 线段树？不管了我 DS 很菜，想起来再补。