2017 济南综合班 Day 3

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

T1 黑化

题意：

求一个字符串是否可能包含另一个字符串

字符串中的？可以匹配任意字母

可能输出 God bless You!

一定不可能输出 Game Over!

计算fail数组时，fail数组不具有传递性

例：

pqkbpqsbqszz
pqkbpq?z

在z处失配后：

pqkbpqsbqszz
pqkbpq?z

z匹配成功，误认为包含

因为计算fail时，？匹配了 k，而匹配时？匹配了s

s不和k匹配

即？不具有传递性

#include<cstdio>

#include<cstring>

#define N 100001

using namespace std;

int lens,lent,f[N];

char s[N],t[N];;

void getfail()

{

    int j;

    for(int i=;i<lent;i++)

    {

        j=f[i];

        while(j && t[i]!=t[j]) j=f[j];

        f[i+]= t[i]==t[j] ? j+ : ;

    }

}

void work()

{

    int j=;

    for(int i=;i<lens;i++)

    {

        while(j && s[i]!=t[j] && s[i]!='?' && t[j]!='?') j=f[j];

        if(s[i]==t[j] || s[i]=='?' || t[j]=='?') j++;

        if(j==lent) { printf("God bless You!\n"); return; }

    }

    printf("Game Over!\n");

}

int main()

{

    freopen("trigger.in","r",stdin);

    freopen("trigger.out","w",stdout);

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%s%s",t,s);

        lent=strlen(t);

        lens=strlen(s);

        getfail();

        work();

    }

}

T2 便当

不共行不共列 --> 原图行列交换无影响

原图转化成这样

然后DP

#include<cstdio>

#define N 210

#define mod 504

using namespace std;

int n,k,dp[N][N];

int main()

{

    freopen("kill.in","r",stdin);

    freopen("kill.out","w",stdout);

    scanf("%d%d",&n,&k);

    if(k>=n*) { printf(""); return ; }

    dp[][]=;

    n=(n<<)-;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=k;j++) dp[i][j]=dp[i-][j];

        for(int j=;j<=k;j++) dp[i][j]=(dp[i][j]+dp[i-][j-]*((i+)/*--(j-)))%mod;

    }

    printf("%d",dp[n][k]);

}

T3 蝉

正解树链剖分线段树维护等差序列

弃疗

90 暴力法：

连续的操作1一块儿弄，spfa

#include<cstdio>

#include<queue>

#include<cstring>

#define N 200001

using namespace std;

int tot,front[N],to[N*],nxt[N*];

int dis[N],tmp[N];

bool v[N],have[N];

queue<int>q;

void add(int u,int v)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot;

}

void bfs()

{

    memset(dis,-,sizeof(dis));

    dis[]=; q.push();

    int now;

    while(!q.empty())

    {

        now=q.front(); q.pop();

        for(int i=front[now];i;i=nxt[i])

         if(dis[to[i]]==-)

         {

             dis[to[i]]=dis[now]+;

             q.push(to[i]);

         }

    }

}

void spfa()

{

    int now;

    while(!q.empty())

    {

        now=q.front(); q.pop(); v[now]=false;

        for(int i=front[now];i;i=nxt[i])

         if(dis[to[i]]>dis[now]+)

         {

             dis[to[i]]=dis[now]+;

             if(!v[to[i]]) q.push(to[i]),v[to[i]]=true;

         }

    }

}

int main()

{

    freopen("cicada.in","r",stdin);

    freopen("cicada.out","w",stdout);

    int n,m;

    scanf("%d%d",&n,&m);

    int u,vv;

    for(int i=;i<n;i++)

    {

        scanf("%d%d",&u,&vv);

        add(u,vv);

    }

    bfs();

    have[]=true;

    int opt,x;

    while(m--)

    {

        scanf("%d%d",&opt,&x);

        if(opt==)

        {

            if(tmp[])

            {

                spfa();

                for(int j=;j<=tmp[];j++) printf("%d\n",dis[tmp[j]]);

                tmp[]=;

            }

            if(!have[x]) q.push(x),dis[x]=,v[x]=true;

        }

        else tmp[++tmp[]]=x;

    }

    if(tmp[])

    {

        spfa();

        for(int j=;j<=tmp[];j++) printf("%d\n",dis[tmp[j]]);

    }

}