$T1$

考试错误：无。

思路：

找规律题，规律为 (n%2==1)?(n/2)*(n/2+1):(n/2+1)*(n/2-1) 。

代码：

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

$T2$

考试错误：无。

思路：

本题思路过于简单，唯一的坑点只有 $long\ long$，具体思路参考表达式求值，略。

代码：

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

$T3$

考试错误： 写的暴力，骗了 $40$ 分。

思路:

由于代号 $>n$ 的武器无法获得，所以只需统计 $n$ 以下的数字即可。

接下来使用 DP 求前缀和（见代码$↓$）

最后再求组合数即可。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int mp[N];
int a[N],b[N],idx,n,m;
signed f[500][N];
int C(int n,int b){
    if(b==1) return n;
    if(b==2) return n*(n-1)/2;
    if(b==3) return n*(n-1)*(n-2)/6;
    if(b==4) return n*(n-1)*(n-2)*(n-3)/24;
}
signed main(){
	freopen("wq.in","r",stdin);
	freopen("wq.out","w",stdout);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		if(a[i]<=n) mp[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(mp[i]>=i){
			b[++idx]=i;
			for(int j=1;j<=n;j++){
				f[idx][j]=f[idx][j-1]+(a[j]==i);
			}
		}
	}
	cin >> m;
	while(m--){
		int l,r,k;
		cin >> l >> r >> k;
		int cnt=0;
		for(int i=1;i<=idx;i++){
			if(f[i][r]-f[i][l-1]>=b[i]) cnt++;
		}
        if(cnt<k) cout << 0 << endl;
		else cout << C(cnt,k) << endl;
	}
}

$T4$

考试错误：取巧骗分，拿了 $50$ 分。

思路（记搜）：

使用一个栈和一个数组实现 $O(1)$ 查找配对括号。

随后使用记搜：

如果 $l$ 和 $r$ 匹配，则只需查找 [l+1,r-1] 即可，否则就需要查找 [l,R[l]] 和 [R[l]+1,r] 两个区间，其余的细节见代码(注意，代码中的 cost 数组表示涂色的代价)

代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+50;
int dp[N][N][3][3],cost[3];
int n;
int R[N];
stack<int> stk;
int dfs(int l,int r,int x,int y){
    if(R[l]==r&&x!=y) return -1;
    if(dp[l][r][x][y]>=0) return dp[l][r][x][y];
    int mx=0;
    if(R[l]==r){
        int v=cost[x];
        if(r-l==1) mx=v;
        else{
            for(int i=0;i<3;i++){
                for(int j=0;j<3;j++){
                	if(i==x||j==y) 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,R[l],x,i)+dfs(R[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);
    string s;
	cin >> n >> cost[1] >> cost[2];
    cin >> s;
    memset(dp,-1,sizeof dp);
    for(int i=0;i<n;i++){
        if(s[i]=='(') stk.push(i);
        else{
            R[stk.top()]=i;
            stk.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 << endl;
}