【考试总结】2022-01-21
高中数列问题
Let \(p_i\) be \(\lfloor\frac {i+b}c\rfloor,sf_i\) be \(\sum_{i=1}^n,q_j\) be the first k whose \(p_k=j\),which is found to be \(\rm jC-B\)
\[\begin{aligned}a[n]-A&=\sum_{i=1}^n f_{i}a[p_i]\\ a[n]-A&=\sum_{i=1}^n f_i\left(A+\sum_{j=1}^{p_i}f_ja[p_j]\right)\\ a[n]-A&=Asf_n+\sum_{i=1}^{p_n}f_ia[p_i]\sum_{k=q_i}^n f_k\\ a[n]-A-Asf_n&=\sum_{i=1}^{p_n}f_ia[p_i]\left(sf_n-sf_{q_i-1}\right) \end{aligned}\]By Using Lagrange interpolation,it's easy to calculate \(sf_n\) for any n in \(\Theta(Deg)\) 's time
Define \(G_i=f_i(sf_i-sf_{q_i})\) Here we get a \(2m+1\) degree polynomial in the subProblem
With Similar deduction we can get the following formula
\[\sum_{i=1}^n G(i)a[p_i]=AsG_n+\sum_{i=1}^{p_n}f_ia[p_i](sg_n-sg_{q_i-1}) \]\[G'[i]=f_i(sg_{n}-sg_{q_i-1}) \]Attention here \(q_i-1\) is a primary function of \(i\),so Lagrange interpolation is available here
The degree of the polynomial increases by \(m+1\) in a recursion so overall the complexity is \(\Theta(m^2\log^3n)\)
Code Display
const int N=1e4+10;
int fac[N],ifac[N],pre[N],poly[N],suf[N],A,B,C,n,m;
inline int lagrange(int x,int *y,int deg){
if(x<0) return 0;
if(x<=deg+1) return y[x];
pre[0]=suf[deg+2]=1;
rep(i,1,deg+1) pre[i]=mul(pre[i-1],(mod+(x-i)%mod)%mod);
Down(i,deg+1,1) suf[i]=mul(suf[i+1],((x-i)%mod+mod)%mod);
int ans=0;
rep(i,1,deg+1){
int prod=mul(pre[i-1],mul(suf[i+1],mul(ifac[deg-i+1],ifac[i-1])));
if((deg-i)&1) ckadd(ans,mul(y[i],prod));
else ckdel(ans,mul(y[i],prod));
}
return ans;
}
inline int GetF(int x){
int res=0;
Down(i,m,0) res=add(mul(res,x),poly[i]);
return res;
}
int y[N],tmp[N],sg[N];
inline int Q(int x){return C*x-B;}
inline int solve(int n,int deg){
if(n<=deg+1){
vector a={A};
for(int i=1;i<=n;++i) a.push_back(add(a.back(),mul(a[(i+B)/C],GetF(i))));
int ans=0;
rep(i,1,n) ckadd(ans,mul(del(sg[i],sg[i-1]),a[(i+B)/C]));
return ans;
}
int New=deg+m+1,sgn=lagrange(n,sg,deg+1);
for(int i=1;i<=2+New;++i) if(Q(i)<=n) tmp[i]=mul(GetF(i),del(sgn,lagrange(Q(i)-1,sg,deg+1)));
rep(i,1,New+2) sg[i]=add(sg[i-1],tmp[i]),tmp[i]=0;
return add(mul(A,sgn),solve((n+B)/C,New));
}
signed main(){
freopen("seq.in","r",stdin); freopen("seq.out","w",stdout);
n=10000; fac[0]=1;
for(int i=1;i<=n;++i) fac[i]=mul(fac[i-1],i);
ifac[n]=ksm(fac[n],mod-2);
Down(i,n,1) ifac[i-1]=mul(ifac[i],i);
n=read(); A=read(); B=read(); C=read(); m=read();
rep(i,0,m) poly[i]=read();
vector a={A}; a.resize(1000);
for(int i=1;i<=100;++i) a[i]=add(a[i-1],mul(a[(i+B)/C],GetF(i)));
rep(i,1,m+2) sg[i]=add(sg[i-1],GetF(i));
print(add(A,solve(n,m)));
return 0;
}
机动车限行
以下展开的讨论以 \(1\) 为例，因为对于颜色 \(2,3\) 而言除数字不同之外没有任何差别
考虑将 \(2\) 号点去掉之后产生了若干连通块，删掉 \(3\) 号点之后原图产生若干连通块，去除不含有 \(1\) 号点的连通块之后分别将其重标号
此时对于同时存在于连通块 \(p,q\) 的点 \(i\) 就在 \(p,q\) 之间连一条边，不难发现现在图是一张二分图
现在的问题时使用选择最小的边覆盖所有的点，答案时点数-最大匹配数
方案的构造就是选择所有的匹配边，对于非匹配点随便找一条出边，由于不再能找到奇数长度增广路，那么找哪条是没有区别的
Code Display
const int N=1e5+10;
int m,n,dep[N],S,T,tot,head[N],cnt,cur[N];
struct edge{int to,nxt,lim,id;}e[N<<1];
inline void adde(int u,int v,int w,int id){
e[++cnt]={v,head[u],w,id}; head[u]=cnt;
return ;
}
inline void add(int u,int v,int w,int id){return adde(u,v,w,id),adde(v,u,0,id);}
inline bool bfs(){
for(int i=1;i<=tot;++i) cur[i]=head[i],dep[i]=0; dep[S]=1;
queue q; q.push(S);
while(q.size()){
int fr=q.front(); q.pop();
for(int i=head[fr];i;i=e[i].nxt) if(e[i].lim){
int t=e[i].to; if(dep[t]) continue;
q.push(t); dep[t]=dep[fr]+1;
}
}
return dep[T];
}
inline int dfs(int x,int in){
if(x==T) return in; int out=0;
for(int i=cur[x];i;cur[x]=i,i=e[i].nxt)if(e[i].lim){
int t=e[i].to; if(dep[x]!=dep[t]-1) continue;
int res=dfs(t,min(in,e[i].lim));
in-=res; out+=res; e[i].lim-=res; e[i^1].lim+=res;
if(!in) break;
} if(!out) dep[x]=0;
return out;
}
int id[3][N],typ[N];
struct DSU{
int fa[N],mark[N];
inline void init(){rep(i,1,n) mark[i]=0,fa[i]=i; return ;}
inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void merge(int x,int y){return fa[find(x)]=find(y),void();}
}Dsu[3];
vector g[N];
bool vis[N];
inline void solve(int Id){
int alr=0; tot=0; cnt=1; S=++tot; T=++tot;
memset(head,0,sizeof(head));
memset(vis,0,sizeof(vis));
int num[3]={};
for(int ban:{1,2,3}) if(Id!=ban){
Dsu[++alr].init();
rep(i,1,n) if(typ[i]!=ban){
for(auto t:g[i]) if(typ[t]!=ban) Dsu[alr].merge(i,t);
}
rep(i,1,n) if(typ[i]==Id) Dsu[alr].mark[Dsu[alr].find(i)]++;
rep(i,1,n) if(Dsu[alr].mark[i]){
id[alr][i]=++tot;
if(alr==1) add(S,tot,1,0);
else add(tot,T,1,0);
}
num[alr]=tot;
}
for(int i=1;i<=n;++i) if(typ[i]==Id) add(id[1][Dsu[1].find(i)],id[2][Dsu[2].find(i)],1,i);
int ans=0;
while(bfs()) ans+=dfs(S,0x3f3f3f3f3f3f3f3f);
print(tot-2-ans);
for(int i=head[S];i;i=e[i].nxt) if(e[i].lim==0) vis[e[i].to]=1;
for(int i=head[T];i;i=e[i].nxt) if(e[i].lim) vis[e[i].to]=1;
for(int i=3;i<=num[1];++i) if(vis[i]){
for(int j=head[i];j;j=e[j].nxt) if(!e[j].lim) print(e[j].id);
}else print(e[head[i]].id);
for(int i=num[1]+1;i<=num[2];++i) if(!vis[i]) print(e[head[i]].id); puts("");
return ;
}
signed main(){
freopen("restriction.in","r",stdin); freopen("restriction.out","w",stdout);
n=read(); m=read(); rep(i,1,n) typ[i]=read();
for(int i=1;i<=m;++i){
int u=read(),v=read();
g[u].pb(v); g[v].pb(u);
}
solve(1); solve(2); solve(3);
return 0;
}
城市绿化
我的做法可以通过所有数据，并且我自己有理论上的 hack 方法：
找到两种平方算法：子树剥离和层间询问，层间点数小于 \(50\) 时跑层间询问，否则跑子树剥离
在子树剥离的过程中有些底层优化，利用的时都没有被确定的点和已经被确定的点的 \(\rm LCA\) 的深度信息来减少赘余，但是完全有可能时负优化就不瞎写了
一种可能的 hack 方法时将树分成 \(1000\) 个大小为 \(100\) 的块，造成卡子树剥离的树的形态，那么每个深度大的点要逐块询问次数比较多些
EOF
一种标算也是求出所有点的深度之重链剖分，根号次重构，每次询问一个新点的父亲逐个链底找 \(\rm LCA\)，最多跳 \(\log\) 次，两次重构之间随机剖分
注意到加入的点超过 \(\sqrt n\) 个就会重构，而这些可能不满足的点都被压到了很少的深度，所以是正确的
而套用 WC2018即时战略做法 的做法询问次数明显比我的做法的询问次数要小得多
Code Display
#include "green.h"
const int N=1e5+10;
int bz[N][20],dep[N],fa[N];
inline bool insub(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
return visit(x,y)==dep[y]-dep[x];
}
vector son[N];
inline int lca(int x,int y){
if(dep[x]=dep[y]) x=bz[x][i];
if(x==y) return x;
for(int i=19;~i;--i) if(bz[x][i]!=bz[y][i]) x=bz[x][i],y=bz[y][i];
return bz[x][0];
}
inline void init(int x){
bz[x][0]=fa[x];
for(int i=1;bz[x][i-1];++i) bz[x][i]=bz[bz[x][i-1]][i-1];
return ;
}
inline int jump(int x,int dst){
for(int i=19;~i;--i) if(dst>>i&1) x=bz[x][i];
return x;
}
inline void link(int x,int y){
if(dep[x]>dep[y]) swap(x,y);
son[fa[y]=x].push_back(y);
init(y);
return ;
}
int alr[N];
inline int getanc(int x,int tar){return jump(x,dep[x]-tar);}
inline void solve(vector > vec,int dmn,int dmx){
if(dmx==dmn) return ;
if(dmx-dmn==1){
for(auto t:vec[1]) link(vec[0][0],t);
return ;
} // father of nodes with depth of dmn has been calculated
int dnow=dmn+1;
for(auto node:vec[1]) link(node,vec[0][0]);
if(vec[dnow-dmn].size()==1) while(dnow > undecide;
rep(i,dnow+1,dmx){
for(auto t:vec[i-dmn]) alr[t]=vec[0][0],undecide.insert(make_pair(i,t));
}
vector > > tmp;
tmp.resize(vec[dnow-dmn].size());
map mp,app;
int siz=vec[dnow-dmn].size();
rep(i,0,siz-1) mp[vec[dnow-dmn][i]]=i,tmp[i].push_back({vec[dnow-dmn][i]});
for(auto t:vec[dnow+1-dmn]) if(undecide.count({dnow+1,t})){
while(dep[alr[t]] >::iterator it=undecide.begin();
for(;it!=undecide.end();){
int t2=it->sec;
if(lca(alr[t2],alr[t])!=alr[t2]){++it; continue;}
int lcadep=(dep[t]+dep[t2]-visit(t,t2))/2;
if(lcadep>=dnow){
if(tmp[kk].size()<=it->fir-dnow) tmp[kk].push_back({it->sec});
else tmp[kk][it->fir-dnow].push_back(it->sec);
++it; undecide.erase(prev(it));
}else{
int ee=getanc(alr[t],lcadep);
int tar=son[ee][getanc(alr[t],lcadep+1)==son[ee][0]];
if(dep[tar]>dep[alr[t2]]) alr[t2]=tar;
++it;
}
}
}
rep(i,0,siz-1) solve(tmp[i],dnow,dnow+tmp[i].size()-1);
return ;
}
vector > Dep[2];
vector nds;
void findtree(int n,int m,int *p){
if(n==1) return ;
rep(i,2,n) if((dep[i]=visit(i,1))==1) fa[i]=1,nds.push_back(i);
int dmx=0;
rep(i,2,n) ckmax(dmx,dep[i]);
cerr<