C
看到通配符首先想到FFT。统计S与T的匹配数fi，首先假设没有通配符，枚举0~9的每个数c，若s[i]=t[j]=c，则f[i-j]++。根据容斥原理，S的一个子串通过通配符与T匹配的方案数=S对应字符是通配符的数量+T对应字符是通配符的数量-二者对应字符都是通配符的数量。二者皆可通过FFT求出，时间复杂度O(11nlogn)
#include<bits/stdc++.h> using namespace std; const double pi=acos(-1.0); const int N=2e6+7; int n,m,nn,st,ss[N],R[N],f[N],ans[N]; char s[N],t[N]; struct node{ double x,y; node(double xx=0,double yy=0){x=xx,y=yy;} node operator*(node a){return node(x*a.x-y*a.y,x*a.y+y*a.x);} node operator+(node a){return node(x+a.x,y+a.y);} node operator-(node a){return node(x-a.x,y-a.y);} }a[N],b[N],p[N]; void fft(node *A,double f) { for(int i=0;i<nn;i++)if(i<R[i])swap(A[i],A[R[i]]); for(int i=1;i<nn;i<<=1) { node wn(cos(pi/i),f*sin(pi/i)); for(int j=0;j<nn;j+=i<<1) { node w(1,0); for(int k=0;k<i;k++,w=w*wn) { node x=A[j+k],y=w*A[j+i+k]; A[j+k]=x+y,A[j+i+k]=x-y; } } } } int main() { int T;scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); scanf("%s%s",s,t); reverse(t,t+m); int len=0; nn=1;while(nn<=m+n-2)nn<<=1,len++; for(int i=0;i<=nn;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(len-1)); for(int i=0;i<=nn;i++)p[i]=node(0,0),ans[i]=f[i]=0; for(int c=0;c<=9;c++) { for(int i=0;i<=nn;i++)a[i]=node((i<n&&s[i]-'0'==c)?1:0,0); for(int i=0;i<=nn;i++)b[i]=node((i<m&&t[i]-'0'==c)?1:0,0); fft(a,1),fft(b,1); for(int i=0;i<=nn;i++)p[i]=p[i]+a[i]*b[i]; } fft(p,-1); for(int i=0;i<=nn;i++)f[i]+=(int)(p[i].x/nn+0.5); for(int i=0;i<n;i++)ss[i+1]=0; st=0; for(int i=0;i<n;i++)ss[i+1]=ss[i]+(s[i]=='*'); for(int i=0;i<m;i++)st+=t[i]=='*'; for(int i=0;i<=nn;i++)p[i]=node(0,0); for(int i=0;i<=nn;i++)a[i]=node((i<n&&s[i]=='*')?1:0,0); for(int i=0;i<=nn;i++)b[i]=node((i<m&&t[i]=='*')?1:0,0); fft(a,1),fft(b,1); for(int i=0;i<=nn;i++)p[i]=a[i]*b[i]; fft(p,-1); for(int i=0;i<=nn;i++)f[i]-=(int)(p[i].x/nn+0.5); for(int i=m-1;i<n;i++)ans[m-(f[i]+ss[i+1]-ss[i-m+1]+st)]++; for(int i=1;i<=m;i++)ans[i]+=ans[i-1]; for(int i=0;i<=m;i++)printf("%d ",ans[i]); } }
D
签到。统计每种斜率出现次数。Bob的最优策略是避开斜率次数出现多的直线，Alice的最优策略是最小化斜率出现次数的最大值，即每次从每种斜率直线中各选一条
#include<bits/stdc++.h> using namespace std; const int N=1e5+7; pair<int,int>a[N]; int n,ans[N]; int main() { int T;scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1;i<=n;++i) { ans[i]=0; int x1,y1,x2,y2,dx,dy,d; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); dx=x1-x2,dy=y1-y2; if(!dx)dy=1;else if(!dy)dx=1; else{ if(dx<0)dx*=-1,dy*=-1; d=__gcd(abs(dx),abs(dy)); dx/=d,dy/=d; } a[i]=make_pair(dx,dy); } sort(a+1,a+n+1); for(int i=1,j;i<=n;i=j) { j=i;while(j<=n&&a[i]==a[j])++j; for(int k=1;k<=j-i;++k)++ans[k]; } for(int i=1,j=1;i<=n;++i) { while(!ans[j])++j; --ans[j]; printf("%d ",i-j); } } }
G
懒得写了，很没意思的一道签到题，纯粹考虑阅读能力。
贡献对255取min维护前缀和，时间复杂度O(n+q)
K
签到题，对区间长度记忆化搜索即可，代码略
持续更新中……