题解：P12542 [APIO2025] 排列游戏
liuzhangfeiabc · · 题解
题目大意：给定一个长为
你要先求出：在两人的最优策略下，最终排列有多少个数归位（即
数据范围：
Warning：本题思维复杂性较高，阅读本题解之前请确保你处于大脑清醒的状态。
先看一些简单的 Case:
m=2
相当于你可以每次直接交换排列的两个位置，那么就非常简单了：你只需要贪心地每次把一个数归位，至多
e>m
这是本题的第一个重要的观察：为什么
答：此时你无能为力，初始排列直接就是最优解。
为什么？我们直接证明一个更强的结论：只要图中有
考虑图中一个点
由于图中所有的点权是两两不同的，因此上述两种情况在一个点
因此，如果图中存在
那么问题来了：一张简单连通图没有
此外，容易看出当未归位的点数不超过
e=m-1
链的情况，我们开始进行一些真正接近题目本质的分析。
对于任意排列
假设我们交换了两个位置
- 如果
i,j 原本不在同一个环上，这次交换会将两个环直接合并； - 如果
i,j 原本在同一个环上，假设环大小为p ，两点在环上的距离为q ，则这次交换会将环拆分为两个环，大小分别为q 和p-q 。 - 特别地，交换同一个环上相邻的两个位置会增加一个归位的点（因为多了一个大小为
1 的环）。
然后我们有如下几种操作：
- “强制归位”：对于一个大小
\ge m 的环，只需要顺次选择环上m 个相邻的点，交互库就必然要选择两个相邻点交换使得多一个点归位； - “强制合并”：对于两个大小加起来
\ge m 的环，可以在一个环上顺次选一些相邻的点，再在另一个环上顺次选一些相邻的点，这样交互库就要么选择一个环上的相邻两个点（这会让一个点归位）要么选择两个环上的点（这会合并这两个环）。这一操作也可以推广到多个环上，只要这些环大小之和\ge m ，就逼迫交互库选择其中相邻两个环进行合并。
基于这两种操作我们可以轻松解决链的情况：只需要先将所有环全都合并起来，再每次强制归位一个点，就能操作到仅剩
e=m
接下来是环的情况，在展开更详细的分类讨论之前，首先要说明环相对于链的一些不同之处。
- 对于“强制合并”影响不大，只不过在多个环时让交互库多了一种将首尾两个环合并的选择；
- 然而对于“强制归位”的影响是关键的，因为这相当于在链的情形中增加了允许交互库选择链的首尾两个点，这会导致环断成两段而不是恰好拆出一个点。因此如果你还想达到强制归位的效果，就只能在大小恰好等于
m 的环上执行。 - 那么遇到更大的环该怎么办？为此我们必须开发出一种“强制拆分”操作：对于某个你想要的拆分距离
d ，如果我们能在当前这个环上选取一系列点，使得（包括首尾在内，下同）相邻两个点的距离要么是1 要么是d ，那么交互库为了不增加归位的点数就必须选择两个间距为d 的点。如下图就是d=2 的情形，分为m 是偶数/奇数两种情形，对应的选取序列分别为0, 2, 4, \dots, m-2, m-1, m-3, \dots, 1 和0, 2, 4, \dots, m-1, m-2, m-4, \dots,1 。需要注意的是，这样的操作并不是我们随心所欲的，需要根据m,d 和具体的环大小构造方案。
再讨论一些比较平凡的界：
- 对于剩余点数小于
m 的情形，显然没法继续操作了； - 对于剩余点数恰为
m 的情形，可以将所有环合并成一个之后归位一次，得到剩余m-1 个点即为最优； - 对于剩余点数恰为
m+1 的情形，也没法更进一步了，因为想要更进一步就必须先搞出大小为m 的环，但若果真如此那么剩下一个点已经自动归位了，于是就矛盾了。
那么问题来了：当剩余点数更多时，是否总能操作到只剩
e=m=\texttt{奇数}
先看
那么偶环呢？很遗憾，对于偶环我们又无能为力了。具体而言，考虑当前排列里的奇环总数（包括大小为
证明很简单：如果想使得奇环的数量增加，唯有将一个偶环拆分成两个奇环。然而如果我们将偶环进行间隔二染色，再选出
基于上述分析，当前排列中奇环的数量就成了答案的上界。对于
然而，当
所以我们可以优先取出一个最大的奇环，首先考虑将其与所有的偶环合并，直到大小不小于
注意到一旦合并出了第一个不小于
于是我们就完成了
e=m=4
来到了
此时的理论上限是剩余
- 对于
4 元环可以归位一个点； - 对于
\ge 6 的环，可以从中拆下来一个4 元环，选取点的序列为0, 1, 5, 4 ； - 对于
5 元环，不能直接进行操作，必须先与任意一个环合并； - 对于两个
2 ，可以合并成一个4 ； - 对于两个
3 ，可以合并成一个6 ； - 尽量不要合并
2 和3 ，因为得到5 是不优的。
请注意上面的第二个操作，它可以扩展为一般的偶数
容易看出，只要按照上述操作序列依次执行，除合并
e=m=\texttt{偶数}
终于到了最复杂的情形，我们首先要看一下
- 对于大小为
m+2,m+4, \dots 的环，仍然可以每次拆分一个2 出来，直到变成m ； - 对于大小为
m+3,m+5, \dots 的环，每次拆一个2 只能最终达到m+3 ，再拆成m+1 是没有意义的。因此我们必须要设计从m+3 直接拆出一个3 的策略。
具体方法是对
分类讨论看着很繁琐，其实本质都是同一种方案：先
再加上对小环的合并操作，我们便可以达到剩余
容易想到的操作序列如下：
- 如果存在一个
m ，就进行一次归位； - 如果有两个环大小之和为
m ，合并之； - 如果最大环
\ge {3m \over 2} ，拆出一个m ； - 如果最大环
\ge m+2 但< {3m \over 2} ，拆出一个2 或3 ； - 如果最大的环
=m+1 ，就将其随便合并一个环（例如次大环）； - 如果最大的环
<m ，就从大到小开始合并；例外是如果它与次大环加起来等于m+1 ，就去考虑合并更小的环，除非别无选择。
然而，这样实际上并不能达到
- 将
m-1 和2 合并为m+1 ； - 将
m+1 和2 合并为m+3 ； - 将
m+3 拆分为m 和3 ； - 对
m 执行一次归位变为m-1 ； - 将
m-1 和3 合并为m+2 ； - 将
m+2 拆分为m 和2 ； - 对
m 执行一次归位变为m-1 。
总共使用
怎么办？容易发现这一操作序列即使处理
这启发我们如果场上有
再回看
因此，对于更大的
总结上述的全过程，可以得到如下操作流程：
- 如果有
m ，归位之； - 如果有两个环大小之和为
m ，合并之； - 如果最大环
\ge {3m \over 2} ，拆出一个m ； - 如果最大环
\ge m+2 但< {3m \over 2} ，拆出一个2 或3 ； - 如果最大环
=m+1 ，随便找一个环（如次大环）合并； - 如果最大环
=m-1 且次大环=m-1 ，合并二者； - 如果最大环
=m-1 且次大环=m-2 ，找出第三大环：如果为2 ，则与m-2 合并（避免与m-1 合并得到m+1 ），否则与m-1 合并； - 如果最大环
=m-1 且次大环<m-2 ，就从次大环开始顺次合并（除非次大环与所有更小的环加起来已经不到m 了，就将最大环与次大环合并）； - 如果最大环
<m-1 ，就从最大环开始顺次合并。
分析总的操作次数：
我们要用
首先是最开始要合并出两个
其次进行主操作流程，直至剩余
最后是剩余
综上，在“每
#include <bits/stdc++.h>
using namespace std;
int Bob(std::vector<int> t);
int m,e,n,nwas,cnt;
vector<int> u,v,p;
vector<int> vis,deg;
vector<vector<int>> cycles;
vector<int> cyc_id, cyc_size, cyc_pos; // 一个点所在的环编号、大小以及它在环上的位置
vector<int> cyc_list,cyc_odd,cyc_even; // 按从大到小的顺序排序后的所有环，后面两个是所有的奇环和偶环
vector<int> dfn,map_g; // dfn是图上节点编号的映射,map_g是dfn的逆
vector<vector<int>> edges; // 图上的边
vector<int> oper,oper_tmp; // 操作序列
void get_cycle(){ // 生成排列里所有的环
cycles.clear();
cyc_list.clear();
cyc_odd.clear();
cyc_even.clear();
nwas = 0;
memset(vis.data(),0,sizeof(int) * n);
for(int i = 0;i < n;++i) if(!vis[i]){
if(i == p[i]){ // 把已经归位的去掉
++nwas;
continue;
}
vector<int> q; q.clear(); q.push_back(i); vis[i] = 1;
for(int j = p[i];!vis[j];j = p[j]){
q.push_back(j); vis[j] = 1;
}
int cycle_id = cycles.size(); // 当前环的编号
cyc_list.push_back(cycle_id);
for(int j = 0;j < q.size();++j){
cyc_id[q[j]] = cycle_id; // 所在环编号
cyc_size[q[j]] = q.size(); // 所在环大小
cyc_pos[q[j]] = j; // 所在环上的位置
}
cycles.push_back(q);
}
// 按环长排序
sort(cyc_list.begin(),cyc_list.end(),[=](int x,int y){return cycles[x].size() > cycles[y].size();});
// 将环按奇偶分类
for(int i = 0;i < cyc_list.size();++i){
int x = cyc_list[i];
if(cycles[x].size() % 2) cyc_odd.push_back(x);
else cyc_even.push_back(x);
}
}
int nwdfn;
void dfs(int x){
map_g[x] = nwdfn;
dfn[nwdfn] = x;
++nwdfn;
for(int i = 0;i < edges[x].size();++i){
int y = edges[x][i];
if(map_g[y] != -1) continue;
dfs(y);
}
}
bool chk_deg(){
oper.resize(m); memset(oper.data(),0,sizeof(int) * m);
oper_tmp.resize(m); memset(oper_tmp.data(),0,sizeof(int) * m);
deg.resize(m); memset(deg.data(),0,sizeof(int) * m);
edges.resize(m);
for(int i = 0;i < m;++i) edges[i].clear();
for(int i = 0;i < e;++i){
++deg[u[i]];
++deg[v[i]];
edges[u[i]].push_back(v[i]);
edges[v[i]].push_back(u[i]);
}
for(int i = 0;i < m;++i) if(deg[i] >= 3) return 0;
// 求出图上点编号的映射关系
map_g.resize(m); memset(map_g.data(),-1,sizeof(int) * m);
dfn.resize(m); memset(dfn.data(),-1,sizeof(int) * m);
nwdfn = 0;
if(e == m - 1){ // 链的情况，要从1度点开始dfs
for(int i = 0;i < m;++i) if(deg[i] == 1){
dfs(i);break;
}
}
else dfs(0);
return 1;
}
int get_ans(){
get_cycle();
int ans = nwas;
if(!chk_deg()) return ans; // 有3度及以上的点就GG了
if(m == 2) return n; // 2个点
if(ans > n - m) return ans; // ans已经很大了
if(e == m - 1) return n - m + 1; // 链
if(ans == n - m) return n - m + 1; // 剩下刚好m个点没归位
if(m % 2 == 0) return n - m - 1; // 如果是偶数，则一定能剩下m+1个点
int nwsz = 0;
for(int i = 0;i < cycles.size();++i){
if(cycles[i].size() % 2 == 0) nwsz += cycles[i].size(); // 累加上所有偶环的大小
else ++ans; // 一个奇环意味着答案能+1
}
// 要从大到小检查这些奇环，直到能合并出来一个>=m的为止
bool fg = 0;
for(int i = 0;i < cyc_odd.size() && nwsz < m;++i){
int x = cyc_odd[i];
if(fg){ // 这个奇环已经要被合并了
nwsz += cycles[x].size();
fg = 0;
}
else if(cycles[x].size() + nwsz < m){ // 要付出2的代价合并两个奇环
ans -= 2;
nwsz += cycles[x].size();
fg = 1;
}
else break;
}
return ans;
}
inline void add_node(int &nw, int x){oper[dfn[nw++]] = x;} // 注意要套一层dfn
inline void add_node_cyc(int &nw, int x,int j){
add_node(nw,cycles[x][j]);
}
void get_m(int x){ // 从第x个环上切下长为m的一段来
// 0 1 2 ... m/2-1 3m/2-1 3m/2-2 ... m+1 m
int nw = 0;
for(int i = 0;i < m / 2;++i) add_node_cyc(nw,x,i);
for(int i = m / 2 - 1;i >= 0;--i) add_node_cyc(nw,x,i + m);
}
void get_3(int x){ // 从第x个环上切下长为3的一段来
int j;
int nw = 0;
for(j = 0;(m - j) % 3 != 1;++j){ // 前面%3多出来的部分
add_node_cyc(nw,x,j);
}
for(;j < m;j += 3){ // 间隔3个往前调
add_node_cyc(nw,x,j);
}
int fg = -1;
for(j = m - 2;j > 0;j -= 3 + fg){ // 从m-2开始，按照-1 -3 +1 -3 -1...的模式往回跳
add_node_cyc(nw,x,j);
add_node_cyc(nw,x,j + fg);
fg *= -1;
}
}
void get_2(int x){ // 从第x个环上切下长为2的一段来
int nw = 0;
// 1 3 5 ... m-1 m-2 m-4 ... 2 0
// 正着走，间隔2个放一个
for(int j = 1;j < m;j += 2){
add_node_cyc(nw,x,j);
}
// 倒着走，间隔2个放一个
for(int j = m - 2;j >= 0;j -= 2){
add_node_cyc(nw,x,j);
}
}
void gen_merge2(int x,int y){ // 合并两个环，大小之和至少是m
int nw = 0;
for(int j = 0;nw + 1 < m && j < cycles[x].size();++j){ // 第一个环最多放m-1个点
add_node_cyc(nw,x,j);
}
for(int j = 0;nw < m && j < cycles[y].size();++j){
add_node_cyc(nw,y,j);
}
}
void run(){ // 生成下一个操作序列，存在oper里
if(m == 2){ // 把第一个i!=p[i]的强制归位
for(int i = 0;i < n;++i) if(p[i] != i){
oper[0] = i;
oper[1] = p[i];
return;
}
}
if(e == m - 1 || nwas == n - m){
// 如果是链，或者剩余未归位的总点数恰好等于m，可以直接这么干
int nw = 0;
// 从大到小遍历所有的环，把点顺次加进操作序列
for(int i = 0;nw < m && i < cyc_list.size();++i){
int x = cyc_list[i];
for(int j = 0;nw < m && j < cycles[x].size();++j){
add_node_cyc(nw,x,j);
}
}
return;
}
int xx = -1;
for(int i = 0;i < cycles.size();++i) if(cycles[i].size() == m){
xx = i;break; // 找到了一个大小为m的环
}
if(xx != -1){ // 如果存在一个环刚好大小为m，就可以拆出来一个点
int nw = 0;
for(int j = 0;j < cycles[xx].size();++j){
add_node_cyc(nw,xx,j);
}
return;
}
if(m % 2 == 1){ // 奇环
// 由于还能继续操作，一定还有奇环
int x = cyc_odd[0];
int nw = 0;
if(cycles[x].size() > m){ // 第一个奇环足够大
// 0 2 4 ... m-1 m-2 m-4 ... 3 1
// 正着走，间隔2个放一个
for(int j = 0;j < m;j += 2){
add_node_cyc(nw,x,j);
}
// 倒着走，间隔2个放一个
for(int j = m - 2;j > 0;j -= 2){
add_node_cyc(nw,x,j);
}
return;
}
if(cycles[x].size() == m){ // 第一个奇环刚好是m，就强制拆出来一个点
for(int j = 0;j < cycles[x].size();++j){
add_node_cyc(nw,x,j);
}
return;
}
// 第一个环不够大
// 先把第一个环全都加进去
for(int j = 0;nw < m && j < cycles[x].size();++j){
add_node_cyc(nw,x,j);
}
// 然后把偶环加进去
for(int i = 0;nw < m && i < cyc_even.size();++i){
int x = cyc_even[i];
for(int j = 0;nw < m && j < cycles[x].size();++j){
add_node_cyc(nw,x,j);
}
}
// 最后再加入其余的奇环
for(int i = 1;nw < m && i < cyc_odd.size();++i){
int x = cyc_odd[i];
for(int j = 0;nw < m && j < cycles[x].size();++j){
add_node_cyc(nw,x,j);
}
}
}
else{ // 偶环
int x = cyc_list[0];
int nw = 0;
vector<int> sz;sz.resize(m);memset(sz.data(),-1,sizeof(int) * m);
for(int i = 0;i < cycles.size();++i) if(cycles[i].size() < m){
int nwsz = cycles[i].size();
if(sz[m - nwsz] != -1){ // 这两个环的大小之和刚好是m，合并之
int y = sz[m - nwsz];
gen_merge2(i,y);
return;
}
sz[nwsz] = i;
}
if(cycles[x].size() == m - 1){ // 第一个环是m-1，特殊情况
int y = cyc_list[1];
if(cycles[y].size() == m - 1){ // 第二个环也是m-1，那么把他俩合并
gen_merge2(x,y);
return;
}
int tot_nxt = 0;
for(int j = 1;j < cyc_list.size();++j)
tot_nxt += cycles[cyc_list[j]].size();
if(tot_nxt >= m){
int z = cyc_list[2];
if(cycles[y].size() + cycles[z].size() == m + 1){ // 这种情况让z和x合并
gen_merge2(x,y);
}
else{
// 把剩下的都合并到y上
for(int j = 1;nw < m && j < cyc_list.size();++j){
int w = cyc_list[j];
for(int k = 0;k < cycles[w].size() && nw < m;++k){
add_node_cyc(nw,w,k);
}
}
}
return;
}
// tot_nxt<m的情况不归这里考虑，回归到普通情形
}
if(cycles[x].size() < m){ // 第一个环不够大
// 从大到小遍历所有的环，把点顺次加进操作序列
for(int i = 0;nw < m && i < cyc_list.size();++i){
int x = cyc_list[i];
for(int j = 0;nw < m && j < cycles[x].size();++j){
add_node_cyc(nw,x,j);
}
}
return;
}
if(cycles[x].size() == m + 1){ // 第一个环刚好是m+1，消除不了，要融合进去下一个环
int y = cyc_list[1];
gen_merge2(x,y);
return;
}
if(cycles[x].size() >= 3 * m / 2){ // 第一个环特别大，允许拆出一个m
get_m(x);
return;
}
if(cycles[x].size() != m + 2 && cycles[x].size() != m + 4){ // 精细构造拆出一个3
// update：每次拆下来两个点会有问题，因为每次干掉一个点之后剩下的是m-1，就意味着还需要合并两个2才行
// 所以这里尽可能用了每次拆下来3个点的操作
get_3(x);
return;
}
// 第一个环足够大而且不是m+3，可以每次拆下来两个点
get_2(x);
}
}
int Alice(int _m, int _e, std::vector<int> _u, std::vector<int> _v, int _n, std::vector<int> _p){
m = _m, e = _e, n = _n;
u = _u, v = _v, p = _p;
vis.resize(n); memset(vis.data(),0,sizeof(int) * n);
cyc_id.resize(n); memset(cyc_id.data(),0,sizeof(int) * n);
cyc_size.resize(n); memset(cyc_size.data(),0,sizeof(int) * n);
cyc_pos.resize(n); memset(cyc_pos.data(),0,sizeof(int) * n);
int final_ans = get_ans();
cnt = 0;
while(nwas < final_ans){
++cnt;
run();
int res = Bob(oper);
swap(p[oper[u[res]]], p[oper[v[res]]]);
get_cycle(); // 重新生成环
}
return final_ans;
}