大意: 给定排列p, 0/1序列b, 有n个烤串, 每秒钟第i串会移动到$p_i$, 若$p_i$为1则翻面, 可以修改b和p, 求最少修改次数使得每串在每个位置正反都被烤过.
显然只需要将置换群合并为1个即可, 并且序列b中1的个数要为奇数.
考虑合并置换群的花费, 若置换群初始为1个则花费0, 否则为置换群的个数.
#include <iostream> #include <algorithm> #include <math.h> #include <cstdio> #include <set> #include <map> #include <string> #include <vector> #include <string.h> #include <queue> #define PER(i,a,n) for(int i=n;i>=a;--i) #define REP(i,a,n) for(int i=a;i<=n;++i) using namespace std; const int N = 2e5+10, INF = 0x3f3f3f3f; int n, vis[N], s[N], b[N], p[N]; vector<int> g[N], q; void dfs(int x) { if (vis[x]) return; vis[x] = 1, dfs(p[x]); } int main() { scanf("%d", &n); REP(i,1,n) scanf("%d", p+i); REP(i,1,n) scanf("%d", b+i); int f = 1, ans = 0; REP(i,1,n) f ^= b[i]; REP(i,1,n) if (!vis[i]) ++ans,dfs(i); if (ans==1) ans = 0; printf("%d\n", ans+f); }