Codeforces Round 797 (Div. 3) F Shifting String

思路：

根据这个排列进行替换的操作可以往置换环考虑，就是对于每一段字串，它的变换都是有规律的，经过一定的操作之后都会回到原点，可以想象转化成图上问题。

参考ygg的题解，直接用链表模拟这个转化的过程，然后暴力计数，因为要满足所有点都回到对应原位，所以求所有满足条件的长度之后求lcm即可

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
const int N = 200+10,mod = 1e9+7;

int p[N];
bool v[N];
vector<int> c;
void dfs(int x){//找到完整的一个环并且存在vector c中
	if(v[x])return;
	v[x] = 1;
	c.push_back(x);
	dfs(p[x]);
}
void solve() {
	int n;
	string s;
	cin >> n >> s;
	s = " " + s;
	for(int i = 1; i <= n; i ++) cin >> p[i],v[i] = 0;
	int res = 1;
	for(int i = 1; i <= n; i ++){
		if(!v[i]){
			c.clear();
			dfs(i);
			list<char> pres,nows;
//			for(int j = i; v[j]; v[j] = 1, j = p[j])
//				pres.push_back(s[j]);
			for(auto id: c) pres.push_back(s[id]);
			nows = pres;
			nows.push_back(nows.front());//把头结点移动到尾部，就是模拟这个环上的点移动的过程
			nows.pop_front();
			int t = 1;
			while(pres != nows){
				nows.push_back(nows.front());
				nows.pop_front();
				t ++;//不断重复上述操作然后计数
			}
			res = res * t /__gcd(res,t);
		}
	}
	
	cout << res <<'\n';

}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int _t = 1;
	cin >> _t;
	while(_t --)
		solve();
	
	return 0;
}

Educational Codeforces Round 4, E Square Root of Permutation

参考ygg的题解，补充注释

代码

#include<bits/stdc++.h>
//#define int long long
using namespace std;
typedef pair<int,int> pii;
const int N = 1e6+10,mod = 1e9+7;


int ans[N],p[N],vis[N],n;
vector<int> c;
vector<vector<int>> cyc[N]; //cyc[i]存的是大小为i的每个环 每个环用一个vector来存
void update(vector<int> x){//把环还原成排列
	for(int i = 1; i < x.size(); i++){
		ans[x[i-1]] = x[i];
	}
	ans[x.back()] = x[0];
}
void dfs(int u){
	if(vis[u]) return;
	vis[u] = 1;
	c.push_back(u);
	dfs(p[u]);
}

void solve() {
	cin >> n;
	for(int i = 1; i <= n; i ++) ans[i] = i,cin >> p[i];
	for(int i = 1; i <= n;i ++){
		if(!vis[i]){
			c.clear();
			dfs(i);//把排列拆成各种大小的环
			cyc[c.size()].push_back(c);
		}
	}
	for(int sz = 1; sz <= n; sz ++){
		if(sz%2 == 0 && cyc[sz].size() % 2 == 1){
			cout << "-1\n";
			return;
		}
	}
	for(int sz = 1; sz <= n; sz ++){
		if(sz%2 == 1){
			for(auto c: cyc[sz]){//遍历大小为奇数的环
				vector<int> now(c.size());
				int id = 0;
				for(auto it: c){
					now[id % c.size()] = it;
					id+=2;
				}
				update(now);
			}
		} else {//遍历大小为偶数的环
			for(int i = 0; i < cyc[sz].size(); i += 2){
				vector<int> c1 = cyc[sz][i],c2 = cyc[sz][i+1];//每次c1，c2代表合成一对的环
				vector<int> now;//now存合成的环，交替放入now中
				for(int i = 0; i < c1.size(); i ++){
					now.push_back(c1[i]);
					now.push_back(c2[i]);
				}
				update(now);
			}
		}
	}
	
	for(int i = 1; i <= n ;i ++) cout << ans[i] << " ";
	cout <<'\n';
	
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int _t = 1;
	//cin >> _t;
	while(_t --)
		solve();
	
	return 0;
}

Codeforces Round 789 (Div. 2) E Tokitsukaze and Two Colorful Tapes

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
const int N = 1e5+10,mod = 1e9+7;

int a[N],b[N],to[N];
bool v[N];
vector<int> c;

void dfs(int x){
	if(v[x]) return;
	v[x] = 1;
	c.push_back(x);
	dfs(to[x]);
}
void solve() {
	int n;
	cin >> n;
	for(int i = 1; i<= n;i ++) v[i] = 0;
	int mi = 1,mx = n;
	for(int i = 1; i<= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++) cin >> b[i],to[a[i]] = b[i];
	int ans = 0;
	
	auto cal=[&](){
		if(c.size() == 1) return 0ll;
		vector<int> v;
		for(int i = 0; i < c.size() - c.size() % 2; i ++){
			if(i%2 == 0) v.push_back(mx--);
			else v.push_back(mi ++);
		}
		int res = 0;
//		for(auto i:v){
//			cout << i <<" ";
//		}
//		cout << '\n';
		for(int i = 1; i < v.size(); i ++) {
			res += abs(v[i] - v[i - 1]);
		}
		res += abs(v.back() - v[0]);
		return res;
	};
	
	for(int i = 1; i <= n;i ++){
		if(!v[i]){
			c.clear();
			dfs(i);
			int k = cal();
			//cout << k << "\n";
			ans += k;
		}
	}
	
	cout << ans <<'\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int _t = 1;
	cin >> _t;
	while(_t --)
		solve();
	
	return 0;
}