Mutter:
Originally, I thought it was the same difficulty as the previous questions. As a result, I would write a question. I didn't learn the line segment tree at that time, and I couldn't learn multiple groups of backpacks, but in fact, this difficulty is acceptable
Portal
A-mimi games
Main idea of the title:
Ask you one string at a time to determine whether it is connected by mq

Difficulty:
After you understand the topic, you can do it well. A sign in question
Topic type: simulation

Idea:
1. It must be an even string connected by mq
2. If it is an even string, use a variable of strng class to simulate the connection process

Complexity:
\thetaθ (log n)

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int main(){
    int q;
    js;
    cin>>q;
    string s,ss;
    while(q--){
        s="";
        cin>>ss;
        int len = ss.size();
        if(len&1){
            cout<<"No"<<endl;
            continue;
        }
        len>>=1;
        for(int i = 0 ; i < len ;++i) s+="mq";
        if(s==ss) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

B-triangle
Main idea of the title:
Take one number from each group of n numbers and add it to get a sum a[i], and find the sum of the first m small and a[i]

Difficulty:
At the beginning, if I thought of violent enumeration and then observed how to optimize, I could still do it. At that time, I just wanted violent enumeration.. This is impossible
Topic type: dp

Idea:
After careful observation, it will be found that all the n treasure boxes and may not be large, so you can enumerate all the situations with dp and take the first m as large.
Multiple sets of knapsacks, status dp[i][k], indicates the number of knapsacks with a sum of K when processing (summing) the ith knapsack, and dp[i][k]=0 indicates that there is no such sum;
State transition equation: dp[i][k]+=dp[i-1][k-a[i][j]], the final answer is to add up the first m in dp[n][1~tot], and tot is the largest sum of N treasure boxes

Complexity:
In case of violent enumeration, it will not time out, but all schemes cannot be saved. The complexity of dynamic planning:
Enumerate n treasure boxes, take out m treasures, and up to 10000 results, so the total complexity is \ theta θ (10000*nm)

#include<bits/stdc++.h>
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int f[105][10005],a[105][105];
int n,m,tot=0;
int main() {
    js;
    cin>>n>>m;
    for(int i=1;i<=n;++i) {
        cin>>a[i][0];
        int sum=0;
        for(int j=1;j<=a[i][0];++j) {
            cin>>a[i][j];
            sum=sum<a[i][j]?a[i][j]:sum;
        }
        tot+=sum;
    }
    f[0][0]=1;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=a[i][0];++j)
            for(int k=tot;k>=a[i][j];--k)    if(f[i-1][k-a[i][j]]) {
                f[i][k]+=f[i-1][k-a[i][j]];
            }
    int cnt=0,ans=0;
    for(int i=1;i<=tot;++i) {
        while(f[n][i]) {
            ans+=i;
            --f[n][i];
            ++cnt;
            if(cnt==m) return cout<<ans<<endl,0;
        }//If direct ans+=i* f[n][i], the number may exceed m 
    }
}

C-interval plus
Main idea of the title:
Niu Mei has a group of numbers with length n stored in the array in order. She wants to change these numbers into m. she can add all the numbers in it by selecting any interval [ai~aj], J > = I. The I and j of each interval, i.e. the starting point and ending point, cannot be the same. How many schemes are there

Idea:
The meaning of the question is that the starting point and end point of the interval are different, which is very important.
It can be written as bracket matching. First, a[i] represents the number of operations required for Ai=m. on this basis, a[i]-=a[i-1] represents whether the number of operations required for Ai=m is more or less than A(i-1)=m. in particular, a[1] represents the number of operations required for Ai=m, and a[n+1] represents the opposite number of operations required for An=m. after this processing, the bracket matching problem is solved.
If a[i]=1 means that Ai=m requires 1 more operations than A(i-1)=m, we need to put an open bracket at the position of I, that is, now + +;
If a[i]=-1 means that Ai=m requires 1 fewer operations than A(i-1)=m, we need to put a right bracket at I-1. There are now options for the corresponding left bracket, and adding a right bracket will reduce one left bracket, so the answer is multiplied by now –;
If a[i]=0, it means Ai=A(i-1). You may enclose I-1 or I-1 and I with left parentheses, and then add a right parenthesis or fixed left and right parentheses at a fixed position. There are now schemes, or you can do nothing, so the answer is multiplied by (now+1). In particular, when now==0, it means that Ai and A(i-1) are m, and no operation is required.
Note: if a[i] is greater than 1 or less than - 1, it means that a[i]=-1 means that Ai=m requires more or less operations than A(i-1)=m. this scheme does not exist. For example, a[i]=2, we can only put an open bracket in I. if we also put one at I-1, it is obvious that Ai and A(i-1) will not be equal, but multiple brackets cannot be placed at one position, so the direct output answer is 0 at this time, Other situations are similar.

Complexity:
Judge whether to add parentheses from beginning to end, complexity \ theta θ (n)
Topic type: Thinking

#include<bits/stdc++.h>
#define ll long long 
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod = 998244355;
int a[2005],n,m;
int main() {
    js;
    cin>>n>>m;
    for(int i=1;i<=n;++i) {
        cin>>a[i];        //Deposit Ai 
        a[i]=m-a[i];    //a[i] indicates the number of operations required for Ai=m 
    }
    for(int i=n+1;i>=1;--i)    a[i]-=a[i-1];    //a[i]=-1 means less operations than i-1, that is, greater than i-1, and vice versa. If it is equal to 0, it is equal 
    ll now=0,ans=1;
    for(int i=1;i<=n+1;++i) {
        if(a[i]<-1||a[i]>1)    return cout<<"0"<<endl,0;
        if(a[i]==-1)    ans=ans*now-- % mod;
        if(!a[i])    ans=ans*(now+1) % mod;
        if(a[i]==1)    ++now;    
    }
    cout<<ans<<endl;
    return 0;
}

D-multivariate group
Main idea of the title:
Given a sequence a, how many increasing subsequences with length m are there

Leading knowledge:
ai=109 is relatively large, and the discretization of line segment tree is needed to compress ai=109 to n=10^5
Then we use the tree array to get the sum of the intervals

Difficulty:
No line segment tree and discretization are not easy to write
Topic type: dp, discretization, tree array

Idea:
It can be regarded as the problem of finding LIS (longest increasing subsequence) with length m.
Status: dp[i][j], ending with a[i], lis with length j
State transition equation: dp[i][j]=\sum_{1}^{i-1}{dp[k][j-1]}∑
1
i−1
​
dp[k][j−1]
Σ can be maintained with a tree array. If you enumerate the length of a tree array first.
The specific operations are as follows:
Status: tree[len][a[i]], lis with length len ending with a[i],
State transition equation: tree[len][a[i]]+=sum(len-1,a[i]-1). State transition needs to be maintained with add, and other places involving a[i] need to be modified

Complexity:
O(mnlog⁡n)

code:

#include<bits/stdc++.h>
#define ll long long 
#define  js  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int mod = 1e9+7;
ll tree[51][100001];
inline int lowbit(int x) {
    return (x&-x);    //Get the power of the first non-zero 1 of x binary 
}
void add(int i,int x,ll v) {
    while(x<=100000) {
        tree[i][x]=(tree[i][x]+v)%mod;
        x+=lowbit(x);
    }
}//State transition and maintain places containing a[i] 
ll sum(int i,int x) {
    ll sum=0;
    while(x) {
        sum=(sum+tree[i][x])%mod;
        x-=lowbit(x);
    }
    return sum;
}//The number of lis whose ending is less than or equal to x
int a[100001], b[100001],n,m;
int main() {
    js;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int cnt=unique(b+1,b+1+n)-b-1;    //Get the number of non repeating elements in b, and the redundant elements are moved to the back of the array 
    for(int i=1;i<=n;++i)    a[i]=lower_bound(b+1,b+1+cnt,a[i])-b;    //Discretization
    for(int i=1;i<=n;++i)
        for(int len=1;len<=m;++len)
            if(len==1)    add(1,a[i],1);
            else add(len,a[i],sum(len-1,a[i]-1));
    cout<<sum(m,n)<<endl;
    return 0;
}