差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest9 [2021/08/01 14:35]
王智彪
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest9 [2021/08/06 21:07] (当前版本)
jxm2001
@@ 行 5: / 行 5: @@
 ^  题目  ^  蒋贤蒙  ^  王赵安  ^  王智彪  ^
 |  A  |  0  |  0  |  0  |
-|  C  |  2  |  0  |  0  |
+|  C  |  2  |  1  |  0  |
-|  E  |  0  |  0  |  0  |
+|  E  |  2  |  0  |  1  |
-|  F  |  0  |  0  |  2  |
+|  F  |  0  |  1  |  2  |
 |  G  |  2  |  0  |  2  |
-|  I  |  0  |  0  |  0  |
+|  I  |  2  |  1  |  0  |
-|  J  |  2  |  0  |  1  |
+|  J  |  2  |  1  |  1  |
 ====== 题解 ======
+===== C. Cheating and Stealing =====
+==== 题意 ====
+给定一个长度为 $n$ 的 $01$ 串 $S$，对每个 $i=1\sim n$，询问下述流程的结果：
+  - 初始化答案为 $0$
+  - 找到最短的前缀满足至少有 $i$ 个 $0$ 或者 $i$ 个 $1$，且 $0$ 的个数和 $1$ 的个数的差值不小于 $2$，如果没有满足条件的前缀则输出答案
+  - 对这个前缀，如果 $1$ 比 $0$ 多，则答案加一
+  - 删除这个前缀，跳回操作  $2$
+==== 题解 ====
+首先不难发现对于固定 $i$，由于每次操作至少取出长度为 $i$ 的前缀，所以上述操作最多执行 $O\left(\frac ni\right)$ 次，所以总操作次数  $O(n\log n)$。
+所以如果能 $O(1)$ 找到每次操作满足条件的前缀，即可 $O(n\log n)$ 解决此题。
+首先考虑如何找到至少有 $i$ 个 $0$ 或者 $i$ 个 $1$ 的最短前缀，可以提前记录第 $k$ 个 $0$ 和 $1$ 的位置，分被为 $p(0,k)$ 和 $p(1,k)$。
+于是可以 $O(1)$ 跳转。接下来在这个位置的基础上寻找满足 $0$ 的个数和 $1$ 的个数的差值不小于 $2$ 的位置。
+如果当前位置已经满足条件，则已经找到前缀。否则假如当前位置的得分差为 $1$，则在移动一位，使得分差为 $0$ 或 $2$。如果是 $2$ 则也已经找到前缀。
+接下来只需要考虑得分差为 $0$ 的情况，提前维护 $\text{next}$ 数组表示从得分相同到比赛结束的位置。
+不难发现有 $\text{next}(i)=(s[i]==s[i+1])?(i+1):\text{next}(i+2)$，提前预处理后也可以 $O(1)$ 跳转。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e6+5,MAXM=21,mod=998244353;
+char s[MAXN];
+int pre[MAXN],nxt[MAXN],det[MAXN],p1[MAXN],p0[MAXN],cnt1,cnt0;
+int quick_pow(int n,int k){
+	int ans=1;
+	while(k){
+		if(k&1)ans=1LL*ans*n%mod;
+		n=1LL*n*n%mod;
+		k>>=1;
+	}
+	return ans;
+}
+int solve(int n,int i){
+	int lef=1,ans=0;
+	while(true){
+		int c1=cnt1-pre[lef-1],c0=n-lef+1-c1,rig=n+1;
+		if(c1>=i)
+		rig=min(rig,p1[pre[lef-1]+i]);
+		if(c0>=i)
+		rig=min(rig,p0[lef-1-pre[lef-1]+i]);
+		if(rig==n+1)
+		break;
+		if(abs(det[rig]-det[lef-1])<2){
+			if(det[rig-1]!=det[lef-1])
+			rig++;
+			rig=nxt[rig];
+		}
+		if(rig==0)
+		break;
+		if(det[rig]-det[lef-1]>=2)
+		ans++;
+		lef=rig+1;
+	}
+	return ans;
+}
+int main(){
+	int n=read_int();
+	scanf("%s",s+1);
+	_rep(i,1,n){
+		if(s[i]=='W'){
+			p1[++cnt1]=i;
+			pre[i]=1;
+			det[i]=1;
+		}
+		else{
+			p0[++cnt0]=i;
+			pre[i]=0;
+			det[i]=-1;
+		}
+		pre[i]+=pre[i-1];
+		det[i]+=det[i-1];
+	}
+	for(int i=n-1;i;i--)
+	nxt[i]=(s[i]==s[i+1])?i+1:nxt[i+2];
+	int ans=0;
+	_rep(i,1,n)
+	ans=(ans+1LL*solve(n,i)*quick_pow(n+1,i-1))%mod;
+	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+===== E. Eert Esiwtib =====
+==== 题意 ====
+给定一棵以 $1$ 为根的点权树，记第 $i$ 个点的原始点权为 $a_i$。每条边有一种操作符，可能为 $\text{OR},\text{AND},\text{XOR}$。
+设路径 $u\to v$ 上的点权和操作符依次为 $p_1,e_1,p_2\cdots e_{k-1},p_k$，则路径的权重 $w(u,v)=p_1 e_1(p_2 e_2(\cdots (p_{k-2}e_{k-2}(p_{k-1}e_{k-1}p_k))\cdots))$。
+定义 $\text{Tree}(u)$ 表示 $u$ 的子树，不包括 $u$ 本身。接下来若干询问，每次给定 $d,u$，将每个点的点权变为 $a_i+d\times i$，求
+$$
+\text{OR}_{v\in Tree(u)}w(u,v),\text{AND}_{v\in Tree(u)}w(u,v),\text{XOR}_{v\in Tree(u)}w(u,v)
+$$
+注意，每组询问对点权的修改独立，即一个询问对点权的修改不影响另一个询问。同时有 $0\le d\le 100$。
+==== 题解 ====
+发现 $d$ 很小，直接枚举 $d$，暴力树形 $\text{dp}$ 即可。设 $\text{dp}(u,0/1/2)$ 表示 $u$ 求 $\text{OR},\text{AND},\text{XOR}$ 情况下的答案，大力分类讨论即可。
+注意权值直接运算时每个位是独立的，所以在讨论时可以只考虑权值是 $0/1$ 的情况，然后枚举 $u$ 是 $0,1$ 考虑一下即可。
+例如，考虑边是 $\text{XOR}$ 的情况，计算下式
+$$
+(a_u\oplus v_1)|(a_u\oplus v_2)|\cdots (a_u\oplus v_k)
+$$
+首先假设 $a_u=0$，得到 $(a_u\oplus v_1)|(a_u\oplus v_2)|\cdots |(a_u\oplus v_k)=v_1|v_2|\cdots |v_k=\text{dp}(v,0)$。
+假设 $a_u=1$，得到 $(a_u\oplus v_1)|(a_u\oplus v_2)|\cdots |(a_u\oplus v_k)=(\sim v_1)|(\sim v_2)|\cdots |(\sim v_k)=\sim (v_1\And v_2\And \cdots \And v_k)=\sim \text{dp}(v,1)$。
+于是有 $\text{dp}(u,0)|=((\sim a_u)\And \text{dp}(v,0))|(a_u\And (\sim \text{dp}(v,1)))$。注意 $\text{dp}(v)$ 不包含 $v$ 本身的贡献所以还有 $\text{dp}(u,0)|=a_u|a_v$。
+总时间复杂度 $O(nd)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXV=105;
+struct Edge{
+	int to,w,next;
+}edge[MAXN];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v,int w){
+	edge[++edge_cnt]=Edge{v,w,head[u]};
+	head[u]=edge_cnt;
+}
+LL a0[MAXN],a[MAXN],dp[MAXN][3];
+int sz[MAXN];
+void dfs(int u){
+	dp[u][0]=dp[u][2]=0;
+	dp[u][1]=-1;
+	sz[u]=1;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		dfs(v);
+		sz[u]+=sz[v];
+		LL t;
+		if(edge[i].w==0)t=a[u]|a[v];
+		else if(edge[i].w==1)t=a[u]&a[v];
+		else t=a[u]^a[v];
+		dp[u][0]|=t;
+		dp[u][1]&=t;
+		dp[u][2]^=t;
+		if(sz[v]==1)continue;
+		sz[v]--;
+		if(edge[i].w==0){
+			dp[u][0]|=a[u]|dp[v][0];
+			dp[u][1]&=a[u]|dp[v][1];
+			if(sz[v]&1)
+			dp[u][2]^=a[u]|((~a[u])&dp[v][2]);
+			else
+			dp[u][2]^=(~a[u])&dp[v][2];
+		}
+		else if(edge[i].w==1){
+			dp[u][0]|=a[u]&dp[v][0];
+			dp[u][1]&=a[u]&dp[v][1];
+			dp[u][2]^=a[u]&dp[v][2];
+		}
+		else{
+			dp[u][0]|=(a[u]&(~dp[v][1]))|((~a[u])&dp[v][0]);
+			dp[u][1]&=(a[u]&(~dp[v][0]))|((~a[u])&dp[v][1]);
+			if(sz[v]&1)
+			dp[u][2]^=a[u]^dp[v][2];
+			else
+			dp[u][2]^=dp[v][2];
+		}
+	}
+}
+vector<pair<int,int> > c[MAXV];
+LL ans[MAXN][3];
+int main(){
+	int n=read_int(),q=read_int();
+	_rep(i,1,n)
+	a0[i]=read_int();
+	_rep(i,2,n){
+		int f=read_int(),s=read_int();
+		Insert(f,i,s);
+	}
+	_for(i,0,q){
+		int d=read_int(),u=read_int();
+		c[d].push_back(make_pair(i,u));
+	}
+	_for(d,0,MAXV){
+		_rep(i,1,n)
+		a[i]=a0[i]+i*d;
+		dfs(1);
+		for(pair<int,int> t:c[d]){
+			_for(j,0,3)
+			ans[t.first][j]=dp[t.second][j];
+		}
+	}
+	_for(i,0,q){
+		space(ans[i][0]);
+		space(ans[i][1]);
+		enter(ans[i][2]);
+	}
+	return 0;
+}
+</code>
+</hidden>
 ===== F. Finding Points =====
