比较惊人的排行榜
更不用说爆零的人数了，为什么联赛会这么难！！害怕了
还要再努力鸭
T1 Emotional Flutter
考场上没切掉的神仙题
考率如何贪心，我们把黑色的条延长$s$，白色的缩短$s$，这样把$jiao$的长度变成一
方便做，然后如果黑条长度大于$k$显然不合法，直接判出
然后考虑将黑条左右范围对$k$取模，然后发现这个答案和起始的位置有一一对应的关系
但是他并不是恰好对应的，即起始点是$0$的时候取模对应的值是$7$，这样我感觉很麻烦
于是将黑条的起始点移动到$k-1$，这样对应的起始点位置为$1~k-1$，方便理解
然后如果对黑条的左右端点取模发现$l>r$，那么他对应的区间是$[0,r],[l,k-1]$
最后排个序看看能否有一个点不被所有区间覆盖即可
细节很多，改题的时候改崩溃了
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 namespace AE86{ 5 inline int read(){ 6 int x=0,f=1;char ch=getchar(); 7 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 8 while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f; 9 }inline void write(int x,char opt=‘\n‘){ 10 char ch[20];int len=0;if(x<0)x=~x+1,putchar(‘-‘); 11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x); 12 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);} 13 }using namespace AE86; 14 15 const int NN=5e5+5,inf=1e15; 16 int s,k,n,T,pos[NN],tmp,a[NN]; 17 bool f; 18 struct SNOW{int l,r;}line[NN]; 19 inline bool cmp(SNOW a,SNOW b){return a.l==b.l? a.r<b.r: a.l<b.l;} 20 21 namespace WSN{ 22 inline short main(){ 23 T=read(); 24 while(T--){ 25 s=read();k=read();n=read();f=0;tmp=0; 26 if(k<s){puts("NIE");continue;} pos[0]=1; 27 for(int i=1;i<=n;i++){ 28 a[i]=read(); 29 pos[i]=pos[i-1]+a[i]; 30 } 31 for(int i=1;i<=n;i++) if(i&1){ 32 int l=pos[i-1]+1,r=pos[i]+s-1; 33 if(r-l+1>=k){puts("NIE");f=1;break;} 34 l%=k; r%=k; 35 if(l>r){ 36 line[++tmp]=(SNOW){0,r}; 37 line[++tmp]=(SNOW){l,k-1}; 38 }else line[++tmp]=(SNOW){l,r}; 39 } 40 if(f) continue; 41 sort(line+1,line+tmp+1,cmp); 42 int i=1,maxn=0; bool fini=0; 43 if(line[1].l>0){puts("TAK");continue;} 44 for(int i=1;i<=tmp;i++){ 45 if(maxn+1<line[i].l) fini=1; 46 maxn=max(maxn,line[i].r); 47 }if(maxn<k-1) fini=1; 48 puts(fini?"TAK":"NIE"); 49 } 50 return 0; 51 } 52 } 53 signed main(){return WSN::main();}
T2 Medium Counting
神仙$dp$题，拍过的。。。
设$dp_{l,r,p,c}$表示从第$l$个串到第$r$个串，强制后缀第$p$位至少是$c$的方案数
然后记忆化搜索每次枚举$l~r$区间内的串，转移的时候分别讨论加后缀或者提升字符字典序即可
状态定义是真的神仙，不过$dp$还是比较好打的
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 namespace AE86{ 5 inline int read(){ 6 int x=0,f=1;char ch=getchar(); 7 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 8 while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f; 9 }inline void write(int x,char opt=‘\n‘){ 10 char ch[20];int len=0;if(x<0)x=~x+1,putchar(‘-‘); 11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x); 12 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);} 13 }using namespace AE86; 14 15 const int mod=990804011; 16 int n,dp[55][55][30][30],len[55],a[55][25],maxn; 17 char s[55][25]; 18 19 inline int dfs(int l,int r,int p,int c){ 20 if(l>r) return dp[l][r][p][c]=1; 21 if(dp[l][r][p][c]!=-1) return dp[l][r][p][c]; 22 if(p>maxn) return dp[l][r][p][c]=(l==r); 23 if(c>26) return dp[l][r][p][c]=0; 24 dp[l][r][p][c]=dfs(l,r,p,c+1); 25 for(int i=l;i<=r;i++){ 26 if(!(a[i][p]==c || (c&&a[i][p]==27))) break; 27 (dp[l][r][p][c]+=dfs(l,i,p+1,0)*dfs(i+1,r,p,c+1)%mod)%=mod; 28 } 29 return dp[l][r][p][c]; 30 } 31 32 namespace WSN{ 33 inline short main(){ 34 n=read();memset(dp,-1,sizeof(dp)); 35 for(int i=1;i<=n;i++){ 36 scanf("%s",s[i]+1); 37 len[i]=strlen(s[i]+1); 38 maxn=max(maxn,len[i]); 39 for(int j=1;j<=len[i];j++){ 40 a[i][j]=s[i][j]-‘a‘+1; 41 if(s[i][j]==‘?‘) a[i][j]=27; 42 } 43 }write(dfs(1,n,1,0)); 44 return 0; 45 } 46 } 47 signed main(){return WSN::main();}
T3 Huge Counting
又是$dp$。。
考率题意可以转化为（如果他不$%2$）从（1，1）走到（i，j）的步数
不难发现这个数是可重级排列：$\frac{(\sum_{i=1}^{n}x_i)!}{\prod_{i=1}^{n}(x_i!)}$
那么对其取模$2$，表示这个数是奇数还是偶数，那么找分子分母的$2$的出现次数即可
有这样一个虱子：$\sum_{w=2^i} (\lfloor \frac{\sum_{x_i}}{w} \rfloor-\sum{\lfloor \frac{x_i}{w}\rfloor})$
然后我们就发现，如果有相加的时候有进位，那么它就会对下一位有贡献，而这一位的贡献不变。这意味着上式的值至少加$1$
所以，若要它等于$0$，一定要保证相加的时候没有进位，也就是每一位上为$1$1的数至多有$1$个
那么考虑$dp$，数位$dp$这样子
设$dp_{pos,S}$表示从高到低$dp$到第$pos$位，然后$S$是贴上界的状态
1 #include<bits/stdc++.h> 2 #define int long long 3 using namespace std; 4 namespace AE86{ 5 inline int read(){ 6 int x=0,f=1;char ch=getchar(); 7 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 8 while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f; 9 }inline void write(int x,char opt=‘\n‘){ 10 char ch[20];int len=0;if(x<0)x=~x+1,putchar(‘-‘); 11 do{ch[len++]=x%10+(1<<5)+(1<<4);x/=10;}while(x); 12 for(int i=len-1;i>=0;--i)putchar(ch[i]);putchar(opt);} 13 }using namespace AE86; 14 15 const int p=990804011; 16 int T,k,dp[70][600],l[10],r[10],lim[10],ans; 17 inline int DP(int pos,int S){ 18 if(dp[pos][S]!=-1) return dp[pos][S]; 19 int ans=0; 20 for(int i=0;i<k;i++)if( (!(S&(1ll<<i))) || (lim[i]&(1ll<<pos-1)) ){ 21 int sta=S; 22 for(int j=0;j<k;j++) if( i!=j && (lim[j]&(1ll<<pos-1)) ) sta^=S&(1<<j); 23 ans+=DP(pos-1,sta); 24 }int sta=S; 25 for(int j=0;j<k;j++) if(lim[j]&(1ll<<pos-1)) sta^=S&(1<<j); 26 ans+=DP(pos-1,sta); return dp[pos][S]=ans%p; 27 } 28 inline int ask(){ 29 for(int i=0;i<k;i++) if(lim[i]<0) return 0; 30 memset(dp,-1,sizeof(dp)); 31 for(int i=0;i<(1<<k);i++) dp[0][i]=1; 32 return DP(63,(1ll<<k)-1); 33 } 34 namespace WSN{ 35 inline short main(){ 36 T=read(); 37 while(T--){ 38 k=read();ans=0; 39 for(int i=1;i<=k;i++) l[i]=read(),r[i]=read(); 40 for(int i=0;i<(1<<k);i++){ 41 int cnt=0; 42 for(int j=0;j<k;j++) 43 if(i&(1<<j)) ++cnt, lim[j]=l[j+1]-2; 44 else lim[j]=r[j+1]-1; 45 ans+=ask()*((cnt&1)?-1:1); 46 }write((ans%p+p)%p); 47 } 48 return 0; 49 } 50 } 51 signed main(){return WSN::main();}
T4 字符消除2
考场上发现是$kmp$，但是构造部分不大会，据说看懂题就很神了
然后冲了个暴力，美滋滋～
正解是先处理出原串的$kmp$，
那么他的可行$t$集合是$n-nxt_i,n-nxt_{nxt_i},.......$
然后考虑构造一个和原串的$nxt$数组一样的$01$串
首先把处理出来的$nxt$迭代数组找个最小的，如果他大于1
表示最短串的$bouder$不是$1$，那么如果它全是$0$，则不会构造合法，
为了保证字典序，只需向$pre[1]$的位置添加一个$1$即可
然后我们可以枚举刚才迭代到没有的$nxt$，表示你这个$01$串构造到$pre_i$的时候他的$nxt_i$指向$pre_{i-1}$
考虑两种情况，如果$pre_i-pre_{i-1}>pre_{i-1}$，这个时候直接把原来的串当作前缀复制到最后，中间没有填满的
用$0$填上，但是这样可能不合法，因为中间放$0$可能会导致$kmp$偏移到这段$0$中的某一个，这时我们跑构造串的$kmp$
直接查看他的$nxt$是否指向$pre_{i-1}$即可
另一种就是你复制的时候会和前面的串怼到一起，这回就需要直接在后面接原来串的后缀即可，正确性可以$yy$得到
更加详细的讲解可以看$学长博客$
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int NN=2e5+5; 5 int T,n,nxt[NN],pre[NN],cnt,ans[NN],p,nt[NN]; 6 char s[NN],ch[NN]; 7 8 inline void kmp(){ 9 memset(nxt,0,sizeof(nxt)); 10 for(int i=2,j=0;i<=n;i++){ 11 while(j&&s[i]!=s[j+1]) j=nxt[j]; 12 if(s[i]==s[j+1]) ++j; 13 nxt[i]=j; 14 } 15 } 16 inline void Kmp(int n){ 17 memset(nt,0,sizeof(nt)); 18 for(int i=2,j=0;i<=n;i++){ 19 while(j&&ans[i]!=ans[j+1]) j=nt[j]; 20 if(ans[i]==ans[j+1]) ++j; 21 nt[i]=j; 22 } 23 } 24 25 namespace WSN{ 26 inline short main(){ 27 cin>>T; 28 while(T--){ 29 scanf("%s",s+1);n=strlen(s+1);kmp(); 30 cnt=0;memset(pre,0,sizeof(pre));memset(ans,0,sizeof(ans)); 31 int i=n; pre[++cnt]=n;while(nxt[i]){pre[++cnt]=nxt[i];i=nxt[i];} 32 reverse(pre+1,pre+cnt+1); if(pre[1]>1) ans[pre[1]]=1; 33 // for(int i=1;i<=n;i++) cout<<nxt[i]<<" ";cout<<endl; 34 for(int i=2;i<=cnt;i++) 35 if(pre[i-1]*2>=pre[i]) 36 for(int j=pre[i-1]+1;j<=pre[i];j++) 37 ans[j]=ans[j+pre[i-1]-pre[i]]; 38 else{ 39 int len=pre[i]-pre[i-1]; 40 for(int j=1;j<=pre[i-1];j++) ans[j+len]=ans[j]; 41 Kmp(pre[i]);if(nt[pre[i]]!=pre[i-1]) ans[len]=1; 42 } 43 for(int i=1;i<=n;i++) printf("%d",ans[i]);puts(""); 44 } 45 return 0; 46 } 47 } 48 signed main(){return WSN::main();}