给定两棵 \(n\) 个点的树,求一个编号最大的点满足他在第一棵树上的点是第一棵树上的点 \(u\) 的祖先和在第二棵树上的点是第二棵树上的点 \(v\) 的祖先。多组询问 \(u,v\) 。
在第一棵树上看第二棵树,第二棵树上的祖先关系可以理解为 dfs 序子树形成区间的嵌套关系。因此在第一棵树上维护每个节点到根节点中每个节点在第二棵树上子树形成区间的并集。但是要求编号最大的,直接把并集换成编号最大值。没有就是 0 。
复杂度 \(\mathcal O(n\log n)\)
我当时没意识到换成最大值,写了个倍增。
#include <cstdio> #include <iostream> #include <vector> #define macro_expand(x) #x #define print_macro(x) printf("%s\n",macro_expand(x)) #define FOR(i,l,r) for(int i=(l),i##ADJK=(r);i<=i##ADJK;++i) #define ROF(i,r,l) for(int i=(r),i##ADJK=(l);i>=i##ADJK;--i) using namespace std; typedef long long LL; const int MN=1e5+5; int N,fa[MN][17]; vector<int> T[MN]; int in[MN],out[MN],dfstime; void dfs(int u){ in[u]=++dfstime; for(auto v:T[u])dfs(v); out[u]=dfstime; } const int MT=MN*4*17; int rt[MN],tag[MT],ls[MT],rs[MT],tot_node; void add(int pre,int &o,int l,int r,int ql,int qr,int v){ if(l>qr||r<ql)return; o=++tot_node,ls[o]=ls[pre],rs[o]=rs[pre],tag[o]=tag[pre]; if(ql<=l&&r<=qr)return tag[o]+=v,void(); int mid=(l+r)>>1; add(ls[pre],ls[o],l,mid,ql,qr,v); add(rs[pre],rs[o],mid+1,r,ql,qr,v); } int query(int o,int l,int r,int p){ if(!o)return 0; if(l==r)return tag[o]; int mid=(l+r)>>1; return ((p<=mid)?query(ls[o],l,mid,p):query(rs[o],mid+1,r,p))+tag[o]; } int f2[MN]; int Q; void print(int o,int l,int r){ if(!o)return; cerr<<"o:"<<o<<" l:"<<l<<" r:"<<r<<" tag[o]:"<<tag[o]<<endl; int mid=(l+r)>>1; print(ls[o],l,mid); print(rs[o],mid+1,r); } int main(){ freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); scanf("%d%d",&N,&Q); FOR(i,2,N)scanf("%d",&fa[i][0]); FOR(i,1,16)FOR(j,1,N)fa[j][i]=fa[fa[j][i-1]][i-1]; FOR(i,2,N)scanf("%d",&f2[i]),T[f2[i]].push_back(i); dfs(1); add(0,rt[1],1,N,in[1],out[1],1); FOR(i,2,N)add(rt[fa[i][0]],rt[i],1,N,in[i],out[i],1); int lastans=0; while(Q--){ int x=0,y=0;scanf("%d%d",&x,&y); x=(x+lastans)%N+1,y=(y+lastans)%N+1; ROF(i,16,0)if(fa[x][i]&&query(rt[x],1,N,in[y])-query(rt[fa[x][i]],1,N,in[y])==0){ x=fa[x][i]; } printf("%d\n",lastans=x); } fclose(stdin); fclose(stdout); return 0; }
给定一个由数字组成的序列,求一个最小的 \(n\) 满足 \(n,n+1,\cdots,n+k-1\) 每个数取出一个数字恰好就是这个数字序列。这个数字序列有 \(k\) 项。
\(n\le 10^5\)
这是一个进位相关的问题。进位相关的问题我还是会觉得很抽象,虽然本身其实一点也不抽象,但是在开始仔细思考之前就是很抽象。
考虑 \(+k\) 的影响主要影响还是后 5 位。这样的话就枚举 \(n\) 的后 5 位。
剩下的影响就是后 5 位向前的进位了。进位只有 0 和 1 两种情况。
而对于除了后 5 位,前面的那些位其实后面连续的 9 并不起作用。因为进一位其实几乎就可以达到出现更多没有出现过的数字的效果了。
分类讨论就可以处理掉进位。
但是这样的需要的操作是枚举后 5 位,然后枚举进位,再判断一遍,复杂度 \(\mathcal O(n^2)\) ,寄了。
下面考虑一种递归的做法,实质是将上面枚举的若干个数的公共部分给优化掉了。
考虑枚举 \(n\) 模 10 的余数。每次看余数能够解决多大一部分问题,剩下的数留着,到上一位再解决。
具体来说,每一个数用一个二进制数来记录当前时刻它必须有哪些位。
每次向上递归就可以了。
有一个细节是如果递归到最后,\(k=2\) 了再递归有可能还是 \(k=2\) (因为可能末尾是 9 )。不过容易发现,可以发现连续两次向上进位是不优的,当成一个数就必须满足条件就可以了。
#include <cstdio> #include <iostream> #define macro_expand(x) #x #define print_macro(x) printf("%s\n",macro_expand(x)) #define FOR(i,l,r) for(LL i=(l),i##ADJK=(r);i<=i##ADJK;++i) #define ROF(i,r,l) for(LL i=(r),i##ADJK=(l);i>=i##ADJK;--i) using namespace std; typedef long long LL; template<typename T>bool chkmax(T &x,const T y){return (x<y)?(x=y,1):0;} template<typename T>bool chkmin(T &x,const T y){return (x>y)?(x=y,1):0;} const LL MN=1e5+5; int K,B[MN],state[9][MN],len[9]; int moth; LL dfs(int level,bool tag){ if(len[level]==1||tag){ if(tag)state[level][1]|=state[level][2]; LL tmp=state[level][1]; int minv=0; bool fu=tmp&1; FOR(i,1,9)if((tmp>>i)&1){minv=i;break;} if(minv==0){ if(fu==0)return 0ll; else return 10ll; }else{ int now=minv; if(fu)now=now*10; FOR(i,minv+1,9)if((tmp>>i)&1)now=now*10+i; // 这从minv+1开始 return now; } } LL ret=1e18; FOR(i,0,9){ int &L=len[level+1]; L=1;state[level+1][L]=0; FOR(j,1,len[level]){ state[level+1][L]|=state[level][j]-(state[level][j]&(1<<((i+j-1)%10))); if((i+j-1)%10==9&&j!=len[level])++L,state[level+1][L]=0; } LL tmp=dfs(level+1,(i==9)&&len[level]==2&&len[level+1]==2); chkmin(ret,tmp*10+i); } return ret; } int main(){ freopen("note.in","r",stdin); freopen("note.out","w",stdout); scanf("%d",&K); FOR(i,1,K){ scanf("%d",&B[i]); state[0][i]=(1<<B[i]); } len[0]=K; printf("%lld\n",dfs(0,0)); fclose(stdin); fclose(stdout); return 0; }
求数列 A202061 的第 \(n\) 项。\(n\le 50\)。
从前向后 dp,限制有几个:
#include <cstdio> #include <iostream> #include <unordered_map> #define macro_expand(x) #x #define print_macro(x) printf("%s\n",macro_expand(x)) #define FOR(i,l,r) for(int i=(l),i##ADJK=(r);i<=i##ADJK;++i) #define ROF(i,r,l) for(int i=(r),i##ADJK=(l);i>=i##ADJK;--i) #define fi first #define se second using namespace std; typedef long long LL; const int MN=55,Mod=258280327; int add(int &x,int y){return ((x+=y)>=Mod)?(x-=Mod):x;} int dec(int &x,int y){return ((x-=y)<0)?(x+=Mod):x;} int N; unordered_map<LL,int> f[2][MN][2]; int get_last(LL s,bool tag){ int cnt=0; FOR(i,0,N)if((s>>i)&1){ ++cnt; if(cnt==1&&tag==0)return i; else if(cnt==2&&tag==1)return i; } return -1; } int main(){ freopen("axelavir.in","r",stdin); freopen("axelavir.out","w",stdout); scanf("%d",&N); f[1][1][0][1]=1; FOR(i,1,N-1){ bool cur=i&1; FOR(j,0,i)FOR(z,0,1)f[cur^1][j][z].clear(); FOR(j,0,i){ FOR(z,0,1){ for(auto s:f[cur][j][z]){ if(s.se==0)continue; int x=get_last(s.fi,z); int mn=get_last(s.fi,0); FOR(k,0,j){ // zui hou yi ge shu int nw_j=j; if(k>x)++nw_j; int xj=0; if(k>mn)ROF(o,k-1,0)if((s.fi>>o)&1){xj=o;break;} LL nw_s=s.fi|(1ll<<k); add(f[cur^1][nw_j-xj][(k<=mn)?0:1][nw_s>>xj],s.se); } } } } } int ans=0; FOR(j,0,N)FOR(z,0,1)for(auto s:f[N&1][j][z])add(ans,s.se); printf("%d\n",ans); fclose(stdin); fclose(stdout); return 0; }