G - Game Night （前缀和 K-Kingpin Escape （给树加边变成边双连通图

比赛传送门

G - Game Night

题意：
你一条长度 $n$ 的字符串，代表 $n$ 个人坐在一个圆桌上， 每个人都在 $a，b，c$ 三个组中，每次个调换两个人的位置，问：最小需要调换多少人能达到最少操作次数使这三组中的人都相邻
问的是有多少位置上的人需要换座
思路：
巨佬博客
先变环成链
求出链的前缀和
枚举 $ABC$ 三个字符的所有状态
对于一种状态，枚举长度为 $n$ 的串的起点，然后按照排列顺序维护最大匹配度，减去就可以得到需要移动的位置数
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
int sum[maxn][3];
string s;

int f(int x, int y, int z){// 按照 x y z 的顺序排列
	int ans = 0, cntx = sum[n][x], cnty = sum[n][y];
	for(int i = 1; i <= n; ++i){// 枚举起点，维护长度为n的子串的最大匹配度 
		int tmp = 0; 
		tmp += sum[i + cntx - 1][x] - sum[i - 1][x];
		tmp += sum[i + cntx + cnty - 1][y] - sum[i + cntx - 1][y];
		tmp += sum[i + n - 1][z] - sum[i + cntx + cnty - 1][z];
		ans = max(ans, tmp); 
	}
	return n - ans;
}
void work()
{
	cin >> n >> s;s = s + s;
	for(int i = 1; i <= n * 2; ++i){
		for(int j = 0; j < 3; ++j) sum[i][j] = sum[i-1][j];
		sum[i][s[i-1]-'A']++; 
	}
	int ans = inf;
	int a[10] = {0, 1, 2};
	do{
		ans = min(ans, f(a[0], a[1], a[2]));
	}while(next_permutation(a, a + 3));
	cout << ans;
}

int main()
{
	ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}

K-Kingpin Escape

题意：
给定一棵树，$n$ 个点，$m$ 为终点，要求删除任意一条边之后仍能从任意点到 $m$
输出添加的最少边数和添加的边
思路：
题解
写法的话就是拿以 $m$ 为根的 $dfs$ 序里的度为 $1$ 的节点（并不一定是叶子，也可能是度为 $1$ 的根）两两匹配
设度为 $1$ 的节点 $cnt$ 个，用 $i$ 匹配 $\lfloor \frac{cnt}{2}\rfloor +i$
如果 $cnt$ 是奇数，就把 $dfn[cnt]$ 和 $dfn[1]$ 连一起

好像就是把所有的 $i$ 连到另外一个以根节点为父亲的子树中，这样删除当前节点所在子树与根连的边，也能保证仍与根相连
code：

#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define ld long double
#define all(x) x.begin(), x.end()
#define mem(x, d) memset(x, d, sizeof(x))
#define eps 1e-6
using namespace std;
const int maxn = 2e5 + 9;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll n, m;
vector <int> e[maxn];
int dfn[maxn], cnt, deg[maxn];

void dfs(int x, int fa){
	if(deg[x] == 1) dfn[++cnt] = x;
	for(int to : e[x]) if(to != fa)
		dfs(to, x);
} 
void work()
{
	cin >> n >> m;
	for(int i = 1; i < n; ++i){
		int a, b;cin >> a >> b;
		e[a].push_back(b);e[b].push_back(a);
		deg[a]++;deg[b]++;
	} 
	dfs(m, -1);
	cout << (cnt + 1) / 2 << endl;
	for(int i = 1; i <= cnt / 2; ++i){
		cout << dfn[i] << " " << dfn[i + cnt / 2] << endl;
	}
	if(cnt & 1) cout << dfn[1] << " " << dfn[cnt] << endl;
}

int main()
{
	ios::sync_with_stdio(0);
//	int TT;cin>>TT;while(TT--)
	work();
	return 0;
}