今天掉大分，预估回青名吧。实时录屏
A. Grass Field
题目描述：
/1.png)
题目分析
给定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;
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
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
B. Permutation
题目描述：
/2.png)
题目分析
就是说，我们需要让排列中的一个值（这个值是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;
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
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
C. Line Empire
题目描述
/3.png)
题目分析
m个工作，n个人，每个工作有一个熟练工，如果让熟练工完成，那么只需要一个小时，让其余工人完成都需要两个小时。
我们直接二分答案就行了，至于check函数，我们就先计算每个工人的熟练工作个数。
然后做出如下算法：
- 对于一个人，若它熟练a[i]种工作，那么它会尽量花费a[i]的时间去做完这a[i]的工作，若时间有剩，那么剩余时间做
(t-a[i])/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;
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++){
if(a[i]<t){
ans+=a[i];
ans+=(t-a[i])/2;
}
else{
ans+=t;
}
}
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;
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
int t=1;
cin>>t;
while(t--)solve();
return 0;
}
|
小结
啥也不说了，猛练吧。
