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

A-夹娃娃

1）知识点

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

2）算法操作

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

3）打代码

  1. 输入数据用于初始化前缀和（毕竟是个简单题目，就尽量缩减计算，能少一步就能快几毫秒）。
  2. 然后输入并输出前缀和差值。
  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）算法分析

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

4）算法操作

  1. 组合数就直接模拟杨辉三角就好了： 
    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;
}
//组合数初始化
  2. 就用栈一个一个除出来保存就好了： 
    while (pos) {
    pos--;
    st.push(info[pos % 5]);
    pos /= 5;
}
  3. 最后就来个栈输出： 
    while (!st.empty()) {
    cout << st.top();
    st.pop();
}
cout << endl;
//倒序输出

5）打代码

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

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）算法分析

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

4）算法操作

  1. 说了这些，那我们怎么操作呢？
  2. 我们主要就是实现上面说到的递推步骤。
  3. 首先是实现我们上面说到的排除两种情况进行判断： 
    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，正常递推->后面不要，前面必须要。
//差一位的情况不进行判断，留给下面判断不相等的时候判断
  4. 然后呢，就是前后不同的转移判断了： 
    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]);
}
//后面的数不等于前面的数时，直接判断看是否继承（判断上面两种情况）
  5. 这样转移到最后，选择dp[n][0]和dp[n][1]中的较小值进行输出就可以了。

5）打代码

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

假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）算法操作

  1. 计算的话，我们知道组合数是可以用阶层求出来的，但是这里要取模，所以必须要用到逆元（逆元就是倒数，这里就不细讲了）。
  2. 逆元要怎么求呢？就要用到费马小定理，我们就可以得到公式inv[a] = ap-2：（逆元我们用inv表示） 
    inv[k]  =  modpow(factorial[k], MOD - 2);
  3. 根据组合数我们可以得到公式： 
    C(n,  k)  =  factorial[n] * inv[k] % MOD * inv[n - k] % MOD;
  4. 将其带入就是： 
    C(n,  k)  =  factorial[n] * modpow(factorial[k], MOD - 2) % MOD * modpow(factorial[n - k], MOD - 2) % MOD;
  5. 补充：上面的方法没有问题，除此之外逆元也可以递推打表： 
    // 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）打代码

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

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

#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;
}
//函数区
比赛 文章被收录于专栏

憨憨的专栏

全部评论

相关推荐

11-25 00:08
陕西理工大学 电子工程师
点赞 评论 收藏
分享
10-11 12:13
湖北工业大学 Java
点赞 评论 收藏
分享
11-22 12:45
北京农学院 项目助理
同程旅行产品经理在职体验
首先，加班这事儿，老实说，还是有点儿的，尤其是项目紧的时候。不过，整体来说，大家的工作节奏还算可以，偶尔加班也能接受，毕竟旅游行业嘛，忙的时候总是有的。再说说校招生的培养机制，感觉公司对新人的培训还是挺重视的，入职后会有专门的导师带你，帮助你快速上手。工作氛围也不错，团队里大家都很友好，互相帮助，偶尔还会一起吃个饭，聊聊天，挺轻松的。生活成本方面，租房问题嘛，像我在市中心租的房子，价格还算合理，但如果想要更便宜的选择，可能得往郊区跑跑了。至于校招和社招的内推，听说有些同事会帮忙，但具体情况还是得看个人关系。
同程旅行工作强度 19人发布
点赞 评论 收藏
分享
2 收藏 评论
分享

全站热榜

正在热议
# 25届秋招总结 #
366473次浏览 3615人参与
# 如果再来一次，你还会选择这个工作吗？ #
95409次浏览 928人参与
# 阿里云管培生offer #
44499次浏览 1106人参与
# 地方国企笔面经互助 #
5683次浏览 13人参与
# ai智能作图 #
7406次浏览 126人参与
# 发工资后，你做的第一件事是什么 #
3317次浏览 12人参与
# 百度开奖 #
222615次浏览 1437人参与
# 我的实习求职记录 #
6096394次浏览 83768人参与
# 上班到公司第一件事做什么？ #
14380次浏览 164人参与
# 阿里求职进展汇总 #
71387次浏览 768人参与
# 简历被挂麻了，求建议 #
2519541次浏览 33410人参与
# 听到哪句话就代表面试稳了or挂了？ #
95965次浏览 807人参与
# 华为工作体验 #
108738次浏览 851人参与
# 网易求职进展汇总 #
38687次浏览 308人参与
# 如何写一份好简历 #
614848次浏览 8691人参与
# 如果有时光机，你最想去到哪个年纪？ #
26296次浏览 545人参与
# 面试体验感最好的是哪家？ #
91150次浏览 891人参与
# 牛客租房专区 #
1740次浏览 68人参与
# 如何一边实习一边秋招 #
1001424次浏览 12712人参与
# 实习中的菜狗时刻 #
279592次浏览 2752人参与
# 还记得你第一次面试吗？ #
27194次浏览 361人参与
# 腾讯求职进展汇总 #
203709次浏览 1683人参与
牛客网
牛客企业服务