A
题意其实有点迷(其实是自己读题没认真)
就是只要问字符串是不是由若干个"mq"组成
所以长度奇数的肯定就是No(不过数据貌似没有mqmqm这种？试了下竟然ac了)
否则就去看奇数位置是不是m 偶数位置是不是q 都是的话就Yes 不然就No

#include<bits/stdc++.h>
using namespace std;
int main(){

    int q;cin>>q;
    while(q--){
        string s;cin>>s;
        int len=s.size();
        if(len&1) {puts("No");continue;}
        int flag=0;
        for(int i=0;i<len;i++){
            if(i&1 && s[i]!='q') flag=1;
            else if(!(i&1) && s[i]!='m') flag=1;
        }
        puts(flag?"No":"Yes");
    }
    return 0;
}

B
背包计数问题
dp[i][j]表示对于前i个宝箱，能装的价值为j的方案数有多少
转移的话就很简单了 dp[i][j]+=dp[i-1][j-v] v为当前宝物的价值 因为只能选一个 类比01背包 所以j倒序
最后只要计算Σ(dp[i][j]*j)即可 其中(Σj)=k

#include<bits/stdc++.h>
using namespace std;
int dp[105][105*105],a[105];
int main(){
    ios::sync_with_stdio(0);
    int n,m;cin>>n>>m;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        int x;cin>>x;
        for(int j=1;j<=x;j++){
            int q;cin>>q;
            for(int k=10000;k>=q;k--)
                dp[i][k]+=dp[i-1][k-q];
        }
    }
    int ans=0;
    for(int i=1;i<=10000;i++){
        if(dp[n][i]<m){
            ans+=dp[n][i]*i;
            m-=dp[n][i];
        }
        else
        {
            ans+=m*i;
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

C
序列这种区间加的问题，还是先考虑下差分，首先让a[i]=m-A[i]
算出每个位置离m还需要进行多少次操作，
然后进行差分a[i]-a[i-1] 这样算出来位置i比位置i-1需要多操作几次或者少操作几次
这里注意一下 差分之后的值b[i] 如果＞1 或者＜-1，那么直接输出0即可。
想一下，如果我这个位置比上一个位置多了2，意味着i位置这里比i-1位置多进行了两次操作，
怎么多呢，肯定是在i位置放一个左括号，但是因为一个位置左括号只能放一个，
如果还想让i位置操作次数增加，就只能放在i位置前面了，也就是放在≤i-1的位置
那这样这个左括号又同时覆盖了i-1和i位置，所以如果差分数组abs(b[i])>1 直接输出0即可
那么剩下了三种情况我们需要维护一个变量now来表示从左往右当前的左边为匹配的左括号数量
一、如果a[i]==1，意味着i比i-1要多操作一次，所以在i这个位置放一个左括号,未配对左括号多了一个，now++。
二、如果a[i]==-1,意味着i比i-1要少操作一次，所以在i-1这个位置放一个右括号，这里就要去计算下答案ans=ans * now
意思就是看i-1这个右括号，在前面now个左括号选一个配对，此时左括号配对了一个，now--。
三、a[i]==0，说明i和i-1操作次数一样，那么我们可以什么都不动，也可以在i处放一个右括号，所以方案数就是ans=ans * (now+1),now个左括号可以选择，还有一种不进行操作的可能。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244355;
ll a[2005],b[2005];
int main(){
    ios::sync_with_stdio(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]=m-a[i],b[i]=a[i]-a[i-1];
    ll ans=1,now=0;
    for(int i=1;i<=n;i++){
        if(abs(b[i]>1)) return cout<<0,0;
        if(b[i]==1) ++now;
        if(b[i]==-1) (ans*=now)%=mod,now--;
        if(b[i]==0) (ans*=(now+1))%=mod;
    }
    cout<<ans<<endl;
    return 0;
}

D
就是一个长度为n的序列，求长度为k的递增子序列个数呗？
(话说这不是原题嘛？ https://ac.nowcoder.com/acm/contest/3566/C 原题的链接 改个模数和树状数组大小都过了)
仔细地说一下吧
首先考虑的是dp
dp[i][j]表示以a[i]结尾的长度为j的个数
转移也很简单 就是dp[i][j]+=dp[k][j-1] && a[i]>a[k] 代码如下

 dp[0][0]=1;

    for(int i=1; i<=n; i++)
    {
        for(int j=0; j<i; j++)
        {
            for(int kk=1; kk<=k; kk++)
            {
                if(a[i]>a[j])
                    dp[i][kk]=(dp[i][kk]+dp[j][kk-1])%mod;
            }
        }
    }

这样子复杂度是n * n * k 高的批爆 肯定不行
接下来我们考虑优化 对于长度k这一层肯定是不行的，肯定就是从k-1个转移到k个来
对于a[i]>a[j]这一步而言 a[i]需要和他前面所有的数进行比较大小
所以 考虑树状数组维护已经计算过的以a[i]结尾的的长度为k的方案数
那么我们去维护k个树状数组，对于每次的长度k，我们去计算长度为k-1的树状数组中 结尾＜a[i]的方案数
长度为k-1，最后一个数还＜a[i]，那我把a[i]接到后面，不就形成了以a[i]结尾的长度为k的方案数嘛
所以长度为k的以a[i]结尾的方案数 = 长度为k-1的树状数组中 结尾＜a[i]的方案数
然后我们把长度为k的以a[i]结尾的方案数更新到维护的长度为k的树状数组上即可
最后我们只要计算维护长度为k的树状数组中所有的方案数总和就是答案了
复杂度 n * logn *k

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e5+5;
ll c[maxn][52],a[maxn],b[maxn];
void add(ll x,ll k,ll v){
    for(;x<maxn;x+=x&(-x)) (c[x][k]+=v)%=mod;
}
ll sum(ll x,ll k){
    ll ans=0;
    for(;x;x-=x&(-x)) (ans+=c[x][k])%=mod;
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i],b[i]=a[i];
    sort(b+1,b+1+n);
    int m=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++) a[i]=lower_bound(b+1,b+1+m,a[i])-b;
    for(int i=1;i<=n;i++){
        add(a[i],1,1);
        for(int j=2;j<=k;j++){
            add(a[i],j,sum(a[i]-1,j-1));
        }
    }
    cout<<sum(n,k)<<endl;
    return 0;
}