牛客多校第一场

A

题意：给两个相同长度的数字串，求一个最大的p,使两个数字串都满足[1,p]中任何一个区间的最小值下标都相同，

思路：对于两个数字串要求最大的p，可以想到这个p的左边的区间[1,x]也肯定满足，所以想到从左往右顺推，然后每次都新加一个数字，判断这个新的区间是否满足，就只需要判断这个数字左侧第一个比它小的数字位置是否相同，如果相同那么新加的这个数字可以，否则最长长度到此为止。判断每个数字左侧第一个比它小的位置可以用单调栈维护一个递增的序列来求,对于每次入栈的数字，栈中上一个元素的位置就是第一个比它小的位置。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+10;
int a[maxn],b[maxn];
int st[maxn];
int lmin1[maxn],lmin2[maxn];

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        for(int i=1; i<=n; i++)
            scanf("%d",&b[i]);
        int l,r;
        l=1;
        r=0;
        for(int i=1; i<=n; i++)
        {
            while(l<=r&&a[st[r]]>=a[i])
                r--;
            lmin1[i]=st[r];
            st[++r]=i;
        }
        l=1;
        r=0;
        for(int i=1; i<=n; i++)
        {
            while(l<=r&&b[st[r]]>=b[i])
                r--;
            lmin2[i]=st[r];
            st[++r]=i;
        }
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            if(lmin1[i]==lmin2[i])
                ans=i;
            else
                break;
        }
        printf("%d
",ans);
    }
}

E

题意：求有多少种字符串满足含有n个AB的子序列和m个BA的子序列。

思路：咋这么难想了QAQ，设状态转移方程f[i,j]表示：（在构成这个长度为n+m的字符串的过程中）前缀长度为i+j的字符串中有i个A和j个B的合法方案数有多少，合法方案就是可能满足条件的方案，可以想到不满足条件的方案就是前i+j中出现了大于n+j(j<=m)个A或者前i+j中出现了大于m+i(i<=n)个B，其余的都是合法方案，然后转移方程f[i][j]+=f[i-1][j]&&f[i][j]+=f[i][j-1]表示只能从前一个长度的字符串加个A或者加个B的方案数转移过来。

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e3+10;
const int mod=1e9+7;
#define ll long long
ll f[maxn*2][maxn*2];
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0; i<=n; i++)
            f[i][0]=1;
        for(int i=0; i<=m; i++)
            f[0][i]=1;
        for(int i=1; i<=n+m; i++)
            for(int j=1; j<=n+m; j++)
            {
                if(i<=(n+min(j,m))) f[i][j]=(f[i][j]+f[i-1][j])%mod;
                if(j<=(m+min(i,n))) f[i][j]=(f[i][j]+f[i][j-1])%mod;
            }
        printf("%lld
",f[n+m][n+m]);
    }
}