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

A-夹娃娃

1）知识点

赤裸裸的前缀和，没有任何操作（加个快读，不快读听说会超时）。

2）算法操作

前缀和我就不详细说明了，sum[n]就是前n个数的和，输入的时候一个数组累加统计就好了。
用差值就可以求出来某一段连续区间的和：
```
sum[r] - sum[l - 1]
```

3）打代码

输入数据用于初始化前缀和（毕竟是个简单题目，就尽量缩减计算，能少一步就能快几毫秒）。
然后输入并输出前缀和差值。
直接看代码吧~

AC代码

#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 1e6 + 7;
int sum[MAX];
//全局变量区

template<class T> inline void read(T& res);
template<class T> inline void write(T res);
//函数预定义区

int main() {
    int n, k; read(n); read(k);
    for (int i = 1; i <= n; i++) {
        read(sum[i]);
        sum[i] += sum[i - 1];
    }
    while (k--) {
        int l, r; read(l); read(r);
        write(sum[r] - sum[l - 1]); putchar(10);
    }
    return 0;
}
template<class T> inline void read(T& res) {
    char c; int flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
template<class T> inline void write(T res) {
    if(res < 0) {
        putchar('-');
        res = -res;
    }
    if(res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
//函数区

B-莫得难题

1）知识点

这道题主要考察了进制转换，再加上了栈的运用和一点数学思想。

2）看题目

这题目说了，有五个数字可以进行字符串连接，我们要选出这个组合数算出来的第k小数（k就是组合数值）。

3）算法分析

不仔细想想还真没想到，如果这道题的数字不是12359，而是01234。是不是就是把一个十进制变成五进制了呢？
这没错，不过除此之外要注意一点：这道题的最小的数不是0而是1，导致%不可以直接使用。所以计算之前要先-1。

4）算法操作

组合数就直接模拟杨辉三角就好了：

for (int i = 1; i <= 100; i++) {
    C[i][0] = C[i][i] = 1;
        for (int j = 1; j <= i - 1; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
}
//组合数初始化

就用栈一个一个除出来保存就好了：

while (pos) {
    pos--;
    st.push(info[pos % 5]);
    pos /= 5;
}

最后就来个栈输出：

while (!st.empty()) {
    cout << st.top();
    st.pop();
}
cout << endl;
//倒序输出

5）打代码

就是输入数据。
然后变成五进制并转换。
然后输出。
下面全代码~

AC代码

#include <iostream>
#include <stack>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MOD = 1e9 + 7;
int info[5] = { 1, 2, 3, 5, 9 };
int C[107][107];
stack<int> st;
//全局变量区

int main() {
    IOS;
    for (int i = 1; i <= 100; i++) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j <= i - 1; j++)
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
    }
    //组合数初始化
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        int pos = C[n][m];
        while (pos) {
            pos--;
            st.push(info[pos % 5]);
            pos /= 5;
        }
        //转换为五进制栈
        while (!st.empty()) {
            cout << st.top();
            st.pop();
        }
        cout << endl;
        //倒序输出
    }
    return 0;
}
//函数区

C-不平衡数组

1）知识点

这道题拿到手我就知道是稳妥妥的dp，但是我动态规划了挺久，愣是没有规出来，就写了一个假暴力。

说是假暴力是因为我连自己的样例都没过，居然得了满分（暴力没有特判临位差1的情况，代码贴下面了）。

2）看题目

首先我们看题目，我们发现，我们就是把连续相同的数字变得不连续相同罢了。

如果我们这道题不是数字+1，而只是单纯变得不同就行了的话，那么只要连续的数字隔一个变一个就好了。

但是这道题是数字+1，所以我们要考虑到我们在+1了之后会不会比变得和上一个数字，或者下一个数字相同。

3）算法分析

说到dp，首先就是：动态规划最重要的就是递推和dp数组的含义。
所以我们先讲dp数组的含义是什么吧：我们题目的重点是，数组的位置和这个点是不是要加一，那么dp数组就是：
```
ll dp[MAX][2];//dp[第i个位置][加/不加] = 最小代价
//开ll是因为数字太大
```
然后就是递推怎么递推了，递推我们要考虑到上面看题时说到的情况：是否会在+1后等于前面或后面的数字。
所以我们就排除这这个情况不进行正常的判断，单纯就让他进行前后数字不等时的递推就好了（因为前后不等时的判断就是一个简单的判定最小情况的过程）。

4）算法操作

说了这些，那我们怎么操作呢？
我们主要就是实现上面说到的递推步骤。

首先是实现我们上面说到的排除两种情况进行判断：

if (a[i] + 1 != a[i - 1]) dp[i][1] = min(dp[i][1], dp[i - 1][0] + b[i]);
//如果后一位不比前一位大1，就正常递推->后面的要，前面的就不要
if (a[i] != a[i - 1] + 1) dp[i][0] = min(dp[i][0], dp[i - 1][1]);
//如果后一位不比前一位小1，正常递推->后面不要，前面必须要。
//差一位的情况不进行判断，留给下面判断不相等的时候判断

然后呢，就是前后不同的转移判断了：

if (a[i] != a[i - 1]) {
    dp[i][0] = min(dp[i][0], dp[i - 1][0]);
    dp[i][1] = min(dp[i][1], dp[i - 1][0] + b[i]);
}
//后面的数不等于前面的数时，直接判断看是否继承（判断上面两种情况）

这样转移到最后，选择dp[n][0]和dp[n][1]中的较小值进行输出就可以了。

5）打代码

首先毫无疑问的输入数据。
然后将dp数组标记为无穷大，并将起始点设为0.
按照上面方法向后递推。
最后输入dp[n][0]和dp[n][1]中的较小值。
下面全代码~

假AC代码

#include <iostream>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MAX = 2e5 + 7;
int a[MAX], b[MAX];
//全局变量区

template<class T> inline void read(T& res);
template<class T> inline void write(T res);
//函数预定义区

int main() {
    int n; read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]); read(b[i]);
    }
    int l = 1, r = 2, ans = 0;
    while (l <= n) {
        while (r <= n && a[l] == a[r]) r++;
        if (r - l > 1) {
            int sum1 = 0;
            for (int j = l; j < r; j += 2) sum1 += b[j];
            int sum2 = 0;
            for (int j = l + 1; j < r; j += 2) sum2 += b[j];
            ans += min(sum1, sum2);
        }
        l = r; r++;
    }
    write(ans); putchar(10);
    return 0;
}
template<class T> inline void read(T& res) {
    char c; int flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
template<class T> inline void write(T res) {
    if(res < 0) {
        putchar('-');
        res = -res;
    }
    if(res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
//函数区

AC代码

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
#define debug(t) cout << #t << " = " << t << endl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 2e5 + 7;
int a[MAX], b[MAX];
ll dp[MAX][2];//dp[第i个位置][加/不加] = 最小代价
//全局变量区

template<class T> inline void read(T& res);
template<class T> inline void write(T res);
//函数预定义区

int main() {
    int n; read(n);
    for (int i = 1; i <= n; i++) {
        read(a[i]); read(b[i]);
    }
    memset(dp, INF, sizeof dp);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] + 1 != a[i - 1]) dp[i][1] = min(dp[i][1], dp[i - 1][0] + b[i]);
        //如果后一位不比前一位大1，就正常递推->后面的要，前面的就不要
        if (a[i] != a[i - 1] + 1) dp[i][0] = min(dp[i][0], dp[i - 1][1]);
        //如果后一位不比前一位小1，正常递推->后面不要，前面必须要。
        //差一位的情况不进行判断，留给下面判断不相等的时候判断
        if (a[i] != a[i - 1]) {
            dp[i][0] = min(dp[i][0], dp[i - 1][0]);
            dp[i][1] = min(dp[i][1], dp[i - 1][0] + b[i]);
        }
        //后面的数不等于前面的数时，直接判断看是否继承（判断上面两种情况）
    }
    write(min(dp[n][0], dp[n][1])); putchar(10);
    return 0;
}
template<class T> inline void read(T& res) {
    char c; int flag = 1;
    while ((c = getchar()) < '0' || c > '9')
        if (c == '-')
            flag = -1;
    res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        res = res * 10 + c - '0';
    res *= flag;
}
template<class T> inline void write(T res) {
    if(res < 0) {
        putchar('-');
        res = -res;
    }
    if(res > 9) write(res / 10);
    putchar(res % 10 + '0');
}
//函数区

