CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest10 [2021/08/06 01:39]
王智彪
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest10 [2021/08/11 16:00] (当前版本)
jxm2001
@@ 行 4: / 行 4: @@
 ^  题目  ^  蒋贤蒙  ^  王赵安  ^  王智彪  ^
-|  A  |  0  |  0  |  2  |
+|  A  |  0  |  1  |  2  |
 |  B  |  0  |  0  |  0  |
 |  C  |  1  |  0  |  2  |
-|  D  |  2  |  0  |  0  |
+|  D  |  2  |  1  |  0  |
-|  E  |  0  |  0  |  0  |
+|  E  |  2  |  0  |  0  |
-|  G  |  0  |  0  |  0  |
+|  G  |  0  |  1  |  2  |
 |  J  |  2  |  0  |  1  |
-|  K  |  0  |  0  |  0  |
+|  K  |  2  |  0  |  0  |
 ====== 题解 ======
@@ 行 283: / 行 283: @@
 }
 </code>
+</hidden>
+===== E. Growing Tree =====
+==== 题意 ====
+给定一棵树，初始时只有一个颜色为 $c$ 的 $1$ 号结点，接下来 $m$ 个操作：
+  - 对结点 $u$ 添加一个颜色为 $c$ 的叶子结点 $n+1$(设当前共有 $n$ 个结点)
+  - 查询结点 $u$ 子树颜色为 $c$ 的结点数量
+==== 题解 ====
+维护每个结点 $u$ 的最新儿子 $\text{hson}(u)$ 以及每个结点的子树在单括号序列的终止结点 $\text{dfr}(u)$(子树不包含该点)。
+于是新插入叶子结点 $n+1$ 时，如果 $u$ 没有叶子结点，则有 $\text{dfr}(n+1)\gets \text{dfr}(u)$，否则有 $\text{dfr}(n+1)\gets \text{hson}(u)$。
+然后将 $\text{hson}(u)$ 更新为 $n+1$ 即可实现序列的维护。$u$ 的子树查询等价于查询序列 $[\text{pos}(u),\text{pos}(\text{dfr}(u)))$ 的信息。
+接下来为每种颜色开一个平衡树，每棵平衡树维护该颜色结点的所有位置。
+则操作 $2$ 等价于查询颜色为 $c$ 的平衡树中位置位于 $[\text{pos}(u),\text{pos}(\text{dfr}(u)))$ 的结点个数。
+发现 $\text{pos}(u)$ 是动态更新的，但是 $\text{pos}(u),\text{pos}(v)$ 的相对大小是不会改变的，因此考虑建立一棵平衡树维护所有 $\text{pos}(u)$。
+如果用 $\text{splay}$ 维护 $\text{pos}(u)$，则每次查询 $\text{pos}(u)$ 时间复杂度为 $O(\log n)$，在颜色为 $c$ 的平衡树查询的结点数的时间复杂度为 $O\left(\log^2 n\right)$。
+考虑 $O(1)$ 查询 $\text{pos}(u)$。一种想法是将 $\text{pos}(u)$ 映射到实数空间，每次插入叶子结点则将 $\text{pos}(n+1)$ 赋值为 $\cfrac {\text{pos}(u)+\text{pos}(v)}{2}$。
+其中 $u,v$ 表示 $n+1$ 在单括号序列的左右相邻结点，但这样会导致精度误差。
+考虑替罪羊树维护 $\text{long long}$ 空间，替罪羊树定期重构重新赋值部分 $\text{pos}(u)$，保证了树的深度，不会导致精度误差。
+算法总时间复杂度变为  $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5;
+const LL MAXV=1LL<<62;
+LL val[MAXN];
+namespace Tree1{
+	#define lch(k) node[node[k].lch]
+	#define rch(k) node[node[k].rch]
+	const double alpha=0.70;
+	struct Node{
+		int lch,rch,sz;
+	}node[MAXN];
+	int root,a[MAXN],n;
+	bool isbad(int k){
+		return alpha*node[k].sz<max(lch(k).sz,rch(k).sz);
+	}
+	void build(int &k,int lef,int rig,LL vl,LL vr){
+		if(lef>rig) return k=0,void();
+		int mid=lef+rig>>1;
+		k=a[mid];
+		val[k]=vl+vr>>1;
+		if(lef==rig){
+			node[k].lch=node[k].rch=0;
+			node[k].sz=1;
+			return;
+		}
+		build(node[k].lch,lef,mid-1,vl,val[k]-1);
+		build(node[k].rch,mid+1,rig,val[k]+1,vr);
+		node[k].sz=lch(k).sz+rch(k).sz+1;
+	}
+	void dfs(int k){
+		if(!k)return;
+		dfs(node[k].lch);
+		a[++n]=k;
+		dfs(node[k].rch);
+	}
+	void rebuild(int &k,LL vl,LL vr){
+		n=0;
+		dfs(k);
+		build(k,1,n,vl,vr);
+	}
+	void check(int &k,int id,LL vl,LL vr){
+		if(k){
+			if(isbad(k))
+			rebuild(k,vl,vr);
+			else if(val[id]<val[k])
+			check(node[k].lch,id,vl,val[k]-1);
+			else
+			check(node[k].rch,id,val[k]+1,vr);
+		}
+	}
+	void Insert(int &k,int id){
+		if(!k){
+			k=id;
+			node[k].lch=node[k].rch=0;
+			node[k].sz=1;
+			return;
+		}
+		node[k].sz++;
+		if(val[id]<val[k])
+		Insert(node[k].lch,id);
+		else
+		Insert(node[k].rch,id);
+	}
+	void Insert(int id){
+		Insert(root,id);
+		check(root,id,0,MAXV);
+	}
+	#undef lch
+	#undef rch
+}
+namespace Tree2{
+	struct Node{
+		int r,sz,ch[2];
+	}node[MAXN];
+	#define lch(k) node[node[k].ch[0]]
+	#define rch(k) node[node[k].ch[1]]
+	void push_up(int k){
+		node[k].sz=lch(k).sz+rch(k).sz+1;
+	}
+	void split(int k,int &k1,int &k2,LL v){
+		if(!k) return k1=k2=0,void();
+		if(val[k]<=v){
+			k1=k;
+			split(node[k].ch[1],node[k1].ch[1],k2,v);
+			push_up(k1);
+		}else{
+			k2=k;
+			split(node[k].ch[0],k1,node[k2].ch[0],v);
+			push_up(k2);
+		}
+	}
+	void merge(int &k,int k1,int k2){
+		if(!k1||!k2)return k=k1|k2,void();
+		if(node[k1].r>node[k2].r){
+			k=k1;
+			merge(node[k].ch[1],node[k1].ch[1],k2);
+			push_up(k);
+		}else{
+			k=k2;
+			merge(node[k].ch[0],k1,node[k2].ch[0]);
+			push_up(k);
+		}
+	}
+	void Insert(int &root,int id){
+		node[id].r=rand();
+		node[id].sz=1;
+		node[id].ch[0]=node[id].ch[1]=0;
+		int lef,rig;
+		split(root,lef,rig,val[id]);
+		merge(lef,lef,id);
+		merge(root,lef,rig);
+	}
+	int rank(int root,LL v){
+		int lef,rig,ans;
+		split(root,lef,rig,v-1);
+		ans=node[lef].sz+1;
+		merge(root,lef,rig);
+		return ans;
+	}
+	int query(int root,LL vl,LL vr){
+		return rank(root,vr)-rank(root,vl);
+	}
+	#undef lch
+	#undef rch
+};
+int root[MAXN],col[MAXN],hson[MAXN],dfr[MAXN];
+void solve(){
+	int n=1;
+	col[1]=read_int();
+	val[1]=0;
+	val[0]=MAXV;
+	Tree1::Insert(1);
+	Tree2::Insert(root[col[1]],1);
+	int m=read_int(),lastans=0;
+	while(m--){
+		int t=read_int()^lastans,u=read_int()^lastans,c=read_int()^lastans;
+		if(t==1){
+			int v=hson[u]?hson[u]:dfr[u];
+			hson[u]=++n;
+			col[n]=c;
+			dfr[n]=v;
+			val[n]=val[u]+val[v]>>1;
+			Tree1::Insert(n);
+			Tree2::Insert(root[c],n);
+		}
+		else{
+			lastans=Tree2::query(root[c],val[u],val[dfr[u]]);
+			enter(lastans);
+		}
+	}
+	Tree1::root=0;
+	_rep(i,1,n){
+		root[col[i]]=0;
+		hson[i]=dfr[i]=0;
+	}
+}
+int main()
+{
+	int T=read_int();
+	while(T--)
+	solve();
+	return 0;
+}
+</code>
+</hidden>
+===== G. Hasse Diagram  =====
+==== 题意 ====
+给一个根节点的值，然后它延伸出去的点的值都是这个值恰好除以它的一个素因子得到的值，我们把一个点的 $f$ 函数值记做这个图的边数，求 $f(x)$ 的前缀和。
+==== 题解 ====
+题干给了 $12$ 的图，可以观察到，如果只是一个 $3$ 的图，也就是 $3$ 和 $1$ 两个点的图。
+$12$ 的图在这个基础上，可以分为 $12$ 和 $4$ ， $6$ 和 $2$ 这两组点，每组都和 $3$ 的图一样，并且这些图之间有边相连，比如 $12$ 连 $6$ ， $6$ 连 $3$ ， $4$ 连 $2$ ， $2$ 连 $1$ ，这些边的个数是 $3$ 的因子数乘 $12$ 除以 $3$ 是 $12$ 除以 $6$ 的多少次幂。
+如果看到这里，可以推出递推式： $f(n)=(e+1)f({\frac n {p^{e}}})+ed({\frac n {p^{e}}})$ 。
+经过这道题才知道从 $f(x)$ 推出 $f({\frac n {p^{e}}})$ 的结构也可以用 $Min-25$ 筛来做，原来一直以为必须是积性函数的...
+于是我们对板子魔改一下，变成同时求 $f$ 和 $d$ 的。 $d$ 显然是积性函数，并且 $d(p)$ 和 $d(p^{t})$ 都是很好算的，于是在筛中一起解决， $f$ 用到 $d$ 的结果，一并算出就结束了~
+<hidden 代码>
+<code cpp>
+#include<cstdio>
+#include<algorithm>
+#include<cstring>
+#include<cmath>
+#define ll long long
+using namespace std;
+const ll MOD=1145140019,inv2=(MOD+1)>>1,N=3e6,maxn=5e6;
+ll prime[maxn],num,sp0[maxn];
+ll n,Sqr,tot,g0[maxn],w[maxn],ind1[maxn],ind2[maxn];
+bool flag[maxn];
+void pre(int n) { //预处理，线性筛
+	flag[1]=1;
+	for(int i=1; i<=n; i++) {
+		if(!flag[i]) {
+			prime[++num]=i;
+			sp0[num]=(sp0[num-1]+1)%MOD;
+		}
+		for(int j=1; j<=num&&prime[j]*i<=n; j++) {
+			flag[i*prime[j]]=1;
+			if(i%prime[j]==0)break;
+		}
+	}
+}
+pair<ll,ll> S(ll x,int y) { //第二部分
+	if(prime[y]>=x)return make_pair(0,0);
+	ll k=x<=Sqr?ind1[x]:ind2[n/x];
+	ll ansf=(g0[k]-sp0[y]+MOD)%MOD,ansd=ansf*2%MOD;
+	for(int i=y+1; i<=num&&prime[i]*prime[i]<=x; i++) {
+		ll pe=prime[i];
+		for(int e=1; pe<=x; e++,pe=pe*prime[i]) {
+			pair<ll,ll> pp=S(x/pe,i);
+			ansf=(ansf+1ll*(e+1)*pp.first%MOD+1ll*e*(pp.second+(e!=1))%MOD)%MOD;
+			ansd=(ansd+(e+1)*(pp.second+(e!=1))%MOD);
+		}
+	}
+	ansf%=MOD;
+	ansd%=MOD;
+	return make_pair(ansf,ansd);
+}
+int main() {
+	int t;
+	scanf("%d",&t);
+	pre(N);
+	while(t--) {
+		scanf("%lld",&n);
+		Sqr=sqrt(n);
+		tot=0;
+		for(ll i=1; i<=n;) {
+			ll j=n/(n/i);
+			w[++tot]=n/i;
+			g0[tot]=(w[tot]%MOD-1+MOD)%MOD;
+			if(n/i<=Sqr)ind1[n/i]=tot;
+			else ind2[n/(n/i)]=tot;
+			i=j+1;
+		}
+		for(int i=1; i<=num; i++) {
+			for(int j=1; j<=tot&&prime[i]*prime[i]<=w[j]; j++) {
+				ll k=w[j]/prime[i]<=Sqr?ind1[w[j]/prime[i]]:ind2[n/(w[j]/prime[i])];
+				g0[j]=(g0[j]-(g0[k]-sp0[i-1])%MOD+MOD)%MOD;
+			}
+		}
+		printf("%lld\n",S(n,0).first);
+	}
+	return 0;
+}
+</code>
 </hidden>
