T1 emotional flutter

把脚长合到黑条中。

每个黑条可以映射到统一区间，实际操作就是左右端点取模。长度大于$k$时显然不合法。

然后检查一遍区间内有没有不被黑条覆盖的点即可。

区间端点处理属实$ex$

$code:$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 typedef long long LL;

 4

 5 namespace IO{

 6     inline int read(){

 7         int x=0,f=1; char ch=getchar();

 8         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

 9         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

10         return x*f;

11     }

12     inline void write(int x,char sp){

13         char ch[20]; int len=0;

14         if(x<0){ putchar('-'); x=~x+1; }

15         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

16         for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

17     }

18 } using namespace IO;

19

20 const int NN=5e5+5;

21 int t,n,cnt;

22 LL a[NN],d[NN],s,k,step,mx;

23 bool skip,win;

24 struct black{ LL l,r; }b[NN];

25 inline bool cmp(black x,black y){ return x.l==y.l?x.r<y.r:x.l<y.l; }

26

27 signed main(){

28     t=read();

29     while(t--){

30         s=read(); k=read(); n=read(); cnt=0; skip=0; mx=0; win=0;

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

32             a[i]=read(), d[i]=d[i-1]+a[i];

33         for(int i=1;i<=n;i+=2){

34             int l=(d[i-1]+1)%k,r=(d[i]+s-1)%k;

35             if(d[i]+s-d[i-1]-2>=k){ skip=1; break; }

36             if(l<=r) b[++cnt]=(black){l,r};

37             else b[++cnt]=(black){0,r}, b[++cnt]=(black){l,k-1};

38         }

39         if(skip){ puts("NIE"); continue; }

40         sort(b+1,b+cnt+1,cmp);

41         if(b[1].l) win=1;

42         for(int i=1;i<=cnt;i++){

43             if(mx+1<b[i].l){ win=1; break; }

44             mx=max(mx,b[i].r);

45         }

46         if(mx<k-1) win=1;

47         puts(win?"TAK":"NIE");

48     }

49     return 0;

50 }

T2 medium counting

神仙$DP$。

设$f_{l,r,i,c}$表示只考虑$l$到$r$的串，强制让它们前$i$位相等，且第$i$位至少是$c$的方案。

转移时枚举$l$与$r$之间的一个串$i$。

不知道该说什么，太神仙了

