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;
}