今天掉大分,预估回青名吧。实时录屏

A. Grass Field

题目描述:

1

题目分析

给定2×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
#include<bits/stdc++.h>
#define maxn 500002
using namespace std;
int a[maxn];
const int mod=1e9+7;
int dx[]={1,0,0,-1},dy[]={0,1,-1,0};
queue<pair<int,int>>q;//y,x
int n,m;

void solve(){
int a[4];
scanf("%d %d %d %d",a,a+1,a+2,a+3);
int sum=a[1]+a[2]+a[3]+a[0];
if(sum==0){
puts("0");
return ;
}
if(sum!=4){
puts("1");
return ;
}
puts("2");
}

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



return 0;
}

B. Permutation

题目描述:

2

题目分析

就是说,我们需要让排列中的一个值(这个值是a[i+1]/a[i])尽可能多的出现,一样多的情况下输出值较大的。这题贪就完了,我们长度超过4的我们就选2。从1开始2倍去填上数,再选没填过的,也是2倍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
42
43
44
45
46
47
48
49
50
51
52
#include<bits/stdc++.h>
#define maxn 200002
using namespace std;
int a[maxn];
const int mod=1e9+7;
int dx[]={1,0,0,-1},dy[]={0,1,-1,0};
queue<pair<int,int>>q;//y,x
int n,m;
void solve(){
int n;
scanf("%d",&n);
memset(a,0,sizeof(int)*(n+1));
if(n==2){
puts("2\n1 2");
return ;
}
if(n==3){
puts("3\n2 1 3");
return ;
}
puts("2");
int i=1;
while(i<=n){

if(a[i]==1){
i++;
continue;
}
for(int j=i;j<=n;j*=2){
printf("%d ",j);
a[j]=1;
}
i++;
}
puts("");


}

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



return 0;
}

C. Line Empire

题目描述

3

题目分析

m个工作,n个人,每个工作有一个熟练工,如果让熟练工完成,那么只需要一个小时,让其余工人完成都需要两个小时。

我们直接二分答案就行了,至于check函数,我们就先计算每个工人的熟练工作个数。

然后做出如下算法:

  1. 对于一个人,若它熟练a[i]种工作,那么它会尽量花费a[i]的时间去做完这a[i]的工作,若时间有剩,那么剩余时间做 (t-a[i])/2 个工作。
  2. 判断n个工人在t时间内是否能完成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
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
#include<bits/stdc++.h>
#define maxn 200002
using namespace std;
int a[maxn],b[maxn];
const int mod=1e9+7;
int dx[]={1,0,0,-1},dy[]={0,1,-1,0};
queue<pair<int,int>>q;//y,x
int n,m,t;
int cmp(int a,int b){
return a>b;
}
int cal(int t){
int ans=0;
for(int i=1;i<=n;i++){
//printf("a[%d]=%d\n",i,a[i]);
// if(!a[i]){
// break;
// }
if(a[i]<t){
ans+=a[i];
ans+=(t-a[i])/2;
}
else{
ans+=t;
}
}
//printf("time=%d ans=%d\n",t,ans);
return ans;
}

void solve(){
scanf("%d %d",&n,&m);
memset(a,0,sizeof(int)*(n+1));
for(int i=1;i<=m;i++){
int x;
scanf("%d",&x);
a[x]++;
}
sort(a+1,a+1+n,cmp);
t=(m/n)*2+(!!(m%n))*2;
int l=1,r=t;

while(l<r){
int mid=l+r>>1;
//printf("mid=%d\n",mid);
int res=cal(mid);


if(res<m){
l=mid+1;
}
else{
r=mid;
}
}
printf("%d\n",l);


}

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



return 0;
}

小结

啥也不说了,猛练吧。