$code:$

 1 #include<bits/stdc++.h>

 2 #define int long long

 3 #define rin register signed

 4 using namespace std;

 5

 6 namespace IO{

 7     inline int read(){

 8         int x=0,f=1; char ch=getchar();

 9         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

10         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

11         return x*f;

12     }

13     inline void write(int x,char sp){

14         char ch[20]; int len=0;

15         if(x<0){ putchar('-'); x=~x+1; }

16         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

17         for(rin i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

18     }

19 } using namespace IO;

20

21 const int p=990804011;

22 int n,mxl,f[60][60][30][30],len[60],a[60][30];

23 char ch[60][30];

24

25 int dfs(int l,int r,int pos,int c){

26     if(l>r) return f[l][r][pos][c]=1;

27     if(~f[l][r][pos][c]) return f[l][r][pos][c];

28     if(pos>mxl) return f[l][r][pos][c]=(l==r);

29     if(c>26) return f[l][r][pos][c]=0;

30     f[l][r][pos][c]=dfs(l,r,pos,c+1);

31     for(rin i=l;i<=r;i++){

32         if(!(a[i][pos]==c||(c&&a[i][pos]==27))) break;

33         (f[l][r][pos][c]+=dfs(l,i,pos+1,0)*dfs(i+1,r,pos,c+1)%p)%=p;

34     }

35     return f[l][r][pos][c];

36 }

37

38 signed main(){

39     n=read(); memset(f,-1,sizeof(f));

40     for(rin i=1;i<=n;i++){

41         scanf("%s",ch[i]+1);

42         len[i]=strlen(ch[i]+1);

43         mxl=max(len[i],mxl);

44         for(rin j=1;j<=len[i];j++)

45             a[i][j]=(ch[i][j]=='?')?27:(ch[i][j]-'a'+1);

46     }

47     write(dfs(1,n,1,0),'\n');

48     return 0;

49 }

T3 huge counting

一个函数的实际贡献只于将它所有参数减到$1$的方案数奇偶性有关。

多重集排列：$\frac{\sum{x_i}!}{\prod{x_i!}}$

考虑如何得到奇偶性。将分子分母质因子中$2$的个数相减，考虑差是否为$0$。

$\sum_{w=2^i} (\lfloor \frac{\sum_{x_i}}{w} \rfloor-\sum{\lfloor \frac{x_i}{w}\rfloor})$

发现所有$x$加和时不发生二进制进位时有贡献，即一个二进制位至多只能有$1$个$1$。

于是数位$DP$，记考虑哪一位与卡上界的状态。

最后高维容斥得到区间方案。

$code:$

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3

  4 namespace IO{

  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(); }

  9         return x*f;

 10     }

 11     inline void write(int x,char sp){

 12         char ch[20]; int len=0;

 13         if(x<0){ putchar('-'); x=~x+1; }

 14         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

 15         for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

 16     }

 17 } using namespace IO;

 18

 19 const int NN=2e5+5;

 20 int n,t,top,pos,nex[NN],anx[NN],stk[NN],ans[NN];

 21 char ch[NN];

 22

 23 void getnex(){

 24     memset(nex,0,sizeof(nex));

 25     for(int i=2,j=0;i<=n;i++){

 26         while(j&&ch[i]!=ch[j+1]) j=nex[j];

 27         if(ch[i]==ch[j+1]) nex[i]=++j;

 28         else nex[i]=0;

 29     }

 30 }

 31 void judgeans(){

 32     memset(anx,0,sizeof(anx));

 33     for(int i=2,j=0;i<=n;i++){

 34         while(j&&ans[i]!=ans[j+1]) j=anx[j];

 35         if(ans[i]==ans[j+1]) anx[i]=++j;

 36         else anx[i]=0;

 37     }

 38 }

 39

 40 signed main(){

 41     int t=read();

 42     while(t--){

 43         memset(ans,0,sizeof(ans)); top=0;

 44         scanf("%s",ch+1); n=strlen(ch+1);

 45         getnex(); pos=n;

 46         while(pos) stk[++top]=pos, pos=nex[pos];

 47         reverse(stk+1,stk+top+1);

 48         if(stk[1]>1) ans[stk[1]]=1;

 49         for(int i=2;i<=top;i++)

 50             if((stk[i-1]<<1)>=stk[i])

 51                 for(int j=stk[i-1]+1;j<=stk[i];j++)

 52                     ans[j]=ans[j+stk[i-1]-stk[i]];

 53             else{

 54                 int len=stk[i]-stk[i-1];

 55                 for(int j=1;j<=stk[i-1];j++) ans[j+len]=ans[j];

 56                 judgeans();

 57                 if(anx[stk[i]]!=stk[i-1]) ans[len]=1;

 58             }

 59         for(int i=1;i<=n;i++) putchar(ans[i]+'0'); puts("");

 60     }

 61     return 0;

 62 }

 63 /*

 64     int T,n,top;

 65     int nxt[maxn],kmp[maxn],stk[maxn],str[maxn];

 66     char s[maxn];

 67     inline void getnxt(){

 68         fill(nxt,0);

 69         for(int i=2,j=0;i<=n;i++){

 70             while(j && s[i]!=s[j+1]) j=nxt[j];

 71             if(s[i]==s[j+1]) j++;

 72             nxt[i]=j;

 73         }

 74     }

 75     inline void check(){

 76         fill(kmp,0);

 77         for(int i=2,j=0;i<=n;i++){

 78             while(j && str[i]!=str[j+1]) j=kmp[j];

 79             if(str[i]==str[j+1]) j++;

 80             kmp[i]=j;

 81         }

 82     }

 83

 84     inline int main(){

 85         T=read();

 86         while(T--){

 87             scanf("%s",s+1); n=strlen(s+1); fill(str,0);

 88             getnxt();

 89             int pos=n; top=0;

 90             while(pos) stk[++top]=pos,pos=nxt[pos];

 91             sort(stk+1,stk+1+top);

 92             if(stk[1]>1) str[stk[1]]=1;

 93             for(int i=2;i<=top;i++){

 94                 if(stk[i-1]*2>=stk[i]){

 95                     for(int j=stk[i-1]+1;j<=stk[i];j++)

 96                         str[j]=str[j+stk[i-1]-stk[i]];

 97                 }else{

 98                     int len=stk[i]-stk[i-1];

 99                     for(int j=1;j<=stk[i-1];j++) str[j+len]=str[j];

100                     check();

101                     if(kmp[stk[i-1]+len]!=stk[i-1]) str[len]=1;

102                 }

103             }

104             for(int i=1;i<=n;i++) printf("%d",str[i]); puts("");

105         }

106         return 0;

107     }

108 }

109 signed main(){return CL::main();}

11

 1 #include<bits/stdc++.h>

 2 #define rin register signed

 3 #define int long long

 4 using namespace std;

 5

 6 namespace IO{

 7     inline int read(){

 8         int x=0,f=1; char ch=getchar();

 9         while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); }

10         while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); }

11         return x*f;

12     }

13     inline void write(int x,char sp){

14         char ch[20]; int len=0;

15         if(x<0){ putchar('-'); x=~x+1; }

16         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

17         for(rin i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

18     }

19 } using namespace IO;

20

21 const int p=990804011;

22 int t,k,ans,l[10],r[10],d[10],f[70][550];

23

24 int dfs(int s,int lmt){

25     if(~f[s][lmt]) return f[s][lmt];

26     int res=0,sta;

27     for(int i=0;i<k;i++) if(!(lmt&(1ll<<i))||(d[i]&(1ll<<s-1))){

28         sta=lmt;

29         for(int j=0;j<k;j++)

30             if(i!=j&&(d[j]&(1ll<<s-1))) sta^=lmt&(1<<j);

31         (res+=dfs(s-1,sta))%=p;

32     }

33     sta=lmt;

34     for(int i=0;i<k;i++) if(d[i]&(1ll<<s-1)) sta^=lmt&(1<<i);

35     (res+=dfs(s-1,sta))%=p;

36     return f[s][lmt]=res;

37 }

38 int ANS(){

39     for(int i=0;i<k;i++) if(d[i]<0) return 0;

40     memset(f,-1,sizeof(f));

41     for(int i=0;i<(1<<k);i++) f[0][i]=1;

42     return dfs(63,(1<<k)-1);

43 }

44

45 signed main(){

46     t=read();

47     while(t--){

48         k=read(); ans=0;

49         for(int i=1;i<=k;i++)

50             l[i]=read(), r[i]=read();

51         for(int i=0;i<(1<<k);i++){

52             int cnt=0;

53             for(int j=0;j<k;j++)

54                 if(i&(1<<j)) cnt++, d[j]=l[j+1]-2;

55                 else d[j]=r[j+1]-1;

56             (ans+=((cnt&1)?-1:1)*ANS()%p+p)%=p;

57         }

58         write(ans,'\n');

59     }

60     return 0;

61 }

T4 字符消除2

队爷题解

照着写就行，不会证明正确性，我太弱了。

（感性理解的胜利

$code:$

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3

 4 namespace IO{

 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(); }

 9         return x*f;

10     }

11     inline void write(int x,char sp){

12         char ch[20]; int len=0;

13         if(x<0){ putchar('-'); x=~x+1; }

14         do{ ch[len++]=x%10+(1<<5)+(1<<4); x/=10; }while(x);

15         for(int i=len-1;~i;i--) putchar(ch[i]); putchar(sp);

16     }

17 } using namespace IO;

18

19 const int NN=2e5+5;

20 int n,t,top,pos,nex[NN],anx[NN],stk[NN],ans[NN];

21 char ch[NN];

22

23 void getnex(){

24     memset(nex,0,sizeof(nex));

25     for(int i=2,j=0;i<=n;i++){

26         while(j&&ch[i]!=ch[j+1]) j=nex[j];

27         if(ch[i]==ch[j+1]) nex[i]=++j;

28         else nex[i]=0;

29     }

30 }

31 void judgeans(){

32     memset(anx,0,sizeof(anx));

33     for(int i=2,j=0;i<=n;i++){

34         while(j&&ans[i]!=ans[j+1]) j=anx[j];

35         if(ans[i]==ans[j+1]) anx[i]=++j;

36         else anx[i]=0;

37     }

38 }

39

40 signed main(){

41     int t=read();

42     while(t--){

43         memset(ans,0,sizeof(ans)); top=0;

44         scanf("%s",ch+1); n=strlen(ch+1);

45         getnex(); pos=n;

46         while(pos) stk[++top]=pos, pos=nex[pos];

47         reverse(stk+1,stk+top+1);

48         if(stk[1]>1) ans[stk[1]]=1;

49         for(int i=2;i<=top;i++)

50             if((stk[i-1]<<1)>=stk[i])

51                 for(int j=stk[i-1]+1;j<=stk[i];j++)

52                     ans[j]=ans[j+stk[i-1]-stk[i]];

53             else{

54                 int len=stk[i]-stk[i-1];

55                 for(int j=1;j<=stk[i-1];j++) ans[j+len]=ans[j];

56                 judgeans();

57                 if(anx[stk[i]]!=stk[i-1]) ans[len]=1;

58             }

59         for(int i=1;i<=n;i++) putchar(ans[i]+'0'); puts("");

60     }

61     return 0;

62 }

巴特西

2021.8.19考试总结[NOIP模拟44]

T1 emotional flutter

T2 medium counting

T3 huge counting

T4 字符消除2

最新文章

热门文章