比赛链接
A.Nearest Interesting Number
题目大意:给你一个数 n n n,让你找一个最小的 x x x,满足 n x n\leq x nx,且 x x x的数位和是4的倍数。直接暴力跑一下就行了。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int c(int k){
	int s=0;
	//if(k%4)return 0;
	while(k){
		s+=k%10;
		k/=10;
	}
	if(s%4==0)return 1;
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	int a;
	cin>>a;
	for(int i=a;;i++){
		if(c(i)){
			cout<<i<<endl;
			return 0;
		}
	}	
	return 0;
}

B. Equalize Prices
大意:给你 n , k n,k n,k,一个长度为 n n n的数组,对每个数,最多执行一次操作:每次操作可以对 a i a_i ai加或者减 k k k,要求,每个数不必须大于0。让你找出一个最大的可能值 x x x,使得一些操作之后,每个数都等于 x x x
思路:遍历每个数,找到每个数的可能变化区间 [ l , r ] [l,r] [l,r],用来更新答案区间 [ L , R ] [L,R] [L,R],若中间出现无交集的情况,说明无解,输出-1.有解的答案就是R了。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int t;
int n,a[N],k;
int main(){
	ios::sync_with_stdio(false);
	for(cin>>t;t;t--){
		cin>>n>>k;
		for(int i=1;i<=n;i++)cin>>a[i];
		int L,R,sta=0;
		for(int i=1;i<=n;i++){
			int l=max(1,a[i]-k);
			int r=a[i]+k;
			if(i==1){L=l;R=r;}
			else{
				if(R<l||L>r){
					sta=1;
					break;
				}
				if(l<L){
					if(r<R){
						R=r;
					}
				}else{
					if(r<R){
						R=r;
						L=l;
					}else{
						L=l;
					}
				}
			}
		}
		if(sta)cout<<-1<<endl;
		else cout<<R<<endl;
	}
	return 0;
}

C - Computer Game
大意: q q q组询问,每组询问给出四个数 k , n , a , b k,n,a,b k,n,a,b,初始有 k k k的能源,要进行 n n n回合,你可以在能源严格大于 a a a的时候进行一回合(第一种),在能源严格大于 b b b的时候进行一个回合(第二种)。问你最多可以进行几次第一种回合。若无法完成 n n n轮,输出-1.
思路:答案显然单调,二分答案即可。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
LL q,t;
LL a,b,c,d;
int main(){
	ios::sync_with_stdio(false);
	for(cin>>t;t;t--){
		cin>>a>>b>>c>>d;
		if(d*b>=a){
			cout<<-1<<endl;
		}else{
			LL l=0,r=b,ans=0;
			while(l<=r){
				LL mid=l+r>>1;
				if(mid*c+(b-mid)*d<a)ans=mid,l=mid+1;
				else r=mid-1;
			}
			cout<<ans<<endl;
		}
	}	
	return 0;
}

D - Candy Box (easy version)
大意: q q q次询问,每次询问给出 n n n个数,让你从这给数列找一组数,使得没有出现相同次数的两种数,问最多多少个。
思路:贪心模拟一下。按每个数出现的次数排下序,然后直接加即可。注意下细节。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int cnt[N],n,t,f[N],a[N];
int main(){
	ios::sync_with_stdio(false);
	for(cin>>t;t;t--){
		cin>>n;
		for(int i=1;i<=n;i++)cnt[i]=0;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			cnt[a[i]]++;
			f[i]=i;
		}
		sort(f+1,f+1+n,[](int A,int B){return cnt[A]>cnt[B];});
		int ans=cnt[f[1]];
		int pre=ans;
		for(int i=2;i<=n;i++){
			if(pre==0)break;
			int P=ans;
			if(cnt[f[i]]>=pre){
				if(cnt[f[i]]==1)break;
				ans+=pre-1;
				pre=pre-1;
			}else{
				ans+=cnt[f[i]];
				pre=cnt[f[i]];
			}
			//cout<<ans-P<<endl;
		}
		cout<<ans<<endl;
	}
	return 0;
}

F - Topforces Strikes Back
大意: q q q次询问,每次询问给你一个 n n n,再给出 n n n个数,让你从中选出3或2或1个数使得再满足条件下和最大。输出最大值。
条件:选出的数两两之间互不整除.
思路:先按大小排序,然后对数列去重。建一个大根堆,然后遍历每一个数,在遍历每个数的时候,对大根堆进行操作,若堆顶元素可以被当前数字整除,则弹出这个堆顶直至取满三个数或者堆顶空。然后记录一下最大值即可。

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int t,n,a[N],dp[N];
int main(){
	ios::sync_with_stdio(false);
	for(cin>>t;t;t--){
		cin>>n;
		int ans=0;
		for(int i=1;i<=n;i++)cin>>a[i],ans=max(ans,a[i]);
		sort(a+1,a+1+n);
		n=unique(a+1,a+1+n)-a-1;
		priority_queue<pair<int,int> >q;
		for(int i=1;i<=n;i++){
			int mid=a[i];
			queue<pair<int,int> >res;
			int pre=0;
			while(!q.empty()){
				if(a[i]%q.top().se==0){
					res.push(q.top());
					q.pop();
					continue;
				}
				if(pre){
					if(pre%q.top().se==0){
						res.push(q.top());
						q.pop();
						continue;
					}
				}
				if(!pre){
					mid+=q.top().fi;
					pre=q.top().fi;
					continue;
				}
				mid+=q.top().fi;
				break;
			}
			while(!res.empty()){
				q.push(res.front());
				res.pop();
			}
			ans=max(ans,mid);
			q.push({a[i],a[i]});
		}
		cout<<ans<<endl;
	}
	return 0;
}

