【考试总结】2022-03-03
排队
\(nm\) 的 \(\rm DP\) 是显然的，发现每 \(\bmod\) 次转移系数是一致的，那么可以合并计算
有了矩阵快速幂的雏形关键在于计算矩阵中每个位置的系数，要计算 \(x\) 行的系数可以把数组里面序号为 \(x\) 的位置置 \(1\) 做一次 \(\rm Dp\) 来实现
复杂度 \(\Theta(m^3\bmod)\)
Code Display
int n,m,tot,dp[2010][20][2][2],id[11][2][2],vec[50],f[2][20][2][2];
struct Mat{
int a[50][50]; Mat(){}
}mat;
int a[50][50],tmp[50];
signed main(){
freopen("queue.in","r",stdin); freopen("queue.out","w",stdout);
n=read(); m=read(); mod=read();
dp[2][1][1][0]=dp[2][1][0][1]=1;
for(int i=1;i<=m;++i){
rep(j,0,1) rep(k,0,1) id[i][j][k]=++tot;
}
int now=2;
while((n-now)%mod!=0){
for(int j=1;j<=m;++j){
rep(k,0,1) rep(l,0,1) if(dp[now][j][k][l]){
ckadd(dp[now+1][j+(!k)][1][l],dp[now][j][k][l]);
ckadd(dp[now+1][j+(!l)][k][1],dp[now][j][k][l]);
int gap=j*2-k-l,rem=now-1-gap; gap%=mod;
if(k) gap--,ckadd(dp[now+1][j][0][l],dp[now][j][k][l]);
if(l) gap--,ckadd(dp[now+1][j][k][0],dp[now][j][k][l]);
ckadd(dp[now+1][j][k][l],mul(dp[now][j][k][l],gap));
ckadd(dp[now+1][j+1][k][l],mul(dp[now][j][k][l],rem%mod));
}
}
++now;
}
if(now==n){
int ans=add(add(dp[n][m][0][0],dp[n][m][0][1]),add(dp[n][m][1][0],dp[n][m][1][1]));
print(ans);
exit(0);
}
rep(i,1,m) rep(j,0,1) rep(k,0,1) vec[id[i][j][k]]=dp[now][i][j][k];
int tim=(n-now)/mod;
rep(x,1,m) rep(y,0,1) rep(z,0,1){
int cur=0;
f[cur][x][y][z]=1;
rep(i,now,now+mod-1){
for(int j=1;j<=m;++j){
rep(k,0,1) rep(l,0,1) if(f[cur][j][k][l]){
ckadd(f[cur^1][j+(!k)][1][l],f[cur][j][k][l]);
ckadd(f[cur^1][j+(!l)][k][1],f[cur][j][k][l]);
int gap=j*2-k-l,rem=i-1-gap; gap%=mod;
if(k) gap--,ckadd(f[cur^1][j][0][l],f[cur][j][k][l]);
if(l) gap--,ckadd(f[cur^1][j][k][0],f[cur][j][k][l]);
ckadd(f[cur^1][j][k][l],mul(f[cur][j][k][l],gap));
ckadd(f[cur^1][j+1][k][l],mul(f[cur][j][k][l],rem%mod));
f[cur][j][k][l]=0;
}
} cur^=1;
}
rep(i,1,m) rep(j,0,1) rep(k,0,1) mat.a[id[x][y][z]][id[i][j][k]]=f[cur][i][j][k],f[cur][i][j][k]=0;
}
while(tim){
if(tim&1){
rep(i,1,tot) rep(j,1,tot) ckadd(tmp[j],mul(vec[i],mat.a[i][j]));
rep(i,1,tot) vec[i]=tmp[i],tmp[i]=0;
}
rep(i,1,tot) rep(k,1,tot) rep(j,1,tot) ckadd(a[i][j],mul(mat.a[i][k],mat.a[k][j]));
rep(i,1,tot) rep(j,1,tot) mat.a[i][j]=a[i][j],a[i][j]=0;
tim>>=1;
}
int ans=add(vec[id[m][0][0]],add(vec[id[m][1][1]],add(vec[id[m][1][0]],vec[id[m][0][1]])));
print(ans);
return 0;
}
昵称
使用 \(\rm AC\) 自动机实现一个计算不超过 \(\overline{a_1\dots a_n}\) 的数字中有多少个满足包含给定的 \(S\)
所以我们先二分最后字符串的长度，之后按位确定每个数位是几
注意到一定有连续的一段是 \(S\)，那么对于每个自由位置先判定是不是必须要填 \(S\) 即可，判定次数是自由元个数的级别，也就是 \(\log 10^18\)
那么复杂度也就降到了 \(\Theta(n^2\log n)\)，常数还是蛮大的
Code Display
const int N=2010;
int n,fail[N],son[N][10],m;
char s[N];
int dp[2][N][2][2],up[N];
//dp[cur][match][bound][pas]
inline bool check(int len){
memset(dp,0,sizeof(dp));
int cur=0; dp[cur][0][1][0]=1;
for(int i=0;i=m&&l) return 1;
if(!l&&len-i=m) return 1;
ans+=dp[cur][i][1][1];
if(ans+dp[cur][i][0][1]>=m) return 1;
ans+=dp[cur][i][0][1];
} return 0;
}
int ans[N];
signed main(){
freopen("nickname.in","r",stdin); freopen("nickname.out","w",stdout);
scanf("%s",s+1); n=strlen(s+1); m=read();
son[0][s[1]-'0']=1;
for(int i=0;i>1;
rep(i,1,n+50) up[i]=0;
rep(i,1,mid) up[i]=9;
if(check(mid)) r=mid-1,tar=mid;
else l=mid+1;
}
bool Push=0;
memset(up,0,sizeof(up));
rep(i,1,tar) ans[i]=9,up[i]=9;
for(int i=1;i<=tar;++i){
rep(j,1,tar) up[j]=ans[j];
if(Push==0&&i+n-1<=tar){
for(int j=0;j>1; up[i]=mid;
if(check(tar)) ans[i]=mid,r=mid-1;
else l=mid+1;
}
}
for(int i=1;i<=tar;++i) putchar(ans[i]+'0'); putchar('\n');
return 0;
}
帝国防卫
使用整体二分来计算每个点骑士数量不小于 \(c_i\) 的时间，考虑对于每个位置维护 \(Add_i\) 表示距离为 \(i\) 的点在这个点能得到的贡献，同时维护 \(Del_i\) 表示从哪里跳上来的要减掉
注意这里贡献不能写作加和右移，因为这和右移之后再加和是完全不一样的，这也就是为什么每个深度要单独维护数组的原因了
每次修改跳 \(\log\) 个父亲，每个父亲对应修改其深度即可
剩下的都是整体二分和树状数组 \(\rm dfs\) 序的基础操作了，不再赘述
时间复杂度是 \(\Theta(n\log^3n)\)
一个可行的优化方式就是将所有查询和修改的点拉出来建立虚树，虚树上边权就是两个点之间的距离
还是执行上述操作，不过每个虚树上节点维护权值 \(Add_i,Del_i\) 表示它和虚树上父亲这一段里面的点的“三角形”数组里面的权值的和
这个时候增量和原来的一个数字不同，是一个 \(\Sigma \frac{x}{2^i}\) 关于 \(i\) 的区间和，但是仍然可以 \(\Theta(1)\) 求出来
那么使用一个类似换根 \(\rm DP\) 的东西就能求出来正确的权值了，一种可行的实现是不存真值，而是每个数位 \(1\) 的个数
代码实现的 \(3\) 个 \(\log\) 的，所以上面做法是在口嗨
Code Display
const int N=1e5+10;
int n;
struct BIT{
int c[N];
inline void insert(int x){for(;x<=n;x+=x&(-x)) c[x]++; return ;}
inline int query(int x){int res=0; for(;x;x-=x&(-x)) res+=c[x]; return res;}
}T;
int c[N],fa[N],val[N],in[N],out[N],dfn;
vector G[N],node[N];
inline void get_dfn(int x,int fat){
in[x]=++dfn; fa[x]=fat;
for(auto t:G[x]) if(t!=fat) get_dfn(t,x);
out[x]=dfn;
}
int sum[N],Add[N][19],Del[N][19];
int x[N],delt[N],typ[N],tim[N];
inline int Query(int x){
int res=sum[x],lst=x; x=fa[x];
int up=1;
while(up<=18&&x){
res+=Add[x][up]-Del[lst][up];
++up; x=fa[lst=x];
} return res;
}
inline void insert(int x,int val,int fl){
int now=x,tmp=val;
while(now&&tmp) sum[now]+=tmp*fl,tmp>>=1,now=fa[now];
int lst=0;
while(val&&x){
for(int j=1;val>>j;++j) Add[x][j]+=fl*(val>>j),Del[lst][j]+=fl*(val>>j);
x=fa[lst=x]; val>>=1;
}
return ;
}
inline void solve(int ql,int qr,vector now){
if(ql==qr){
for(auto t:now) tim[t]=ql;
return ;
}
int mid=(ql+qr)>>1;
for(int i=ql;i<=mid;++i) if(typ[i]==1) insert(x[i],delt[i],1);
vector lef,rig;
for(auto e:now) if(Query(e)>=c[e]) lef.push_back(e); else rig.push_back(e);
solve(mid+1,qr,rig);
for(int i=ql;i<=mid;++i) if(typ[i]==1) insert(x[i],delt[i],-1);
solve(ql,mid,lef);
return ;
}
signed main(){
freopen("empire.in","r",stdin); freopen("empire.out","w",stdout);
n=read(); rep(i,1,n) c[i]=read();
for(int i=1;i now;
for(int i=1;i<=n;++i) if(Query(i)>=c[i]) now.push_back(i);
for(int i=1;i<=Q;++i) if(typ[i]==1) insert(x[i],delt[i],-1);
solve(1,Q,now);
for(int i=1;i<=n;++i) if(tim[i]) node[tim[i]].push_back(i);
for(int i=1;i<=Q;++i){
if(typ[i]==2){
print(T.query(out[x[i]])-T.query(in[x[i]]-1));
}else{
for(auto t:node[i]) T.insert(in[t]);
}
}
return 0;
}
感觉这套题目许多同学现在考和联赛前考得分并不会有什么不一样