专栏文章

题解：P14473 [集训队互测 2025] 少年汹涌

ddiqiuyi奶龙
P14473题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5mg6n
此快照首次捕获于
2025/12/01 20:57
3 个月前
此快照最后确认于
2025/12/01 20:57
3 个月前
查看原文
一个 O(nlog⁡n+nlog⁡2L+log⁡3L)O(n\log n+n\log^2 L+\log^3L) 做法，但是好像跑得很快。（认为 ww 和 log⁡L\log L 同阶）
wiw_i 很小，所以考虑用一些东西来简化变化的过程。
注意到如果不考虑后 66 位，每次变化最多让前面的位 +1+1。设 fi,j,kf_{i,j,k} 表示 x≡i(mod64)x\equiv i\pmod{64}，xx 除掉后 66 位的 popcount(x)=j\text{popcount}(x)=j，让 xx 除掉后 66 位的值增加 2k2^k 所需的次数；gi,j,kg_{i,j,k} 表示此时 xx 后 66 位的值。转移是不难的，可以 O(log⁡3L)O(\log^3L) 预处理出来。注意为了保证能正确处理 jj，只有 2k≤lowbit(x)2^k\le\text{lowbit}(x) 时可以用这些值来更新 xx。
以下用 g(x)g(x) 表示 ⌊x64⌋\lfloor{\frac{x}{64}}\rfloor。
如果 n=1n=1，考虑先让 g(x)=g(L)g(x)=g(L)。可以先把 g(x)g(x) 变成 g(L)g(L) 的一段前缀，再把后面的位补上。而前面部分可以不断让 g(x)←g(x)+lowbit(g(x))g(x)\gets g(x)+\text{lowbit}(g(x))。这样只需要变化 O(log⁡L)O(\log L) 次。后面的部分暴力跳即可。
n>1n>1 时即要求出树的大小。先给 aa 从小到大排序，然后依次加入，然后更新当前树的大小。算大小时先把所有 j<ij<i 的 aja_j 跳成 g(aj)=g(ai)g(a_j)=g(a_i)，注意到此时本质不同的 aja_j 只能有 O(log⁡L)O(\log L) 个。把 aia_i 和所有 aja_j 一起往上跳。先跳 g(x)←g(x)+lowbit(g(x))g(x)\gets g(x)+\text{lowbit}(g(x))，等 lowbit 固定了再从高位到低位枚举即可，过程与普通倍增类似。
所以时间复杂度为 O(nlog⁡n+nlog⁡2L+log⁡3L)O(n\log n+n\log^2 L+\log^3L)。
CPP
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,w[65],g[64][64][64];
ll L,a[60005],f[64][64][64],b[65];
bitset<64> vis;
int mov(ll &sf,int r,ll x,ll y){
	while(x&&x+(x&-x)<=y) 
		sf+=f[__lg(x&-x)][__builtin_popcountll(x)][r],r=g[__lg(x&-x)][__builtin_popcountll(x)][r],x+=x&-x;
	if((x&y)!=x) cout<<x<<' '<<y<<'\n';
	y^=x;
	for(int i=56;~i;i--)
		if(y>>i&1)
			sf+=f[i][__builtin_popcountll(x)][r],r=g[i][__builtin_popcountll(x)][r],x+=(1ll<<i);
	return r;
}
ll lca(ll x,ll r,ll mn){
	ll now=0;int ct=0;
	for(int i=0;i<64;i++) 
		if(vis[i])
			b[ct++]=i;
	while(now<mn){
		int lb=(x?__lg(x&-x):0),pc=__builtin_popcountll(x),vl=g[lb][pc][r];
		bool flg=0;
		for(int i=0;i<ct;i++)
			if(g[lb][pc][b[i]]==vl){
				flg=1;
				break;
			}
		if(!flg){
			now+=f[lb][pc][r],r=vl;
			for(int i=0;i<ct;i++) b[i]=g[lb][pc][b[i]];
			x+=(1ll<<lb);
		}
		else{
			for(lb--;~lb;lb--){
				pc=__builtin_popcountll(x),vl=g[lb][pc][r];
				bool flg=0;
				for(int i=0;i<ct;i++)
					if(g[lb][pc][b[i]]==vl){
						flg=1;
						break;
					}
				if(!flg){
					now+=f[lb][pc][r],r=vl;
					for(int i=0;i<ct;i++) b[i]=g[lb][pc][b[i]];
					x+=(1ll<<lb);
				}
			}
			bitset<64> vs=0;
			r+=(x<<6);
			for(int i=0;i<ct;i++) b[i]+=(x<<6);
			for(int i=0;i<ct;i++)
				while(1){
					vs[b[i]&63]=1,b[i]+=w[__builtin_popcountll(b[i])];
					if((b[i]>>6)>x) break;
				}
			while(!vs[r&63]&&(r>>6)==x)
				now++,r+=w[__builtin_popcountll(r)];
			break;
		}
	}
	return now;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0); 
	cin>>n>>L;
	for(int i=1;i<63;i++) cin>>w[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	for(int k=0;k<57;k++)
		for(int j=56;~j;j--)
			for(int i=63;~i;i--){
				if(k) f[k][j][i]=f[k-1][j][i]+f[k-1][j+1][g[k-1][j][i]],g[k][j][i]=g[k-1][j+1][g[k-1][j][i]];
				else{
					int pc=__builtin_popcount(i)+j;
					if(i+w[pc]>63) f[k][j][i]=1,g[k][j][i]=(i+w[pc]&63);
					else f[k][j][i]=f[k][j][i+w[pc]]+1,g[k][j][i]=g[k][j][i+w[pc]];
				}
			}
	ll ans=0;
	for(int i=1;i<=n;i++){
		ll rs=0;
		int r=mov(rs,a[i]&63,a[i]>>6,L>>6);
		ll x=((L>>6)<<6)+r;
		while(x<=L) x+=w[__builtin_popcountll(x)],rs++;
		rs=min(rs,lca(a[i]>>6,a[i]&63,rs));
		ans+=rs,vis[a[i]&63]=1;
		if(i==n) break;
		bitset<64> nv=0;
		for(int j=0;j<64;j++)
			if(vis[j])
				nv[mov(rs,j,a[i]>>6,a[i+1]>>6)]=1;
		vis=nv;
	}
	cout<<ans<<'\n';
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...