2022 NOIP 题解

建造军营

这道题之前做过一次,我们来转换一下这道题的题意，题中给到了边、点我们可以想到强连通分量，进而想到tarjan算法。通过所给样例及题意，我们可以将原题目转化为以下内容：

给定一张图，选择一些点和边，使得割断任意没有选的边，被选中的点仍联通，最终答案对$10^9+7$取模。

想做这道题，我们得先知道什么是割点、割边（桥）、缩边、双连通分量

看到图和连通，想到tarjan。割断一条没有选的边，选中的点仍连通，割非割边，整张图仍然连通。

把割边删掉，则整张图分成若干连通子图。可以把一张子图看成一个点，这样形成的新图上没有环，因为在环上的边都不是割边，那它就是一棵树。使用vector邻接表建图，dfs一遍，使用$f$数组记录答案，最终将答案转移到$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。
$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$形的左上角 $O(nm)$

然后，我们的目标是：

1. 求出$C$第一行长度的可能结果数
2. 求出$C$ 第一列的可取长度的范围1
3. 求出$C$每一列长度对应的行的可能结果数
4. 目标$1$和目标$3$相乘累加到答案中

以上的步骤全部需要$O(1)$ 完成，所以我们考虑预处理

对于 目标$1$，我们可以预处理出 位置 ( i , j ) (i,j)(i,j) 离右手边最近的障碍的距离。

对于 目标$3$，一个个算肯定是 武则天丧夫 没理智的，但是我们求的是一个区间结果，这个时候就该考虑前缀和

我们用新的数组存储(我们预处理的右手边最近障碍距离)的前缀和，在执行目标$3$时用前缀和作差求出结果。

我们可以再预处理 位置 $(i,j)$ 离正下方最近障碍的距离。那么我们询问的区间就是 $(x+2,j)\sim (x+dis(x),j)$

自此 $c$ 形就解决了！

再考虑$F$形:

如果我们已经确定了 $F$ 形的第二 横，那么可以得到累加多少结果呢？

很显然是 小尾巴 的长度。那么我们对于每一个可能的横都可以预处理出带上小尾巴的结果数，

然后还是熟悉的区间结果查询，我们依旧对上述结果做前缀和。

$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$，记$x_i={\max }_{j=i}^r{a}_j,y_i={\max }_{j=i}^r{b}_j,f_i={\sum }_{j=i}^r{x}_j{y}_j,$那么对于我们所询问的区间$(l,r)，$我们所要求的答案就是${\sum }_{i=l}^r{f}_i。$
$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$这样$O(logn)$的时间能求出${\sum }_{i=l}^r{f}_i$。
用单调栈或者 DP 预处理出$a,b$ 数组每个元素作为最大值往左能控制到的最远位置，这样每个​$a_r$只会更新一段后缀的$x_i,b_r$也同理，都利用线段树来做区间覆盖。也就说，每到一个新的$r$在回答询问前进行下面$3$个步骤:

1. 区间更新一段后缀的$x_i$为$a_r$。
2. 区间更新一段后缀的$y_i$为$b_r$。
3. 在$[l,r]$区间每个$f_i$上加上$x_i\ast y_i$。

线段树记录四个信息$s$表示$f_i$的区间和，$xy$表示区间内$\sum x_i{y}_i,x$表示区间内$\sum x_i,y$表示区间内$\sum{y_i}。

定义6个延迟标记，$c_x,c_y$是覆盖标记，后面四个标记$ad{d}_{xy},ad{d}_x,ad{d}_y,ad{d}_c$分别为$\sum x_i{y}_i,\sum x_i,\sum y_i,\sum 1$(相当于于区间长度)的增量，也就是各自增加的倍数。

规定延迟标记的优先级为，加标记应用在覆盖标记之前，这样在下传的时候，下传的加标记会作用在原先的信息上。也就是说，如果原先存在覆盖标记，下传的加标记会退化 。

对于区间信息的更新，首先$s$应该加上$ad{d}_{xy}\ast \sum x_i{y}_i+ad{d}_x\ast \sum x_i+ad{d}_y\ast \sum y_i+ad{d}_c\ast \sum 1$,然后根据是否有覆盖标记来更新$\sum x_i{y}_i,\sum x_i,\sum y_i,$时间复杂度为$O((n+q)logn)。
$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;
}

喵了个喵

看到这个题我真想$mlgb$道题怎么说呢，很考思维，上次去潍坊培训，老师也说这道题糖丸了，所以昨天这道题我压根都没看，看了题解还一知半解，所以写个部分分出来。

当 $k=2(n-1)$ 时，这个时候就可以在每个栈中放入两个元素，然后留出来一个特殊栈，特殊栈就是要消元素用的。

这样对于某个栈, 来一个属于该栈的卡牌时, 若和底部卡牌相同就利用特殊栈进行 2 操作, 否则就直接放上去。这样可以保证每时每刻, 前$n-1$ 个栈的卡牌个数不超过 2 。

当$k=2n-1$ 时, 此时会出现一种情况: $n-1$ 个栈都包含 $2$个卡牌了, 此时又来最后一种卡牌。

设该卡牌为 $w$, 找到 $n − 1 $ 个放满的栈中底部卡牌之后最先出现的栈$x,x$栈底设为 $u$, 栈顶设为 $v$ , 分下面三种情况讨论:

若 $w$ 的下一次出现时间早于 $u$ , 那么可以 $w$ 直接放到特殊栈（因为特殊栈的作用是消除底部, 在 $u$ 下次出现之前都不会用到特殊栈）
若 $u$下次出现时间早于 $v$ , 那么可以把$w$放到 $x$ 顶部（虽然此时栈内会有 3 个卡牌导致中间的$v$无法消除，但是 $u$ 会早于 $v$ 离开）
剩下的情况意味着下次出现的时间是 $v<u<w$ ，那么可以把 w 放到特殊栈，然后规定接下来的特殊栈改为 x （很明显在 x清空之前，都不会存在 2 操作，所以没影响）
优化成 O ( m ) 要注意几个点:

需要一个数组维护每个卡牌当前所在栈的编号
需要一个队列来分配每个新来的卡牌属于哪个普通栈的，初始每个普通栈能提供两个空位，卡牌出栈会归还空位
查找下一个最先出现底部元素的栈，可以暴力往后找，因为下一次再出现放满栈的局面一定在底部元素出栈后（若是第一种情况 w 先出，就循环到下个 w 结束）。这样所有暴力找的部分不会有交叉, 总循环次数不超过 $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;
}

​

原文地址：https://blog.csdn.net/xiebohang/article/details/143318189

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！