T1 学习求余

k=n/2+1; q=n%k;

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

T2提取数字

遍历字符串s:

s[i]是数字 sum=sum*10+s[i]-'0';

s[i]是字母且之前出现数字 ans+=sum+5; sum=0;

最后判断sum!=0 ans+=sum+5;

cout<<ans;

#include<bits/stdc++.h>
using namespace std;
int main(){
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
	int n;
	cin>>n;
	string s;
	cin>>s;
	long long ans=0,sum=0;
	bool vis=0;
	for(int i=0;i<s.size();i++){
		if(s[i]>='0'&&s[i]<='9'){
			sum=sum*10+(s[i]-'0');
			vis=1;
		}else if(vis){
			sum+=5;
			ans+=sum;
//    cout<<sum<<' ';就是这里忘记删了导致全错了；（不嘻嘻）
			sum=0;
			vis=0;
		}
	}
    if(vis)
    ans+=sum+5;
	cout<<ans;
	return 0;
}

T3武器选择

预处理：前缀和 f[i][j]=f[i][j-1]+(a[j]==i);

d[i] : 需要遇到i次才能得到代号为i的武器；

ans[s][k] : 组合数--答案 $C_s^k$

cnt[i] ： 代号为i的武器出现了几次；

fx : 能获得的武器数量；

遍历武器能否在区间[L，R]获得 s++

最后输出 ans[s][k]

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long a[N],b[N],ans[N][6],cnt[N];
int f[500][N],fx;
int main(){
    freopen("wq.in", "r", stdin);
    freopen("wq.out", "w", stdout);

    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]<=n)
        cnt[a[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(cnt[i]>=i){
            b[++fx]=i;
            for(int j=1;j<=n;j++){
                f[fx][j]=f[fx][j-1]+(a[j]==i);
            }
        }
        ans[i][1]=i;
        if(i>=2) ans[i][2]=i*(i-1)/2;
        if(i>=3) ans[i][3]=i*(i-1)*(i-2)/6;
        if(i>=4) ans[i][4]=i*(i-1)*(i-2)*(i-3)/24;
    }
    int m;
    cin>>m;
    while(m--){
        int l,r,k,s=0;
        cin>>l>>r>>k;
        for(int i=1;i<=fx;i++){
            if(f[i][r]-f[i][l-1]>=b[i])
            s++;
        }
        cout<<ans[s][k]<<endl;
    }
    return 0;
}

T4括号序列

dp+记忆搜索优化

dp[i][j][x][y]:第i个括号的颜色为x，第j个括号的颜色为y

R[i]:左括号i的右括号是R[i]

分情况讨论：

1 .R[l]==r : l与r配对 dfs(l+1,r-1,i,j)

2 .R[l]!=r : l与r不配对 dfs(l,R[l],x,i) dfs(R[l]+1,r,j,y)

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+9;
int n,a,b;
int dp[N][N][3][3];
int L[N],R[N],c[10];
stack<int> t;

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 k=0;
    if(R[l]==r){
        int s=c[x];
        if(l+1==r) return s;

         for(int i=0;i<=2;i++)
            for(int j=0;j<=2;j++){
                if(x==i||y==j) continue;
                k=max(k,s+dfs(l+1,r-1,i,j));
            }
    }
    else{
        for(int i=0;i<=2;i++)
            for(int j=0;j<=2;j++){
                if(i!=j) 
                k=max(k,dfs(l,R[l],x,i)+dfs(R[l]+1,r,j,y));
            }
         
        }
        dp[l][r][x][y]=k;
        return k;
    
}
int main(){
    freopen("bracket.in", "r", stdin);
    freopen("bracket.out", "w", stdout);
    string s;
    cin>>n>>c[1]>>c[2];
    cin>>s;
    memset(dp,-1,sizeof dp);
    for(int i=0;i<n;i++){
        if(s[i]=='(' )  t.push(i);
        else{
            int id=t.top();
            t.pop();
            L[i]=id;
            R[id]=i;
        }
    }
    int ans=0;
    for(int i=0;i<=2;i++)
    for(int j=0;j<=2;j++)
    ans=max(ans,dfs(0,n-1,i,j));

    cout<<ans;    
    
    return 0;
}