2022 NOIP 题解

news/2024/11/2 14:25:49/

建造军营

这道题之前做过一次,我们来转换一下这道题的题意,题中给到了边、点我们可以想到强连通分量,进而想到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中依次取出元素赋值给yif (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)

然后,我们的目标是:

  1. 求出 C C C第一行长度的可能结果数
  2. 求出 C C C 第一列的可取长度的范围1
  3. 求出 C C C每一列长度对应的行的可能结果数
  4. 目标 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个步骤:

  1. 区间更新一段后缀的 x i x_i xi a r a_r ar
  2. 区间更新一段后缀的 y i y_i yi b r b_r br
  3. [ l , r ] [l,r] [l,r]区间每个 f i f_i fi上加上 x i ∗ y i x_i*y_i xiyi

线段树记录四个信息 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} addxyxiyi+addxxi+addyyi+addc1,然后根据是否有覆盖标记来更新 ∑ 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(n1) 时,这个时候就可以在每个栈中放入两个元素,然后留出来一个特殊栈,特殊栈就是要消元素用的。

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

k = 2 n − 1 k=2n−1 k=2n1 时, 此时会出现一种情况: n − 1 n−1 n1 个栈都包含 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);elseprintf("2 %d %d\n", x, y);}}return 0;
}


http://www.ppmy.cn/news/1543891.html

相关文章

redis分布式锁在项目中的应用总结

项目应用 应用1 redis分布式锁实现两个操作的原子性 需求&#xff1a;实现一人一单业务逻辑时&#xff08;如果能走到这个逻辑&#xff0c;代表库存是充足的&#xff09;&#xff0c;我们需要 先查询订单 如果订单不存在即没有买过则创建订单 这两个步骤我们要保证是原子…

6、磁盘管理

如何对硬盘进行分区&#xff1f;创建文件系统&#xff1f;挂载&#xff1f; 如何自动挂载&#xff1f; 硬盘概念 基本概念 硬盘是一种计算机的存储设备&#xff0c;通常是由一个或多个磁盘片组成&#xff0c;硬盘可以安装在计算机的内部&#xff0c;也可以外接计算机&#x…

【搜索引擎】俄罗斯搜索引擎yandex

俄罗斯搜索引擎yandex 1997年&#xff0c;俄罗斯搜索引擎Yandex&#xff08;俄语意为&#xff1a;语言目录&#xff09;首次上线&#xff0c;已发展成为全球第四大搜索引擎和第二大非英语搜索引擎 https://yandex.com/

新能源汽车火灾应急处置程序

摘要&#xff1a;新能源汽车在人们的日常生活中被广泛应用&#xff0c;但其消防安全问题也逐渐凸显。本文分析了新能源汽车的起火原因、燃烧危害性&#xff0c;并着重阐述了新能源汽车发生火灾后消防应急处置程序及应对措施等。 关键词&#xff1a;新能源汽车&#xff1b;火灾…

opencascade源码学习之Convert包

Convert_CircleToBSplineCurve 圆转多义线 Convert_CircleToBSplineCurve Convert_CompBezierCurves2dToBSplineCurve2d Bezier转样条曲线 Convert_CompBezierCurvesToBSplineCurve non-rational Bezier curve转样条曲线 Convert_CylinderToBSplineSurface 圆柱体转换为…

【AI开源项目】FastGPT- 快速部署FastGPT以及使用知识库的两种方式!

文章目录 一、FastGPT大模型介绍1. 开发团队2. 发展史3. 基本概念 二、FastGPT与其他大模型的对比三、使用 Docker Compose 快速部署 FastGPT1、安装 Docker 和 Docker Compose&#xff08;1&#xff09;. 安装 Docker&#xff08;2&#xff09;. 安装 Docker Compose&#xff…

【django】django RESTFramework前后端分离框架快速入门

目录 一、搭建项目开发环境 1.1 pycharm创建项目 1.2 修改配置settings.py 1.3 新增 static与staticfiles文件夹 1.4 生成数据表 1.5 创建超级用户 1.6 启动项目 二、安装REST_Framework 2.1 安装 2.2 配置settings 2.3 重新执行生成数据库脚本 三、修改路由 四、s…

【WPF】如何使用异步方法

【WPF】如何使用异步方法 1. 定义一个异步方法2. 调用异步方法3. 更新UI4. 错误处理小结 1. 定义一个异步方法 首先&#xff0c;需要将你的耗时操作方法标记为 async&#xff0c;并返回一个 Task 对象。使用 Task.Run 将耗时操作放在一个新的线程中执行。这样&#xff0c;主线程…