题解 | #牛客IOI周赛28-普及组#

简单模拟，把第一个移到末尾，移动的次数x不超过n，直接从第x个字符开始输出，然后输出前面的数

类似的如果超过n个字符，每移动n个字符，相当于还是原字符串，所以每次从 $x%n$ 开始输出，再输出 $x%n$ 的数

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
long long n,x;
string s;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>x;
    cin>>s;
    x%=n;
    for(int i=x;i<n;++i) cout<<s[i];
    for(int i=0;i<x;++i) cout<<s[i];
    return 0;
}

Sequence Game

最长上升子序列（LIS）的变式

其实就是二维版LIS
定义 $dp[i][j]$ 为前i个数，取值为第j个值的LIS
可以易得 $dp_{i,j}=max(dp_{x,y}+1) (a[i][j]>a[x][y],x<=i,y<=k)$

直接写出来O(10^12)直接裂开，考虑降维（打击）i维

这里的还有贪心的一点
对于相同的长度即 $dp[i][j]$ ，末尾越小越好，
所以我们可以造一个数组 $ed[i]$ 意为LIS长度为i的最小结尾数

第i行，把 $a[j]$ 与不同长度末尾比较，大了就可以连接成一个更长的LIS
然后还要考虑是否能更新 $ed[]$

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int inf=1e9;
const int maxn=5e3+10;
int a[maxn];
int ed[maxn];//存储长度为i，结尾最小的a的值 
int dp[maxn];//记录以a[i][j]结尾的最长长度 
int k,n;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0); 
    cin>>k>>n;
    for(int i=1;i<=n;++i) ed[i]=inf;//初始化 
    for(int i=1;i<=n;++i){
        for(int j=1;j<=k;++j) cin>>a[j];
        int p=0;
        for(int j=1;j<=k;++j){
            while(p<n && ed[p+1]<a[j]) ++p;//把a[j]和不同长度的末尾比较
            dp[j]=p+1;//此时以a[j]为结尾的最长上升子序列为p+1 
        }
        for(int j=1;j<=k;++j) ed[dp[j]]=min(ed[dp[j]],a[j]);//更新以dp[j]长度为结尾的，是选择a[j]为结尾，还是原数为结尾 
    } 
    for(int i=n;i>=1;--i){//这个长度有值，则输出 
        if(ed[i]!=inf){
            cout<<i<<endl; 
            break;
        }
    }
    return 0;
}

Simple Game

题目背景没有鸟用，直接看输出描述每个地铁站能到达的编号最小的地铁站的编号

反向建图，那么每个点能到达，那么这样就意味着，每个点遍历时，直接把能到这个点的所有点都更新为这个点的编号，从编号1开始搜索即可，搜过的打标记不用搜

因为第一次被搜到的点记录的一定为最小值

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
const int maxn=1e5+10;
int m;
bool book;
int head[maxn];
struct node{
    int v,next;
}e[maxn];
int nr[maxn];
int cnt=0;
int in[maxn];
void add(int u,int v){
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void dfs(int u,int topf){
    nr[u]=topf;
    for(int i=head[u];i;i=e[i].next)
        if(nr[e[i].v]==0)dfs(e[i].v,topf);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;memset(nr,0,sizeof(nr));
    for(int i=1;i<=m;++i){
        int u,v;cin>>u>>v;
        add(v,u);
    }
    for(int i=1;i<=n;++i) if(nr[i]==0)dfs(i,i);
    sort(nr+1,nr+1+n);
    int last=0;bool book=0;
    for(int i=1;i<=n;++i){
        if(nr[i]==last) continue;
        last=nr[i];book=1;
        cout<<nr[i]<<" "; 
    }if(book==0) cout<<1<<endl; 
    return 0;
}

Sweet Game

虽然是个取值题，但实质是一个构造题，构造一个序列使得值最大，构造时就求值，不用求出序列

思路

直接将第n个糖加入序列（因为它右边的糖无糖可吃，满足题意直接加）

那么此时n-1个糖也满足加入序列的条件（因为第n个糖吃完了）

以此类推，所以从后往前枚举，会使得i+1~n的糖都被吃了，第i个糖也满足被吃条件

而加入序列，根据题意则会有两种情况
设a[]为糖的甜度，b[]为糖的变化值

加入整个序列的左边（说明i+1~n的糖将要吃完）
此时 $ans=\sum_{j=i}^{n}b[i]+ans+a[i]$
加入整个序列的右边(说明i+1~n的糖已经吃完)
此时 $ans=ans+a[i]+(n-i)*b[i]$

其实为什么不能从1开始吃
会发现先吃了第1颗糖之后，只能吃第 $2$ ~ $n$ 颗糖
那么接下来只能吃2颗糖，吃完后，又只能吃第 $3$ ~ $n$ 颗糖
以此类推，构造出来的序列是唯一的，所以很大可能不是解

#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
int n;
const int maxn=2e5+10;
long long ans=0;
long long  a[maxn],b[maxn]; 
inline long long  read()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x*f;
}
int main(){
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    for(int i=1;i<=n;++i) b[i]=read();
    for(int i=n;i>=1;--i) {
        long long  nxt=max(ans+sum+a[i],ans+a[i]+(n-i)*b[i]);//ans+sum+a[i]为插入整个序列左边的情况，ans+a[i]+(n-i)*b[i]为插入右边 
        ans=nxt;
        sum+=b[i];//记录当前序列的整体▲d 
    }
    cout<<ans<<endl;return 0;
}

题解 | #牛客IOI周赛28-普及组#

牛客IOI周赛28-普及组

String Game

Sequence Game

Simple Game

Sweet Game