Fork me on GitHub

Round #573 (Div. 2)解题报告

qwq

A:

没啥可说的,直接按照$Mod 4$分类然后讨论就好了.


B:

显然可以发现答案只能是0,1,2,3中的某一个,我们只需要将读入记录下来,然后对于每一种胜利的情况分组枚举一下,记录一个最小的ans就可以了.


C:

考虑每一次操作中,这一页的最右边能消除几个.
我们可以设我们已经消除了$sum$个数字,那么当前的$m_i$在消除之后中的书中的位置就是$m_i-sum$,我们就可以推导出来当前$m_i$的这一页的最右边的一个数字就是$((m_i-sum)/k+1)*k$,我们只需要开一个关于i的指针就可以了,时间复杂度为$O(m)$.


D:

考虑必胜情况:在另外一个人开始取的时候有$2$个或者以上的重复组.或者在有1个重复组时,取出一个重复组(因为不取就会输)之后回和另外一个元素再组成一个重复组.

我们再考虑完这种情况之后,可以发现,我们在将原来的数组排序之后,如果两边都按照最优方式取石子,那么最后的(在决定胜负之前),石子的序列一定是$B_i=i-1$的这样的一个等差数列.所以我们需要对原数组排序,然后统计一个$\sum_{i=1}^n A_i-(i-1)$,判断一下这个$sum$的奇偶性就可以了.

PS:一定要先判断有没有例外的必胜情况(我就是这么WA了4发qwq….)

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,idxx;
int num[N],dis[N];
map<int,bool>mp;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>num[i];
sort(num+1,num+1+n);
int sum=0,dpp=0;
for(int i=1;i<=n;i++){
if(num[i]==num[i-1]&&i>=2){
dpp++;
dis[++idxx]=num[i];
}
sum+=num[i]-i+1;
mp[num[i]]=1;
}
if(n==1){
if(sum&1)
cout<<"sjfnb"<<endl;
else
cout<<"cslnb"<<endl;
return 0;
}
if(dpp==1&&num[1]==0&&num[2]==0){
cout<<"cslnb"<<endl;
return 0;
}
if(dpp==1&&n==2){
cout<<"sjfnb"<<endl;
return 0;
}
if(dpp==1){
if(mp[dis[1]-1])
cout<<"cslnb"<<endl;
else {
if(!(sum&1))
cout<<"cslnb"<<endl;
else
cout<<"sjfnb"<<endl;
}
return 0;
}
if(dpp>=2){
cout<<"cslnb"<<endl;
return 0;
}
if(!(sum&1))
cout<<"cslnb"<<endl;
else
cout<<"sjfnb"<<endl;
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:Round #573 (Div. 2)解题报告

文章作者:KRrrrrrrrr

发布时间:2019年09月11日 - 18:09

最后更新:2019年10月21日 - 11:10

原始链接:http://krrrr.xyz/2019/09/11/Round-1/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。