Codeforces Round 919 (Div. 2)

A - Satisfying Constraints

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e6 + 10;

void solve()
{
	int n;
	int l = -1;
	int r = 1e9 + 10;
	cin >> n;
	map<int,int> bj;
	for(int i=1;i<=n;i++)
	{
		int a,x;
		cin >> a >>x;
		if(a==3) bj[x]++;
		else if(a==1){
			l = max(l,x);
		}else if(a==2){
			r = min(r,x);
		}
	}
	int ans = r - l + 1;
	for(auto [x,y]:bj)
        if(x>=l&&x<=r) ans--;
	cout << max(ans,0ll) <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

B - Summation Game

卡了好久才注意到数组里的元素都是正数。

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e6 + 10;
int pre[N];
int a[N];
void solve()
{
	int n,k,x;
	cin >> n >> k >> x;
	for(int i=1;i<=n;i++) cin >> a[i];
	sort(a+1,a+1+n,greater<int>());
    for(int i=1;i<=n;i++) pre[i] = pre[i-1] + a[i];
	int ans = pre[n] - 2*pre[x];
	for(int i=1;i<=k;i++)
	{
		int sum = pre[n] - pre[i];
		int r = min(n,x+i);
		int len = pre[r] - pre[i];
		sum -= 2*len;
		ans = max(ans,sum);
	}
	cout << ans <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

C - Partitioning the Array

数论不过关。

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef unsigned long long ull;
const int N = 2e5 + 10;
int a[N];
int n;

bool check(int k){
	int g=0;
	for(int i=1;i<=k;i++)
	{
		vector<int> path;
		for(int j=i;j<=n;j+=k)
			path.push_back(a[j]);
		sort(path.begin(),path.end());
		for(int j=1;j<path.size();j++)
			g = __gcd(g,path[j]-path[j-1]);
	}
	//cout << k << " " << g <<endl;
	return g!=1;
}

void solve()
{	
	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) continue;
		if(check(k)) ans++;
	}

	cout << ans <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}

D - Array Repetition

int128魅力时刻

直接暴力模拟即可

小心卡常，长度超过1e18后就不要再继续增大了！！！

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

const int N = 1e5 + 10;
const int M = 1e18;
__int128_t len[N];
int bj[N],num[N];
int n,q;

void solve()
{	
	cin >> n >> q;
	int cnt = 0;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin >> x >> y;
		cnt++;
		if(x==1)
		{
			len[i] = len[i-1] + 1;
			num[i] = y;
			bj[i] = 1;
		}
		else
		{
			len[i] = len[i-1]*(y+1);
			if(len[i]>M) len[i] = M + 1; //这句一定要，不然会卡常！！！！
			bj[i] = 2;
		}
	}

	for(int j=1;j<=q;j++)
	{
		int x;
		cin >> x;
		//int z=lower_bound(len+1,len+1+n,x)-len;
		//z=x;
		//cout << x <<" "<<z<<endl;
		for(int i=lower_bound(len+1,len+1+n,x)-len;i>0;i=lower_bound(len+1,len+1+i,x)-len){
			if(bj[i]==2)
			{
				x %= len[i-1];
				if(x==0) x=len[i-1];
				// if(z==4)
				// {
				// 	cout << i << " " <<x;
				// }
			}
			else
			{
				if(x==len[i]){	
					cout << num[i] <<" ";
					//cout << num[i] <<" "<<z<<endl;
					break;
				}else i--;
			}
		}
	}
	cout <<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
    return 0;
}