题意
给定 \(N\) 个小车,每个小车的编号分别为:\(1,2,\dots,N\)。
现在有 \(Q\) 个操作,每个操作执行 \(3\) 种操作:
1 x y
,将 \(x\) 和 \(y\) 相连。(\(y\) 在 \(x\) 之后)2 x y
,将 \(x\) 和 \(y\) 的连接解除。3 x
,输出 \(x\) 所在链的长度,及其这条链中的所有元素。(从前往后)
思路
我们可以定义一个结构体 \(a\),对于每一个 \(a_i\) 我们保存一个 \(l\) 和 \(r\),分别记录 \(i\) 的前一辆车的编号和 \(i\) 后一辆车的编号。
- 对于操作 1,我们只需要将 \(a_x\) 的 \(r\) 设为 \(y\),\(a_y\) 的 \(l\) 设为 \(x\) 即可。
- 对于操作 2,我们只需要将 \(a_x\) 的 \(r\) 设为 \(0\),\(a_y\) 的 \(l\) 设为 \(0\) 即可。
- 对于操作 3,我们可以从 \(x\) 这个点开始一直通过 \(x \leftarrow a_{x,l}\) 走到这条链的开端,再通过 \(x \leftarrow a_{x,r}\) 的方式走到链的结尾即可。(过程中需要记录一下链中的信息和长度)
Code
#include <bits/stdc++.h>
#define re register
using namespace std;
const int N = 1e5 + 10;
int n,q;
int ans[N];
struct node{
int l;
int r;
}arr[N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
int main(){
n = read();
q = read();
while (q--){
int op;
op = read();
if (op == 1){
int x,y;
x = read();
y = read();
arr[x].r = y;
arr[y].l = x;
}
else if (op == 2){
int x,y;
x = read();
y = read();
arr[x].r = 0;
arr[y].l = 0;
}
else{
int x;
int idx = 0;
x = read();
while (arr[x].l) x = arr[x].l;
while (arr[x].r){
ans[++idx] = x;//记录
x = arr[x].r;
}
ans[++idx] = x;
printf("%d ",idx);
for (re int i = 1;i <= idx;i++) printf("%d ",ans[i]);
puts("");
}
}
return 0;
}
标签:Play,ABC225D,题解,int,while,编号,操作
From: https://www.cnblogs.com/WaterSun/p/18261953