Codeforces Round #842

第一题

结论：对于 $n(n\ge 2)n(n\; \backslash geq\; 2)$ ，都有 $n\mathrm{\mid }((n-1)!+(n-2)!)n\; |\; ((n\; -\; 1)!\; +\; (n\; -\; 2)!)$ ，即 $nn$ 整除 $(n-1)!+(n-2)!(n\; -\; 1)!\; +\; (n\; -\; 2)!$

第二题

题意：给定一个长度为 $nn$ 的序列和正整数 $kk$ ，一次操作可以在序列中选择 $kk$ 个整数，将他们从原位置取出按从小到大的顺序排在序列最后面，求可以使序列递增排序的最小操作数。

设原序列中从 $11$ 开始的顺序排序为 $rr$ ，则最小操作数为 $\lceil (n-r)\mathrm{/}k\rceil \backslash lceil\; (n\; -\; r)\; /\; k\; \backslash rceil$

例：

设 $n=4,k=2n\; =\; 4,\; k\; =\; 2$ 的序列 $[2,3,1,4][2,\; 3,\; 1,\; 4]$ ，其 $r=1r\; =\; 1$ ，则最小操作数为 $\lceil (n-r)\mathrm{/}k\rceil =\lceil (4-1)\mathrm{/}2\rceil =2\backslash lceil\; (n\; -\; r)\; /\; k\; \backslash rceil\; =\; \backslash lceil\; (4\; -\; 1)\; /\; 2\; \backslash rceil\; =\; 2$

第三题：

对于每个位置 $ii$ ，一定满足某个排列该位置的值为 $a[i]a[i]$ ，另一个位置该位置的值 $\le a[i]\backslash leq\; a[i]$ ，模拟从大到小填入 $a[i]a[i]$ 的过程（逆序枚举保证之前贡献的位置后面的数都可以填入），模拟的过程中维护所有可以填数的位置。

如果当前 $a[i]a[i]$ 没在原序列中出现过，那么说明在两个排列中 $a[i]a[i]$ 都和比他大的元素填在一起，从两个排列可以填数的位置各自任取一个填入 $a[i]a[i]$ 即可。

如果 $a[i]a[i]$ 在原序列中出现了一次，那么显然可以把一个 $a[i]a[i]$ 填在 $a[i]a[i]$ 出现的位置，而另一个 $a[i]a[i]$ 可以一起填在这个位置，这样操作可以保证两个排列中可以填数的位置是相等的。

如果 $a[i]a[i]$ 在原序列中出现了两次，那么就把两个 $a[i]a[i]$ 填到这两个位置去，并且会贡献出两个可以填数的位置。

在模拟的过程中如果需要填数但是没有地方可以填或者某个数字出现了超过两次则无解。

代码：

LL T;
cin >> T;
while (T --)
{
	LL n;
	cin >> n;
	
	vector<int> cand0, cand1;
	for (int i = 1;i <= n;i ++) pos[i].clear();
	
	for (int i = 1;i <= n;i ++)
	{
	    int t;
	    cin >> t;
	    pos[t].push_back(i);
	}
	
	bool f = false;
	for (int i = n;i >= 1;i --)
	{
	    if (pos[i].size() > 2)
	    {
	        f = true;
	        break;
	    }
	    else if (pos[i].size() == 2)
	    {
	        p[pos[i][0]] = i;
	        cand1.push_back(pos[i][0]);
	        q[pos[i][1]] = i;
	        cand0.push_back(pos[i][1]);
	    }
	    else if (pos[i].size() == 1)
	    {
	        p[pos[i][0]] = i;
	        cand1.push_back(pos[i][0]);
	        q[cand1.back()] = i;
	        cand1.pop_back();
	    }
	    else
	    {
	        if (cand0.empty() || cand1.empty())
	        {
	            f = true;
	            break;
	        }
	        p[cand0.back()] = i;
	        cand0.pop_back();
	        q[cand1.back()] = i;
	        cand1.pop_back();
	    }
	}
	
	if (f) cout << "NO" << endl;
	else
	{
	    cout << "YES" << endl;
	    for (int i = 1;i <= n;i ++) cout << p[i] << ' ';
	    cout << endl;
	    for (int i = 1;i <= n;i ++) cout << q[i] << ' ';
	    cout << endl;
	}
}

第四题

转置环

参考：https://zhuanlan.zhihu.com/p/596949353