CF & AT 做题记录-JZTXT

选一些 $\text{div 1}$ 中的好题总结一下 $\textrm{qwq}$
从现在开始像 $\color{red}\text{r} \color{black}\text{ainboy}$ 一样打比赛 $\textrm{qaq}$

$$\textrm{Codeforces Round #902 (CF 1876)}$$

$\textrm{C Autosynthesis}$

给定一个 $n$ 个数的序列 $a$。你可以进行若干次操作，每次操作可以在一个数 $a_i$ 上画圈。
你需要满足以下要求：设你的操作次数为 $k$，$p_{1\cdots k}$ 为你每次操作时画圈的下标，你需要满足没有画圈的数字个数 恰好为 $k$，且这些数字组成的子序列 $b_{1\cdots k}$ 与 $p_{1\cdots k}$ 相等。
请你构造一组方案。如果不存在合法方案，输出 -1。
$1\le n\le 2\times 10^5,1\le a_i\le n$。

一开始就在做，比赛唯一场切的题（
方向很清晰，就是细节有点多（？）

如果一个数 $x$ 被圈了，那么一定存在一个没有被圈的数，满足其值为 $x$. 这很有启发性！把每个 $a_i$ 看作 $i \to a_i$ ，那么这个序列就转化为一个内向基环树森林，只需对每个连通块分别求解即可。
从没有被圈的数入手，记这种数为 $1$ 类，被圈的数为 $0$ 类。考虑 $u \to fa$ ，如果 $u$ 是 $1$ ，那么 $fa$ 必须是 $0$. 继续，考虑 $\forall v \to u$ ，如果 $u$ 是 $0$ ，那么所有 $v$ 也必须是 $1$. 以上都可以由题意推出。
既然是基环树，首先要找出环。从底向上推，叶子必须是 $1$，那么不在环上的点的状态唯一确定。对于环上点 $u$ ，要么是 $0$ ，即有一个非环节点是 $1$ 并指向它；要么不确定，即所有指向它的非环节点都是 $0$ ， $u$ 的状态取决于环上 $pre_u$ 的状态，记这种 $u$ 为 $2$ 类。
接下来开始分讨。注意到两个环上 $0$ 可以相邻，对于形如 $0222 \dots 2220$ 的序列，可以 $01$ 交替染色，即 $0101 \dots 010100$，于是只要环上有 $0$ 就有解。如果都是 $2$ ，必须是 $01$ 交替序列，相同数字必不能相邻，于是环长偶数有解，奇数无解。

点击查看代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

//#define DeBug
//#define LOCAL
// #define TestCases

const int N = 2e5;

int n;
int a[N + 5];

vector<int> e[N + 5];

int notuse[N + 5];

int stk[N + 5], top;
int vis[N + 5];
int seq[N + N + 5], len;
int oncir[N + 5];
void findcir(int u)
{
	if (vis[u])
	{
		len = 0;
		while (stk[top] != u)
		{
			seq[++len] = stk[top];
			top--;
		}
		seq[++len] = u;
		reverse(seq + 1, seq + len + 1);
		top--;
		for (int i = 1; i <= len; i++)
		{
			oncir[seq[i]] = 1;
			seq[i + len] = seq[i];
		}
		return ;
	}
	
	stk[++top] = u;
	vis[u] = 1;
	findcir(a[u]);
	return ;
}
void dfs(int u)
{
	vis[u] = 1;
	if (e[u].empty())
	{
		notuse[u] = 1;
		return ;
	}
	
	int zero = 0, one = 0, son = 0;
	for (unsigned int i = 0; i < e[u].size(); i++)
	{
		int v = e[u][i];
		if (oncir[v])
			continue;

		son++;
		dfs(v);
		if (notuse[v] == 0)
			zero++;
		if (notuse[v] == 1)
			one++;
	}

	if (zero == son)
	{
		if (oncir[u])
			notuse[u] = 2;
		else
			notuse[u] = 1;
		return ;
	}
	notuse[u] = 0;
	return ;
}

void calc(int st)
{
	top = 0;
	findcir(st);

	for (int i = 1; i <= len; i++)
		dfs(seq[i]);

	int zero = 0;
	for (int i = 1; i <= len; i++)
	{
		if (notuse[seq[i]] == 0)
		{
			zero = i;
			break;
		}
	}
	if (zero)
	{
		for (int i = zero + 1; i < zero + len; i++)
		{
			if (notuse[seq[i]] == 0)
				continue;
			notuse[seq[i]] = (notuse[seq[i - 1]] ^ 1);
		}
	}
	else
	{
		if (len & 1)
		{
			puts("-1");
			exit(0);
		}
		for (int i = 1; i <= len; i++)
			notuse[seq[i]] = (i & 1);
	}
	return ;
}

void solve()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", a + i);
		e[a[i]].push_back(i);
		notuse[i] = -1;
	}

	for (int i = 1; i <= n; i++)
		if (!vis[i])
			calc(i);

	int cnt = 0;
	for (int i = 1; i <= n; i++)
		cnt += notuse[i];
	printf("%d\n", cnt);
	for (int i = 1; i <= n; i++)
		if (notuse[i])
			printf("%d ", a[i]);
	printf("\n");
	return ;
}

int main()
{
	#ifdef LOCAL
	freopen("data.in", "r", stdin);
	freopen("mycode.out", "w", stdout);
	#endif
	
	int T = 1;
	
	#ifdef TestCases
	scanf("%d", &T);
	#endif
	
	while (T--)
		solve();
	return 0;
}