【CQ18高一暑假前挑战赛2】标程

【昨晚打校赛，5个小时打完很累了，所以搞忘出题了。。。对不起学弟们，不过出的题都亲自写过一遍，可以保证题目和代码长度都不长，题目难度不大】

【A：bush博弈】

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int T,N,K;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&N,&K);

        if(N%(K+)==) puts("B");

        else puts("A");

    }

    return ;

}

【B：DP求最长公共子序列，可以反推前缀】

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

char a[maxn],b[maxn],ans[maxn];

int dp[maxn][maxn];

int main()

{

    int L1,L2,i,j,k;

    scanf("%s%s",a+,b+);

    L1=strlen(a+); L2=strlen(b+);

    for(i=;i<=L1;i++)

       for(j=;j<=L2;j++){

             dp[i][j]=max(dp[i-][j],dp[i][j-]);

          if(a[i]==b[j]) dp[i][j]=max(dp[i][j],dp[i-][j-]+);

    }

    i=L1;j=L2;k=;

    while(i>=&&j>=){

        if(a[i]==b[j]) ans[++k]=a[i],i--,j--;

        else if(dp[i-][j]>=dp[i][j-]) i--;

        else j--;

    }

    for(i=k;i>=;i--) cout<<ans[i];

    return ;

}

【C：nlogn的算法求最长递增子序列】

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int a[maxn];

int main()

{

    int N,x,i,L=,pos=;

    scanf("%d",&N);

    for(i=;i<=N;i++){

        scanf("%d",&x);

        pos=upper_bound(a+,a+L+,x)-a;

        a[pos]=x;

        L=max(L,pos);

    }

    cout<<L<<endl;

    return ;

}

【D：简单处理矩阵：求最大的区间全是1】：问题转化为枚举上下边界，然后连续的一块算。

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int a[maxn][maxn],sum[maxn][maxn];

int main()

{

    int N,M,i,j,k,ans=;

    scanf("%d%d",&N,&M);

    for(i=;i<=N;i++)

      for(j=;j<=M;j++){

        scanf("%d",&a[i][j]);

        sum[i][j]=sum[i-][j]+a[i][j];

    }

    for(i=;i<=N;i++)

      for(j=i;j<=N;j++){

          int L=;

          for(k=;k<=M;k++)

            if(sum[j][k]-sum[i-][k]==j-i+){ L++;ans=max(ans,(j-i+)*L);}

            else L=;

    }

    printf("%d\n",ans);

    return ;

}

【E：区间DP求最长回文，更优的算法有manecher等】

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

char c[maxn];

int dp[maxn][maxn];

int main()

{

    int L,i,j,ans=;

    scanf("%s",c+);

    L=strlen(c+);

    for(i=L;i>=;i--){

        for(j=i;j<=L;j++){

            if(j-i+==) dp[i][j]=;

            else if(j-i+==) dp[i][j]=(c[i]==c[j]?:);

            else if(dp[i+][j-]!=&&c[i]==c[j]) dp[i][j]=dp[i+][j-]+;

            ans=max(ans,dp[i][j]);

        }

    }

    printf("%d\n",ans);

    return ;

}