牛客OI周赛15-普及组

1. 咪咪游戏
bool f1,f2,f;
f1用于记录m
f2用于记录q
f用于判断串的好坏。1为坏，0为好
注意几种情况：
mqm
mmq
具体看代码：

 #include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string s;
    while(n--)
    {
        bool f1=0;
        bool f2=0;
        bool f=0;
        cin>>s;
        char ch=getchar();
        for(int i=0;i<s.length();i++)
        {
            if(s[i]=='m'&&f1==0)
            {
                f1=1;
                continue;
            }
            else if(s[i]=='q'&&f2==0&&f1==1)
            {
                f1=0;
                continue;
            }
            else 
            {
                f=1;
                break;
            }
        }
        if(f||f1)cout<<"No"<<endl;//注意最后判断时，还要判断f1，因为f1=0才说明mq都配对成功，没有多余的m
        else cout<<"Yes"<<endl;
    }
    return 0;
}

2. 三角形
dp问题
我们可以用dp来把所有的情况都算出来，最后取他要求的前m大就行
dp[i][j]表示前i个宝箱，装的宝物价值为j的方案数量，dp=0则说明没有这种情况
转移方程：
dp [ i ] [ k ] + = dp [ i - 1 ] [ k - a [ i ] [ j ] ] ;
最后把dp [ n ] [ j ] ( j = 1 ~ tot）加起来，不要忘了还有限制条件前k个
tot是宝物的最大价值（即每组最贵的宝物之和）

 #include<bits/stdc++.h>
using namespace std;
const int maxn=10200;
int a[maxn][maxn];
int dp[maxn][maxn];
int sum=0;
int tot=0;
int main()
{
    int n,k;
    int m[maxn];
    cin>>n>>k;
    dp[0][0]=1;
    memset(m,0,sizeof(m));
    for(int i=1;i<=n;i++)
    {
        cin>>m[i];
        for(int j=1;j<=m[i];j++)
        {
            cin>>a[i][j];
            sum=max(sum,a[i][j]);
        }
        tot+=sum;
    //    cout<<tot<<endl; 
    }
    sum=0;
    for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= m[i]; j ++)
    for (int k = tot; k >= a[i][j]; k --)
            dp[i][k] += dp[i - 1][k- a[i][j]];

    for(int i=1;i<=tot;i++)
    {
    //    cout<<dp[n][i]<<endl;
        if(k>=dp[n][i])
        {
            sum+=i*dp[n][i];
            k-=dp[n][i];

        }
        else 
        {
            sum+=i*k;
            break;
        }


    }
        cout<<sum;
            return 0;
}

3. 区间加
题解：
序列区间的问题可以考虑差分
先注意题目要求：每个区间的头与尾都是不相同的，也就是说每个位置不能同时放多个左括号或右括号，但允许同时放 ( 和 )
首先我们用a1[]来存a距离目标m差多少
a1 [ ] = m - a [ ]
然后用b来存a1的差分
b [ i ] = a [ i ] - a [ i - 1 ]
根据b的值分成四种情况：
1.当b<-1||b>1,此时i-1与i两个位置的数，差值大于等于2。比如b=2，意味着i位置的数要比i-1位置的数多操作两次，那就说明i-1与i之间要有两个左括号才可以，这样区间包括i但是不包括i-1，但题目要求一个位置不存在多个左括号，所以遇到这种情况，就说明此数据根本无法满足题目要求，输出0即可
2.如果b=1，说明i要比i-1多操作一次，那就是i-1与i之间有一个左括号，i-1 （ i，这样i就在一个区间里而i-1不在，i就比i-1多操作一次。
光有左括号不行还要有右括号，我们可以先把右括号的位置待定，因为后面的数据还没处理到，你不知道右括号要放哪，用w来表示还没配对的左括号的数量。b=1时，w++
3.b=-1时，就是上一种情况反过来，i-1与i之间有一个右括号，此时用到右括号，就去看之前有多少左括号，好去配对
sum用于记录总值，初始为1
sum+=sumw
有w个左括号，说明此处可以形成w个区间，之前已经有sum个区间了，总区间数就是sumw
4.b=0,说明i-1与i相等，那他们俩就在同一个区间里。我们可以选择不操作，如果在i之前有左括号，i之后可以放右括号
sum=sum*w+sum

#include<bits/stdc++.h>
typedef long long ll;
const ll mod=998244355;
const int maxn=2010;
ll a[maxn],a1[maxn],b[maxn];
using namespace std;
int n,m;
ll sum=1,ant;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a1[i]=m-a[i];
        b[i]=a1[i]-a1[i-1];
    }
    int w=0;
    for(int i=1;i<=n;i++)
    {
        if(b[i]<-1||b[i]>1)
        {
            cout<<0;
            return 0;
        }

        else if(b[i]==1)w++;

        else if(b[i]==-1)
        {
            sum=(sum*w)%mod;
            w--;
        }

        else if(b[i]==0)
        {
            sum=(sum*(w+1))%mod;
        }
    }
    cout<<sum;

} 

4. 多元组
题解：
求长度为k的递增子序列的数量：
想了一阵子，最后还是看了看其他题解
诶呀，要上网课了，等有空再更新最后一个题