D-数列统计

1）知识点

这道题的考点就是组合数学和逆元知识。真不好意思，这道题我不会推理QAQ。

2）看题目

这道题的意思就是：给你一个最大数x，求长度为l的自然数不降序排列的方法数。

3）算法分析

这里如果我们会打表就可以直接来找规律了：

当l = 3时的情况：

1 3 6 10 15 21 28 36 45 55

66 78 91 105 120 136 153 171 190 210

231 253 276 300 325 351 378 406 435 465

496 528 561 595 630 666 703 741 780 820

861 903 946 990 1035 1081 1128 1176 1225 1275

当l = 4的情况：

1 4 10 20 35 56 84 120 165 220

286 364 455 560 680 816 969 1140 1330 1540

1771 2024 2300 2600 2925 3276 3654 4060 4495 4960

5456 5984 6545 7140 7770 8436 9139 9880 10660 11480

12341 13244 14190 15180 16215 17296 18424 19600 20825 22100

然后我们就能发现，这和组合数有关系，简单判断一下就能知道是C(l + x - 2, x - 1)。

于是我们只要用逆元求出答案就好了。

4）算法操作

计算的话，我们知道组合数是可以用阶层求出来的，但是这里要取模，所以必须要用到逆元（逆元就是倒数，这里就不细讲了）。
逆元要怎么求呢？就要用到费马小定理，我们就可以得到公式inv[a] = a^p-2：（逆元我们用inv表示）
```
inv[k]  =  modpow(factorial[k], MOD - 2);
```

