題意:
給一個序列,序列值代表對應下標下一秒硬幣要移動到的下標,再給一個相同01序列,1代表在這個位置下一秒硬幣翻轉。問需要修改幾次這兩個序列使得每一枚硬幣經過若干秒后能以正面和反面的姿態都經過過每一個點。
解題思路:
之所以需要修改是硬幣的移動位置會形成循環,而這個循環有可能不是全局的,是分成幾堆硬幣內部循環,我們需要找出這樣硬幣的堆數,如果堆數是一那么正好不用改,如果大于一就需要把這幾堆硬幣串聯再一起,需要的修改數量就是堆數。
而翻轉的序列就很好考慮了,我們只考慮一枚硬幣,這枚硬幣經過其它所以點回到原來點后,如果翻轉次數是偶數,那么回來時的狀態和出發時的狀態是一樣的,這樣就會循環下去,那么肯定是不可以正反兩面都經過每一個點的,所以要求翻轉的次數是奇數。
代碼:
#include <bits/stdc++.h>using namespace std;const int maxn=2e5;int add[maxn];bool rev[maxn];bool vis[maxn];int main(){ int n; scanf("%d", &n); int i; for(i=1; i<=n; i++)scanf("%d", &add[i]); int cir=0; for(i=1; i<=n; i++) { if(vis[i])continue; cir++; int t=i; do { vis[t]=1; t=add[t]; }while(i!=t); } int odd=0; for(i=1; i<=n; i++){scanf("%d", &rev[i]);if(rev[i])odd++;} int ans=0;// PRintf("%d/n", ans); if(odd%2==0)ans++; printf("%d/n", ans+(cir>1?cir:0)); return 0;}
新聞熱點
疑難解答