竞赛讨论区 > 【题解】牛客 IOI 周赛 28 - 普及组题解

【题解】牛客 IOI 周赛 28 - 普及组题解

头像
CSP_Sept
编辑于 2021-09-11 16:41:46 APP内打开
赞 12 | 收藏 2 | 回复15 | 浏览1005

注意到我并不会在本题解中穿插所有部分分的拿分方法,若需要请左转明天下午的出题人讲评:https://www.nowcoder.com/live/634/1/live
录播:https://www.bilibili.com/video/BV1vA411F7hY

下发文件链接及提取码:链接:https://pan.baidu.com/s/1TUzgHsMvyvuY7mam7XRAIQ,提取码:eszx

统计 & 难度情况

统计:

  • AK 人数:12 人
  • A 题通过率:240/537,
  • B 题通过率:42/1082,
  • C 题通过率:88/650,
  • D 题通过率:15/297,

总体而言,大致符合预期。

综合难度:

  • A 题最易,对标 J 组 T1
  • B 题最难,对标 J 组 T3
  • C 题次易,对标 J 组 T4
  • D 题次难,对标 J 组 T2

代码难度排列 ACDB,思维难度排列 AC(B=D),选手参赛数据反映的难度大致符合预期。

A - String Game

本来用的是另外一题,但后来被毙了。

注意到 次操作与不操作是等价的,于是我们拆分 次操作可以抵消,只要关注 即可。

可以用 快速算出,剩下部分模拟即可。

代码:

#include <cstdio>

#define int long long
using namespace std;
int n, x;
char s[100010];
signed main(){
    scanf("%lld%lld", &n, &x);
    scanf("%s", s);
    int m = x % n;
    for(int i = m ; i < n ; i++) printf("%c", s[i]);
    for(int i = 0 ; i < m ; i++) printf("%c", s[i]);
    return 0;
}

B - Sequence Game

(下文中 LIS 表示最长上升子序列)

考虑 DP,设 为确定了前 个数, 确定为 的 LIS。

那么有转移方程:,其中

由题我们知道 ,注意到对于相同的 DP 值, 越小一定越优秀。所以我们把第一维消掉。

表示 的最小 ,我们双指针维护 的信息,最后输出存在 值的最大的 即可。

代码:

#include <cstdio>
#include <algorithm>

#define N 5010
#define INF 1000000010
using namespace std;
int n, k;
int a[N];
int v[N], dp[N];
int main(){
    scanf("%d%d", &k, &n);
    for(int i = 1 ; i <= n ; i++) v[i] = INF;
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= k ; j++) scanf("%d", &a[j]);
        int p = 0;
        for(int j = 1 ; j <= k ; j++){
            while(p + 1 <= n && v[p + 1] < a[j]) p++;
            dp[j] = p + 1;
        }
        for(int j = 1 ; j <= k ; j++) v[dp[j]] = min(v[dp[j]], a[j]);
    }
    for(int j = n ; j >= 1 ; j--){
        if(v[j] != INF){
            printf("%d\n", j);
            return 0;
        }
    }
    return 0;
}

C - Simple Game

《Simple》

为了方便,令 表示从点 能到达的编号最小的点的编号。

对于点 ,很容易想到的先设 ,通过比较 (点 是点 直接到达的点)中的最大值来找到答案。

当然如果产生环,如出现如下的图时会出现死循环。

图片说明

计算 时会等待 ,而 也在等待 ,这样就无法计算出答案。

而这样,我们可以考虑反向建边,即对于边 ,我们建成

遍历 ,从点 ,对于 能到达的所有点 ,若 还没有更新,则

由于 是从小到大枚举的,所以得到的答案必然是正确的。

当然,要去重。

代码:

#include <cstdio>
#include <vector>
#include <algorithm>

#define N 100010
using namespace std;
int n, m;
int a[N];
vector <int> p[N];
void Solve(int x, int v){
    a[x] = v;
    for(int i = 0 ; i < p[x].size() ; i++)
        if(a[p[x][i]] == 0)
            Solve(p[x][i], v);
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0 ; i < m ; i++){
        int u, v;
        scanf("%d%d", &u, &v);
        p[v].push_back(u);
    }
    for(int i = 1 ; i <= n ; i++)
        if(!a[i]) Solve(i, i);
    sort(a + 1, a + n + 1);
    n = unique(a + 1, a + n + 1) - a - 1;
    for(int i = 1 ; i <= n ; i++)
        printf("%d ", a[i]);
    return 0;
}

D - Sweet Game

注意到我们可以这样构造 Cindy 的吃糖顺序:

  • 首先,将糖 添加到序列中。
  • 然后我们将糖 添加到糖 的左侧或右侧。
  • 然后我们在当前糖序列的左侧或右侧添加糖
  • 接下来,在左端或右端添加糖
  • 依此类推。

我们枚举 ,对于糖 ,它只可能插入到原序列的最左边或最右边。

考虑贪心。

设插入数 前的糖序列为 ,令

  • 若将 插入 左边,则新数列对答案的贡献为
  • 若将 插入 右边,则新数列对答案的贡献为

比较一下上面两个式子即可,即比较 的大小。

  • ,则将 插入 右边。
  • ,则将 插入 右边;若 ,则将 插入 左右两侧均可。

在下面的程序中默认将 都插入左边,将 都插入右边。

代码:

#include <cstdio>

#define N 200010
#define int long long 
using namespace std;
inline int rd();
int a[N], d[N];
int n, ans[2 * N], l, r;
int k = 0;
signed main(){
    n = rd();
    l = r = 200000;
    for(int i = 1 ; i <= n ; i++) a[i] = rd();
    for(int i = 1 ; i <= n ; i++) d[i] = rd();
    ans[l] = n;
    k = d[n];
    for(int i = n - 1 ; i ; i--){
        if(k >= (n - i) * d[i]) l--, ans[l] = i;
        else r++, ans[r] = i;
        k += d[i];
    }
    int Ans = 0, j = 0;
    for(int i = l ; i <= r ; i++){
        Ans += (a[ans[i]] + j * d[ans[i]]);
        j++;
    }
    printf("%lld\n", Ans);
    return 0;
}
inline int rd(){
    char c;
    bool flag = 0;
    while((c = getchar()) < '0' || c > '9')
        if(c == '-') flag = 1;
    int res = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

欢迎发表对本场比赛的看法,我之后可能会在牛客出其他比赛,期待你的反馈 >_<

若需要请左转明天下午的出题人讲评:https://www.nowcoder.com/live/634/1/live

届时会给出讲评课件、pdf 版题目 & 题解的下载链接,一定要来!

图片说明

15条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