前面的碎碎念：
本次比赛A了A/D两题，B题拿优先队列BFS瞎搞了半天，发现状态数太多无法开出标记数组，遂扑街。C题思考了一会，发现有点差分数组那味，但是没有想出啥解法，遂扑街。赛后补完题，感觉B题没有做出来有点不应该，优先队列做法其实很像BFS搜索的过程，DP做法也很妙，思维上还是差一点。C题有点接近了，但是最关键的部分并没有想出来，不过比赛中A了这题的人并不多，情有可原。

题解部分：

A-咪咪游戏
签到题。字符串若全是由mq链接而成，这个字符串长度肯定是偶数，所以长度为奇数的字符串肯定非法。若字符串长度为偶数，我们就遍历一遍，看其是否均由mq连接而成即可。
时间复杂度：O(Q图片说明|s|)

代码部分：

#include<bits/stdc++.h>
using namespace std;

char R[100005];
int main()
{
    int i,n,Q;
    bool flag;
    scanf("%d",&Q);
    while(Q--)
    {
        scanf("%s",R);
        n=strlen(R),flag=1;
        if(n&1)flag=0;
        for(i=0;flag&&i<n;i+=2)
        {
            if(R[i]=='m'&&R[i+1]=='q')continue;
            else flag=0;
        }
        if(flag)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

B-三角形
此题既可以使用优先队列求解，也可以使用DP求解。
解法一：优先队列
首先对每行都从小到大排序，之后我们开个B数组，用以保存最终的前k小值。先把第一行元素全部赋给B数组，然后开始逐行更新B数组：
对于第i行，我们把B[1]+A[i][1],B[2]+A[i][1],...,B[k]+A[i][1]全部压入优先队列。之后开始出队，出队更新B数组的同时，还要把其对应的A[i][j]替换成A[i][j+1]再次压入队。什么意思呢，比如出队元素的值对应为原来的B[1]+A[i][1]，那么我们就要把B[1]+A[i][2]压入队，也就是把B[1]+A[i][1]-A[i][1]+A[i][2]压入队。通过这样的操作，我们就可以得到一个新的B数组，其保存了从第一行到该行的前k小值，这部分的做法其实有点类似于BFS搜索。
经过逐行更新后，我们最后再遍历一遍B数组，把前小值全部加起来输出即可。
时间复杂度：O(n图片说明k图片说明log(k))

代码部分：

#include<bits/stdc++.h>
using namespace std;

struct node
{
    int w,h;
    bool operator<(const node &a)const
    {
        return a.w<w;
    }
}r,f;
int A[105][105],B[10005];
priority_queue<node>Q;
int main()
{
    int i,j,k,n,m,ans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&A[i][0]);
        for(j=1;j<=A[i][0];j++)scanf("%d",&A[i][j]);
        sort(A[i]+1,A[i]+1+A[i][0]);
    }
    for(i=1;i<=A[1][0];i++)B[i]=A[1][i];
    B[0]=A[1][0];
    for(i=2;i<=n;i++)
    {
        while(!Q.empty())Q.pop();
        for(j=1;j<=B[0];j++)r.w=B[j]+A[i][1],r.h=1,Q.push(r);
        for(j=1;j<=min(m,B[0]*A[i][0]);j++)
        {
            f=Q.top(),Q.pop();
            B[j]=f.w;
            if(f.h+1<=A[i][0])r.w=f.w-A[i][f.h]+A[i][f.h+1],r.h=f.h+1,Q.push(r);
        }
        B[0]=j-1;
    }
    for(i=1;i<=m;i++)ans+=B[i];
    printf("%d\n",ans);
}

解法二：DP
我们设DP[i][j]为前i行每行选一个元素，其和为j的方案数。设原数组为A，前n行每行选一个数的和的最大值为s，那么有状态转移方程：

for(DP[0][0]=i=1;i<=n;i++)
        for(j=1;j<=A[i][0];j++)
            for(k=s;k>=A[i][j];k--)DP[i][k]+=DP[i-1][k-A[i][j]]

求解出这个DP数组后，我们就知道了前n行每行选一个元素，其和为1,2,3,...,10000的方案数。我们按和从小到大遍历一边DP数组，根据数量进行加减即可得出最终答案。
时间复杂度：O(n^2图片说明m图片说明max(wi))

代码部分：

#include<bits/stdc++.h>
using namespace std;

int A[105][105],DP[105][10005];
int main()
{
    int i,j,k,n,m,s=0,ans=0;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&A[i][0]),k=0;
        for(j=1;j<=A[i][0];j++)scanf("%d",&A[i][j]),k=max(k,A[i][j]);
        s+=k;
    }
    for(DP[0][0]=i=1;i<=n;i++)
        for(j=1;j<=A[i][0];j++)
            for(k=s;k>=A[i][j];k--)DP[i][k]+=DP[i-1][k-A[i][j]];
    for(j=0,i=1;j<m&&i<=s;i++)
    {
        if(m-j>=DP[n][i])j+=DP[n][i],ans+=i*DP[n][i];
        else ans+=(m-j)*i,j=m;
    }
    printf("%d\n",ans);
    return 0;
}

