Codeforces Round 783(Div.2)解析

Codeforces Round #783 (Div. 2)

A. Direction Change

题目描述

1

题目分析

不难发现,我最优的路线只能是向右或者向下走。我先不妨设 $m\ge n$,如果走到底了,不得以我只能向上转变方向然后再右下,这样循环走直到终点,只考虑到了最后一行的情况,不难发现,每次长度+1变为奇数时,走的步数+1,否则+3。最后特判一下走不了的情况,当只有一行且有超过2列的情况为走不了。

标程

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
#include<bits/stdc++.h>
using namespace std;
void solve(){
int n,m;
cin>>n>>m;
if(n>m){//m>n
swap(n,m);
}
if(n==1&&m>2){
puts("-1");
return;
}
int ans=0;
ans+=2*n-2;
m-=n;
if(m==0){
ans+=0;
}
else{
if(m%2==0){
ans+=2*m;
}
else{
ans+=2*m-1;
}
}
printf("%d\n",ans);


}
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t=1;
cin>>t;
while(t--)solve();


return 0;
}

B.Social Distance

题目描述

2

题目分析

n个人要做在m把椅子上,每个人对自己有要求,要求左右两边必须有一定数目把空椅子。这个交错两发,后面发现这些人不是按顺序坐的,可以随意排,那么不难发现我们可以对要求从小到大排序然后相邻之间的要求取max最后取和得到一个值与m比较即可。

标程

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
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000006];
void solve(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(n==1){
if(a[1]+1>m){
puts("NO");
}
else{
puts("YES");
}
return ;
}
sort(a+1,a+1+n);

a[0]=a[n];
int ans=n;
for(int i=1;i<=n;i++){
ans+=max(a[i],a[i-1]);
}
if(ans<=m){
puts("YES");
}
else{
puts("NO");
}
//printf("%d\n",ans);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t=1;
cin>>t;
while(t--)solve();



return 0;
}

C. Make it Increasing

题目描述

3

题目分析

给定一个初始值全为0的数组,每个位置可以固定加或减一定的值,要求序列严格递增,求最少操作次数。对于这个问题只需要抓住一个重点:那就是谁为0,根据给定的 $n<5000$ 基本可以判断出来这个要 $O(n^2)$ 的算法。我们只需要循环把一个数强制设置为0,然后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
46
47
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[5005];
int b[5005];
void solve(){
int n,m;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(n==1){
puts("0");
return ;
}
int res=0x7fffffffffffffff;
for(int i=1;i<=n;i++){//zero
memset(b,0,sizeof(b));
int ans=0;
for(int j=i-1;j>=1;j--){
int k=ceil((double)(b[j+1]+1)/a[j]);
ans+=k;
b[j]=k*a[j];
}
for(int j=i+1;j<=n;j++){
int k=ceil((double)(b[j-1]+1)/a[j]);
ans+=k;
b[j]=k*a[j];
}
res=min(res,ans);


}
printf("%lld\n",res);
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
int t=1;
//cin>>t;
while(t--)solve();



return 0;
}

当时也有点没注意到就是数值可能很大,大到超过int,当时初值我只给了0x7fffffff就wa了一发。

这场比赛失误了很多吧,不过最后还得感谢大自然的馈赠,写了一个明显有问题的程序让我hack了,没至于让我掉太多分。

4

继续加油吧,上分之路还很漫长。

文章目录
  1. 1. A. Direction Change
    1. 1.1. 题目描述
    2. 1.2. 题目分析
    3. 1.3. 标程
  2. 2. B.Social Distance
    1. 2.1. 题目描述
    2. 2.2. 题目分析
    3. 2.3. 标程
  3. 3. C. Make it Increasing
    1. 3.1. 题目描述
    2. 3.2. 题目分析
    3. 3.3. 标程
|