根据组合数我们可以得到公式：

C(n,  k)  =  factorial[n] * inv[k] % MOD * inv[n - k] % MOD;

将其带入就是：

C(n,  k)  =  factorial[n] * modpow(factorial[k], MOD - 2) % MOD * modpow(factorial[n - k], MOD - 2) % MOD;

补充：上面的方法没有问题，除此之外逆元也可以递推打表：

// inv[MAX - 1] = modpow(factorial[MAX - 1], MOD - 2);
// for (int i = MAX - 2; i >= 0; i--)
//     inv[i] = inv[i + 1] * (i + 1) % MOD;
//逆元初始化

5）打代码

所以我们就先初始化阶乘（随便推不推逆元）。
然后输入。
最后直接按公式求。
下面全代码~

打表代码（用于理解题目+找规律）

#include <iostream>
using namespace std;
//代码预处理区

int l, x, ans; 
//全局变量区

void dfs(int num, int deep);
//函数预定义区

int main() {
        cin >> l;
    int T; T = 50;
    for (int i = 1; i <= T; i++) {
        x = i;
        ans = 0;
        dfs(1, 1);
        printf("%8d   ", ans);
        if (i % 10 == 0) putchar(10);
    }
    return 0;
}
void dfs(int num, int deep) {
    if (deep == l) {
        ans++;
        return;
    }
    for (int i = num; i <= x; i++)
        dfs(i, deep + 1);
}
//函数区

AC代码

#include <iostream>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//代码预处理区

const int MOD = 911451407;
const int MAX = 2e6 + 7;
int l, x; 
ll factorial[MAX], inv[MAX];
//全局变量区

ll C(ll n, ll k);
ll modpow(ll a, ll b);
//函数预定义区

int main() {
    IOS;
    factorial[0] = 1;
    for (int i = 1; i < MAX; i++)
        factorial[i] = i * factorial[i - 1] % MOD;
        //阶乘初始化
    // inv[MAX - 1] = modpow(factorial[MAX - 1], MOD - 2);
    // for (int i = MAX - 2; i >= 0; i--)
    //     inv[i] = inv[i + 1] * (i + 1) % MOD;
    //逆元初始化
    int T; cin >> T;
    while (T--) {
        cin >> l >> x;
        cout << C(l + x - 2, x - 1) << endl;
    }
    return 0;
}
ll C(ll n, ll k) {
    return factorial[n] * modpow(factorial[k], MOD - 2) % MOD * modpow(factorial[n - k], MOD - 2) % MOD;
    // return factorial[n] * inv[k] % MOD * inv[n - k] % MOD;
}
ll modpow(ll a, ll b) {
    ll mul = 1;
    while (b) {
        if (b & 1) mul = mul * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return mul;
}
//函数区