T1 黑化
题意：
求一个字符串是否可能包含另一个字符串
字符串中的？可以匹配任意字母
可能输出 God bless You!
一定不可能 输出 Game Over!
计算fail数组时，fail数组不具有传递性
例：
pqkbpqsbqszz
pqkbpq?z在z处失配后：
pqkbpqsbqszz
pqkbpq?zz匹配成功，误认为包含
因为计算fail时，？匹配了 k，而匹配时 ？匹配了s
s不和k匹配
即？不具有传递性
#include#include #define N 100001using namespace std;int lens,lent,f[N];char s[N],t[N];;void getfail(){ int j; for(int i=1;i
T2 便当
不共行不共列 --> 原图行列交换无影响
原图转化成这样
然后DP
#include#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#include #include #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 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