【牛客OI周赛15-普及组】补题

牛客OI周赛15-普及组
链接：https://ac.nowcoder.com/acm/contest/4911

A

A很简单不多说

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        //cout<<t;
        string s;
        cin>>s;
        int len =s.size();
        if(len&1){
            cout << "No"<<endl;
            continue;
        }
        bool flag=0;
        for(int i=1;i<len;i+=2){
            if(!(s[i]=='q'&&s[i-1]=='m')){
                cout << "No"<<endl;
                flag=1;
                break;
            }
        }
        if(!flag) cout << "Yes"<<endl;
    }

    return 0;
}

B

方法1：(堆)
先从每行只有两个数的简单情况分析
设两个序列为a和b，且a，b已升序排序
不难想到最小和一定是a[1]+b[1]，那么次小和就是min( a[1]+b[2], a[2]+b[1])
假设次小和是a[2]+b[1]，那么第三小的就是min( a[1]+b[2], a[2]+b[2], a[3]+b[1]) ...
从上述规律可以发现
如果a[i]+b[j]为第t小，那么a[i+1]+b[j], a[i]+b[j+1]就会成为第t+1小的备选答案
到这里也就不难想到用一个初始只有a[1]+b[1]的二叉堆来维护找前k小和的过程
对于n个序列，可以先求出前两个序列的前k小和，用这k小和组成一个新序列，再与第三个序列处理产生新的前k小和
反复n次最终得到所求答案
方法2：DP，dp[i][s]第i个宝箱得到价值为s的方案数
dp[i][s] = 累加{dp[i - 1][s - a[i][j]}
本题参考官方题解

#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = N * N;
int n, k;
int m[N], a[N][N];
int dp[N][M];//前i个盒子拿价值s的方案数量
int main()
{
    cin >> n >> k;
    int ma = 0;
    for (int i = 1; i <= n; i ++)
    {
        cin >> m[i];
        int cur = 0;
        for (int j = 1; j <= m[i]; j ++)
        {
            cin >> a[i][j];
            cur = max(cur, a[i][j]);
        }
        ma += cur;
    }

    dp[0][0] = 1;
    for (int i = 1; i <= n; i ++)               
        for (int j = 1; j <= m[i]; j ++)         //m[i]表示每一行的数量
            for (int s = ma; s >= a[i][j]; s --)
                if(dp[i - 1][s - a[i][j]])
                    dp[i][s] += dp[i - 1][s - a[i][j]];

    int nuk = 0, ans = 0;
    for (int i = 1; i <= ma; i ++)//从小开始遍历所有价值
    {
        while(dp[n][i]>0)//只要可以拿到，即方案数>0
        {
            ans += i;
            nuk++;
            dp[n][i]--;
            if(nuk == k) return printf("%d\n", ans), 0;
        }
    }
}

D.多元组——树状数组迭代

给你一个序列a，m为元组个数，求比如m=3时有多少个满足 $图片说明$

分析：设t1[i]为a[i]左边比他小的数的个数；
m=2时，显然答案为 $图片说明$

m=3时，序列中a[i]作为第二个数时的贡献即为
左边比他小得数的数量X右边比他大的数的数量，可以直接用两个树状数组就ok
m=任意值时候可以这么去想，先仔细去想想，是不是t1[i]保存的是以i为结尾的二元组的数目?
要求以i为结尾的三元组数目，是不是等价于===求以"i左边小于a[i]的数"为结尾的二元组数目(二元组数目不就是t1[i]吗？)，
同理要求以i为结尾的k元组数目，是不是等价于===求以"i左边小于a[i]的数"为结尾的k-1元组数目；
这个可以在更新树状数组时迭代实现。详见代码
tree数组增加一维表示m，用来迭代

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ENTER cout<<endl
priority_queue<int, vector<int>, greater<int>> pq; //小顶堆
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

inline int read()
{
    int sum=0,ff=1; char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-') ff=-1;
        ch=getchar();
    }
    while(isdigit(ch))
        sum=sum*10+(ch^48),ch=getchar();
    return sum*ff;
}
/***********************************************************/
const int MOD = 1e9+ 7;
const int maxn = 1e7+1;
const int MAXN = 1e5 + 10;
/***********************************************************/
int tree[51][MAXN]={0};
int MAXNTREE;
#define sumMod(x) ((x)>=(MOD)?(x)-(MOD):(x))
inline int query(int k,int pos)
{
    //printf("pos = %d\n",pos);
    int ans = 0;
    while (pos > 0) {
        ans = sumMod(tree[k][pos]+ans);
        pos -= pos & (-pos);
    }
    return ans;
}
inline void update(int k,int pos, int val)
{
    int ans = 0;
    while (pos <= MAXNTREE) {
        tree[k][pos] = sumMod(tree[k][pos]+val);
        pos += pos & (-pos);
    }
}
int Cmp(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int nums[MAXN],sortNums[MAXN],indexArr[MAXN];

signed main()
{
    //freopen("1.in","r",stdin);
    int n,m;
    cin>>n>>m;
    if(m==1) {
        cout<<n<<endl;
        return 0;
    }   
    for(int i=1;i<=n;++i){
        cin>>nums[i];
        sortNums[i]=nums[i];
    }
    ///***索引数组start**///
    sort(sortNums+1,sortNums+n+1);
    int mx=unique(sortNums+1,sortNums+n+1)-sortNums-1;
    int numsSize=mx;
    MAXNTREE=mx;

    for(int i=1;i<=n;i++){
        indexArr[i]=lower_bound(sortNums+1,sortNums+mx+1,nums[i])-sortNums;
    }
    ///***索引数组end**///
    int tmpCnt,i;
    for(i = 1; i<=n; ++i)
    {
        //cout<<indexArr[i]<<endl;
        update(1,indexArr[i], 1);
        for(int k=2;k<=m;++k){
            tmpCnt = query(k-1,indexArr[i] - 1);
            update(k,indexArr[i],tmpCnt);
        }
    }

    ll res = 0;
    for(int i=1;i<=mx;i++){
        res=(res+query(m,i)-query(m,i-1)+MOD)%MOD;
    }
    cout<<res%MOD<<endl;
    return 0;
}