首页 > 代码库 > 2017 济南综合班 Day 3
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 100001using namespace std;int lens,lent,f[N];char s[N],t[N];;void getfail(){ int j; for(int i=1;i<lent;i++) { j=f[i]; while(j && t[i]!=t[j]) j=f[j]; f[i+1]= t[i]==t[j] ? j+1 : 0; }}void work(){ int j=0; for(int i=0;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 504using 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*2) { printf("0"); return 0; } dp[0][0]=1; n=(n<<1)-1; for(int i=1;i<=n;i++) { for(int j=0;j<=k;j++) dp[i][j]=dp[i-1][j]; for(int j=1;j<=k;j++) dp[i][j]=(dp[i][j]+dp[i-1][j-1]*((i+1)/2*2-1-(j-1)))%mod; } printf("%d",dp[n][k]);}
T3 蝉
正解 树链剖分线段树维护等差序列
弃疗
90 暴力法：
连续的操作1一块儿弄，spfa
#include<cstdio>#include<queue>#include<cstring>#define N 200001using namespace std;int tot,front[N],to[N*2],nxt[N*2];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,-1,sizeof(dis)); dis[1]=0; q.push(1); int now; while(!q.empty()) { now=q.front(); q.pop(); for(int i=front[now];i;i=nxt[i]) if(dis[to[i]]==-1) { dis[to[i]]=dis[now]+1; 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]+1) { dis[to[i]]=dis[now]+1; 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=1;i<n;i++) { scanf("%d%d",&u,&vv); add(u,vv); } bfs(); have[1]=true; int opt,x; while(m--) { scanf("%d%d",&opt,&x); if(opt==1) { if(tmp[0]) { spfa(); for(int j=1;j<=tmp[0];j++) printf("%d\n",dis[tmp[j]]); tmp[0]=0; } if(!have[x]) q.push(x),dis[x]=0,v[x]=true; } else tmp[++tmp[0]]=x; } if(tmp[0]) { spfa(); for(int j=1;j<=tmp[0];j++) printf("%d\n",dis[tmp[j]]); }}
2017 济南综合班 Day 3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。