Fork me on GitHub

Round #582解题报告

qwq

A.Chips Moving

题意就是给你n个数,你每次可以选择一个数,对他进行免费的加2或者减2.或者花费1的代价,对某个数进行加一或者减一,求让所有的数变成一样的最小代价.

很显然可以发现,奇数和奇数之间可以相互转变,偶数和偶数之间也可以相互转变,那么我们只需要考虑让奇数全部变成偶数或者让偶数变成奇数就好了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int cnto = 0;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
cnto += x & 1;
}
cout << min(cnto, n - cnto) << endl;
return 0;
}

B.Bad Prices

题意就是给你一个序列$A$,让你求出所有$A_i$中,$\sum_{i=1}^n[A_i>A_{j(i<j<=n)}?0:1]$

显然可以直接维护一个后缀最小值,然后判断一下当前$A_i$的值和当前后缀最小值的大小关系,如果$A_i>num_i$,那么ans++

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
#include<bits/stdc++.h>
using namespace std;

const int N=150005;

int n;
int num[N];
int mins[N];

int main(){

int T;
scanf("%d",&T);
while(T--){
memset(mins,0x3f3f3f3f,sizeof(mins));
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
for(int i=n-1;i>=1;i--)
mins[i]=min(mins[i+1],num[i+1]);
int ans=0;
for(int i=1;i<n;i++)
if(num[i]>mins[i])
ans++;
printf("%d\n",ans);
}

return 0;
}
//

C.Book Reading

显然可以发现,题目中要求的个位数字只受要除的数的个位的影响,所以我们在求出来了倍数的个数$num$时,可以发现,个位数字的出现是有周期的,而这个周期和周期中的数字是由要除的数字的个位决定的.而因为要除的数字的个位最多只有10个,所以我们可以先预处理出每个数字的周期以及他们的和,再对多出来的部分直接暴力就可以了.

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
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m;
int ned[10],idx[10];
int sum[10][10];

signed main(){

ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

for(int i=1;i<=9;i++){
int now=i;
sum[i][++idx[i]]=i;
now+=i;
while(now!=i){
if(now>=10)
now-=10;
sum[i][++idx[i]]=now;
now+=i;
}
}
for(int i=1;i<=9;i++)
for(int j=1;j<=idx[i];j++)
ned[i]+=sum[i][j];
int T;
cin>>T;

while(T--){
int ans=0;
cin>>n>>m;
int numm=n/m;
int tmp = m;
tmp%=10;
if(tmp==0||numm==0){
cout<<"0"<<endl;
continue;
}
int fir = numm/idx[tmp];
ans+=fir*ned[tmp];
// cout<<fir<<" "<<tmp<<endl;
int sos=0;
for(int i=fir*idx[tmp]+1;i<=numm;i++)
ans+=sum[tmp][i-fir*idx[tmp]];
cout<<ans<<endl;
}


return 0;
}
//

D.Equalizing by Division

我们可以发现,对于某一个数$i$,他能变成的数的个数为$log_2i+1$个,而且题目中$i$的权值也不大,所以我们可以开一个桶,按照从小到大的顺序处理每一个数字,每次处理的时候将它能变成的$log_2i$个数字在桶中的权值全部+1,同时花费就是从原来的i到目前的数字要除几次二,当发现有桶中的数字大于给定的$k$时,更新答案.

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
#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int n,k,ans=2147483647;
int num[N];
struct Node{
int val;
int now;
}buck[N];

int main(){

ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);

cin>>n>>k;
for(int i=1;i<=n;i++) {
cin>>num[i];
buck[num[i]].now++;
if(buck[num[i]].now>=k){
cout<<"0"<<endl;
return 0;
}
}
sort(num+1,num+1+n);
for(int i=1;i<=n;i++){
int idx=1,tmp=num[i]/2;
while(tmp){
buck[tmp].now++;
buck[tmp].val+=idx;
if(buck[tmp].now>=k)
ans=min(ans,buck[tmp].val);
tmp/=2;
idx++;
}
}
cout<<ans<<endl;
return 0;
}
//
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:Round #582解题报告

文章作者:KRrrrrrrrr

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

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

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

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