【牛客IOI周赛17-普及组】

A 夹娃娃

求一下前缀和，即可 $O(1)$ 回答询问。整体复杂度 $O(n + k)$ 。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, k, a[N];
int main() {
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        a[i] += a[i - 1];
    }
    while(k--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d\n", a[r] - a[l - 1]);
    }
    return 0;
}

B 莫的难题

求 $C(n, m) \% 10^9+7$
利用公式 $C(n, m) = C(n - 1, m - 1) + C(n - 1, m)$ 可递推求出。
求第 $k$ 小的数。
先列一下从小到大的几个数： $1, 2, 3, 5, 9, 11, 12, 13, 15, 19, 21, 22, 23, 25,...$
显然和进制有关，我们将 $(1,2,3,5,9)$ 转化为 $(0, 1, 2, 3, 4)$ 。
那么数字序列即为：

$0,1,2,3,4$
$00,01,02,03,04,10,11,12,13,14, ...$
$000, 001, 002, 003, ...$
这样就比较显然了：
① 位数为 $n$ 的数字共有 $5^n$ 个。
② 对于位数相同的这些数，即为所对应的五进制数。
因此可以先据 ① 求出 $k$ 所对应的位数长度，以及在该长度下对应的数字大小。然后转五进制就可以了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
ll n, m, C[101][101], f[15], b[] = {1, 2, 3, 5, 9};
void get(ll x) {
    for(int i = 1; ; i++)
        if(x <= f[i]) {
            vector<int> tmp;
            x--;
            for(int j = 0; j < i; j++) {
                tmp.push_back(x % 5);
                x /= 5;
            }
            for(int i = tmp.size() - 1; i >= 0; i--) cout << b[tmp[i]];
            cout << endl;
            break;
        } else x -= f[i];
}
int main() {
    for(int i = 0; i <= 100; i++) {
        C[i][0] = 1;
        for(int j = 1; j <= i; j++) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
    }
    f[0] = 1;
    for(int i = 1; i < 15; i++) f[i] = f[i - 1] * 5;
    int T; cin >> T;
    while(T--) {
        cin >> n >> m;
        ll v = C[n][m];
        get(v);
    }
    return 0;
}

C 不平衡数组

设 $dp[i][1/0]$ 表示 a[i] 是否 $+1$ ，并且使 $1 \sim i$ 均不相同的最小代价。
然后分情况写一下 $dp$ 方程就好了。
如 $a[i] == a[i - 1]$ ，那么若 $a[i]+1$ ，则 $a[i-1]$ 不能 $+1$ ，若若 $a[i]$ 不 $+1$ ，则 $a[i-1]$ 必 $+1$ 。
即：

$dp[i][1] = dp[i - 1][0] + b[i];$

$dp[i][0] = dp[i - 1][1];$

其它情况讨论一下就行。

具体 $dp$ 方程见代码。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
int n, a[N], b[N];
ll dp[N][2];
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    a[0] = a[n + 1] = -10;
    for(int i = 1; i <= n; i++) {
        if(a[i] == a[i - 1]) {
            dp[i][1] = dp[i - 1][0] + b[i];
            dp[i][0] = dp[i - 1][1];
        } else if(a[i - 1] + 1 == a[i]) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]) + b[i];
        } else if(a[i] + 1 == a[i - 1]) {
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][1] + b[i];
        } else {
            dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + b[i];
        }
    }
    cout << min(dp[n][0], dp[n][1]) << endl;
    return 0;
}

D 数列统计

算是一个结论题吧，做过几个基于这个结论出的题了。

当时的姿势应该是这个样子的：

先设 dp[i][j] 表示以 $j$ 结尾，长度为 $i$ 的不下降序列个数。那么 $dp[i][j] = \sum \limits_{k=1}^jdp[i-1][k]$ 。其实就是 $i$ 次前缀和。
4
然后呢打表找规律：

1 1 1 1 1 1 ...
1 2 3 4 5 ...
1 3 6 10 ...
1 4 10 ...
1 5 ...
1 ...

发现是一个斜着的杨辉三角。然后就可以得到答案就是 $C(x + l - 2, x - 1)$ 。
觉着不靠谱的话可以再证明一下。

然后预处理出阶乘 $f[i]$ ，和阶乘逆元 $g[i]$ ，即可 $O(1)$ 回答询问。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
const int mod = 911451407;
int f[N], g[N];
void init() {
    int n = 2e6;
    f[0] = 1;
    for(int i = 1; i <= n; i++) f[i] = 1l * f[i - 1] * i % mod;
    g[0] = g[1] = 1;
    for(int i = 2; i <= n; i++) g[i] = 1ll * (mod - mod / i) * g[mod % i] % mod;
    for(int i = 2; i <= n; i++) g[i] = 1ll * g[i - 1] * g[i] % mod;
}
int C(int n, int m) { return 1ll * f[n] * g[m] % mod * g[n - m] % mod; }
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    int T; cin >> T;
    while(T--) {
        int n, m; cin >> n >> m;
        cout << C(n + m - 2, n - 1) << endl;
    }
    return 0;
}