G - Candy Box (hard version)
大意:跟简单版本的差不多,就是多了一个问题,对每个数给出一个 f f f,现在让你在原有的基础上,最大化 f = 1 f=1 f=1的个数。输出最多几个数和最多几个 f = 1 f=1 f=1的数。
思路:记录每个数出现的次数和 f = 1 f=1 f=1的个数,然后还是先按出现次数排序。然后遍历每种数,假设我们上一次使用的数字的个数是 p r e pre pre,那么这次必然是 &lt; p r e &lt; pre <pre个,那么对于出现次数 p r e 1 \geq pre-1 pre1的我们拿的都是一样多的,也就是说在这个意义下这类数的贡献是一样的,那么我们必然从中找出现 f = 1 f=1 f=1的最多的一种数。
注意两个细节:
1.在每次遍历的时候,若堆顶元素出现的次数大于等于 p r e pre pre且,当前遍历到的数字出现的次数小于 p r e 1 pre-1 pre1,那么我们必然要从堆中先取数,才能构成最多的第一个答案。
2.遍历完数后,若堆中还有元素,还要把他取完直到 p r e = 0 pre=0 pre=0

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
int cnt[N],n,t,f[N],a[N],F[N],sa[N];
int main(){
	ios::sync_with_stdio(false);
	for(cin>>t;t;t--){
		cin>>n;
		for(int i=1;i<=n;i++)cnt[i]=0,sa[i]=0;
		for(int i=1;i<=n;i++){
			cin>>a[i]>>F[i];
			cnt[a[i]]++;
			f[i]=i;
			if(F[i])sa[a[i]]++;
		}
		sort(f+1,f+1+n,[](int A,int B){return cnt[A]>cnt[B];});
		int ans=0,B=0;
		int pre=1e9;
		priority_queue<pair<int,int> >q;
		for(int l=1;l<=n&&pre>1;l++){
			int last=l;
			while(!q.empty()&&q.top().se>=pre&&cnt[f[l]]<pre-1){
				ans+=pre-1;
				B+=min(q.top().fi,pre-1);
				pre--;
				q.pop();
			}
			if(pre==1)break;
			q.push({min(sa[f[l]],min(cnt[f[last]],pre-1)),min(cnt[f[last]],pre-1)});
			while(l+1<=n&cnt[f[l+1]]>=min(cnt[f[last]],pre-1)){
				l++;
				q.push({min(sa[f[l]],min(cnt[f[last]],pre-1)),min(cnt[f[last]],pre-1)});
			}
			ans+=min(q.top().se,pre-1);
			B+=min(q.top().fi,min(q.top().se,pre-1));
			pre=min(q.top().se,pre-1);
			q.pop();
		}
		while(!q.empty()){
			if(pre==0)break;
			ans+=min(q.top().se,pre-1);
			B+=min(q.top().fi,min(q.top().se,pre-1));
			pre=min(q.top().se,pre-1);
			q.pop();			
		}
		cout<<ans<<' '<<B<<endl;
	}
	return 0;
}

H - Subsequences (hard version)
大意:给你一个长为 n n n的字符串,再给一个数 k k k,让你从这个字符串中找k个不重复子序列使得花费最小。
假设一个子序列长度为 x x x那么花费就是 n x n-x nx
思路:递推, d p [ i ] [ j ] dp[i][j] dp[i][j]表示前 i i i个字符中,存在 d p [ i ] [ j ] dp[i][j] dp[i][j]个长度为 j j j的子序列。
初始条件 d p [ 0 ] [ 0 ] = 1 dp[0][0]=1 dp[0][0]=1.
对于每一个二元组 i , j {i,j} i,j,这个数由 0 <mtext>   </mtext> i 1 0~i-1 0 i1位置上的 x , j 1 {x,j-1} x,j1递推而来,但是,我们考虑一个问题,现在有一个二元组{2,1},现在他要对{3,2}产生贡献了,那么假设3这个位置的字符与4这个位置的字符相同,那么{4,2}的答案就不可以再加{2,1}的答案,因为他们的子序列是相同,即答案重复。注意这个细节就好了。因为 n n n很小,所以这个暴力跑的很快。
ps:序列自动机优化一下可能更好(懒)

#include<bits/stdc++.h>

#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;

LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
map<pair<int,pair<int,char> > ,int>vis;
LL dp[111][111],n,K,cnt[111];
char a[N];
int main(){
	ios::sync_with_stdio(false);
	cin>>n>>K>>a+1;
	dp[0][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++){
			for(int k=j-1;k<i;k++){
				if(vis[{k,{j-1,a[i]}}])continue;
				dp[i][j]+=dp[k][j-1];
				vis[{k,{j-1,a[i]}}]=1;
				dp[i][j]=min(dp[i][j],K);
			}
		}
	}
	LL ans=0;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=i;j++){
			cnt[j]+=dp[i][j];
		}
	}
	for(int i=n;i>=0;i--){
		LL res=min(K,cnt[i]);
		ans+=(n-i)*res;
		K-=res;
	}
	if(K)cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}