【题解】牛客 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，
- 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 版题目 & 题解的下载链接，一定要来！
投递拼多多等公司10个岗位 >