2021-09-11 16:41 已编辑江西省上饶市玉山县玉山一中机械设计/制造

关注

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

注意到我并不会在本题解中穿插所有部分分的拿分方法，若需要请左转明天下午的出题人讲评：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， $44.7\%$
B 题通过率：42/1082， $3.9\%$
C 题通过率：88/650， $13.5\%$
D 题通过率：15/297， $5\%$

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

综合难度：

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

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

A - String Game

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

注意到 $n$ 次操作与不操作是等价的，于是我们拆分 $x=pn+r(0\le r<n)$ 。 $pn$ 次操作可以抵消，只要关注 $r$ 即可。

$r$ 可以用 $x\bmod n$ 快速算出，剩下部分模拟即可。

代码：

#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，设 $dp_{i,j}$ 为确定了前 $i$ 个数， $a_i$ 确定为 $j$ 的 LIS。

那么有转移方程： $dp_{i,j} = \max(dp_{k,l} + 1)$ ，其中 $k<i,l<j$ 。

由题我们知道 $1\le dp_{i,j}\le n$ ，注意到对于相同的 DP 值， $j$ 越小一定越优秀。所以我们把第一维消掉。

令 $v_i$ 表示 $dp_j\ge i$ 的最小 $j$ ，我们双指针维护 $v,dp$ 的信息，最后输出存在 $v_i$ 值的最大的 $i$ 即可。

代码：

#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》

为了方便，令 $G(u)$ 表示从点 $u$ 能到达的编号最小的点的编号。

对于点 $u$ ，很容易想到的先设 $G(u)=u$ ，通过比较 $G(u)$ 和 $G(v)$ （点 $v$ 是点 $u$ 能直接到达的点）中的最大值来找到答案。

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

图片说明

计算 $G(2)$ 时会等待 $G(4),G(3)$ ，而 $G(3)$ 也在等待 $G(2)$ ，这样就无法计算出答案。

而这样，我们可以考虑反向建边，即对于边 $u\to v$ ，我们建成 $v\to u$ 。

遍历 $1\sim n$ ，从点 $u$ ，对于 $u$ 能到达的所有点 $v$ ，若 $G(v)$ 还没有更新，则 $G(v)=u$ 。

由于 $1\sim n$ 是从小到大枚举的，所以得到的答案必然是正确的。

当然，要去重。

代码：

#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 的吃糖顺序：

首先，将糖 $n$ 添加到序列中。
然后我们将糖 $n-1$ 添加到糖 $n$ 的左侧或右侧。
然后我们在当前糖序列的左侧或右侧添加糖 $n-2$ 。
接下来，在左端或右端添加糖 $n-3$ 。
依此类推。

我们枚举 $n\sim 1$ ，对于糖 $i$ ，它只可能插入到原序列的最左边或最右边。

考虑贪心。

设插入数 $a$ 前的糖序列为 $\{x_m\}$ ，令 $k=\sum d_i$ ， $sum=\sum x_i$ 。

若将 $a$ 插入 $x$ 左边，则新数列对答案的贡献为 $sum+a+\sum\limits_{i=1}^m(i-1)d_i+k$ 。
若将 $a$ 插入 $x$ 右边，则新数列对答案的贡献为 $sum+a+\sum\limits_{i=1}^m(i-1) d_i+md_a$ 。

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

若 $k<md_a$ ，则将 $a$ 插入 $x$ 右边。
若 $k>md_a$ ，则将 $a$ 插入 $x$ 右边；若 $k=md_a$ ，则将 $a$ 插入 $x$ 左右两侧均可。

在下面的程序中默认将 $k\ge md_a$ 都插入左边，将 $k<md_a$ 都插入右边。

代码：

#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 版题目 & 题解的下载链接，一定要来！

图片说明