cf_564_div2部分题解

完整题解看这里

太菜了,事后补题也只会前4道签到题…

A 规律

签到不说了

1173B Nauuo and Chess

在一个 m×m 的棋盘上放 n 颗棋子,第 i 颗棋子的坐标为 (ri,ci),需要满足 |ri−rj|+|ci−cj|≥|i−j|,求 m 的最小值以及任意一种摆放方案。

input
4
output
3
1 1
1 3
3 1
3 3
这题是个spj,只要符合条件的答案都对

把奇数棋子放在对角线,偶数棋子放在相邻的奇数棋子下面。这样因为每个棋子两坐标之差的和都是1,所以m肯定是最小的且符合要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int main() {
int a; cin>>a;
if(a == 1) {
cout<<"1"<<endl;
} else {
cout<<(a) / 2 + 1<<endl;
}
int x = 1,y = 0;
for(int i = 1; i <= a; ++i) {
if(i % 2 == 0) cout<<++x<<" "<<y<<endl;
else cout<<x<<" "<<++y<<endl;
}
return 0;
}

1173C Nauuo and Cards 规律

n 张带标号的牌和 n 张空白牌,n 张在手上剩下在牌堆里(牌堆有序),
每次可以从手上选一张牌放牌堆底部并从牌堆顶部抽一张牌,需要使牌堆从上到下递增地放 1 ~ n,求最小操作数。

1≤n≤2×10^5。

input
3
0 2 0
3 0 1
output
2

input
3
0 2 0
1 0 3
output
4

input
11
0 0 0 5 0 0 0 4 0 0 11
9 2 6 0 8 1 7 0 3 0 10
output
18

div1的A题,但是以我现在的水平不太好做出来。嗯。

首先,一张牌要想最快打出来,那么如果在牌堆里,操作数就是这张牌在牌堆中次序pos[b[i]]+ 1。也就是摸到后立刻打出来。特别地,如果已经在手里那么pos[i] = 0

然后看一下能不能不打空白牌,直接打完。先判断牌堆的末尾有没有从1开始的连续的一段,如果有,那么它们就不用再从牌堆里抽出来了,后面的牌只要放在它们的末尾就行了(这个可以通过观察样例得到)。假设末尾的数是i,然后对于在手中或在牌堆中其他位置的牌j,检查一下它们最小操作数能否支持放在那堆连续牌的末尾(p[j] <= j - i,这个看一下代码就行了)。如果都行,那么最小操作数就是n-i+1

如果不行的话,就是先打空白牌,再打别的非空白的牌。所以总的最小操作数就是max{p[i] + 1 + n - i},即i最快就是p[i] + 1时打出来,还需要打n - i张。当然有可能p[i]时摸到了但是无法连续的打完所有牌(就是还需要打几张空白牌才能连续的出非空白),所以取一个max满足所有条件。

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
#include <bits/stdc++.h>
using namespace std;
int a[200010],b[200010],p[200010];
int main() {
int n; scanf("%d",&n);
for(int i = 1; i <= n; ++i) {
scanf("%d",a + i);
p[a[i]] = 0;
}
for(int i = 1; i <= n; ++i) {
scanf("%d",b + i);
p[b[i]] = i;
}
if(p[1]) {
int i = 2,j;
while(p[i] == p[1] + i - 1) ++i;
if(p[i - 1] == n) {
for(j = i; j <= n && p[j] <= j - i; ++j);
if(j > n) {
printf("%d\n",n - i + 1);
return 0;
}
}
//printf("%d\n",n);
}

int ans = 0;
for(int i = 1; i <= n; ++i)
ans = max(ans,p[i] + 1 + n - i);
printf("%d\n",ans);

return 0;
}

1173D Nauuo and Circle 排列组合 规律

圆上画一 n 点树,树给定,边要求直而不交,画法与排列一一对应,求方案数。

2≤n≤2×10^5

inputCopy
4
1 2
1 3
2 4
outputCopy
16

inputCopy
4
1 2
1 3
1 4
outputCopy
24

这个实际上就是个排列组合找规律题,虽然第一眼看上去挺难的。

先随便选一个根,比如1,然后观察错误样例。你会发现1的两个子树组成的区间[2,4][3]有重叠,而正确的答案两个区间都是不会交的。这样就是一个切入点。

从1入手,1有n个位置可选,假设有k个子树,那么它们每个的区间排列顺序就是k!,然后对于每颗子树,假设它有x个子树,它们的排列也是(x + 1)!(加上这个子树的根也要排列)。总之当你把这个式子展开时就会发现总答案就相当于每个节点度的阶乘 x n。然后就没问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <bits/stdc++.h>
using namespace std;
const long long m = 998244353;
long long d[200010];
int main() {
int n; scanf("%d",&n);
long long ans = n;
for(int i = 1; i < n; ++i) {
int u,v; scanf("%d%d",&u,&v);
ans = (ans * ((++d[u]) * (++d[v]) % m)) % m;
}
printf("%lld",ans);
}

E Nauuo and Pictures 概率dp

FNauuo and ODT 数据结构