@@ 行 232: / 行 447: @@
 	ans=min(ans,A[i]+B[S^i]-a-b);
 	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+===== I. Interval Queries =====
+==== 题意 ====
+给定一个长度为 $n$ 的序列 $A$，接下来有 $q$ 个询问。每次询问给定 $l,r,k$，求
+$$
+\sum_{i=0}^{k-1}f(l-i,r+i)(n+1)^i
+$$
+其中 $f$ 定义如下
+$$
+f(l,r)=\max(\{k|\exists x\forall i(0\le i\le k-1\to \exists j(l\le j\le r,a_j=x+i))\})
+$$
+==== 题解 ====
+考虑回滚莫队处理询问，难点在于怎么维护最大的 $k$。
+实际上，这等价于维护数轴上的最长连续线段。可以令 $\text{vl}(x)$ 表示以数 $x$ 为左端点的线段在数轴上的右端点。
+$\text{vr}(x)$ 表示以数 $x$ 为右端点的线段在数轴上的左端点。于是只需要保证每条线段的两个端点的 $\text{vl},\text{vr}$ 正确性即可，不难 $O(1)$ 维护。
+时间复杂度 $O\left(n\sqrt q+\sum k\right)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,mod=998244353;
+int blk_sz,a[MAXN];
+struct query{
+	int l,r,k,idx;
+	bool operator < (const query &b)const{
+		if(l/blk_sz!=b.l/blk_sz)return l<b.l;
+		return r<b.r;
+	}
+}opt[MAXN];
+struct node{
+	int p1,v1,p2,v2,ans;
+}st[MAXN];
+int curlen,vis[MAXN],vl[MAXN],vr[MAXN],tp;
+void add(int v){
+	if(vis[v]++)return;
+	int l=vis[v-1]?vl[v-1]:v;
+	int r=vis[v+1]?vr[v+1]:v;
+	st[++tp]=node{l,vr[l],r,vl[r],curlen};
+	vr[l]=r;
+	vl[r]=l;
+	curlen=max(curlen,r-l+1);
+}
+void del(int v){
+	if(--vis[v])return;
+	vr[st[tp].p1]=st[tp].v1;
+	vl[st[tp].p2]=st[tp].v2;
+	curlen=st[tp].ans;
+	tp--;
+}
+int solve(int l,int r,int k,int n){
+	int ans=curlen,base=1;
+	_for(i,1,k){
+		add(a[l-i]);
+		add(a[r+i]);
+		base=1LL*base*(n+1)%mod;
+		ans=(ans+1LL*curlen*base)%mod;
+	}
+	for(int i=k-1;i;i--){
+		del(a[r+i]);
+		del(a[l-i]);
+	}
+	return ans;
+}
+int ans[MAXN];
+int main()
+{
+	int n=read_int(),q=read_int();
+	_rep(i,1,n)
+	a[i]=read_int();
+	_for(i,0,q){
+		int l=read_int(),r=read_int(),k=read_int();
+		opt[i]=query{l,r,k,i};
+	}
+	blk_sz=n/sqrt(q)+1;
+	sort(opt,opt+q);
+	_for(i,0,q){
+		if(opt[i].l/blk_sz==opt[i].r/blk_sz){
+			_rep(j,opt[i].l,opt[i].r)
+			add(a[j]);
+			ans[opt[i].idx]=solve(opt[i].l,opt[i].r,opt[i].k,n);
+			for(int j=opt[i].r;j>=opt[i].l;j--)
+			del(a[j]);
+		}
+	}
+	int lef=1,rig=0,lst=-1;
+	_for(i,0,q){
+		if(opt[i].l/blk_sz!=opt[i].r/blk_sz){
+			if(opt[i].l/blk_sz!=lst){
+				while(lef<=rig)del(a[rig--]);
+				lst=opt[i].l/blk_sz;
+				rig=min(lst*blk_sz+blk_sz-1,n);
+				lef=rig+1;
+			}
+			while(rig<opt[i].r)add(a[++rig]);
+			int tlef=lef;
+			while(tlef>opt[i].l)add(a[--tlef]);
+			ans[opt[i].idx]=solve(opt[i].l,opt[i].r,opt[i].k,n);
+			while(tlef<lef)del(a[tlef++]);
+		}
+	}
+	_for(i,0,q)enter(ans[i]);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具