[离线+bitset维护传递闭包+卡空间]2022“杭电杯”中国大学生算法设计超级联赛（3）10【Range Reachability Query】题解
题目概述HDU7171解题报告题目保证了DAG，所以是个DAG上的传递闭包问题，考虑用bitset做。定义 $f_{i,j}$ 表示是否能通过 $j$ 询问中的 $[l_i,r_i]$ 边从 $u_j$ 走到 $i$ 点，用bitset记录。然后做拓扑，对于 $i$ 号边 $x_i\to y_i$ ，则 $f_{y_i}=f_{y_i}\cup(f_{x_i}\cap S_i)$ ，其中 $S_i$ 表示包含 $i$ 号边的询问集合，可以通过扫描线处理。由于 $m$ 比较大恭喜我们成功炸空间了，类似这题，我们想办法把空间除掉个常数，因此我们每隔 $4$ 个扫描线中的点才记录一次bitset，然后查询时再花 $4$ 次补全 $S_i$ ，这样就不会炸空间了。示例程序#include<cstdio> #include<cctype> #include<bitset> #include<algorithm> #define fr first #define sc second #define mp make_pair using namespace std; const int maxn=50000,maxm=100000,maxq=50000,maxs=maxq<<1; int te,n,m,Q,X[maxm+5],Y[maxm+5]; int U[maxq+5],V[maxq+5],L[maxq+5],R[maxq+5]; int E,D[maxn+5],lnk[maxn+5],nxt[maxm+5],ID[maxm+5],to[maxm+5]; int cnt;pair<int,int> s[maxs+5]; int que[maxn+5]; bitset<maxq> S[(maxs>>2)+5],f[maxn+5],now; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } inline void Add(int x,int y,int z) {to[++E]=y;ID[E]=z;nxt[E]=lnk[x];lnk[x]=E;} int Find(int x){ int L=0,R=cnt-1; for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) s[mid].fr<=x?L=mid+1:R=mid-1; return R; } int main(){ for (readi(te);te;te--){ readi(n);readi(m);readi(Q); E=0;for (int i=1;i<=n;i++) lnk[i]=D[i]=0,f[i]=0; for (int i=1,x,y;i<=m;i++) readi(X[i]),readi(Y[i]),Add(X[i],Y[i],i),D[Y[i]]++; cnt=0; for (int i=0;i<Q;i++){ readi(U[i]);readi(V[i]);readi(L[i]);readi(R[i]); s[cnt++]=mp(L[i],i);if (R[i]<m) s[cnt++]=mp(R[i]+1,i); f[U[i]][i]=1; } sort(s,s+cnt); S[0]=0; for (int i=0;i<cnt;i++){ if (!(i&3)) S[(i>>2)+1]=S[i>>2]; S[(i>>2)+1].flip(s[i].sc); } int Head=0,Tail=0; for (int i=1;i<=n;i++) if (!D[i]) que[++Tail]=i; while (Head!=Tail) for (int x=que[++Head],j=lnk[x];j;j=nxt[j]){ int pos=ID[j],k=Find(pos); now=S[k>>2];for (int i=(k>>2)<<2;i<=k;i++) now.flip(s[i].sc); f[to[j]]|=f[x]&now; if (!(--D[to[j]])) que[++Tail]=to[j]; } for (int i=0;i<Q;i++) puts(f[V[i]][i]?"YES":"NO"); } return 0; }
[矩阵维护DP+树链剖分+不重叠ST表]2021牛客暑期多校训练营6 K【Starch Cat】题解
题目概述Starch Cat解题报告正解是猫树，但是我不会，所以我选择黑科技。首先我们能想到一个比较暴力的做法，每次询问 $x,y$ 路径上的最大独立集，就是求 $x\to LCA(x,y),y\to LCA(x,y)$ 的两个最大独立集，然后在 $LCA$ 处讨论一下。定义 $f_{i,0/1}$ 表示 $i$ 点不选/选的最大独立集，然后考虑 $x\to fa_x$ 的DP：$$ f_{fa_x,0}=\max\{f_{x,0},f_{x,1}\}\\ f_{fa_x,1}=f_{x,0}+a_{fa_x} $$这可以用矩阵维护（当然，矩乘定义是 $c_{i,j}=\max_{k}\{a_{i,k}+b_{k,j}\}$ ）：$$ \begin{bmatrix}f_{x,0}&f_{x,1}\end{bmatrix}\begin{bmatrix}0&a_{fa_x}\\0&-\infty\end{bmatrix}=\begin{bmatrix}f_{fa_x,0}&f_{fa_x,1}\end{bmatrix} $$令 $x$ 的矩阵为 $\begin{bmatrix}0&a_{fa_x}\\0&-\infty\end{bmatrix}$ ，那么求出 $x\to LCA(x,y),y\to LCA(x,y)$​ 路径上矩阵的乘积就可以知道DP的值。所以暴力的做法就很显然了：用倍增求出矩阵乘积即可。但是这道题数据范围太大，倍增求LCA的做法复杂度稳定太大了，所以过不了。倍增复杂度太大，我们就考虑常数小很多的树链剖分，但是这样就无法维护ST表了（ST表有重复部分），接下来利用黑科技不重叠ST表来维护区间矩阵乘积就行了。示例程序#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=500000,LOG=19,maxs=1<<LOG,maxm=maxn<<1,MOD=998244353; int n,m,seed,a[maxn+5],dep[maxn+5],si[maxn+5],fa[maxn+5]; int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5]; int dfn,Lt[maxn+5],Rt[maxn+5],SH[maxn+5],top[maxn+5],lg[maxs+5]; struct Matrix{ LL s[2][2]; void build(LL a,LL b,LL c,LL d) {s[0][0]=a;s[0][1]=b;s[1][0]=c;s[1][1]=d;} void clear() {for (int i=0;i<2;i++) for (int j=0;j<2;j++) s[i][j]=-(1e18);} void unit() {clear();for (int i=0;i<2;i++) s[i][i]=0;} }; Matrix M[maxn+5],A[LOG+1][maxn+5],B[LOG+1][maxn+5]; struct Rand{ unsigned int n,seed; Rand(unsigned int n,unsigned int seed) :n(n),seed(seed){} int get(long long lastans){ seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5; return (seed^lastans)%n+1; } }; #define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); lst=='-'?x=-tot:x=tot;return EOLN(ch); } inline void Add(int x,int y) {son[++E]=y;nxt[E]=lnk[x];lnk[x]=E;} inline Matrix operator * (const Matrix &a,const Matrix &b){ static Matrix c;c.clear(); for (int i=0;i<2;i++) for (int j=0;j<2;j++) c.s[i][j]=max(a.s[i][0]+b.s[0][j],a.s[i][1]+b.s[1][j]); return c; } void DFS(int x,int pre=0){ dep[x]=dep[pre]+1;si[x]=1;fa[x]=pre; for (int j=lnk[x],u;j;j=nxt[j]) if ((u=son[j])!=pre){ DFS(u,x);si[x]+=si[u]; if (si[u]>si[SH[x]]) SH[x]=u; } } void HLD(int x,int lst,int pre=0){ Lt[x]=++dfn;top[x]=lst; if (pre) M[dfn].build(0,a[pre],0,-(1e18)); if (SH[x]) HLD(SH[x],lst,x); for (int j=lnk[x],u;j;j=nxt[j]) if ((u=son[j])!=pre && u!=SH[x]) HLD(u,u,x); Rt[x]=dfn; } inline Matrix Ask(int L,int R) {return L==R?M[L]:A[lg[L^R]][R]*B[lg[L^R]][L];} LL Query(int x,int y){ static Matrix X,Y;X.unit();Y.unit(); int s=x,t=y; while (top[x]!=top[y]) if (dep[top[x dep[top[y]]) X=X*Ask(Lt[top[x]],Lt[x]),x=fa[top[x]]; else Y=Y*Ask(Lt[top[y]],Lt[y]),y=fa[top[y]]; int lca=x; if (Lt[x]<Lt[y]) lca=x,Y=Y*Ask(Lt[x]+1,Lt[y]); if (Lt[x]>Lt[y]) lca=y,X=X*Ask(Lt[y]+1,Lt[x]); LL f[2]={max(X.s[0][0],X.s[1][0]+a[s]),max(X.s[0][1],X.s[1][1]+a[s])}; LL g[2]={max(Y.s[0][0],Y.s[1][0]+a[t]),max(Y.s[0][1],Y.s[1][1]+a[t])}; return max(f[0]+g[0],f[1]+g[1]-a[lca]); } #define L(i,k) ((i)>>(k)<<(k)) #define R(i,k) (((i)+(1<<(k))>>(k)<<(k))-1) int main(){ readi(n);readi(m);readi(seed); for (int i=1;i<=n;i++) readi(a[i]); for (int i=2,x;i<=n;i++) readi(x),Add(x,i),Add(i,x); DFS(1);dfn=-1;HLD(1,1); for (int j=1;j<LOG;j++) lg[1<<j]=j; for (int i=1;i<maxs;i++) if (!lg[i]) lg[i]=lg[i-1]; for (int i=0;i<n;i++) A[0][i]=B[0][i]=M[i]; for (int j=1;(1<<j)<=n;j++){ A[j][0].unit();for (int i=0;i<=n-1;i++) A[j][i]=(L(i,j)==i?M[i]:M[i]*A[j][i-1]); B[j][n].unit();for (int i=n-1;i>=0;i--) B[j][i]=(R(i,j)==i?M[i]:B[j][i+1]*M[i]); } LL lstans=0,ans=0; Rand rand(n,seed); for (int i=1;i<=m;i++){ int u=rand.get(lstans); int v=rand.get(lstans); int x=rand.get(lstans); lstans=Query(u,v); ans=(ans+lstans%MOD*x)%MOD; } printf("%lld\n",ans); return 0; }
课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内，所以可以把值域也分块，这样移动指针就不需要带 $log$ 了，每次再用 $O(\sqrt{n+K})$ 来询问。没有找到原题，代码咕咕咕QAQ……K 小值查询把集合分成三部分：$[1,k],(k,2k],(2k,+\infty)$ ，将第二部分提取出来暴力减去 $k$ 后重新加入集合，此时只剩下两部分 $[1,k],(2k,+\infty)$ ，后一部分减去 $k$ 后依然在第一部分后面，所以可以打tag。因为第二部分至少除以 $2$ ，所以复杂度 $O(nlog_2nlog_2k)$ 。操作均可以用Splay完成，好久没手写平衡树了……#include<cstdio> #include<algorithm> using namespace std; const int maxn=100000,maxt=5e6; int n,m; int len,ro,son[maxt+5][2],val[maxt+5],num[maxt+5],si[maxt+5],tag[maxt+5]; #define cmp(p,k) ((k)==val[p]?-1:(k)>val[p]) inline void Pushup(int p) {si[p]=si[son[p][0]]+num[p]+si[son[p][1]];} inline void Rotate(int &p,int d){ int t=son[p][d];son[p][d]=son[t][d^1];son[t][d^1]=p; Pushup(p);Pushup(t);p=t; } inline void Addtag(int p,int k) {if (!p) return;val[p]+=k;tag[p]+=k;} inline void Pushdown(int p) {if (tag[p]) Addtag(son[p][0],tag[p]),Addtag(son[p][1],tag[p]),tag[p]=0;} void Splay(int &p,int k){ int d=cmp(p,k);if (d<0) return;Pushdown(p);int &s=son[p][d],f=cmp(s,k); if (~f) Splay(son[s][f],k),d==f?Rotate(p,d):Rotate(s,f);Rotate(p,d); } void Insert(int &p,int k,int x=1){ if (!p) {p=++len;val[p]=k;num[p]=x;Pushup(p);return;}Pushdown(p); int d=cmp(p,k);if (~d) Insert(son[p][d],k,x); else num[p]+=x;Pushup(p); } int Askkth(int p,int k){ Pushdown(p);int ls=si[son[p][0]];if (ls<k&&k<=ls+num[p]) return val[p]; return k<=ls?Askkth(son[p][0],k):Askkth(son[p][1],k-ls-num[p]); } int Askpre(int p,int k){ if (!p) return -1;Pushdown(p);int now=-1;if (val[p]<k) now=val[p]; return k<=val[p]?max(now,Askpre(son[p][0],k)):max(now,Askpre(son[p][1],k)); } int Asksuf(int p,int k){ if (!p) return 2e9;Pushdown(p);int now=2e9;if (val[p]>k) now=val[p]; return k>=val[p]?min(now,Asksuf(son[p][1],k)):min(now,Asksuf(son[p][0],k)); } void Join(int p,int k){ if (!p) return;Pushdown(p);Insert(ro,val[p]-k,num[p]);Splay(ro,val[p]-k); Join(son[p][0],k);Join(son[p][1],k); } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d",&n,&m);for (int i=1,x;i<=n;i++) scanf("%d",&x),Insert(ro,x),Splay(ro,x); for (int i=1;i<=m;i++){ int tp,k,ans;scanf("%d%d",&tp,&k); if (tp==1) ans=Askkth(ro,k),Splay(ro,ans),printf("%d\n",ans); else{ int L=Askpre(ro,k+1),R=Asksuf(ro,k<<1); if (L==-1&&R==2e9) Addtag(ro,-k); else if (L==-1) Splay(ro,R),Addtag(ro,-k); else if (R==2e9){ Splay(ro,L);int now=son[ro][1]; son[ro][1]=0;Pushup(ro);Join(now,k); } else{ Splay(ro,L);Splay(son[ro][1],R);int now=son[son[ro][1]][0]; son[son[ro][1]][0]=0;Addtag(son[ro][1],-k); Pushup(son[ro][1]);Pushup(ro);Join(now,k); } } } return 0; }抓 fafa 的 qzh考虑离线，不难想到用cdq分治来处理，这样就把问题简化了很多。但是如果分治时间，就维护不了区间可爱值，分治可爱值，就保证不了时间顺序。因此我们需要把一个询问 $[l,r]$ 拆成两个：$<l$ 的部分和 $<r+1$ 的部分，这样就不需要求区间可爱值。那么分治可爱值 $[l,r]$ ，然后用可爱值在 $[l,mid]$ 的修改操作贡献 $[mid+1,r]$ 的询问。但是怎么维护一个点集能够查询 $x$ 到这个点集的距离和呢？和这道题差不多，只不过我们要维护的是链上加等差数列，可以用链剖+线段树或者LCT。我讨厌数据结构……调了好久……#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int maxn=100000,maxm=120000; int n,m,Q;struct data {int tp,ID,x,y,z;} q[maxm+5],tem[2][maxm+5];LL ans[maxm+5]; int dep[maxn+5],son[maxn+5][2],fa[maxn+5],si[maxn+5];bool flip[maxn+5]; LL num[maxn+5],sum[maxn+5],tag[maxn+5][2],D[maxn+5],cnt,S; #define is_ro(p) ((p)!=son[fa[p]][0]&&(p)!=son[fa[p]][1]) #define Son(p) ((p)==son[fa[p]][1]) inline void Pushup(int p){ si[p]=si[son[p][0]]+1+si[son[p][1]]; sum[p]=sum[son[p][0]]+num[p]+sum[son[p][1]]; } inline void Rotate(int t){ int p=fa[t],d=Son(t);son[p][d]=son[t][d^1];son[t][d^1]=p; if (!is_ro(p)) son[fa[p]][Son(p)]=t;Pushup(p);Pushup(t); if (son[p][d]) fa[son[p][d]]=p;fa[t]=fa[p];fa[p]=t; } inline void Addflip(int p) { if (!p) return;swap(son[p][0],son[p][1]);flip[p]^=1; tag[p][0]+=D[p]*(si[p]-1);D[p]=-D[p]; } inline void Addtag(int p,int ID,LL k,LL d=0){ if (!p) return;if (ID==1) num[p]+=k,sum[p]+=k*si[p],tag[p][1]+=k; if (!ID) num[p]+=k+d*si[son[p][0]],sum[p]+=(k+k+d*(si[p]-1))*si[p]/2,tag[p][0]+=k,D[p]+=d; } inline void Pushdown(int p){ if (flip[p]) Addflip(son[p][0]),Addflip(son[p][1]),flip[p]^=1; if (tag[p][0]||D[p]){ LL k=tag[p][0],d=D[p];tag[p][0]=D[p]=0; Addtag(son[p][0],0,k,d);Addtag(son[p][1],0,k+d*(si[son[p][0]]+1),d); } if (tag[p][1]){ LL k=tag[p][1];tag[p][1]=0; Addtag(son[p][0],1,k);Addtag(son[p][1],1,k); } } inline void Splay(int p){ static int top,stk[maxn+5];stk[top=1]=p; for (int i=p;!is_ro(i);i=fa[i]) stk[++top]=fa[i]; while (top) Pushdown(stk[top--]); for (int pre=fa[p];!is_ro(p);Rotate(p),pre=fa[p]) if (!is_ro(pre)) Rotate(Son(p)==Son(pre)?pre:p); } inline int Access(int p,int x=0){ for (int lst=0;p;x=lst=p,p=fa[p]) Splay(p),son[p][1]=lst,Pushup(p);return x; } inline void Makero(int x) {Access(x);Splay(x);Addflip(x);} inline void Link(int x,int y) {Makero(x);fa[x]=y;} inline void Insert(int x,int y,int tp,int k,int d=0) {Makero(y);Access(x);Splay(x);Addtag(x,tp,k,d);} inline int LCA(int x,int y) {return Makero(1),Access(x),Access(y);} inline int Size(int x,int y) {Makero(y);Access(x);Splay(x);return si[x];} inline LL Ask(int x) {Makero(1);Access(x);Splay(x);return sum[x];} inline void Update(int x,int y,int f){ int lca=LCA(x,y),si=Size(x,y);Insert(lca,x,0,f,f);Insert(lca,y,0,f,f); Insert(lca,1,1,f*si);Splay(lca);num[lca]-=f*(si+1);Pushup(lca); cnt+=f*(dep[x]-dep[lca]+dep[y]-dep[lca]+1);S-=f*dep[lca]; S+=f*((LL)(dep[x]+dep[lca])*(dep[x]-dep[lca]+1)>>1); S+=f*((LL)(dep[y]+dep[lca])*(dep[y]-dep[lca]+1)>>1); } void Solve(int L,int R,int l=-1e9,int r=1e9+1){ if (L==R||l==r) return;int mid=l+(r-l>>1),A=0,B=0; for (int i=L;i<=R;i++){ int tp=q[i].tp,ID=q[i].ID,x=q[i].x,y=q[i].y,z=q[i].z; if (z<=mid) tem[0][A++]=q[i]; else tem[1][B++]=q[i]; if (tp==1&&z<=mid) Update(x,y,1);if (tp==2&&z>mid) ans[ID]+=y*(S+(LL)dep[x]*cnt-(Ask(x)<<1)); }for (int i=L;i<=R;i++) if (q[i].tp==1&&q[i].z<=mid) Update(q[i].x,q[i].y,-1); for (int i=0;i<A;i++) q[L+i]=tem[0][i];for (int i=0;i<B;i++) q[L+A+i]=tem[1][i]; if (A) Solve(L,L+A-1,l,mid);if (B) Solve(L+A,R,mid+1,r); } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) si[i]=1; for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Link(x,y); for (int i=1;i<=n;i++) dep[i]=Size(1,i); for (int i=1;i<=m;i++){ int tp,x,y,z;scanf("%d%d%d%d",&tp,&x,&y,&z); if (tp==1) q[++Q]=(data){tp,i,x,y,z},ans[i]=-1; else q[++Q]=(data){tp,i,z,-1,x},q[++Q]=(data){tp,i,z,1,y+1}; }Solve(1,Q);for (int i=1;i<=m;i++) if (~ans[i]) printf("%lld\n",ans[i]);return 0; }Product on the segmentAwD说的那个好神仙啊……我只会 $O(nlog_2n+q)$ 啊……区间修改我们会想到ST表，但是ST表有重叠部分就GG了。我们需要用到一个和ST表有些类似的数据结构，定义 $A_{i,j}=\prod_{k=\lfloor{i\over 2^j}\rfloor2^j}^{i}a_k,B_{i,j}=\sum_{k=i}^{\lceil{i\over 2^j}\rceil2^j-1}a_k$ ，这可以直接 $O(nlog_2n)$ 处理。然后询问区间 $[L,R]$ ，如果 $L=R$ 那么就是 $a_L$ ，否则我们需要找到一个 $k$ 使得 $[L,R]$ 内只存在一个 $2^k$ 的倍数，这样的话就可以直接 $B_{L,k}A_{R,k}$ 得出结果。怎么找呢？上结论！$highbit(L\ xor\ R)$ 就是一个合法的 $k$ ，这很显然。然后还需要卡卡常才能过。#include<cstdio> #include<cctype> #include<algorithm> using namespace std; typedef long long LL; const int maxn=1000000,maxm=312502,Log=20,maxs=1<<Log; int T,n,MOD,te,ans,a[maxn+5],b[maxm+5],A[Log+5][maxn+5],B[Log+5][maxn+5],Lg[maxs]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } #define L(i,k) ((i)>>(k)<<(k)) #define R(i,k) (((i)+(1<<(k))>>(k)<<(k))-1) #define ADD(x,y) (((x)+(y))%MOD) #define MUL(x,y) ((LL)(x)*(y)%MOD) int main(){ freopen("SEGPROD.in","r",stdin);freopen("SEGPROD.out","w",stdout); for (int j=1;j<Log;j++) Lg[1<<j]=j;for (int i=1;i<maxs;i++) if (!Lg[i]) Lg[i]=Lg[i-1]; for (readi(T);T;T--){ readi(n);readi(MOD);readi(te); for (int i=0;i<n;i++) readi(a[i]),A[0][i]=B[0][i]=a[i]; for (int i=0;i<(te>>6)+2;i++) readi(b[i]); for (int j=1;(1<<j)<=n;j++){ A[j][0]=1;for (int i=0;i<=n-1;i++) A[j][i]=(L(i,j)==i?a[i]:MUL(A[j][i-1],a[i])); B[j][n]=1;for (int i=n-1;i>=0;i--) B[j][i]=(R(i,j)==i?a[i]:MUL(B[j][i+1],a[i])); } for (int i=ans=0,L=0,R=0;i<te;i++){ if (!(i&63)) L=b[i>>6],R=b[(i>>6)+1];L=(L+ans)%n;R=(R+ans)%n; if (L>R) swap(L,R);int k=Lg[L^R];ans=ADD((L==R?a[L]:(LL)B[k][L]*A[k][R]),1); }printf("%d\n",ans); }return 0; }Reverse Game怎么网上的题解都说的轻描淡写啊……我感觉这道题的实现技巧还是很巧妙的……由于只有单点操作和列操作，所以我们可以对列建线段树，在线段树上维护连通块个数。怎么维护啊？并查集大法好。每个节点 $[l,r]$ 维护开头( $l$ )列的信息以及结尾( $r$ )列的信息，通过合并左儿子的结尾以及右儿子的开头信息来维护连通块个数。但是很明显我们不能对每列开并查集，而是要用一个全局并查集来维护连通信息。这就出现了一个问题，每次修改之后全局并查集信息都会发生大面积变化，为了方便维护，我们在刚开始维护每列信息的时候，不使用全局并查集，而是直接通过记录编号的方法来标记连通块，这样就可以保证每次修改之前并查集 $father_x=x$ ，因此我们可以直接记录下所有变化过的位置，在每次询问完成之后将这些值初始化。#include<cstdio> #include<vector> #define pb push_back using namespace std; const int maxn=200,maxm=maxn*maxn; int T,n,te,fat[maxm+5];bool a[maxn+5][maxn+5],vis[maxm+5];vector<int> v; int fa[(maxn<<2)+5][2][maxn+5],num[(maxn<<2)+5][2]; #define ID(x,y) (((x)-1)*n+y) inline void Addtag(int x) {if (!vis[x]) v.pb(x),vis[x]=true;} int getfa(int x) {return x==fat[x]?x:(Addtag(x),fat[x]=getfa(fat[x]));} inline void Makefa(int p,int j){ num[p][a[1][j]]=1;num[p][a[1][j]^1]=0;fa[p][0][1]=fa[p][1][1]=ID(1,j); for (int i=2,lst=1;i<=n;i++){ if (a[i][j]!=a[i-1][j]) lst=i,num[p][a[i][j]]++; fa[p][0][i]=fa[p][1][i]=ID(lst,j); } } inline void Pushup(int p,int l,int r){ for (int f=0;f<2;f++) num[p][f]=num[p<<1][f]+num[p<<1|1][f]; for (int i=1;i<=n;i++) if (a[i][l]==a[i][r]){ int x=getfa(fa[p<<1][1][i]),y=getfa(fa[p<<1|1][0][i]);if (x==y) continue; Addtag(x);fat[x]=y;num[p][a[i][l]]--; } for (int i=1;i<=n;i++) fa[p][0][i]=getfa(fa[p<<1][0][i]),fa[p][1][i]=getfa(fa[p<<1|1][1][i]); } void Build(int L,int R,int p=1){ if (L==R) return Makefa(p,L);int mid=L+(R-L>>1); Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p,mid,mid+1); } void Update(int pos,int l=1,int r=n,int p=1){ if (l==r) return Makefa(p,pos);int mid=l+(r-l>>1); pos<=mid?Update(pos,l,mid,p<<1):Update(pos,mid+1,r,p<<1|1);Pushup(p,mid,mid+1); } inline void Clear() {for (int i=0,si=v.size();i<si;i++) fat[v[i]]=v[i],vis[v[i]]=false;v.clear();} int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); for (scanf("%d",&T);T;T--){ scanf("%d",&n);for (int i=1;i<=n;i++) for (int j=1,x;j<=n;j++) scanf("%d",&x),a[i][j]=x; for (int i=1;i<=n*n;i++) fat[i]=i;Build(1,n);Clear(); for (scanf("%d",&te);te;te--){ int tp,x,y;scanf("%d%d",&tp,&x); if (tp==2) scanf("%d",&y),a[x][y]^=1,Update(y); else {for (int i=1;i<=n;i++) a[i][x]^=1;Update(x);} for (int i=1;i<=n;i++) if (a[i][1]==a[i][n]){ int x=getfa(fa[1][0][i]),y=getfa(fa[1][1][i]);if (x==y) continue; Addtag(x);fat[x]=y;num[1][a[i][1]]--; } printf("%d %d\n",num[1][0],num[1][1]);Clear(); } } return 0; }Problem B直接贪心，答案肯定是从最早的黑点 $x$ 开始走，每次找到第一个 $>x+L$ 的黑点跳过去。那么所有黑点构成了一棵树，用LCT维护这棵树就可以快速求答案。但是修改的时候会引发大量信息改动啊？大概和这题差不多，通过建虚点来快速修改就行了：在每个位置建一个灰点，黑点连向 $x+L$ 的灰点，灰点连向最近的黑点或灰点，这样连向每个黑点的就只有一个灰点，修改的点数就是 $O(1)$ 的了。没有找到原题，代码咕咕咕QAQ……Maximum Tree Path题解戳这里⼤ sz 的游戏线段树标记永久化的方法我并没有看……反正可以KDT暴搞……题解戳这里Count on a Treap要利用好Treap的性质，Treap的建立过程可以看作是先按照键值排序，然后选出权值最大的点当做根，之后左右两边递归。也就是说两个点的 $x,y$ 的 $LCA$ 是他们在DFS序中权值最大的点，因此算距离就可以用 $deep_x+deep_y-2deep_{LCA}$ 。根据上面那个结论，$x$ 点的父亲就是离自己最近的权值大于 $w_x$ 的点，我们只需要不停地找父亲就可以得到深度，会发现这就是求两端上升序列长度。因此离线之后用线段树维护一下就行了。#include<cstdio> #include<cctype> #include<algorithm> #include<unordered_map> #define fr first #define sc second #define mp make_pair using namespace std; typedef unsigned int uint; const int maxm=200000,maxn=maxm; int n,m,tp[maxm+5];uint a[maxm+5],b[maxm+5],val[maxn+5],w[maxn+5];unordered_map<uint,int> f; int l[(maxn<<2)+5],r[(maxn<<2)+5],lw[(maxn<<2)+5],rw[(maxn<<2)+5],MAX[(maxn<<2)+5];uint lst; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } int FindL(int p,uint k){ if (l[p]==r[p]) return w[MAX[p k; else if (k>=w[MAX[p<<1|1]]) return FindL(p<<1,k); else return FindL(p<<1|1,k)+lw[p]; } int FindR(int p,uint k){ if (l[p]==r[p]) return w[MAX[p k; else if (k>=w[MAX[p<<1]]) return FindR(p<<1|1,k); else return FindR(p<<1,k)+rw[p]; } inline int Maxer(int x,int y) {return w[x]>w[y]?x:y;} inline void Pushup(int p){ MAX[p]=Maxer(MAX[p<<1],MAX[p<<1|1]); lw[p]=FindL(p<<1,w[MAX[p<<1|1]]); rw[p]=FindR(p<<1|1,w[MAX[p<<1]]); } void Build(int L,int R,int p=1){ l[p]=L;r[p]=R;if (L==R) {MAX[p]=L;return;}int mid=L+(R-L>>1); Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p); } void Update(int pos,int p=1){ if (l[p]==r[p]) return;int mid=l[p]+(r[p]-l[p]>>1); pos<=mid?Update(pos,p<<1):Update(pos,p<<1|1);Pushup(p); } int Askmax(int L,int R,int p=1){ if (L==l[p]&&r[p]==R) return MAX[p];int mid=l[p]+(r[p]-l[p]>>1); if (R<=mid) return Askmax(L,R,p<<1); else if (L>mid) return Askmax(L,R,p<<1|1); else return Maxer(Askmax(L,mid,p<<1),Askmax(mid+1,R,p<<1|1)); } int AskL(int L,int R,int p=1){ if (L==l[p]&&r[p]==R) {int now=FindL(p,lst);lst=max(lst,w[MAX[p]]);return now;} int mid=l[p]+(r[p]-l[p]>>1); if (R<=mid) return AskL(L,R,p<<1); else if (L>mid) return AskL(L,R,p<<1|1); else return AskL(mid+1,R,p<<1|1)+AskL(L,mid,p<<1); } int AskR(int L,int R,int p=1){ if (L==l[p]&&r[p]==R) {int now=FindR(p,lst);lst=max(lst,w[MAX[p]]);return now;} int mid=l[p]+(r[p]-l[p]>>1); if (R<=mid) return AskR(L,R,p<<1); else if (L>mid) return AskR(L,R,p<<1|1); else return AskR(L,mid,p<<1)+AskR(mid+1,R,p<<1|1); } inline int Deep(int x){ int ans=1;lst=w[x];ans+=(x>1?AskL(1,x-1):0); lst=w[x];ans+=(x<n?AskR(x+1,n):0);return ans; } int main(){ freopen("COT5.in","r",stdin);freopen("COT5.out","w",stdout); readi(m);for (int i=1;i<=m;i++){ readi(tp[i]);readi(a[i]);if (tp[i]!=1) readi(b[i]); if (!tp[i]) val[++n]=a[i]; }sort(val+1,val+1+n);for (int i=1;i<=n;i++) f[val[i]]=i;Build(1,n); for (int i=1,pos;i<=m;i++) if (!tp[i]) pos=f[a[i]],w[pos]=b[i],Update(pos); else if (tp[i]==1) pos=f[a[i]],w[pos]=0,Update(pos); else{ int x=f[a[i]],y=f[b[i]],lca;if (x>y) swap(x,y);lca=Askmax(x,y); printf("%d\n",Deep(x)+Deep(y)-(Deep(lca)<<1)); } return 0; }
CodeChef March Challenge 2019 Division 2
像我这种菜鸡只能打Div2QAQ……这里放一下除了Challenge之外的题解。Chef and Number Game最优解只能是正负分两半。#include<cstdio> #include<algorithm> using namespace std; const int maxn=100000; int te,n,A,B; int main(){ freopen("CHNUM.in","r",stdin);freopen("CHNUM.out","w",stdout); for (scanf("%d",&te);te;te--){ scanf("%d",&n);A=B=0;for (int i=1,x;i<=n;i++) scanf("%d",&x),x>0?A++:B++; if (A<B) swap(A,B);B?printf("%d %d\n",A,B):printf("%d %d\n",A,A); }return 0; }Chef and a Beautiful Digit一旦存在一位 $i$ 使得 $a_i>a_{i+1}$ 或者 $a_i>d(i=n)$ ，就肯定会把 $a_i$ 删掉，所以不停地换就行了。#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int maxl=20; int te,D,a[maxl+5];LL n; inline int Find() {for (int i=1;i<=a[0];i++) if (a[i]>a[i+1]) return i;return -1;} int main(){ freopen("CHDIGER.in","r",stdin);freopen("CHDIGER.out","w",stdout); for (scanf("%d",&te);te;te--){ scanf("%lld%d",&n,&D);a[0]=0;do a[++a[0]]=n%10,n/=10; while (n);reverse(a+1,a+1+a[0]);a[a[0]+1]=D; for (int pos=Find();~pos;pos=Find()) {for (int i=pos;i<a[0];i++) a[i]=a[i+1];a[a[0]]=D;} for (int i=1;i<=a[0];i++) putchar(a[i]+48);puts(""); }return 0; }Chef got Recipes直接每次 $O(2^5)$ 维护。#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int maxn=100000,maxs=1<<5; int te,n,ID[256],num[maxs];LL ans; inline char getlow() {char ch=getchar();while (!islower(ch)) ch=getchar();return ch;} int main(){ freopen("JAIN.in","r",stdin);freopen("JAIN.out","w",stdout); ID['a']=0;ID['e']=1;ID['i']=2;ID['o']=3;ID['u']=4; for (scanf("%d",&te);te;te--){ scanf("%d",&n);for (int i=0;i<maxs;i++) num[i]=0;ans=0; for (int i=1;i<=n;i++){ int S=0;for (char ch=getlow();islower(ch);ch=getchar()) S|=1<<ID[ch]; ans+=num[S^maxs-1];for (int s=S;s;s=s-1&S) num[s]++;num[0]++; }printf("%lld\n",ans); }return 0; }Yet Again a Subarray Problem枚举左端点 $L​$ ，然后从左往右推 $R​$ ，按照题意模拟就行了……本来以为这道题会卡常的……就学了一下树状数组求第 $k$ 大，结果线段树随便过……树状数组求第 $k$ 大：从高位到低位检查，假设当前答案为 $ans$ ，那么第 $i$ 位加上去之后会多出 $(ans,ans+2^i]$ 这一块，即 $c[ans+2^i]$ ，检查加上去会不会大于等于 $k$ ，如果大于等于说明不能加这一位。代码超级短，但是不能处理值域很大的情况。#include<cstdio> #include<algorithm> using namespace std; const int maxn=2000,maxa=2000,Log=10; int te,n,m,K,a[maxn+5],MAX,c[maxa+5],ans; inline void Update(int x,int tem) {for (int i=x;i<=MAX;i+=i&-i) c[i]+=tem;} inline int Sum(int x) {int sum=0;for (int i=x;i>0;i-=i&-i) sum+=c[i];return sum;} inline int getkth(int k,int ans=0,int cnt=0){ for (int i=Log;~i;i--) (ans^=1<<i)>MAX||cnt+c[ans]*m>=k?ans^=1<<i:cnt+=c[ans]*m;return ans+1; } int main(){ freopen("SUBPRNJL.in","r",stdin);freopen("SUBPRNJL.out","w",stdout); for (scanf("%d",&te);te;ans=0,te--){ scanf("%d%d",&n,&K);for (int i=1;i<=n;i++) scanf("%d",&a[i]),MAX=max(MAX,a[i]); for (int l=1;l<=n;l++){ for (int i=1;i<=MAX;i++) c[i]=0; for (int r=l;r<=n;r++){ m=(K+r-l)/(r-l+1);Update(a[r],1);int now=getkth(K),cnt=Sum(now)-Sum(now-1); if (cnt<=MAX&&Sum(cnt)-Sum(cnt-1)) ans++; } }printf("%d\n",ans); }return 0; }Cheating on Queue除法分块+卡常题……我们可以处理出每个 $a_i$ 的分段点（值改变的点），然后从后往前处理：刚开始，所有点的分段点都是 $1$ ，随着不断往前，$a_i$ 会从 $a_i$ 变成 $\lfloor{a_i\over 2}\rfloor$（到达了下一个分段点），改变的次数即分段点的个数，总共有 $O(n\sqrt n)$ 个。我们只要在每次改变的时候修改一下贡献就行了。但是会被卡常……所以我们可以预处理 $[1,10^5]$ 所有数的分段点，对于每次询问再预处理一下每个位置贡献改变多少就行了。#include<cstdio> #include<cctype> #include<vector> #define pb push_back using namespace std; typedef long long LL;typedef vector<int>::iterator vit; const int maxn=100000; int te,n,K,a[maxn+5],ans;vector<int> pos[maxn+5],val[maxn+5];LL num[maxn+5],sum; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } int main(){ freopen("CHONQ.in","r",stdin);freopen("CHONQ.out","w",stdout); for (int i=1;i<=maxn;pos[i].pb(i+1),val[i].pb(-1),i++) for (int l=2,lst=i,now;l<=i;l=i/now+1) now=i/l,pos[i].pb(l),val[i].pb(now-lst),lst=now; for (readi(te);te;te--){ readi(n);readi(K);for (int i=1;i<=n;i++) readi(a[i]),num[i]=0;ans=n+1;sum=0; for (int i=1;i<=n;i++) for (vit P=pos[a[i]].begin(),V=val[a[i]].begin();P!=pos[a[i]].end()&&*P<=i;P++,V++) num[i-*P+1]+=*V; for (int i=n;i;i--) if ((sum+=a[i]+num[i])<=K) ans=i;printf("%d\n",ans); }return 0; }Chef and Soccer这题被LTL神仙秒了Orz。由于最多只能走两步，所以只能往回走一下马上走回来，或者一直跳着走，最后走回去。因此我们可以做两次DP，第一次是正着的 $f_{i,0/1}$ 表示走到 $i$ ，$i-1$ 没走过/走过的方案数（记录 $0/1$ 是为了往回走一下以及之后跳回来，由于最多只能走两步所以只需要记录前一个就好了），那么：$$ f_{i,1}=f_{i-1,0}+f_{i-1,1}+[a_{i-2}=2]f_{i-1,0}\\ f_{i,0}=[a_{i-2}=2](f_{i-2,0}+f_{i-2,1}) $$其中 $[a_{i-2}=2]f_{i-1,0}$ 就是从 $i-1$ 往回走到 $i-2$ ，然后走到 $i$ 。接下来要求出 $g_i$ 表示从 $i+1$ 开始往后走，最终走回 $i$ 的方案数（LTL神仙想到的状态Orz），那么 $f_{i+1,0}g_i$ 就对应着从 $1$ 走到 $i+1$ ，然后往后走，最终走回 $i$ 的方案数。$$ g_{i}=[a_{i+1}=2\land a_{i+2}=2]g_{i+2}+[a_{i+2}=2]+1 $$第一个表示从 $i+1$ 走到 $i+3$ ，往后走回到 $i+2$ ，然后从 $i+2$ 回到 $i$ ，第二个表示走到 $i+2$ 后立刻返回 $i$ ，第三个表示直接从 $i+1$ 走到 $i$ 。#include<cstdio> #include<cctype> #include<cstring> using namespace std; typedef long long LL; const int maxn=100000,MOD=1e9+7; int te,n,a[maxn+5],f[maxn+5][2],g[maxn+5],ans; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} int main(){ freopen("CHEFSOC.in","r",stdin);freopen("CHEFSOC.out","w",stdout); for (readi(te);te;te--){ readi(n);memset(a,0,sizeof(a));for (int i=1;i<=n;i++) readi(a[i]);f[1][0]=1; for (int i=2;i<=n;i++){ f[i][0]=f[i][1]=0;AMOD(f[i][1],f[i-1][0]);AMOD(f[i][1],f[i-1][1]); if (a[i-2]==2) AMOD(f[i][0],f[i-2][0]),AMOD(f[i][0],f[i-2][1]),AMOD(f[i][1],f[i-1][0]); }g[n]=0;AMOD(ans=f[n][0],f[n][1]); for (int i=n-1;i;i--){ AMOD(ans,f[i][0]);AMOD(ans,f[i][1]);g[i]=1; if (a[i+1]==2&&a[i+2]==2) AMOD(g[i],g[i+2]);if (a[i+2]==2) AMOD(g[i],1); AMOD(ans,(LL)f[i+1][0]*g[i]%MOD); }printf("%d\n",ans); } return 0; }Perfect Tree Problem鬼畜题……显然有贪心，就是把深度从小到大排序之后依次代入公式，这样肯定是最大的。然后是法老发现了PTREE的性质：随着深度递增，节点数也递增。所以把每个深度的节点个数按顺序拿出来，是一个不降序列，且节点个数相同的深度是连续的。假设深度在 $[L,R]$ 内的节点个数都是 $S$ ，那么我们要计算的式子是（设 $pre$ 表示深度在 $L$ 之前的节点总个数）：$$ V=\sum_{i=0}^{R-L}(L+i)\sum_{j=0}^{S-1}x^{pre+iS+j}\\ =\sum_{i=0}^{R-L}(L+i){x^{pre+iS}(x^{S}-1)\over x-1}\\ ={(x^{S}-1)\over x-1}\sum_{i=0}^{R-L}(L+i)x^{pre+iS}\\ $$后面那个是一个等差数列乘上一个等比数列，可以利用错位相减求出前缀和：$$ S_n=\sum_{i=0}^{n}(L+i)x^{pre+iS}\\ x^SS_n=\sum_{i=0}^{n}(L+i)x^{pre+(i+1)S}=\sum_{i=1}^{n+1}(L+i-1)x^{pre+iS}\\ S_n-x^SS_n=(L-1)x^{pre}-(L+n)x^{pre+(n+1)S}+\sum_{i=0}^{n}x^{pre+iS}\\ S_n={(L-1)x^{pre}-(L+n)x^{pre+(n+1)S}+{x^{pre}(x^{(n+1)S}-1)\over 1-x^S}\over 1-x^S}\\ V={(L-1)x^{pre}-(L+n)x^{pre+(n+1)S}+{x^{pre}(x^{(n+1)S}-1)\over 1-x^S}\over 1-x} $$这样就可以做到 $O(log_210^9)$ 求出一个块内的值。但是块数有多少呢？由于我们把相同的放在一起做，所以块数只有 $O(\sqrt n)$ ，如果能快速求出每个点的块，我们就可以做到 $O(q\sqrt nlog_210^9)$ 的复杂度。其实块并不难求，直接暴力就行了！我们每次从重儿子继承块，然后暴力将轻儿子的信息合并进来就行了，复杂度 $O(nlog_2n+n\sqrt n)$ 。但是……由于有 $O(log_210^9)$ 的存在……这样做就光荣的TLE了……因此我们需要快速求快速幂以及快速求逆元：快速求快速幂：和BSGS一样，将 $x^m$ 分成 $x^{iS+j}$ ，其中 $S=\sqrt{si_v}$ 。快速求逆元：参考这篇Blog。套上这两个东西，然后疯狂卡常（卡常By X_o_r），你就可以过了……下面有两份代码，第一份比较可读（不能过，没有快速求逆元），第二份是卡常的产物（能过）：#include<cstdio> #include<cctype> #include<vector> #include<algorithm> #define pb push_back using namespace std; typedef long long LL; const int maxn=200000,maxt=4e7,MOD=1e9+7; int T,n,te,si[maxn+5],dep[maxn+5],MAX[maxn+5],SH[maxn+5],INV,ans; int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5]; int len,ro[maxn+5],ls[maxt+5],rs[maxt+5],sum[maxt+5],MIN[maxt+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void writei(int x){ static int buf[100],len=0;do buf[len++]=x%10,x/=10; while (x); while (len) putchar(buf[--len]+48);puts(""); } #define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E) void MakeSH(int x,int pre=0){ for (int j=(si[x]=1,MAX[x]=dep[x]=dep[pre]+1,SH[x]=0,lnk[x]),u;j;j=nxt[j]) if ((u=son[j])!=pre) MakeSH(u,x),MAX[x]=MAX[u],si[x]+=si[u],si[u]>si[SH[x]]?SH[x]=u:0; } #define Pushup(p) (MIN[p]=min(MIN[ls[p]],MIN[rs[p]])) int Insert(int p,int pos,int l=1,int r=n){ int now=++len;ls[now]=ls[p];rs[now]=rs[p];sum[now]=sum[p]+1;if (l==r) return MIN[now]=sum[now],now;int mid=l+(r-l>>1); if (pos<=mid) ls[now]=Insert(ls[p],pos,l,mid); else rs[now]=Insert(rs[p],pos,mid+1,r);Pushup(now);return now; } void Join(int x,int pre,int fa){ ro[fa]=Insert(ro[fa],dep[x]); for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Join(son[j],x,fa); } void Dfs(int x,int pre=0){ for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x);ro[x]=Insert(ro[SH[x]],dep[x]); for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre&&son[j]!=SH[x]) Join(son[j],x,x); } int getnum(int p,int pos,int l=1,int r=n){ if (!p) return 0;if (l==r) return sum[p];int mid=l+(r-l>>1); return pos<=mid?getnum(ls[p],pos,l,mid):getnum(rs[p],pos,mid+1,r); } int FindR(int p,int k,int l=1,int r=n){ if (l==r) return l;int mid=l+(r-l>>1); return MIN[rs[p k?FindR(ls[p],k,l,mid):FindR(rs[p],k,mid+1,r); } inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;} inline int Count(int L,int R,int x,int num,int pre){ if (x==1) return ((LL)(L+R)*(R-L+1)>>1)*num%MOD; int q=Pow(x,num),A=Pow(x,pre),B=Pow(q,R-L+1),ans=0;ans=(LL)A*(B-1)%MOD*Pow(q-1,MOD-2)%MOD; AMOD(ans,(LL)A*(MOD+L-1)%MOD);AMOD(ans,MOD-(LL)A*B%MOD*R%MOD);return (LL)ans*INV%MOD; } inline int Ask(int x,int y,int ans=0){ INV=Pow((MOD+1-y)%MOD,MOD-2); for (int L=dep[x],R,pre=0;L<=MAX[x];L=R+1){ int num=getnum(ro[x],L);R=FindR(ro[x],num); AMOD(ans,Count(L-dep[x],R-dep[x],y,num,pre));pre+=num*(R-L+1); }return ans; } int main(){ freopen("PTREE.in","r",stdin);freopen("PTREE.out","w",stdout); for (MIN[0]=2e9,readi(T);T;T--){ readi(n);readi(te);E=0;for (int i=1;i<=n;i++) lnk[i]=0; for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x); len=0;for (int i=1;i<=n;i++) ro[i]=0;MakeSH(1);Dfs(1);ans=0; for (int x,y;te;te--) readi(x),readi(y),x^=ans,y^=ans,writei(ans=Ask(x,y)); }return 0; }卡常的产物（畸形）：#include<cmath> #include<cstdio> #include<cctype> #include<vector> #include<algorithm> #define pb push_back using namespace std; typedef long long LL; const int maxn=200000,MOD=1e9+7,maxs=700; int T,n,te,si[maxn+5],dep[maxn+5],MAX[maxn+5],SH[maxn+5],ans; int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5]; vector<int> que[maxn+5],pos[maxn+5],cnt[maxn+5]; bool vis[maxs+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void writei(int x){ static int buf[100],len=0;do buf[len++]=x%10,x/=10; while (x); while (len) putchar(buf[--len]+48);puts(""); } #define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E) void MakeSH(int x,int pre=0){ for (int j=(si[x]=1,MAX[x]=dep[x]=dep[pre]+1,SH[x]=0,lnk[x]),u;j;j=nxt[j]) if ((u=son[j])!=pre) MakeSH(u,x),MAX[x]=MAX[u],si[x]+=si[u],si[u]>si[SH[x]]?SH[x]=u:0; } void Dfs(int x,int pre=0){ for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Dfs(son[j],x); swap(que[x],que[SH[x]]);que[x].pb(1);int s=que[x].size()-1; if (SH[x]&&si[x]==si[SH[x]]+1){ pos[x]=pos[SH[x]];cnt[x]=cnt[SH[x]]; if (que[x][s-1]>1) pos[x].pb(s),cnt[x].pb(1);return; } for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre&&son[j]!=SH[x]) for (int k=0;k<s;k++) que[x][k]+=que[son[j]][k]; for (int i=(pos[x].pb(0),cnt[x].pb(que[x][0]),0);i<s;i++) if (que[x][i]!=que[x][i+1]) pos[x].pb(i+1),cnt[x].pb(que[x][i+1]); } inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;} #define PowX(num) ((LL)RP[(num)/S]*LP[(num)%S]%MOD) inline LL mod(LL x){return (x%=MOD)<0?x+MOD:x;} inline int Ask(int x,int y){ register int s[maxs+5],sv[maxs+5],INV[maxs+5],ans=0,inv=Pow((MOD+1-y)%MOD,MOD-2),S,LP[maxs+5],RP[maxs+5],top=0,len[maxs+5],l[maxs+5],r[maxs+5],Q[maxs+5];; s[0]=1,S=ceil(sqrt(si[x])),*LP=*RP=1; for (register int i=1;i<=S;i++) LP[i]=(LL)LP[i-1]*y%MOD; for (register int i=1;i<=S;i++) RP[i]=(LL)RP[i-1]*LP[S]%MOD; for (register int i=0,ss=pos[x].size(),L=0,R,mul=1;i<ss;L=R+1,++i) R=MAX[x]-dep[x]-pos[x][i],len[++top]=cnt[x][i],l[top]=L,r[top]=R, (Q[top]=PowX(len[top])-1)?vis[top]=true:(vis[top]=false,Q[top]=1),s[top]=(LL)s[top-1]*Q[top]%MOD; sv[top]=Pow(s[top],MOD-2),INV[top]=(LL)sv[top]*s[top-1]%MOD; for (int i=top-1;i;i--) INV[i]=(LL)(sv[i]=(LL)sv[i+1]*Q[i+1]%MOD)*s[i-1]%MOD; for (register int i=1,pre=0,L,R,num,A,now,B;i<=top;pre+=num*(R-L+1),i++) L=l[i],R=r[i],num=len[i],y==1?AMOD(ans,((LL)(L+R)*(R-L+1)>>1)*num%MOD),0:A=(LL)PowX(pre)*inv%MOD,now=num*(R-L+1),B=PowX(now),AMOD(ans,mod(L-(LL)B*R-1+(vis[i]?(LL)(B-1)*INV[i]:R-L+1))*A%MOD); return ans; } int main(){ freopen("PTREE.in","r",stdin);freopen("PTREE.out","w",stdout); for (readi(T);T--;){ readi(n),readi(te),E=0;for (int i=1;i<=n;i++) lnk[i]=0,que[i].clear(),pos[i].clear(),cnt[i].clear(); for (register int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);MakeSH(1),Dfs(1); for (register int i=1;i<=n;++i) reverse(pos[i].begin(),pos[i].end()),reverse(cnt[i].begin(),cnt[i].end()); ans=0;for (register int x,y;te;te--) readi(x),readi(y),x^=ans,y^=ans,writei(ans=Ask(x,y)); }return 0; }
题目概述有 $n$ 个数 $a_i$ ，求每个数的逆元。解题报告$O(n)$ 求 $n$ 个数逆元？？？Orz WA自动机，感觉这个技巧非常有用，帮助我解决了CC的某道毒瘤题（CC比赛还没结束，就先鸽了）。示例程序#include<cstdio> #include<cctype> using namespace std; typedef long long LL; const int maxn=5000000,MOD=1e9+7,PW=998244353; int n,a[maxn+5],s[maxn+5],sv[maxn+5],INV[maxn+5],ans; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;} inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(n);s[0]=1;for (int i=1;i<=n;i++) readi(a[i]),s[i]=(LL)s[i-1]*a[i]%MOD; sv[n]=Pow(s[n],MOD-2);for (int i=n-1;i;i--) sv[i]=(LL)sv[i+1]*a[i+1]%MOD; for (int i=1;i<=n;i++) INV[i]=(LL)sv[i]*s[i-1]%MOD; for (int i=n,pw=1;i;i--,pw=(LL)pw*PW%MOD) AMOD(ans,(LL)INV[i]*pw%MOD);printf("%d\n",ans);return 0; }
[FWT+快速乘]Codeforces453D【Little Pony and Elements of Harmony】题解
题目概述$a_{t}[i]=\sum_{j}a_{t-1}[j]b[count(i\ xor\ j)]$ ，其中 $count(i)$ 表示 $i$ 二进制下 $1$ 的个数。给出 $a_0,b$ ，求 $a_t$ 。解题报告令 $c[i]=b[count(i)]$ ，那么 $a_{t}=a_{t-1}*c$ （ $*$ 表示异或卷积），FWT裸题？但是模数可能是偶数？WTF？我们可以先将模数扩大 $n$ 倍，然后就可以在FWT的最后直接除以 $n$（考虑到模其实是减法，所以肯定有 $n​$ 这个因子）。但是这样会爆long long，所以要快速（慢速）乘。示例程序#include<cstdio> #include<cctype> using namespace std; typedef long long LL;typedef long double DB; const int maxm=20,maxn=1<<20; int n;LL t,MOD,a[maxn+5],b[maxm+5],c[maxn+5],cnt[maxn+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void AMOD(LL &x,LL tem) {if ((x+=tem)>=MOD) x-=MOD;} inline LL Mul(LL x,LL y) {return (x*y+MOD-(LL)((DB)x/MOD*y)*MOD)%MOD;} inline LL Pow(LL w,LL b) {LL s;for (s=1;b;w=Mul(w,w),b>>=1) if (b&1) s=Mul(s,w);return s;} inline void FWT(LL *a,int n,int f){ for (int k=1;k<n;k<<=1) for (int i=0;i<n;i+=k<<1) for (int j=0;j<k;j++) {LL x=a[i+j],y=a[i+j+k];AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);} if (f<0) for (int i=0;i<=n;i++) a[i]/=n; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); readi(n);readi(t);readi(MOD);MOD*=(1<<n); for (int i=0;i<(1<<n);i++) readi(a[i]),a[i]%=MOD;for (int i=0;i<=n;i++) readi(b[i]),b[i]%=MOD; n=1<<n;for (int i=0;i<n;i++) c[i]=b[cnt[i]=cnt[i>>1]+(i&1)];FWT(a,n,1);FWT(c,n,1); for (int i=0;i<n;i++) a[i]=Mul(a[i],Pow(c[i],t));FWT(a,n,-1); for (int i=0;i<n;i++) printf("%lld\n",a[i]);return 0; }
[离线+后缀数组+STL乱搞]LOJ6041(雅礼集训 2017 Day7)【事情的相似度】题解
题目概述有长度为 $n$ 的 $01$ 串 $s$ 和 $m$ 个询问，每次询问 $[L,R]$ 表示 $s$ 的 $[L,R]$ 这些前缀之间的最大公共后缀。解题报告SAM+LCT什么的好大啊，所以我们来乱搞吧QAQ。把串倒过来，那么就是求后缀的最长公共前缀，这是后缀数组Height数组经典问题，如果询问 $[L,R]$ 满足 $x\in\{rank_i|L\le i\le R\}$ 且 $x-1\in\{rank_i|L\le i\le R\}$ 那么 $Height_x$ 就可以修正这个询问。因此把询问离线之后，通过合并Height数组（大的Height可以合并到相邻的小的Height），我们就可以得到一个 $O(nm)$ 算法。考虑从大到小枚举Height数组，这样我们就可以做到每个询问只修正一次，但是对于 $x$ 要怎么快速找到合法的询问？吃我bitset啦！我们先处理出 $S_i$ 表示符合 $i$ 的询问集合（差分），然后每次通过bitset的&操作就可以快速得到满足条件且还没有被修正过的询问集合，这样复杂度就变成了 $O({nm\over\omega})$ 。还有个黑科技，由于 $m=10^5$ 的时候会MLE，所以我们……做两次 $m=5\cdot10^4$ QAQ！示例程序#include<cstdio> #include<bitset> #include<algorithm> using namespace std; typedef unsigned long long ULL; const int maxn=100000,maxm=50000,maxt=784; int n,Q,SA[maxn+5],rk[maxn+5],t[(maxn<<1)+5],ha[maxn+5],h[maxn+5]; char s[maxn+5];int ID[maxn+5],Lg[23333],ans[maxm+5],fat[maxn+5]; #define pw(i) ((ULL)1<<(i)) struct Bitset{ ULL s[maxt];inline void Clear() {for (int i=0;i<maxt;i++) s[i]=0;} inline void Set(int i) {s[i/64]|=pw(i%64);} inline void Unset(int i) {Set(i);s[i/64]^=pw(i%64);} inline void operator &= (const Bitset &a){ for (int i=0;i<maxt;i+=4) s[i]&=a.s[i],s[i+1]&=a.s[i+1],s[i+2]&=a.s[i+2],s[i+3]&=a.s[i+3]; } inline void operator |= (const Bitset &a){ for (int i=0;i<maxt;i+=4) s[i]|=a.s[i],s[i+1]|=a.s[i+1],s[i+2]|=a.s[i+2],s[i+3]|=a.s[i+3]; } inline void operator ^= (const Bitset &a){ for (int i=0;i<maxt;i+=4) s[i]^=a.s[i],s[i+1]^=a.s[i+1],s[i+2]^=a.s[i+2],s[i+3]^=a.s[i+3]; } inline int Next(int x){ int A=x/64,B=x%64;ULL now;if (B<63&&(now=s[A]&~(pw(B+1)-1))) return A*64+Lg[(now&-now)%23333]; for (int i=A+1;i<maxt;i++) if (s[i]) return i*64+Lg[(s[i]&-s[i])%23333];return 2e9; } }q[maxn+5]; inline void Sort(int n,int m){ for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++; for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i]; } inline void Make(char *s,int n){ int m=255;for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i;Sort(n,m); for (int p=0,k=1;p<n;k<<=1,m=p){ p=0;for (int i=n-k+1;i<=n;i++) t[++p]=i;for (int i=1;i<=n;i++) if (SA[i]>k) t[++p]=SA[i]-k; Sort(n,m);for (int i=1;i<=n;i++) t[i]=rk[i];rk[SA[1]]=p=1; for (int i=2;i<=n;rk[SA[i++]]=p) p+=t[SA[i-1]]<t[SA[i]]||t[SA[i-1]+k]<t[SA[i]+k]; }for (int i=1,k=0;i<=n;h[rk[i++]]=k) {int j=SA[rk[i]-1];if (k) k--;while (s[i+k]==s[j+k]) k++;} for (int i=0;i<64;i++) Lg[pw(i)%23333]=i; } inline bool cmp(const int &a,const int &b) {return h[a]>h[b];} int getfa(int x) {return x==fat[x]?x:fat[x]=getfa(fat[x]);} #include<cstdlib> inline void Solve(int Q){ Bitset now,vis;vis.Clear();for (int i=1;i<=n;i++) q[i].Clear(); for (int i=1;i<=Q;i++){ int l,r,L,R;scanf("%d%d",&l,&r);L=n-r+1;R=n-l+1; q[rk[L]].Set(i);if (R<n) q[rk[R+1]].Set(i);vis.Set(i); }for (int i=1;i<=n;i++) q[rk[i]]^=q[rk[i-1]],fat[i]=i; for (int i=1;i<n;i++){ int x=getfa(ID[i]),y=getfa(ID[i]-1);now=q[x];now&=q[y];now&=vis;q[y]|=q[x];fat[x]=y; for (int j=now.Next(0);j<=Q;j=now.Next(j)) vis.Unset(j),ans[j]=h[ID[i]]; }for (int i=1;i<=Q;i++) printf("%d\n",ans[i]); } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d",&n,&Q);scanf("%s",s+1);for (int i=1;i<=(n>>1);i++) swap(s[i],s[n-i+1]);Make(s,n); for (int i=1;i<n;i++) ID[i]=i+1;sort(ID+1,ID+n,cmp);Solve(Q>>1);Solve(Q-(Q>>1));return 0; }
题目概述有一棵树，刚开始你在 $X​$ ，每次随机走到相邻的点。有 $q​$ 个询问，每次询问给出一些点，求把这些点至少经过一次的期望时间。解题报告不难想到Min-Max容斥，令 $min(S)$ 表示第一次走到 $S$ 集合中的点的期望时间。然后我可能是智障，我刚开始认为 $min(S)=min\{f(i)|i\in S\}$ ，其中 $f(i)$ 表示 $X$ 第一次走到 $i$ 的期望时间（用高斯消元求解），这显然是错的，因为走到 $i$ 的途中可能就已经经过其他在 $S$ 中的点导致违法。那么正确的定义应该加上一维：$f(i,S)$ 表示从 $i$ 出发第一次到达 $S$ 这个集合中的点的期望时间，则可以列出 $n$ 个方程来求解：$$ f(i,S)=\begin{cases}{1\over d_i}\sum_{(i,j)\in E}f(j,S)+1&i\not\in S\\0&i\in S\end{cases} $$这样是 $O(2^nn^3)$ 的，法老表示可以用奇技淫巧搞过去……我没有深入探究过……反正朴素消元是TLE的……接下来上套路：在树上的高斯消元可以变成 $f(x)=a_xf(fa_x)+b_x$ 的形式，这是怎么想到的呢？考虑在树上的方程：$$ f(x,S)=\begin{cases}{1\over d_x}(\sum f(son,S)+f(fa_x,S))+1&x\not\in S,\text{x is not leaf}\\{1\over d_x}f(fa_x,S)+1&x\not\in S,\text{x is leaf}\\0&x\in S\end{cases} $$从叶子往上代入，移项之后发现每次就只剩了父亲节点，并没有儿子节点，于是可以写成 $f(x)=a_xf(fa_x)+b_x$ 。所以对于 $f(x,S)$ ：$$ f(x,S)={1\over d_x}f(fa_x,S)+{1\over d_x}f(x,S)\sum a_{son}+{1\over d_x}\sum b_{son}+1\\ f(x,S)={1\over d_x(1-{1\over d_x}\sum a_{son})}f(fa_x,S)+{1\over d_x(1-{1\over d_x}\sum a_{son})}\sum b_{son}+{1\over1-{1\over d_x}\sum a_{son}} $$由于 $f(X,S)$ 并没有父亲所以 $min(S)=f(X,S)=b_X$ ，就可以求出 $max(S)$ 了。示例程序#include<cstdio> #include<algorithm> using namespace std; typedef long long LL;typedef long double DB; const int maxn=18,maxs=1<<maxn,MOD=998244353; int n,te,st,d[maxn+5],f[maxn+5],g[maxn+5],ans[maxs],cnt[maxs]; int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5]; #define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E) inline int Inv(int x) {int INV=1;while (x>1) INV=(LL)INV*(MOD-MOD/x)%MOD,x=MOD%x;return INV;} inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;} inline void Solve(int s,int x,int pre=0,int A=0,int B=0){ for (int j=lnk[x];j;j=nxt[j]) if (son[j]!=pre) Solve(s,son[j],x),AMOD(A,g[son[j]]),AMOD(B,f[son[j]]); if (s>>x-1&1) f[x]=g[x]=0; else{ int INV=Inv(d[x]);A=Inv((MOD+1-(LL)A*INV%MOD)%MOD);B=(LL)B*INV%MOD;AMOD(B,1); g[x]=(LL)INV*A%MOD;f[x]=(LL)B*A%MOD; } } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d%d%d",&n,&te,&st); for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x),d[x]++,d[y]++; for (int s=1;s<(1<<n);s++) Solve(s,st),cnt[s]=cnt[s>>1]+(s&1),ans[s]=(cnt[s]&1?f[st]:MOD-f[st])%MOD; for (int i=0;i<n;i++) for (int s=1<<i;s<(1<<n);s=(s+1)|(1<<i)) AMOD(ans[s],ans[s^(1<<i)]); while (te--){ int K,s=0;scanf("%d",&K);for (int i=1,x;i<=K;i++) scanf("%d",&x),s|=1<<x-1; printf("%d\n",ans[s]); }return 0; }
[线性筛+启发式分裂]NWERC2017F【Factor-Free Tree】题解
题目概述如果一棵二叉树儿子和祖先权值均互质则是一棵FFT（手动滑稽），现在给出一棵树权值的中序遍历，问是否有一种方案使得该树为FFT。解题报告首先有结论：如果 $[L,R]$ 可以变成FFT，那么随便选一个合法的作为根都是可以的，画画中序遍历发现挺显然的……问题是怎么求出每个点是否与 $[L,R]$ 中其他点均互质，套路：$i$ 质因数分解之后每个因子最近出现的位置中最近的位置就是 $i$ 能到达的最远位置。至于质因数分解可以用线性筛筛出最小素因子。但是就算这样，每次也不可能暴力找一个合法的根？你错了……就是可以暴力找，只要从两端一起开始找就可以，为什么呢？由于是从两端开始找，所以近的一段会先遇到合法的根，次数是合法的根到端点的距离，这可以看作小的块往大的块合并，是启发式合并的逆过程（启发式分裂？），所以复杂度是正常的。示例程序#include<cstdio> #include<cctype> #include<algorithm> using namespace std; const int maxn=1000000,maxa=10000000,maxp=664579; int n,a[maxn+5],pre[maxn+5],nxt[maxn+5],pos[maxp+5],fa[maxn+5]; int D[maxa+5],p[maxp+5];bool pri[maxa+5]; #define Eoln(x) ((x)==10||(x)==13||(x)==EOF) inline char readc(){ static char buf[100000],*l=buf,*r=buf; return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r))?EOF:*l++; } template<typename T> inline int readi(T &x){ T tot=0;char ch=readc(),lst='+'; while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();} while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc(); return lst=='-'?x=-tot:x=tot,Eoln(ch); } inline void Make(){ for (int i=2;i<=maxa;i++){ if (!pri[i]) p[++p[0]]=i,D[i]=p[0]; for (int j=1,t;j<=p[0]&&(t=i*p[j])<=maxa;j++) {D[t]=D[i];pri[t]=true;if (!(i%p[j])) break;} } } bool Dfs(int L,int R,int p=0){ if (L>R) return true; for (int l=L,r=R;l<=r;l++,r--){ if (R<=nxt[l]&&pre[l]<=L) return fa[l]=p,Dfs(L,l-1,l)&&Dfs(l+1,R,l); if (R<=nxt[r]&&pre[r]<=L) return fa[r]=p,Dfs(L,r-1,r)&&Dfs(r+1,R,r); }return false; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); Make();readi(n);for (int i=1;i<=n;i++) readi(a[i]); for (int i=1;i<=p[0];i++) pos[i]=-1; for (int i=1;i<=n;i++){ pre[i]=1;for (int x=a[i];x>1;x/=p[D[x]]) pre[i]=max(pre[i],pos[D[x]]+1); for (int x=a[i];x>1;x/=p[D[x]]) pos[D[x]]=i; } for (int i=1;i<=p[0];i++) pos[i]=n+1; for (int i=n;i;i--){ nxt[i]=n;for (int x=a[i];x>1;x/=p[D[x]]) nxt[i]=min(nxt[i],pos[D[x]]-1); for (int x=a[i];x>1;x/=p[D[x]]) pos[D[x]]=i; } if (Dfs(1,n)) {for (int i=1,fst=true;i<=n;i++) fst?fst=false:putchar(' '),printf("%d",fa[i]);} else puts("impossible");return 0; }
题目概述求一个半径最小的圆使得和 $x$ 轴相切，并且包含了所有给定的点。解题报告很明显可以二分 $r$ ，那么圆心就是 $(x,r)$ ，通过每个点就可以确定 $x$ 的范围，如果 $x$ 有取值那么就验证成功。因为精度要求 $6$ 位，并且 $r$ 的范围有 $10^{15}$ ，long double精度也不够导致二分停不下来，所以要用奇技淫巧，比如__float128 或者做个 $100$ 次就停止。亲测都可过……示例程序#include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long double DB; const int maxn=100000; int n,x[maxn+5],y[maxn+5]; inline int fcmp(const DB &a,const DB &b) {if (fabs(a-b)<1e-10) return 0;return a<b?-1:1;} inline bool check(DB r,DB A=-9e18,DB B=9e18){ for (int i=1;i<=n;i++){ if (fcmp(r*2*y[i]-(DB)y[i]*y[i],0)<0) return false; A=max(A,-sqrt(r*2*y[i]-(DB)y[i]*y[i])+x[i]);B=min(B,sqrt(r*2*y[i]-(DB)y[i]*y[i])+x[i]); }return fcmp(A,B)<=0; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); scanf("%d",&n);bool A=true,B=true; for (int i=1;i<=n;i++) {scanf("%d%d",&x[i],&y[i]);if (y[i]<0) A=false;if (y[i]>0) B=false;} if (!A&&!B) return puts("-1"),0;if (B) for (int i=1;i<=n;i++) y[i]=-y[i]; DB L=0,R=1e15,mid;for (int t=1;t<=100;t++) check(mid=(L+R)/2)?R=mid:L=mid; if (!fcmp(R,1e15)) return puts("-1"),0;printf("%.7f\n",(double)R);return 0; }