@@ 行 396: / 行 688: @@
 		solve();
 	}
+	return 0;
+}
+</code>
+</hidden>
+===== K. Starch Cat =====
+==== 题意 ====
+给定一棵点权树，每次询问一条路径的最大权值，强制在线。其中，路径的权值定义为该路径上的最大权点集，满足点集中所有点都不相邻。
+==== 题解 ====
+考虑建立点分树。对固定的根节点 $\text{rt}$，设 $\text{dp}(u,0/1,0/1)$ 表示从根节点出发到 $u$ 的路径，选/不选根节点以及选/不选 $u$ 结点得到的最大权值。
+不难得到状态转移方程，进一步，设 $f(d,u,0/1)$ 表示 $u$ 在点分树上根节点深度为 $d$ 的结点到 $u$ 的路径，选/不选根节点的最大权值。
+最后对于询问操作，可以找到 $u,v$ 在点分树上的 $\text{LCA}$，设 $\text{LCA}$ 在点分树的深度为 $d$，则答案为
+$$
+\max(f(d,u,0)+f(d,v,0),f(d,u,1)+f(d,v,1)-a_{\text{LCA}})
+$$
+时间复杂度 $O((n+m)\log n)$，尽管 $m$ 很大，但常数很小而且时限比较宽松，所以能过。
+<hidden 查看代码>
+<code cpp>
+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;
+    }
+};
+const int MAXN=5e5+5,MAXD=20;
+const LL inf=1e15;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int sz[MAXN],mson[MAXN],tot_sz,root,root_sz;
+bool vis[MAXN];
+int a[MAXN],rt[MAXD][MAXN];
+LL dp[MAXN][2][2],dp2[MAXD][MAXN][2];
+void dfs(int u,int fa,int dep){
+	rt[dep][u]=root;
+	if(fa==0){
+		dp[u][0][0]=0;
+		dp[u][1][1]=a[u];
+		dp[u][1][0]=dp[u][0][1]=-inf;
+	}
+	else{
+		dp[u][0][0]=max(dp[fa][0][0],dp[fa][0][1]);
+		dp[u][0][1]=dp[fa][0][0]+a[u];
+		dp[u][1][0]=max(dp[fa][1][0],dp[fa][1][1]);
+		dp[u][1][1]=dp[fa][1][0]+a[u];
+	}
+	dp2[dep][u][0]=max(dp[u][0][0],dp[u][0][1]);
+	dp2[dep][u][1]=max(dp[u][1][0],dp[u][1][1]);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v]||v==fa)
+		continue;
+		dfs(v,u,dep);
+	}
+}
+void solve2(int u,int dep){
+	dfs(u,0,dep);
+}
+void find_root(int u,int fa){
+	sz[u]=1;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v]||v==fa)
+		continue;
+		find_root(v,u);
+		sz[u]+=sz[v];
+		mson[u]=max(mson[u],sz[v]);
+	}
+	mson[u]=max(mson[u],tot_sz-sz[u]);
+	if(mson[u]<root_sz){
+		root=u;
+		root_sz=mson[u];
+	}
+}
+void solve(int u,int dep){
+	int cur_sz=tot_sz;
+	vis[u]=true;
+	solve2(u,dep);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v])
+		continue;
+		tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];
+		root_sz=MAXN;
+		find_root(v,u);
+		solve(root,dep+1);
+	}
+}
+LL query(int u,int v){
+	int d=0;
+	while(rt[d][u]&&rt[d][u]==rt[d][v])d++;
+	d--;
+	return max(dp2[d][u][0]+dp2[d][v][0],dp2[d][u][1]+dp2[d][v][1]-a[rt[d][u]]);
+}
+int main(){
+	int n=read_int(),m=read_int(),seed=read_int();
+	_rep(i,1,n)a[i]=read_int();
+	_rep(i,2,n){
+		int f=read_int();
+		Insert(f,i);
+		Insert(i,f);
+	}
+	root_sz=MAXN;
+	tot_sz=n;
+	find_root(1,0);
+	solve(root,0);
+	long long lastans=0,ans=0;
+	constexpr int P=998244353;
+	Rand rand(n,seed);
+	for(int i=0;i<m;i++){
+	    int u=rand.get(lastans);
+	    int v=rand.get(lastans);
+	    int x=rand.get(lastans);
+	    lastans=query(u,v);//calculate the answer
+	    ans=(ans+lastans%P*x)%P;
+	}
+	enter(ans);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

页面工具