题目传送门

A 学习求余

B 提取数字

C 武器选择

D 括号序列

T1学习求余

思路

首先要想积最大那么余数(b)和除数(a)插要小，还要保证在$a+b=n$以及$a!=b$那么奇数是$(n/2)*(n/2-1)$，偶数是$(n/2+1)*(n/2-1)$

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	long long n;
	cin>>n;
	if(n%2==1)cout<<(n/2)*(n/2+1);
	else cout<<(n/2+1)*(n/2-1);
}

#T2提取数字

思路

遇到数字即数位分离求出数字，每个数加5，求和得出答案

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	long long n,c=0;
	string s;
	cin>>n;
	cin>>s;
	for(long long i=0;i<s.size();i++){
		if(s[i]>='0'&&s[i]<='9'){
			long long w=0;
			while(s[i]>='0'&&s[i]<='9'&&i<s.size()){
				w=w*10+s[i]-'0';
				i++;
			}
			i--;
			c+=w;
			c+=5;
		}
	}
	cout<<c;
}

T3武器选择

思路

用前缀和，但要优化，首先代号比关卡多的不能，其次这件武器的个数没到他的代号的不要，然后求前缀和（最多也只有500件可行武器），最后算答案（公式不要写错我就写错了）

代码

#include<bits/stdc++.h>
using namespace std;
long long a[100010],b[100010],c[100010][10],st[100010],n,q;
int f[555][100010],d;
int main(){
	freopen("wq.in","r",stdin);
	freopen("wq.out","w",stdout);
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]<=n)st[a[i]]++;
	}
	for(long long i=1;i<=n;i++){
		if(st[i]>=i){
			b[++d]=i;
			for(long long j=1;j<=n;j++){
				f[d][j]=f[d][j-1]+(a[j]==i);
			}
		}
	}
	cin>>q;
	while(q--){
		long long l,r,k,s=0;
		cin>>l>>r>>k;
		for(long long i=1;i<=d;i++){
			if(f[i][r]-f[i][l-1]>=b[i])s++;
		}
		if(s<k)cout<<0;
		else if(k==1)cout<<s;
		else if(k==2)cout<<s*(s-1)/2;
		else if(k==3)cout<<s*(s-1)*(s-2)/6;
		else cout<<s*(s-1)*(s-2)*(s-3)/24;
		cout<<"\n";
	}
}

错的点

想到前缀和了，但没想到优化，以后要多掌握优化技巧

T4

思路

首先先用一个栈预处理，能在$O(1)$的时间复杂找到左括号配对的有括号（不要配对反了我就配对反了）。然后开始记搜： $l$ 和 $r$ 匹配，找 $l+1$到$r-1$的区间 否则找 $l$到$R[l]$和 $R[l]+1$到$r$ ，其余的自行理解代码最后输出。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a,b,dp[1001][1001][3][3],rr[1010],dj[4];
string s;
stack<int>ss;
int dfs(int l,int r,int x,int y){
	if(rr[l]==r&&x!=y)return -1;
	if(dp[l][r][x][y]>=0)return dp[l][r][x][y];
	int mx=-1;
	if(rr[l]==r){
		int v=dj[x];
		if(l+1==r)mx=v;
		else{
			for(int i=0;i<3;i++){
				for(int j=0;j<3;j++){
					if(x==i||y==j)continue;//此处||打成&&
					mx=max(mx,v+dfs(l+1,r-1,i,j));
				}
			}
		}
	}
	else{
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				if(i!=j)mx=max(mx,dfs(l,rr[l],x,i)+dfs(rr[l]+1,r,j,y));
			}
		}
	}
	dp[l][r][x][y]=mx;
	return mx;
}
signed main(){
	freopen("bracket.in","r",stdin);
	freopen("bracket.out","w",stdout);
	cin>>n>>a>>b;
	cin>>s;
	dj[1]=a;
	dj[2]=b;
	memset(dp,-1,sizeof dp);
	for(int i=0;i<s.size();i++){
		if(s[i]=='(')ss.push(i);
		else{
			rr[ss.top()]=i;//此处配对反了
			ss.pop();
		}
	}
	int mx=0;
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			mx=max(mx,dfs(0,n-1,i,j));
		}
	}
	cout<<mx;
}

错的点

考试没想到记搜，有点难没想到，只拿了暴力分，以后要多思考一下