2022 NOIP 题解
建造军营
这道题之前做过一次,我们来转换一下这道题的题意，题中给到了边、点我们可以想到强连通分量，进而想到tarjan算法。通过所给样例及题意，我们可以将原题目转化为以下内容：
给定一张图，选择一些点和边，使得割断任意没有选的边，被选中的点仍联通，最终答案对 1 0 9 + 7 10^9+7 109+7取模。
想做这道题，我们得先知道什么是割点、割边（桥）、缩边、双连通分量
看到图和连通，想到tarjan。割断一条没有选的边，选中的点仍连通，割非割边，整张图仍然连通。
把割边删掉，则整张图分成若干连通子图。可以把一张子图看成一个点，这样形成的新图上没有环，因为在环上的边都不是割边，那它就是一棵树。使用vector邻接表建图，dfs一遍，使用 f f f数组记录答案，最终将答案转移到 a n s ans ans上。
上一次做这道题代码愣是写了120行，昨天换了个思路，尝试着把dfs压缩了一下，代码就短多了。
code
//本质使得割掉一些边之后,剩下的点仍然联通
//看到连通块就想到tarjan算法
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 500005;
const int mod = 1e9 + 7;
ll n, m;//城市个数,双向道路数量
ll ans;//方案数
//tarjan算法的常用数组
ll st[N], dfn[N], low[N],bl[N];
ll f[N];
vector<int>e[N], g[N];//使用vector为了方便
void tarjan(int x, int fa) {
st[++st[0]] = x;
dfn[x] = low[x] = ++dfn[0];
for (int y : e[x]){//从数组e中依次取出元素赋值给y
if (y != fa) {
if (!dfn[y]){
tarjan(y, x);
}
low[x] = min(low[x], low[y]);
}
}
if (dfn[x] == low[x]) {
m++;
while (st[st[0]] != x)bl[st[st[0]--]] = m;
bl[st[st[0]--]] = m;
}
}
void dfs(int k, int fa) {
ans = (ans + f[k]) % mod;
for (int i : g[k]){
if (i != fa) {
dfs(i, k);
f[i] = f[i] * (mod + 1) / 2 % mod;
ans = (ans + f[k] * f[i]) % mod;
f[k] = (f[k] + f[i] + f[k] * f[i]) % mod;
}
}
}
int main() {
cin >> n >> m;
//输入边+建图
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
//临接表建图
e[x].push_back(y);
e[y].push_back(x);
}
m = 0;
tarjan(1, 0);
for (int i = 1; i <= m; i++){
f[i]++;
}
for (int i = 1; i <= n; i++){
f[bl[i]] = f[bl[i]] * 2 % mod;
}
for (int i = 1; i <= m; i++){
f[i]--;
}
for (int i = 1; i <= n; i++){
for (int j : e[i]){
if (bl[i] != bl[j]){
g[bl[i]].push_back(bl[j]);
}
}
}
dfs(1, 0);
for (int i = 1; i <= n; i++){
for (int j : e[i]){
if (i < j){
ans = ans * 2 % mod;
}
}
}
cout << ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const int M = 4e6;
const int mod = 1e9 + 7;
int add(int x, int y) {
return ((x += y) >= mod) ? x - mod : x;
}
void addn(int &x, int y) {
if ((x += y) >= mod) x -= mod;
}
int mins(int x, int y) {
return ((x -= y) < 0) ? x + mod : x;
}
struct G {
struct edge {
int to, nxt, w;
} e[M << 1];
int head[M], cnt1 = 1;
void link(int u, int v) {
e[++cnt1] = {v, head[u], 1};
head[u] = cnt1;
}
} g1, g2;
int fa[M];
int dfn[M], low[M], cnt;
bool cut[M];
void tarjan(int u, int f) {
low[u] = dfn[u] = ++cnt;
for (int i = g1.head[u]; i; i = g1.e[i].nxt) {
int v = g1.e[i].to;
if (v == f) continue;
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) g1.e[i].w = g1.e[i ^ 1].w = 0; // 0 标记为割边，i^1 用了成对变换的技巧，把反边一起标记
} else low[u] = min(low[u], dfn[v]);
}
}
int siz1[M], siz2[M];
bool vis[M];
int bl[M];
int n, m;//n城市个数,m双向道路数量
int cnt2;
// 用于划分连通块，siz1 对应行文中的 cntp，点数；siz2 对应行文中的 cnte，边数
void dfs2(int u, int f, int t) {
bl[u] = t;
vis[u] = 1;
++siz1[t];
for (int i = g1.head[u]; i; i = g1.e[i].nxt) {
if (g1.e[i].w) ++siz2[t];
int v = g1.e[i].to;
if (g1.e[i].w == 0 || v == f) continue;
if (!vis[v]) dfs2(v, u, t);
}
}
int sm[M];
// 用于计算文中的 sum 数组，子树中边数和，包括被缩掉者
void dfs4(int u, int fa) {
sm[u] = siz2[u];
for (int i = g2.head[u]; i; i = g2.e[i].nxt) {
int v = g2.e[i].to;
if (v == fa) continue;
dfs4(v, u);
sm[u] += sm[v] + 1;
}
}
int dp[M][2], pw[M], ans;
// 统计答案的 dfs，dp 意义如上文所叙
// dp_{u,0} 强制 u 及其子树不选任意一个点（空）
// dp_{u,1} 强制 u 及其子树选至少一个点，且所有被选的点与 u 连通（不空）。
void dfs3(int u, int fa) {
dp[u][0] = pw[siz2[u]];
dp[u][1] = 1ll * pw[siz2[u]] * (pw[siz1[u]] - 1) % mod;
int tot = 0;
for (int i = g2.head[u]; i; i = g2.e[i].nxt) {
int v = g2.e[i].to;
if (v == fa) continue;
dfs3(v, u);
dp[u][1] = add(1ll * dp[u][1] * add(1ll * dp[v][0] * 2 % mod, dp[v][1]) % mod, 1ll * dp[u][0] * dp[v][1] % mod);
dp[u][0] = 1ll * dp[u][0] * 2 % mod * dp[v][0] % mod;
addn(tot, dp[v][1]);
}
if (u != n + 1) addn(ans, 1ll * dp[u][1] * pw[sm[n + 1] - sm[u] - 1] % mod);
else addn(ans, 1ll * dp[u][1] % mod);
}
int find(int u) {
return u == fa[u] ? u : fa[u] = find(fa[u]);
}
void merge(int u, int v) {
if ((u = find(u)) != (v = find(v))) fa[u] = v;
}
int main() {
scanf("%d %d", &n, &m);
pw[0] = 1;
for (int i = 1; i <= 2 * n + m; i++) pw[i] = 1ll * pw[i - 1] * 2 % mod;
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d %d", &u, &v);
g1.link(u, v);
g1.link(v, u);
}
tarjan(1, 0);
cnt2 = n;
for (int i = 1; i <= n; i++) if (!vis[i]) dfs2(i, 0, ++cnt2);
for (int i = n + 1; i <= 2 * n; i++) {
siz2[i] /= 2;
}
// 缩边
for (int i = 1; i <= 2 * n; i++) fa[i] = i;
for (int u = 1; u <= n; u++) {
for (int i = g1.head[u]; i; i = g1.e[i].nxt) {
int v = g1.e[i].to;
if (find(bl[u]) != find(bl[v])) g2.link(bl[u], bl[v]), g2.link(bl[v], bl[u]), merge(bl[u], bl[v]);
}
}
// n+1 是缩完边后树的根
dfs4(n + 1, 0);
dfs3(n + 1, 0);
printf("%d\n", ans);
}
种花
这道题其实是道计数4+模拟的题，非常简单的想法，用两个函数把我们所需要求的写成两个函数，按照题目中的要求实现就行，但是好像会T。
80
p
t
s
80pts
80pts
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e3 + 10;
const int md = 998244353;
int t, id;
int n, m, c, f;
bool mapp[maxn][maxn];
ll ac, af;
string s;
//快速幂模板
ll qmul(ll a, ll b) {
ll res = 0;
while (b) {
if (b & 1)res += a;
a *= 2;
b >>= 1;
}
return res;
}
void cc() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!mapp[i][j]) {
int x = 0, xx = 0, y = 0;
while (!mapp[i][j + x] && j + x <= m)x++;
if (!(x - 1))continue;
while (!mapp[i + y][j] && i + y <= n)y++;
if (!(y - 2))continue;
for (int k = 2; k <= y - 1; k++) {
xx = 0;
while (!mapp[i + k][j + xx] && j + xx <= m)xx++;
if (!xx)continue;
ac += qmul(x - 1, xx - 1);
ac = ac % md;
}
}
}
}
}
void ff() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (!mapp[i][j]) {
int x = 0, xx = 0, y = 0;
while (!mapp[i][j + x] && j + x <= m)x++;
if (!(x - 1))continue;
while (!mapp[i + y][j] && i + y <= n)y++;
if (!(y - 3))continue;
for (int k = 2; k <= y - 2; k++) {
xx = 0;
while (!mapp[i + k][j + xx] && j + xx <= m)xx++;
if (!xx)continue;
af += qmul(qmul(x - 1, xx - 1), (y - 1 - k));
af = af % md;
}
}
}
}
}
int main() {
cin >> t >> id;
while (t--) {
memset(mapp, 0, sizeof(mapp));
cin >> n >> m >> c >> f;
ac = 0, af = 0;
for (int i = 1; i <= n; i++) {
cin >> s;
for (int j = 1; j <= m; j++)mapp[i][j] = s[j - 1] == '0' ? 0 : 1;
}
if (c)cc();
if (f)ff();
cout << ac << ' ' << af << '\n';
}
return 0;
}
先考虑 C C C形，
我们可以确定 C C C形的左上角 O ( n m ) O( n m ) O(nm)
然后，我们的目标是：
- 求出 C C C第一行长度的可能结果数
- 求出 C C C 第一列的可取长度的范围1
- 求出 C C C每一列长度对应的行的可能结果数
- 目标 1 1 1和目标 3 3 3相乘累加到答案中
以上的步骤全部需要 O ( 1 ) O(1) O(1) 完成，所以我们考虑预处理
对于 目标 1 1 1，我们可以预处理出 位置 ( i , j ) (i,j)(i,j) 离右手边最近的障碍的距离。
对于 目标 3 3 3，一个个算肯定是 武则天丧夫 没理智的，但是我们求的是一个区间结果，这个时候就该考虑前缀和
我们用新的数组存储(我们预处理的右手边最近障碍距离)的前缀和，在执行目标 3 3 3时用前缀和作差求出结果。
我们可以再预处理 位置 ( i , j ) ( i , j ) (i,j) 离正下方最近障碍的距离。那么我们询问的区间就是 ( x + 2 , j ) ∼ ( x + d i s ( x ) , j ) ( x + 2 , j ) ∼ ( x + d i s ( x ) , j ) (x+2,j)∼(x+dis(x),j)
自此 c c c 形就解决了！
再考虑 F F F形:
如果我们已经确定了 F F F 形的第二 横，那么可以得到累加多少结果呢？
很显然是 小尾巴 的长度。那么我们对于每一个可能的横都可以预处理出带上小尾巴的结果数，
然后还是熟悉的区间结果查询，我们依旧对上述结果做前缀和。
c o d e code code
#include<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
void wt(int x) {
static int sta[35];
int f = 1;
if(x < 0) f = -1,x *= f;
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
if(f == -1) putchar('-');
while (top) putchar(sta[--top] + 48);
}
int T,id;
const int N = 1005,mod = 998244353;
int n,m,c,f;
char d[N];
int s[N][N],h[N][N];
int ss[N][N],_s[N][N];
void init() {
memset(s,0,sizeof(s));
memset(ss,0,sizeof(ss));
memset(h,0,sizeof(h));
memset(_s,0,sizeof(_s));
}
void solve() {
init();
n = rd(),m = rd(),c = rd(),f = rd();
for(int i = 1;i<=n;i++) {
scanf("%s",d + 1);
for(int j = 1;j<=m;j++)
s[i][j] = d[j] - '0';
}
for(int j = 1;j<=m;j++)
for(int i = n,k = n + 1;i>=1;i--)
if(s[i][j]) k = i,h[i][j] = k - i - 1;
else h[i][j] = k - i - 1;
for(int i = 1;i<=n;i++)
for(int j = m,k = m + 1;j >= 1;j--)
if(s[i][j]) k = j,s[i][j] = k - j - 1;
else s[i][j] = k - j - 1;
for(int j = 1;j<=m;j++) {
for(int i = n;i>=1;i--){
ss[i][j] = ss[i + 1][j] + s[i][j];
_s[i][j] = s[i][j] * h[i][j];
_s[i][j] = _s[i + 1][j] + _s[i][j];
}
}
int C = 0,F = 0;
for(int j = 1;j<=m;j++) {
int k = 1,re = 0;
while(k + 2 <= n) {
while((s[k][j] == -1 || s[k + 1][j] == -1 || s[k + 2][j] == -1) && k <= n) k++;
if(k >= n - 1) break;
re = s[k][j];
(C += re * (ss[k + 2][j] - ss[k + h[k][j] + 1][j])) %= mod;
if(k + 3 <= n && ~s[k + 3][j])
(F += re * (_s[k + 2][j] - _s[k + h[k][j] + 1][j])) %= mod;
k++;
}
}
wt(c * C),putchar(' '),wt(f * F);
putchar('\n');
}
signed main() {
T = rd(),rd();
while(T--) solve();
return 0;
}
比赛
想了想，对于题中的所有询问，我们先从
r
r
r开始，从小到大一个挨着一个的开始遍历。如果当前考虑到
r
r
r，记
x
i
=
max
j
=
i
r
a
j
,
y
i
=
max
j
=
i
r
b
j
,
f
i
=
∑
j
=
i
r
x
j
y
j
,
x_i=\max _{j=i}^{r} a_j,y_i=\max_{j=i}^{r} b_j,f_i=\sum_{j=i}^{r} x_jy_j,
xi=maxj=iraj,yi=maxj=irbj,fi=∑j=irxjyj,那么对于我们所询问的区间
(
l
,
r
)
，
(l,r)，
(l,r)，我们所要求的答案就是
∑
i
=
l
r
f
i
。
\sum_{i=l}^{r} f_i。
∑i=lrfi。
20
p
t
s
20pts
20pts
//暴力做法
//20pts
#include<bits/stdc++.h>
using namespace std;
#define LL long long//数据较大，要开long long
const int N = 3e5;
struct Node {
int l, id;
};
LL read(){
LL x=0,f=1;
char ch=getchar();
while(ch<'0' || ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
vector<Node> d[N];//将询问存在vector里
LL a[N], b[N];
LL f[N];
LL x[N], y[N];
LL ans[N];//记录答案
int main() {
int t;
int n, q;
t=read();
n=read();
//小n队
for (int i = 1; i <= n; i++) {
a[i]=read();
}
//小o队
for (int i = 1; i <= n; i++) {
b[i]=read();
}
//比赛场数
q=read();
for (int i = 1; i <= q; i++) {
int l, r;
//比赛参数
l=read(),r=read();
d[r].push_back({l, i});
}
//将所有询问按照右端点排序
// 对所有访问按照r从小到大来
for (int r = 1; r <= n; r++) {
for (int i = 1; i <= r; i++) {
// 考虑到r
// 两个数组的最大值
x[i] = max(x[i], a[r]);
y[i] = max(y[i], b[r]);
//f[i]对于每个r,x[i]*y[i]的累加和,相当于固定左端点是i,右端点是[i,r]任意数的贡献和
f[i] += x[i] * y[i];
}
// 答案为\sum _{i=l}^{r}f_i
// 转换为将p固定住，将q移动
for (auto [l, id] : d[r]) {
for (int i = l; i <= r; i++)
ans[id] += f[i];
}
}
for (int i = 1; i <= q; i++) {
printf("%lld\n", ans[i]);
}
// 时间复杂度O(n^2+nq)
return 0;
}
正解
考虑优化，用线段树来维护
f
i
f_i
fi这样
O
(
l
o
g
n
)
O(log n)
O(logn)的时间能求出
∑
i
=
l
r
f
i
\sum_{i=l}^{r}f_i
∑i=lrfi。
用单调栈或者 DP 预处理出
a
,
b
a,b
a,b 数组每个元素作为最大值往左能控制到的最远位置，这样每个
a
r
a_r
ar只会更新一段后缀的
x
i
,
b
r
x_i,b_r
xi,br也同理，都利用线段树来做区间覆盖。也就说，每到一个新的
r
r
r在回答询问前进行下面
3
3
3个步骤:
- 区间更新一段后缀的 x i x_i xi为 a r a_r ar。
- 区间更新一段后缀的 y i y_i yi为 b r b_r br。
- 在 [ l , r ] [l,r] [l,r]区间每个 f i f_i fi上加上 x i ∗ y i x_i*y_i xi∗yi。
线段树记录四个信息 s s s表示 f i f_i fi的区间和， x y xy xy表示区间内 ∑ x i y i , x \sum{x_i}{y_i},x ∑xiyi,x表示区间内 ∑ x i , y \sum{x_i},y ∑xi,y表示区间内$\sum{y_i}。
定义6个延迟标记， c x , c y c_x,c_y cx,cy是覆盖标记，后面四个标记 a d d x y , a d d x , a d d y , a d d c add_{xy},add_x,add_y,add_c addxy,addx,addy,addc分别为 ∑ x i y i , ∑ x i , ∑ y i , ∑ 1 \sum{x_i}{y_i},\sum{x_i},\sum{y_i},\sum{1} ∑xiyi,∑xi,∑yi,∑1(相当于于区间长度)的增量，也就是各自增加的倍数。
规定延迟标记的优先级为，加标记应用在覆盖标记之前，这样在下传的时候，下传的加标记会作用在原先的信息上。也就是说，如果原先存在覆盖标记，下传的加标记会退化 。
对于区间信息的更新，首先
s
s
s应该加上
a
d
d
x
y
∗
∑
x
i
y
i
+
a
d
d
x
∗
∑
x
i
+
a
d
d
y
∗
∑
y
i
+
a
d
d
c
∗
∑
1
add_{xy}*\sum{x_iy_i}+add_{x}*\sum{x_i}+add_{y}*\sum{y_i}+add_{c}*\sum{1}
addxy∗∑xiyi+addx∗∑xi+addy∗∑yi+addc∗∑1,然后根据是否有覆盖标记来更新
∑
x
i
y
i
,
∑
x
i
,
∑
y
i
,
\sum{x_iy_i},\sum{x_i},\sum{y_i},
∑xiyi,∑xi,∑yi,时间复杂度为$O((n+q)logn)。
c
o
d
e
code
code
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
const int N = 250005;
struct Qode {
int l, id;
};
vector<Qode> d[N];
ULL a[N], b[N];
ULL ans[N];
int la[N], lb[N];
struct Node {
ULL s, xy, x, y;
} tr[N << 2];
struct Tag {
// 先应用加标记，再应用覆盖标记
ULL cx, cy; //覆盖标记,0 表示无覆盖
ULL add_xy, add_x, add_y, add_c;
} lazy[N << 2];
void push_up(int u) {
tr[u] = {tr[u << 1].s + tr[u << 1 | 1].s,
tr[u << 1].xy + tr[u << 1 | 1].xy,
tr[u << 1].x + tr[u << 1 | 1].x,
tr[u << 1].y + tr[u << 1 | 1].y};
}
void gx(int u, int len, Tag t) {
// 标记更新标记
auto &[cx, cy, add_xy, add_x, add_y, add_c] = lazy[u];
if (cx && cy) {
add_c += t.add_xy * cx * cy + t.add_x * cx + t.add_y * cy + t.add_c;
} else if (cx) {
add_c += t.add_x * cx + t.add_c;
add_y += t.add_xy * cx + t.add_y;
} else if (cy) {
add_c += t.add_y * cy + t.add_c;
add_x += t.add_xy * cy + t.add_x;
} else {
add_xy += t.add_xy;
add_x += t.add_x;
add_y += t.add_y;
add_c += t.add_c;
}
if (t.cx) cx = t.cx;
if (t.cy) cy = t.cy;
// 标记更新信息
auto &[s, xy, x, y] = tr[u];
s += t.add_xy * xy + t.add_x * x + t.add_y * y + t.add_c * len;
if (t.cx && t.cy) {
xy = t.cx * t.cy * len;
x = t.cx * len;
y = t.cy * len;
} else if (t.cx) {
xy = t.cx * y;
x = t.cx * len;
} else if (t.cy) {
xy = t.cy * x;
y = t.cy * len;
}
}
void push_down(int u, int len1, int len2) {
if (lazy[u].cx || lazy[u].cy || lazy[u].add_xy || lazy[u].add_x || lazy[u].add_y || lazy[u].add_c) {
gx(u << 1, len1, lazy[u]);
gx(u << 1 | 1, len2, lazy[u]);
lazy[u] = {0, 0, 0, 0, 0, 0};
}
}
void update(int u, int l, int r, int x, int y, Tag t) {
if (x <= l && r <= y) {
gx(u, r - l + 1, t);
return;
}
int mid = l + r >> 1;
push_down(u, mid - l + 1, r - mid);
if (x <= mid) update(u << 1, l, mid, x, y, t);
if (y > mid) update(u << 1 | 1, mid + 1, r, x, y, t);
push_up(u);
}
ULL query(int u, int l, int r, int x, int y) {
if (x <= l && r <= y) return tr[u].s;
int mid = l + r >> 1;
push_down(u, mid - l + 1, r - mid);
ULL res = 0;
if (x <= mid) res += query(u << 1, l, mid, x, y);
if (y > mid) res += query(u << 1 | 1, mid + 1, r, x, y);
return res;
}
int main() {
int n, q;
scanf("%*d%d", &n);
a[0] = b[0] = 1e9;
for (int i = 1; i <= n; i++) {
scanf("%llu", &a[i]);
la[i] = i;
while (a[i] > a[la[i] - 1]) la[i] = la[la[i] - 1];
}
for (int i = 1; i <= n; i++) {
scanf("%llu", &b[i]);
lb[i] = i;
while (b[i] > b[lb[i] - 1]) lb[i] = lb[lb[i] - 1];
}
scanf("%d", &q);
for (int i = 1; i <= q; i++) {
int l, r;
scanf("%d%d", &l, &r);
d[r].push_back({l, i});
}
for (int r = 1; r <= n; r++) {
update(1, 1, n, la[r], r, (Tag){a[r], 0, 0, 0, 0, 0});
update(1, 1, n, lb[r], r, (Tag){0, b[r], 0, 0, 0, 0});
update(1, 1, n, 1, r, (Tag){0, 0, 1, 0, 0, 0});
for (auto [l, id] : d[r]) {
ans[id] = query(1, 1, n, l, r);
}
}
for (int i = 1; i <= q; i++) printf("%llu\n", ans[i]);
return 0;
}
喵了个喵
看到这个题我真想 m l g b mlgb mlgb道题怎么说呢，很考思维，上次去潍坊培训，老师也说这道题糖丸了，所以昨天这道题我压根都没看，看了题解还一知半解，所以写个部分分出来。
当 k = 2 ( n − 1 ) k=2(n-1) k=2(n−1) 时，这个时候就可以在每个栈中放入两个元素，然后留出来一个特殊栈，特殊栈就是要消元素用的。
这样对于某个栈, 来一个属于该栈的卡牌时, 若和底部卡牌相同就利用特殊栈进行 2 操作, 否则就直接放上去。这样可以保证每时每刻, 前 n − 1 n-1 n−1 个栈的卡牌个数不超过 2 。
当 k = 2 n − 1 k=2n−1 k=2n−1 时, 此时会出现一种情况: n − 1 n−1 n−1 个栈都包含 2 2 2个卡牌了, 此时又来最后一种卡牌。
设该卡牌为 w w w, 找到 $n − 1 $ 个放满的栈中底部卡牌之后最先出现的栈 x , x x,x x,x栈底设为 u u u, 栈顶设为 v v v , 分下面三种情况讨论:
若
w
w
w 的下一次出现时间早于
u
u
u , 那么可以
w
w
w 直接放到特殊栈（因为特殊栈的作用是消除底部, 在
u
u
u 下次出现之前都不会用到特殊栈）
若
u
u
u下次出现时间早于
v
v
v , 那么可以把
w
w
w放到
x
x
x 顶部（虽然此时栈内会有 3 个卡牌导致中间的
v
v
v无法消除，但是
u
u
u 会早于
v
v
v 离开）
剩下的情况意味着下次出现的时间是
v
<
u
<
w
v<u<w
v<u<w ，那么可以把 w 放到特殊栈，然后规定接下来的特殊栈改为 x （很明显在 x清空之前，都不会存在 2 操作，所以没影响）
优化成 O ( m ) 要注意几个点:
需要一个数组维护每个卡牌当前所在栈的编号
需要一个队列来分配每个新来的卡牌属于哪个普通栈的，初始每个普通栈能提供两个空位，卡牌出栈会归还空位
查找下一个最先出现底部元素的栈，可以暴力往后找，因为下一次再出现放满栈的局面一定在底部元素出栈后（若是第一种情况 w 先出，就循环到下个 w 结束）。这样所有暴力找的部分不会有交叉, 总循环次数不超过
m
m
m。
#include <bits/stdc++.h>
using namespace std;
struct Node {
int op, x, y;
};
int main() {
int _;
scanf("%d", &_);
while (_--) {
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
vector<int> a(m + 1);
vector<Node> ans;
vector<int> home(k + 1); //每个卡片所属的栈编号
vector<deque<int>> s(n + 1); //栈
queue<int> q; //可以分配的栈的编号
int kong = n; //特殊栈编号
for (int i = 1; i < n; i++) q.push(i), q.push(i); //除了特殊栈 每个栈可以提供两个空位
for (int i = 1; i <= m; i++) {
scanf("%d", &a[i]);
}
auto cz1 = [&](int x, int t) {
ans.push_back({1, x, 0});
if (s[x].size() > 0 && s[x].back() == t) {
s[x].pop_back();
if (x != kong && s[x].size() < 2) q.push(x);
home[t] = 0;
} else {
s[x].push_back(t);
home[t] = x;
}
};
auto cz2 = [&](int x, int y) {
ans.push_back({2, x, y});
home[s[x][0]] = 0;
s[x].pop_front();
s[y].pop_front();
if (s[x].size() < 2) q.push(x);
};
for (int i = 1; i <= m; i++) {
int x = home[a[i]];
if (x) {
if (s[x].size() == 1)
cz1(x, a[i]);
else if (s[x].back() == a[i])
cz1(x, a[i]);
else {
cz1(kong, a[i]);
cz2(x, kong);
}
continue;
}
if (q.size() > 0) {
x = q.front();
q.pop();
cz1(x, a[i]);
continue;
}
// 此时除特殊栈外，其他栈都有两个元素
// 找到底部最早出来的栈x 暴力找不会有交叉 保证复杂度O(m)
for (int j = i + 1;; j++) {
if (a[j] == a[i]) {
break;
}
if (s[home[a[j]]][0] == a[j]) {
x = home[a[j]];
break;
}
}
if (x == 0) { //把a[i]放入特殊栈不影响
cz1(kong, a[i]);
} else {
int u = s[x].front(), v = s[x].back();
for (int j = i + 1;; j++) {
if (a[j] == u) {
cz1(x, a[i]); //底部先出，放到x此时会有3个元素
break;
}
if (a[j] == v) {
// 顶部先出，把x作为特殊栈
cz1(kong, a[i]);
q.push(kong); //kong这个栈还能放一个元素
kong = x;
break;
}
}
}
}
printf("%d\n", ans.size());
for (auto [op, x, y] : ans) {
if (op == 1)
printf("1 %d\n", x);
else
printf("2 %d %d\n", x, y);
}
}
return 0;
}