本文主要是介绍Codeforces Round 919 (Div. 2),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
实时
A.
限定范围,计数范围里不等于
B.
贪心
1.计算全部,最大几个为负数
2.计算删完k个,再负数
暴力枚举k,枚举不到中间位置
x必然全部都加上
没思路
C.
数论
没思路
题解
A.
// Problem: A. Satisfying Constraints
// Contest: Codeforces - Codeforces Round 919 (Div. 2)
// URL: https://codeforces.com/contest/1920/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <iostream>
#include<cstring>
#define eps 1e-5
#define INF 2e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N],b[N],vis[N];
void Lan(){int n;cin>>n;int k=0;int res=INF;int num=0;memset(vis,0,sizeof(vis));memset(b,0,sizeof(b));for(int i=1;i<=n;i++){int a,x;cin>>a>>x;if(a==1){k=max(k,x);}else if(a==2){res=min(res,x);}else{b[i]=x;vis[i]=1;num++;}}for(int i=1;i<=n;i++){if(vis[i]){if(b[i]<k || b[i]>res){num--;} }}int ans=max(res-k+1,0)-num;cout<<ans<<'\n';}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int q;cin>>q;while (q--) {Lan();}return 0;
}
B.
贪心
如果删了小的,大的肯定也被删了,枚举删了几个
x操作肯定是全部都用上了
思考怎么实现,枚举k次操作
1.前缀和(区间求和),可以通过一个例子思考一下
54321,x=1,k=1
->-4321
可以通过容斥原理思考出式子
ans=max(prefix[n]-2*(prefix[min(n,i+x)])+a[i])
// Problem: B. Summation Game
// Contest: Codeforces - Codeforces Round 919 (Div. 2)
// URL: https://codeforces.com/contest/1920/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
ll a[N];
void Lan(){int n,k,x;cin>>n>>k>>x;for(int i=1;i<=n;i++){cin>>a[i];}ll ans=-INF;sort(a+1,a+1+n,greater<ll>());for(int i=1;i<=n;i++){a[i]+=a[i-1];}for(int i=0;i<=k;i++){ans=max(ans,a[n]-2*a[min(i+x,n)]+a[i]);}cout<<ans<<'\n';}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int q;cin>>q;while (q--) {Lan();}return 0;
}
2.
双指针
如果删了1个就加回来个,x就减去2倍就是负数了
// Problem: B. Summation Game
// Contest: Codeforces - Codeforces Round 919 (Div. 2)
// URL: https://codeforces.com/contest/1920/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
void Lan(){int n,k,x;cin>>n>>k>>x;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+1+n);int ans=0;for(int i=1;i<=n-x;i++){ans+=a[i];}for(int i=n-x+1;i<=n;i++){ans-=a[i];}int temp=ans;for(int i=1;i<=k;i++){if(n-i+1>=1){temp+=a[n-i+1];}if(n-i+1-x>=1){temp-=2*a[n-i+1-x];}ans=max(ans,temp);}cout<<ans<<'\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int q;cin>>q;while (q--) {Lan();}return 0;
}
C.
枚举因数,关键在如何确认每个子数组都是一样的
把每个作差,(把余数去除)
对其作gcd运算,如果g!=1,就肯定存在m的倍数。
ans+=(g!=1)
// Problem: C. Partitioning the Array
// Contest: Codeforces - Codeforces Round 919 (Div. 2)
// URL: https://codeforces.com/contest/1920/problem/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <iostream>
#include<cmath>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
void Lan(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int ans=0;for(int k=1;k<=n;k++){if(n%k==0){int g=0;for(int i=1;i+k<=n;i++){g=gcd(g,abs(a[i+k]-a[i]));}ans+=(g!=1);}}cout<<ans<<'\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int q;cin>>q;while (q--) {Lan();}return 0;
}
这篇关于Codeforces Round 919 (Div. 2)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!