CF1173

Posted on | Edited on | Views:

$Div.2$

官方题解

A Nauuo and Votes

  • 签到题.

B Nauuo and Chess

  • 构造题.
  • 可以将所有数沿着第一列与最后一行放成一个 $L$ 形.容易验证一定是合法的.

  • 这样构造, $m=\lfloor \frac n 2 \rfloor+1$ .而考虑首尾两个位置,有
    $$
    |r_1-r_n|+|c_1-c_n|\geq n-1
    $$

  • 而 $|r_1-r_n|\leq m-1,|c_1-c_n|\leq m-1$ ,所以 $2m-2\geq n-1$ , $m$ 为整数,可得到 $m\geq \lfloor \frac n 2 \rfloor+1$ .

  • 所以这样构造一定是一个最优解.

C Nauuo and Cards

  • 策略是如果能不打 $0$ 直接完成,就直接完成,否则先打若干 $0$ ,然后再也不打 $0$ .
  • 考虑如果已经打了若干 $0$ ,开始一直打数字牌,那么此时 $1$ 必定在手中, $2$ 必定在手中或在牌堆的第 $1$ 个位置(打了 $1$ 就会被摸到手中), $3$ 必定在手中或在第 $2$ 个位置,以此类推.
  • 如果有一些牌的位置不合要求,那么我们需要先打空白牌来将他们加入到手中或是放到正确的位置.
  • 在手中可以看做位置 $0$ ,记 $p_i$ 为 $i$ 的初始位置,那么答案就是 $n+\max\limits_{i=1}^n (p_i-i+1)$ .
  • $n$ 是因为要连续打出 $1\sim n$ 这些牌,后面的部分是将 $p_i$ 调整到 $i-1$ 所需打出的 $0$ 的数目.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=2e5+10;
int n,a[MAXN],b[MAXN],p[MAXN];
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	for(int i=1;i<=n;++i)
		p[b[i]=read()]=i;
	if(p[1])
	{
		int x;
		for(x=2;p[x]==p[1]+x-1;++x);
		if(p[x-1]==n)
		{
			int y;
			for(y=x;y<=n && p[y]<=y-x;++y);
			if(y>n)
			{
				cout<<n-x+1<<endl;
				return 0;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;++i)
		ans=max(ans,p[i]-i+1);
	cout<<ans+n<<endl;
	return 0;
}

D Nauuo and Circle

  • $dp$ 计数.
  • 考虑 $dp$ ,设 $f_u$ 表示子树 $u$ 的方案数,先钦定根节点为 $1$ ,最后答案就是 $n\cdot f_1$ .
  • 画子树时,先要给所有儿子,若不为根,还有自己排序,转移有 $f_u=(|son_u|+[u==1])!\cdot \prod\limits_{v \in son_u}f_v$ .
  • 把 $dp$ 的式子展开,可以发现答案就是 $n\cdot \prod\limits _{i=1}^n deg_i$ , $deg$ 表示度数.

待续…