Codeforces Round #775 (Div. 2)

A. Game

数组,你只能在是 的位置移动,且只能从 ,花费为 ,也可以跳跃一次从 ,花费为

第一个和最后一个位置都是 ,问从第一个到最后一个位置最小花费是多少?

开始向右移动,直到下一位是 停下来

开始向左移动,直到下一位是 停下来

答案即是这两个下标之差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<int> a(n);
for(auto &i:a)cin>>i;
int l=0,r=n-1;
while(l<n-1&&a[l+1]==1)l++;
if(l==n-1){cout<<"0\n";continue;}
while(a[r-1]==1)r--;
cout<<r-l<<"\n";
}
}

B. Game of Ball Passing

个人,给你这些人的总传球次数,问最少有几个球?

考虑是否可以一个球,把问题转换一下,每次选 可以进行无数次,问最终是否可以使得数组 全为 或仅有一个为 其他都为 ?

考虑临界的情况,每次操作都让数组 里最大的减 ,这样进行许多次,如果最大的数还不是 ,那么就说明不能只有一个球,那么最少球数就是 ,否则最小球数就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
vector<long long> a(n);
long long sum=0,mx=0;
for(auto &i:a){
cin>>i;
mx=max(i,mx);
sum+=i;
}
if(mx==0){cout<<"0\n";continue;}
mx-=sum-mx+1;
cout<<1+max(0ll,mx)<<"\n";;
}
}

C. Weird Sum

个单元格,每个单元格都标有颜色,请计算每对相同颜色的单元格之间的曼哈顿距离之和(公式表示:

其实是互不影响的,我们就单独地计算它就好了

考虑计算相同颜色 之和,我们可以把相同颜色 扔在一个数组里,排下序, 那么之和就是

计算相同颜色 之和同理

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
#include<bits/stdc++.h>
using namespace std;
long long solve(vector<vector<int>> a){
long long ans=0;
for(int i=1;i<=100000;i++){
if(a[i].empty())continue;
sort(a[i].begin(),a[i].end());
long long sum=0;
for(int j=a[i].size()-1;j>=0;j--){
ans+=sum-1ll*(a[i].size()-1-j)*a[i][j];
sum+=a[i][j];
}
}
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
vector<vector<int>> row(100001),lie(1000001);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int x;
cin>>x;
row[x].push_back(i);
lie[x].push_back(j);
}
}
cout<<solve(row)+solve(lie);
}

D. Integral Array

给你一个数组,从这个数组里任选两个数 ,且 ,问所有的是否都在数组里?

枚举 复杂度显然不行,那就换下思路想,枚举 和倍数 ,如果数组有数在区间 里的话,那就判断倍数 是否在数组里,不在的话就说明并非全部的都在数组里,输出 No

时间复杂度:

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
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;
cin>>t;
while(t--){
int n,c;
cin>>n>>c;
vector<int> pd(c+1,0),sum(c+1,0);
for(int i=1,j;i<=n;i++){
cin>>j;
pd[j]=1;
}
for(int i=1;i<=c;i++){
sum[i]=sum[i-1]+pd[i];
}
for(int i=1;i<=c;i++){
if(!pd[i])continue;
for(int j=1;i*j<=c;j++){
if(!(sum[min(c,i*(j+1)-1)]-sum[i*j-1]))continue;
if(!pd[j]){cout<<"No\n";goto end;}
}
}
cout<<"Yes\n";
end:;
}
}

Codeforces Round #775 (Div. 2)

http://blog.therehello.top/cf1649/

发布于

2022-03-17

更新于

2022-03-21

许可协议

评论

:D 一言句子获取中...

加载中,最新评论有1分钟缓存...