problem

洛谷鏈接

solution

弱化版：如果不考慮翻面，那就是轉化為若干個環的問題了。

這里我們嘗試用同樣的思路解決。

首先明確幾個硬幣一次交換后的等價情況，如圖（灰色表示反面）

（$u\to v$ 箭頭的意思是硬幣 $u$ 的下標應該在硬幣 $v$ 所在位置）

case1 單獨考慮每個環。初始零狀態，隨便選擇一個硬幣作切入點，破環。

大小為 $x$ 的環，經過 $x?1$ 次操作就可以變到其該在的位置，但是最后會有兩個硬幣是反面的。

顯然，不可能兩步就做到將硬幣再翻面且位置正確。

假設是 $(\bar{a},\bar{b},c)$ 這樣情況的三枚硬幣（括號強調順序，三個硬幣的位置都是對的，但 $a,b$ 目前是反面朝上）。

$(\bar{a},\bar{b},c)\to (b,a,c)\to (b,\bar{c},\bar{a})\to (a,\bar{c},\bar{b})\to (a,b,c)$，一共操作 $4$ 次。符合要求。

由三元環的啟示，我們不妨倒退一個狀態，讓三枚硬幣都還未處于正確的狀態（只要反面或位置不對都不算正確狀態）。

則此時理應用了 $x?2$ 次操作，狀態應是一枚反面正確位置，一枚正面錯誤位置，一枚反面錯誤位置。

接著，$(\bar{a},c,\bar{b})\to (\bar{c},a,\bar{b})\to (\bar{c},b,\bar{a})\to (a,b,c)$，只用三步即可。

這樣就做到了一個 $x$ 的環 $x+1$ 次操作。

case2 但這僅僅是一個環，如果原題中有若干個環，額外次數卻只有 $1$，還是不能通過。

事實上，單環的關鍵就在于每次有且僅有兩枚反面朝上的硬幣。

我們完全可以將兩個環，任意交換一對硬幣，從而是兩環聯通為一環。

這樣花費是 $1$，同樣直接進入單環問題的第一個狀態（即初始有兩個反面朝上的硬幣）。

換言之，兩個環 $x_1,x_2$，只用 $x_1+x_2+1?1$ 步操作便可。

因此，可以兩兩環合并后再操作，就不會產生額外的 $1$。

如果有奇數個環，那么將最后一個環和第一個自環匹配一下，做個工具環即可。

這也是 $m+1$ 的上限來源。

code

#include <bits/stdc++.h> using namespace std; #define maxn 200005 vector < pair < int, int > > ans; int n, cnt; int c[maxn], p[maxn]; bool vis[maxn];void Swap( int x, int y ) {swap( c[x], c[y] );ans.push_back( make_pair( x, y ) ); }void work( int x, int y ) {Swap( x, y );while( c[x] ^ y ) Swap( x, c[x] );while( c[y] ^ x ) Swap( y, c[y] );Swap( x, y ); }int main() {scanf( "%d", &n );for( int i = 1;i <= n;i ++ ) scanf( "%d", &c[i] );for( int i = 1;i <= n;i ++ )if( ! vis[i] ) {p[++ cnt] = i;for( int k = i;! vis[k];k = c[k] ) vis[k] = 1;}if( cnt == 1 ) {int x = p[1], y = c[x];Swap( x, y );while( c[c[x]] ^ x ) Swap( x, c[x] );int z = c[x];Swap( y, z );Swap( x, z );Swap( x, y );}else {for( int i = 1;i + 1 <= cnt;i += 2 ) work( p[i], p[i + 1] );if( cnt & 1 ) work( p[1], p[cnt] );}printf( "%d\n", ans.size() );for( int i = 0;i < ans.size();i ++ ) printf( "%d %d\n", ans[i].first, ans[i].second );return 0; }

總結

以上是生活随笔為你收集整理的CodeForces 1491G Switch and Flip（结论）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。