Codeforces Round 810(Div.2)解析
这场打回来一点吧，只是看隔壁div1好像被喷烂了的样子，咱也不懂，也没资格打div1，很多细节没注意到送出去罚时就很难受，本场录屏在B站了，
A. Perfect Permutation
题目描述
/1.png)
题目分析
这题题意看了我有点久，就是构造一串能使得 a[i]/i 为整数比较少的序列，那么 i=1 它可以被任意数整除。但是 i>1 我总能找到不能整除的数，因此这里构造的序列就是，第一个给 n，后面的给 i-1 即可。
标程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int a[maxn],b[maxn];
char s[maxn];
int n,m;
int dp[maxn],sum1[maxn],sum2[maxn];
void solve(){
scanf("%d",&n);
printf("%d ",n);
for(int i=1;i<n;i++){
printf("%d ",i);
}putchar(10);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Party
题目描述
/2.png)
题目分析
这个题目比较有意思，出的也挺好的感觉，虽然一开始可能题意有点没读懂。有n个人，m对关系，如果每个人如果没来就会产生 $a_i$ 的不开心度，如果来了一对朋友那这对朋友要消耗一个蛋糕，一次只能生产偶数个蛋糕不能浪费。那么很显然，如果关系本身就是偶数对，那么所有人都可以来。如果关系是奇数对，我就得考虑踢人了，踢掉一个人的情况，使奇数对变成偶数对的方式就是，这个人有奇数对关系，那么踢了这个人就少了奇数对关系，结果变成偶数对了。踢掉两个人的情况，如果所有人的关系数都是奇数对或者本身踢掉两个人比踢掉一个人产生不开心指数更多，我就要考虑后面的情况了。那么我如果要踢掉两个人，那么这两个人一定都有偶数对关系，因为但凡有一个奇数对关系我都可以只踢掉那个人而保留下来另一个，显然这样的作法比较优。那么踢掉的两个人都是偶数对关系怎么办呢？如果它们自己产生了一对关系，那么两个人的偶数关系发生一个关系的重合，总体下来就是奇数对关系了。那么我们就需要踢掉两个朋友关系的，开心指数较小的两个人。
然后min一下即可。
标程
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
| #include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int b[maxn];
char s[maxn];
int n,m;
int dp[maxn],sum1[maxn],sum2[maxn];
int table[maxn];
struct eee{
int v;
int i;
}a[maxn];
vector<int>G[maxn];
int cmp(eee a,eee b){
return a.v<b.v;
}
void solve(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i].v);
a[i].i=i;
vector<int>().swap(G[i]);
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
table[a[i].i]=i;
}
int x,y;
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
G[table[x]].push_back(table[y]);
G[table[y]].push_back(table[x]);
}
if(m%2==0){
puts("0");
return ;
}
m=1e9;
for(int i=1;i<=n;i++){
if(G[i].size()%2){
m=a[i].v;
break;
}
}
for(int i=1;i<=n;i++){
if(a[i].v>m)break;
for(auto x=G[i].begin();x!=G[i].end();x++){
if(a[i].v+a[*x].v<m){
if(G[i].size()%2==0&&G[*x].size()%2==0){
m=a[i].v+a[*x].v;
}
}
}
}
printf("%d\n",m);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
C. Color the Picture
题目描述
/3.png)
题目分析
这题也还挺好的，就是刷格子，然后要求一每个格子响铃格子都至少有三块相同色块，那么就是说你最多只有一个不同色块的相邻，并且告诉你了怎么处理边界的色块。那么它下面展示的图其实还是比较生动的，就是刷两列或者两行，然后再刷两列两列，如此往复。当然，三列四列都可以，一列是不行的，因为左右就有两个不同颜色的色块了。
那么我们直接每行每列看看能不能放的出对应的行或者列数即可。但是这里需要特判，如果我们都只能放两列，但是却只有奇数列，这种情况是不行的！！
最后不开 long long 见祖宗，万事给我加上一句#define int long long。
标程
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
60
61
62
63
64
65
66
67
68
69
70
71
| #include<bits/stdc++.h>
#define maxn 200005
using namespace std;
int a[maxn],b[maxn],c[maxn];
char s[maxn];
int n,m,k;
int dp[maxn],sum1[maxn],sum2[maxn];
int table[maxn];
void solve(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=k;i++){
scanf("%d",&a[i]);
b[i]=a[i]/n;
c[i]=a[i]/m;
}
long long ans=0;
int flag1=0,flag2=0;
for(int i=1;i<=k;i++){
if(b[i]<2){
continue;
}
if(b[i]!=2)flag1=1;
ans+=b[i];
}
if(ans>=m){
if(!flag1&&m%2){
}
else{
puts("YES");
return ;
}
}
ans=0;
for(int i=1;i<=k;i++){
if(c[i]<2){
continue;
}
if(c[i]!=2)flag2=1;
ans+=c[i];
}
if(ans>=n){
if(!flag2&&n%2){
}
else{
puts("YES");
return ;
}
}
puts("NO");
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
总结
最后说一句吧，就是细节问题真的要考虑周全一点的，小上一波分，但是离1600还是差远了，只能继续努力了，期待下次上大分了。