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

A 咪咪游戏

直接判断奇数位是否均为m，偶数位均为q即可。

/*
* @Author: wxyww
* @Date: 2020-04-03 19:18:25
* @Last Modified time: 2020-04-03 19:20:35
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 100010;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[N];
void solve() {
    scanf("%s",s + 1);
    int n = strlen(s + 1);
    if(n & 1) {
        puts("No");return;
    }
    for(int i = 1;i <= n;i += 2) 
        if(s[i] != 'm') {
            puts("No");return;
        }
    for(int i = 2;i <= n;i += 2)
        if(s[i] != 'q') {
            puts("No"); return;
        }
    puts("Yes");
}
int main() {
    int Q = read();
    while(Q--) {
        solve();
    }

    return 0;
}

B 三角形

用f[i][j]表示前i个箱子，宝物价值和为j的方案数。状态是 $n^2m$ 的。转移的时候枚举当前箱子选的宝物，背包转移即可。复杂度为 $O(n)$
总复杂度就是 $O(n^3m)$ 。

最后枚举宝物价值和，找到前K中方案即可。

/*
* @Author: wxyww
* @Date: 2020-04-03 19:29:25
* @Last Modified time: 2020-04-03 20:43:42
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 110;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
ll ans;
int f[N][N * N];
int a[N][N],len[N];
int main() {
    int n = read(),K = read();
    for(int i = 1;i <= n;++i) {
        len[i] = read();
        for(int j = 1;j <= len[i];++j)
            a[i][j] = read();
    }

    f[0][0] = 1;
    for(int i = 1;i <= n;++i) {
        for(int j = 1;j <= len[i];++j) {
            for(int k = a[i][j];k <= 10000;++k) {
                f[i][k] += f[i - 1][k - a[i][j]];
                f[i][k] = min(f[i][k],K);
            }
        }
    }

    for(int i = 1;i <= 10000;++i) {
        int w = min(K,f[n][i]);
        K -= w;
        ans += w * i;
    }
    cout<<ans;

    return 0;
}

C 区间加

一开始理解错题意了。题目要求“对于任意两次区间加的起始，结束位置各不相同。”而不是“两个区间的不能相同。”

我们用now记录下现在还没有匹配的区间左端点的个数，用 $a[i]$ 表示第 $i$ 个点到 $m$ 还需要加多少。

这样如果 $a[i]$ 比 $a[i - 1]$ 小1，我们就要在i - 1这个位置放一个右端点，对应的左端点有now种选择，所以答案乘以now。

如果 $a[i]$ 比 $a[i-1]$ 大1，我们就要在i这个位置放一个左端点，就让now++

如果a[i]与a[i-1]相等的话，我们可以在i-1处放一个右端点，再在i处放一个左端点，防止右端点的时候有now种方案，也可以什么都不做，所以就有(now+1)种方案，所以答案乘以(now+1)即可。

/*
* @Author: wxyww
* @Date: 2020-04-03 21:19:10
* @Last Modified time: 2020-04-04 07:58:55
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 2010,mod = 998244355;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int a[N];
int main() {
    int n = read(),m = read();
    for(int i = 1;i <= n;++i) a[i] = m - read();
    for(int i = n + 1;i >= 1;--i) a[i] -= a[i - 1];
    ll now = 0,ans = 1;
    for(int i = 1;i <= n + 1;++i) {
        if(abs(a[i]) > 1) {
            puts("0");return 0;
        }
        if(a[i] == -1) ans = ans * now-- % mod;
        if(a[i] == 0) ans = ans * (now + 1) % mod;
        if(a[i] == 1) ++now;
    }
    cout<<ans;
    return 0;
}

D 多元组

用 $f[i][j]$ 表示前 $i$ 个数字，选择了j个数字的方案数量。

如果暴力转移的话就是 $f[i][j]=\sum\limits_{a_k < ai}f[k][j - 1]$

先将一开始的数组离散化一下,然后开K个树状数组优化一下，转移的复杂度就变成了 $O(logn)$ ，总的复杂度就是 $O(n^2logn)$ 。

/*
* @Author: wxyww
* @Date: 2020-04-03 21:07:29
* @Last Modified time: 2020-04-03 21:15:18
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<algorithm>
#include<string>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int N = 100010;
const int mod = 1e9 + 7;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,m,a[N],ls[N],f[N][52];
void update(int *tree,int pos,int c) {
    while(pos <= n) {
        tree[pos] += c;
        tree[pos] >= mod ? tree[pos] -= mod : 0;
        pos += pos & -pos;
    }
}
int query(int *tree,int pos) {
    int ret = 0;
    while(pos) {
        ret += tree[pos];
        ret >= mod ? ret -= mod : 0;
        pos -= pos & -pos;
    }
    return ret;
}
int tree[52][N];
int main() {
    n = read(),m = read();
    for(int i = 1;i <= n;++i) a[i] = ls[i] = read();
    sort(ls + 1,ls + n + 1);

    for(int i = 1;i <= n;++i) a[i] = lower_bound(ls + 1,ls + n + 1,a[i]) - ls;

    ll ans = 0;
    for(int i = 1;i <= n;++i) {
        f[i][1] = 1;
        for(int j = 2;j <= m;++j)
            f[i][j] = query(tree[j - 1],a[i] - 1);
        for(int j = 1;j <= m;++j)
            update(tree[j],a[i],f[i][j]);

        ans += f[i][m];
        ans >= mod ? ans -= mod : 0;
    }
    cout<<ans;

    return 0;
}