C-区间加
此题有位大佬写的很妙，这里借鉴他的做法，考虑从差分数组的角度理解。
我们用A数组保存每个位置离变成m，还需要加多少次1，用j记录下现在还没有匹配的区间左端点的个数。
那么从左往右扫一遍A数组，令ans初值为1，有以下四种情况：
一：若A[i]-A[i+1]的绝对值大于1，那么就表示非法，直接输出0结束程序。因为每个点只能作为最多一个区间的端点，这样假设相邻的两个点i,i+1。i左边未配对的左端点数量为a，如果i处放一个右端点，那么包含i的区间数量就是a，包含i+1的就是a(在i+1处放一个左端点)或者a-1(i+1处不放左端点)。如果i处放一个左端点，那么包含i的区间数量为a+1，包含i+1的为a+1(i+1处放一个右端点或不放)或a+2(i+1处放一个左端点)。所以所有情况都满足i和i+1的差值不超过1。
二：若A[i]-A[i+1]=1，那么我们就要在i这个位置放一个右端点，对应的左端点有j种选择，所以答案乘以j。同时因为左端点已经匹配了一个，因此j要减一。
三：若A[i]-A[i+1]=0，我们可以在i处放一个右端点，再在i+1处放一个左端点，放右端点的时候有j种方案。当然可以什么都不做，所以就有(j+1)种方案，所以答案乘以(j+1)即可。
四：若A[i]-A[i+1]=-1，我们就要在i+1这个位置放一个左端点，因此j要加一。
时间复杂度：O(n)。

代码部分：

#include<bits/stdc++.h>
using namespace std;

const long long mod=998244355;
int main()
{
    int i,j,n,m,A[2005]={0};
    long long ans=1;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&j),A[i]=m-j;
    for(i=j=0;i<=n;i++)
    {
        if(abs(A[i]-A[i+1])>1)
        {
            printf("0\n");
            return 0;
        }
        if(A[i]-A[i+1]==1)ans=ans*j%mod,j--;
        else if(A[i]==A[i+1])ans=ans*(j+1)%mod;
        else j++;
    }
    printf("%lld\n",ans);
    return 0;
}

D-多元组
我们先考虑DP解法，设状态DP[i][j][k]为：前i个元素中，长度为j，且最后一个元素值为k的严格上升序列的个数，那么DP[n][m][0]+DP[n][m][1]+...+DP[n][m][max(a)]即为最终答案，状态转移方程如下：

for(i=1;i<=n;i++)
{
    for(j=1;j<=m;j++)
        for(k=0;k<=max(a);k++)DP[i][j][k]=DP[i-1][j][k];
    DP[i][1][a[i]]++;
    for(j=2;j<=m;j++)
        for(k=0;k<a[i];k++)DP[i][j][a[i]]+=DP[i-1][j-1][k];
}

其中DP数组第一维可以利用滚动数组优化，而第三维可以利用离散化+二分查找优化，但即使如此，此DP做法的时间复杂度也高达O(m图片说明n^2图片说明log(n))。
观察状态转移方程，我们不难发现这个状态转移过程可以由树状数组优化。设DP[i][j]为长度为i，且最后一位为j的严格上升序列的个数。那么状态转移过程就变成了：

for(i=1;i<=n;i++)
{
    update(1,a[i],1);
    for(j=2;j<=m;j++)update(j,a[i],getsum(j-1,a[i]-1));
}

那么最终答案即是getsum(m,max(a[i]))。当然同样的，我们要先对a数组进行离散化处理，不然a[i]太大会导致树状数组开不出来。
时间复杂度：O(n图片说明m图片说明log(n))
代码部分：

#include<bits/stdc++.h>
using namespace std;

const int mod=1e9+7;
int L,A[100005],B[100005],DP[55][100005];
int lowbit(int x)
{
    return x&(-x);
}
void update(int j,int i,int x)
{
    while(i<L)DP[j][i]=(DP[j][i]+x)%mod,i+=lowbit(i);
}
int getsum(int j,int i)
{
    int s=0;
    while(i)s=(s+DP[j][i])%mod,i-=lowbit(i);
    return s;
}
int main()
{
    int i,j,k,n,m;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)scanf("%d",&A[i]),B[i]=A[i];
    sort(B+1,B+1+n);
    for(i=L=2;i<=n;i++)if(B[i]!=B[i-1])B[L++]=B[i];
    for(i=1;i<=n;i++)
    {
        k=lower_bound(B+1,B+L,A[i])-B;
        update(1,k,1);
        for(j=2;j<=m;j++)update(j,k,getsum(j-1,k-1));
    }
    printf("%d\n",getsum(m,L-1));
    return 0;
}

完结撒花，若有疏漏之处，请大佬们轻喷。