2016 多校赛4 A dp,KMP E(待补) F(待补) J LIS变形,套路 K 水 L 水

2016 Multi-University Training Contest 4

题意：给出两个字符串A、B，问B在A中有多少种匹配。例如，A：hehehehe，B：hehe，有“*hehe”,“he*he”,“hehe*”,“**”,“hehehehe” 共5种匹配。

tags：菜鸡根本没看出是dp，2333。 dp[i]表示A匹配到第 i个时的匹配方案数，dp[i]=dp[i-1]+(B==A.substr(i-|B|+1, |B|) dp[i-|B| 。对于(B==A.substr(i-|B|+1, |B|)，先KMP快速匹配出即可。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,b,a) for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 100005, mod=1000000007;

char A[N], B[N];
int lena, lenb, nex[N];
bool mark[N];
ll dp[N];
void getnext()
{
    mes(nex, 0);   nex[0]=-1;
    for(int i=0, k=-1; i<lenb; )
    {
        if(k==-1 || B[i]==B[k]) {
            ++i, ++k;
            nex[i]=k;
        } else k=nex[k];
    }
}
ll KMP()
{
    mes(mark, false);
    getnext();
    for(int i=0, j=0; i<lena; )
    {
        if(j==-1 || A[i]==B[j]) ++i, ++j;
        else  j=nex[j];

        if(j==lenb)  mark[i-1]=1;
    }
    dp[0]=mark[0];
    rep(i,1,lena-1)
        if(mark[i]==0) dp[i]=dp[i-1];
        else dp[i]= (dp[i-1]+dp[i-lenb]+1)%mod;
    return (dp[lena-1]+1+mod)%mod;
}
int main()
{
    int T;  scanf("%d", &T);
    rep(cas, 1, T)
    {
        scanf("%s %s", A, B);
        lena=strlen(A), lenb=strlen(B);
        printf("Case #%d: %lld
", cas, KMP());
    }

    return 0;
}

View Code

E - Lucky7

题意：7的倍数是幸运数，给出n对pi和ai，这些倍数中除pi且余ai的数不能算作幸运数，问[x,y]中有多少个幸运数。

待补

F - Substring

待补

J - The All-purpose Zero

题意：数组a[]，可以将数组中的0改为任意数，a[i]<=1e6，求最长严格递增子序列。

tags：真是套路，，，一开始想dp，发现搞不出来，看了题解。。

首先明确，所有的0都用上肯定不亏。但是，一个0用上了，它可能会对其它数有影响，这个影响该怎么消除？有个很简单的办法，比如a[i]不为0，而它前面有cnt个0，就让a[i]-=cnt。最后把所有0都提出来，算改变后的LIS，再加上0的个数就是答案。

#include<bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define rep(i,a,b) for (int i=a;i<=b;i++)
#define per(i,b,a) for (int i=b;i>=a;i--)
#define mes(a,b)  memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
typedef long long ll;
const int N = 100005;

int n, a[N], cnt, f[N], ans;
int main()
{
    int T;  scanf("%d", &T);
    rep(cas, 1, T)
    {
        ans=cnt=0;  mes(f, INF);
        scanf("%d", &n);
        rep(i,1,n) {
            scanf("%d", &a[i]);
            if(a[i]==0) ++cnt;
            else {
                a[i]-=cnt;
                int k=lower_bound(f+1, f+1+n, a[i])-f;
                ans=max(ans, k);
                f[k]=a[i];
            }
        }
        printf("Case #%d: %d
", cas, ans+cnt);
    }

    return 0;
}

View Code

K 水

L 水