E
$n$ 个顶点的树，初始时每条边为蓝色，执行 $n-1$ 次操作：选定只包含蓝色边的路径 $u\rightarrow v$ ，并移除路径上的某一条蓝边，并加入一条 $u\rightarrow v$ 的红边。问是否能让最终的红树与给定的红树相同
开始时状态不好考虑，先考虑最后一步操作时：蓝边一定同时存在于蓝树和红树上
可以找到任意一条这样的边，分别在红蓝图上合并两端的点，剩下继续处理子问题
用并查集合并节点，暴力遍历出度数小的点进行启发式合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| const int N=5e5+10;
int n,d[N];
queue<PII> q;
set<int> e[N];
map<PII,int> s;
struct DSU{
int fa[N];
inline void init(int n){ for(rei i=1;i<=n;i++) fa[i]=i;}
int find(int x){ return fa[x]==x ? x : fa[x]=find(fa[x]);}
}dsu;
inline PII get(int x,int y){return mk(min(x,y),max(x,y));}
inline void ins(int x,int y){
e[x].insert(y),e[y].insert(x);
PII now=get(x,y); ++s[now];
if(s[now]==2) q.push(now);
}
int main(){
scanf("%d",&n);
dsu.init(n);
for(rei i=1,u,v;i<n*2-1;i++) scanf("%d%d",&u,&v),ins(u,v);
for(rei i=1,x,y;i<n;i++){
while(1){
if(!q.size()) return puts("NO"),0;
PII top=q.front(); q.pop();
x=dsu.find( top.first ),y=dsu.find( top.second );
if(x!=y) break;
}
if(e[x].size()>e[y].size()) x^=y,y^=x,x^=y;
dsu.fa[x]=y;
s.erase(get(x,y)),e[y].erase(x);
for(set<int>::iterator it=e[x].begin();it!=e[x].end();++it){
rei t=dsu.find(*it);
if(t==y) continue;
s.erase(get(x,t)); ins(t,y);
e[t].erase(x),e[x].erase(t);
}
}
puts("YES");
getchar(),getchar();
return 0;
}
|
F
给定长度 $n$ 排列 $P$ ，对其进行奇怪排序直至升序：
对于每一轮： 找到序列 $P$ 的所有前缀最大值（ $P_i$ 为前缀最大值当且仅当 $\forall 1\leq j\leq i \quad 有 P_j\leq P_i$），取出所有前缀最大值并按照原顺序移到队尾
求至少需要多少轮才能对 $P$ 排序
定义 $high$ 为前缀最大值, $low$ 为前缀最小值
假设忽略 $1$ ，用 $T$ 次排列好 $[2,n]$ ，答案就是 $T/T+1$
考虑 $T-1$ 轮后序列状态：设 $f$ 为第一个数，如果 $1$ 出现在 $f,2$ 之间则答案为 $T$ ，否则为 $T-1$
结论 $1$ : $f$ 不会出现：不在第一个位置且为 $high$ 的情况
反证法易得
结论 $2$ : 定义循环序列 $(a,b,c)=(b,c,a)=(c,a,b)$ ，则 $1,2,f$ 在前 $T-1$ 次组成的，关于位置的循环序列不变
考虑 $[i,n]$ ，设 $T_i$ 为对该序列排序需要的操作数
设 $f_i$ 为 $T_i-1$ 次操作后的第一个整数 ，$q_i$ 为 $i$ 在初始序列中的位置( $p_{q_i}=i$ ) 。按照 $i=n\sim 1$ 的顺序计算 $T_i,f_1$ ，答案就为 $T_1$
- 若 $T_{i+1}=0$
- 若 $q_i>q_{i+1}$ ，则 $T_i=1,f_i=i+1$
- 否则 $T_i=0,f_i无$
- 否则
- 若 $q_{f_{i+1}},q_i,q_{i+1}$ 处于循环顺序，则 $T_i=T_{i+1},f_i=f_{i+1}$
- 否则 $T_i=T_{i+1}+1,f_i=i+1$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| const int N=2e5+100;
int q[N],p[N],n,T[N],f[N];
int main(){
scanf("%d",&n);
for(rei i=1;i<=n;++i) scanf("%d",&p[i]),q[ p[i] ]=i;
for(rei i=n-1;i;--i){
if(!T[i+1])
if(q[i]>q[i+1]) T[i]=1,f[i]=i+1;
else T[i]=0;
else{
rei cnt=0;
cnt+=q[ f[i+1] ]<q[i];
cnt+=q[i]<q[i+1];
cnt+=q[i+1]<q[ f[i+1] ];
if(cnt==2) T[i]=T[i+1],f[i]=f[i+1];
else T[i]=T[i+1]+1,f[i]=i+1;
}
}
printf("%d\n",T[1]);
getchar(),getchar();
return 0;
}
|