• A string game

比较简单的一题。 显然首先需要对操作次数x进行取模n的操作，然后我们从x%n这个位置开始输出到最后，接着从0开始到x%n-1输出。就可以了。 代码：

using namespace std;
string s;
int n;
long long x;
int main()
{
    cin>>n>>x;
    cin>>s;
    x%=n;
    for(int i=x;i<s.size();i++)cout<<s[i];
    for(int i=0;i<x;i++)cout<<s[i];
    return 0;
}
  • B Sequence Game

题目是求在ai中任选组合一个序列，求组合出的若干序列中最长上升子序列的最大长度。 一开始想到的是dp[i][j]表示ai取到值为j时候的最大LIS长度。 这样我们是可以得到一个转移方程的： dp[i][j]=max{dp[k][l]}其中k<i,j<l。 这样是一个四重循环。其中i枚举1 ~ n，j枚举值1 ~ 1000，k枚举1 ~ i-1，l其实可以二分查找离j最近的那个。三重还是会超时。

太菜了优化不出来了

于是考虑LIS的经典优化能否实现。经典nlogn的优化是利用dp[i]表示LIS为i时候的最小结尾数。 考虑dp[i][j]表示LIS长度为i时候以a[j]为结尾的最小值。看着比较绕，实际上我们在维护LIS为i时，由于a[j]这里是可以有K种选择的，因此我们加了一维j来限制当前选择a[j]时候的最小结尾。 这样我们可以得到对于dp[i][j]，我们维护一个M=max{dp[i-1][k]}(k<i)。 然后可以利用二分查找找到第一个大于M的a[j][pos]，然后更新dp[i][j]=a[j][pos] 同时维护当前已经得到的最大LIS值len。最后我们的答案就是len. 代码：

using namespace std;
int dp[1001][1005];
int k,n;
int a[1001][5005];
int main()
{
    cin>>k>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++)cin>>a[i][j];
    }
    int len=1;
    for(int i=1;i<=n;i++)dp[1][i]=a[i][1];
    for(int i=2;i<=n;i++){
        for(int l=1;l<=len;l++){
            int tmpmx=1000;
            for(int j=1;j<i;j++)if(dp[l][j])tmpmx=min(tmpmx,dp[l][j]);
            int pos=upper_bound(a[i]+1,a[i]+1+k,tmpmx)-a[i];
            if(pos<=k){
                dp[l+1][i]=a[i][pos];
                if(l==len){
                    len++;
                    break;
                }
            }
        }
    }
    cout<<len<<endl;
    return 0;
}

+C Simple Game

若是一个环，则环中所有点可以相互到达，答案就是环中元素的最小编号。 若没有环，则变成一个DAG。那么我们可以用dp[i]表示从i出发所能到达的最小编号。 显然，若有u->v，则dp[u]=min(dp[u],dp[v])，一个dfs就可以解决了。 因此，对于有环的情况，我们先缩点，然后跑一边DAG就可以了。 这里缩点用了tarjan，注意缩点的时候把同一个连通块内的编号全部变成块内最小元素的编号。 代码：

using namespace std;
const int maxn=100050;
int n,m;
int in[maxn];
int tot,head[maxn],head2[maxn],tot2;
int dfn[maxn],low[maxn],color[maxn],cnt;
int stk[maxn],indx,top;
int vis[maxn],dp[maxn];
struct node{
    int to,idx,next;
}e[maxn*2],e2[maxn];
void init(){
    tot=0;
    memset(head,-1,sizeof(head));
    memset(head2,-1,sizeof(head2));
    memset(dp,0x3f3f3f3f,sizeof(dp));
}
void add(int a,int b){
    tot++;
    e[tot].to=b;
    e[tot].next=head[a];
    head[a]=tot;
}
void add2(int a,int b){
    tot2++;
    e2[tot2].to=b;
    e2[tot2].next=head2[a];
    head2[a]=tot2;
}
void tarjan(int u){
    dfn[u]=low[u]=++indx;
    stk[++top]=u;
    for(int i=head[u];~i;i=e[i].next){
        int v=e[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!color[v]){
            low[u]=min(low[u],low[v]);
        }
    }
    if(dfn[u]==low[u]){
        int top2=top;
        int mini=u;
        while(stk[top]!=u){
            mini=min(mini,stk[top--]);
        }
        for(int i=top;i<=top2;i++)color[stk[i]]=mini;
        top--;
    }
}
void build(){
    for(int u=1;u<=n;u++){
        for(int i=head[u];~i;i=e[i].next){
            int v=e[i].to;
            if(color[u]!=color[v]){
                add2(color[u],color[v]);
                in[color[v]]++;
            }
        }
    }
}
int dfs(int x){
    if(vis[x])return dp[x];
    vis[x]=1;
    dp[x]=x;
    for(int i=head2[x];~i;i=e2[i].next){
        int y=e2[i].to;
        dp[x]=min(dp[x],dfs(y));
    }
    return dp[x];
}
int main()
{
    cin>>n>>m;
    init();
    while(m--){
        int u,v;
        cin>>u>>v;
        add(u,v);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
    build();  //重新建图
    int count=0;
    for(int i=1;i<=n;i++){
        count=max(count,color[i]);
        if(in[color[i]]==0)dfs(color[i]);  //寻找DAG中入度为0的点进入dfs
    }
    if(count==1){   //特判整个图是一个环
        cout<<1<<endl;
        return 0;
    }
    sort(dp+1,dp+1+count);
    int siz=unique(dp+1,dp+1+count)-dp-1;
    for(int i=1;i<=siz;i++){
        if(dp[i]==0x3f3f3f3f)break;
        cout<<dp[i]<<' ';
    }
    return 0;
}