CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:other:错题集_4 [2021/02/08 20:38]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:other:错题集_4 [2021/02/28 19:08] (当前版本)
jxm2001
@@ 行 395: / 行 395: @@
 	}
 	enter(ans);
+	return 0;
+}
+</code>
+</hidden>
+===== 6、Minimum Difference =====
+[[https://codeforces.com/contest/1476/problem/G|链接]]
+==== 题意 ====
+给定 $n$ 个位置，每个位置一个照明范围为 $p_i$ 的灯，如果该灯朝左，则照明区域为 $[i-p_i,i-1]$，如果该灯朝右，则照明区域为 $[i+1,i+p_i]$。
+判定是否可以给每个灯一个朝向，使得 $[1,n]$ 区域全被照明，同时输出合法方案。
+==== 题解 ====
+设 $\text{dp}(i)$ 表示前 $i$ 个灯的最大照明前缀。
+设 $\text{pre}(i)$ 如果为 $0$ 则表示第 $i$ 个灯没有约束，如果不为 $0$ 则表示第 $i$ 个灯强制朝左且第 $[\text{pre}(i)+1,i-1]$ 灯贪心朝右。
+如果第 $i$ 个灯强制朝左，则考虑与之前的照明前缀拼接，于是需要找到 $j$ 满足 $\text{dp}(j)+1\ge i-p_i$。如果存在 $j$，则 $\text{dp}(i)$ 至少为 $i-1$。
+然后 $j+1\sim i-1$ 的所有灯可以贪心考虑全部朝右，于是可以选取 $\max_{j+1\le k\le i-1} (i+p_i)$ 更新 $\text{dp}(i)$，可以 $\text{ST}$ 表维护。
+另外如果 $\text{pre}(j)=0$，即 $j$ 没有强制向左的约束，还可以用 $j+p_j$ 更新 $\text{dp}(i)$。
+不难发现满足条件的 $j$ 越小 $\text{dp}(i)$ 越大，于是权值线段树维护满足条件的最小下标即可。
+如果第 $i$ 个灯朝右，首先 $\text{dp}(i)$ 至少为 $\text{dp}(i-1)$。如果 $\text{dp}(i-1)\ge i$，则 $\text{dp}(i)\gets i+p_i$。
+最后，如果强制朝左的收益大于朝右的收益，则强制朝左且 $\text{pre}(i)=j$，否则贪心朝右且 $\text{pre}(i)=0$。
+输出方案所有灯贪心朝右，遇到 $\text{pre}(pos)\neq 0$ 则把该灯改成朝左且跳转到 $\text{pre}(pos)$ 即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5,MAXM=20,inf=1e9;
+namespace ST{
+	int d[MAXN][MAXM],lg2[MAXN];
+	void build(int *a,int n){
+		lg2[1]=0;
+		_rep(i,2,n)lg2[i]=lg2[i>>1]+1;
+		_rep(i,1,n)d[i][0]=a[i];
+		for(int j=1;(1<<j)<=n;j++){
+			_rep(i,1,n-(1<<j)+1)
+			d[i][j]=max(d[i][j-1],d[i+(1<<(j-1))][j-1]);
+		}
+	}
+	int query(int lef,int rig){
+		int len=rig-lef+1;
+		return max(d[lef][lg2[len]],d[rig-(1<<lg2[len])+1][lg2[len]]);
+	}
+};
+int p[MAXN],a[MAXN],dp[MAXN],pre[MAXN];
+char ans[MAXN];
+int lef[MAXN<<2],rig[MAXN<<2],s[MAXN<<2];
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R,s[k]=inf;
+	if(L==R)return;
+	int M=L+R>>1;
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+}
+void update(int k,int pos,int v){
+	s[k]=min(s[k],v);
+	if(lef[k]==rig[k])return;
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=pos)update(k<<1,pos,v);
+	else update(k<<1|1,pos,v);
+}
+int query(int k,int L,int R){
+	if(L<=lef[k]&&rig[k]<=R)return s[k];
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=R)return query(k<<1,L,R);
+	else if(mid<L)return query(k<<1|1,L,R);
+	return min(query(k<<1,L,R),query(k<<1|1,L,R));
+}
+int main()
+{
+	int T=read_int();
+	while(T--){
+		int n=read_int();
+		_rep(i,1,n)p[i]=read_int(),a[i]=min(p[i]+i,n);
+		ST::build(a,n);
+		build(1,0,n);
+		_rep(i,1,n){
+			int last=query(1,max(0,i-p[i]-1),n);
+			if(last==inf){
+				dp[i]=dp[i-1];
+				pre[i]=0;
+			}
+			else{
+				int vl=i-1,vr=dp[i-1];
+				if(!pre[last])vl=max(vl,ST::query(last,i-1));
+				else if(last+1<=i-1)vl=max(vl,ST::query(last+1,i-1));
+				if(dp[i-1]>=i)vr=max(vr,a[i]);
+				if(vl<=vr){
+					dp[i]=vr;
+					pre[i]=0;
+				}
+				else{
+					dp[i]=vl;
+					pre[i]=last;
+				}
+			}
+			update(1,dp[i],i);
+		}
+		if(dp[n]<n)puts("NO");
+		else{
+			puts("YES");
+			_rep(i,1,n)ans[i]='R';
+			ans[n+1]='\0';
+			int pos=n;
+			while(pos){
+				if(pre[pos])ans[pos]='L',pos=pre[pos];
+				else
+				pos--;
+			}
+			puts(ans+1);
+		}
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 7、Make Them Similar =====
+[[https://codeforces.com/problemset/problem/1257/F|链接]]
+==== 题意 ====
+给定一个长度为 $n$ 的序列 $a_1,a_2\cdots a_n$，要求找到 $x$ 使得 $a_1\oplus x,a_2\oplus x\cdots a_n\oplus x$ 中的二进制表示的 $1$ 一样多。
+其中 $n\le 100,a_i\lt 2^{30}$。
+==== 题解 ====
+暴力枚举 $x$ 的低 $15$ 位和高 $15$ 位。假设当前枚举低 $15$ 位，且当前枚举的数为 $v$，记 $b_i$ 为 $a_i\oplus v$ 的二进制表示中的 $1$ 的个数。
+将 $b_2-b_1,b_3-b_1\cdots b_n-b_1$ 所代表的序列插入字典树。然后枚举高位时查看有无刚好可以构成相反数的序列即可。
+时间复杂度 $O(n\sqrt v)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=105,MAXL=15,MAXV=1<<MAXL,MAXS=MAXN*MAXV;
+int n,a[MAXN],b[MAXN];
+int cal(int v){
+	int cnt=0;
+	while(v){
+		cnt+=v&1;
+		v>>=1;
+	}
+	return cnt;
+}
+int ch[MAXS][MAXL<<1|1],val[MAXS],cnt;
+void Insert(int v){
+	int pos=0;
+	_for(i,1,n){
+		if(!ch[pos][b[i]])
+		ch[pos][b[i]]=++cnt;
+		pos=ch[pos][b[i]];
+	}
+	val[pos]=v;
+}
+void query(int v){
+	int pos=0;
+	_for(i,1,n){
+		if(!ch[pos][b[i]])return;
+		pos=ch[pos][b[i]];
+	}
+	enter((v<<15)|val[pos]);
+	exit(0);
+}
+int main()
+{
+	n=read_int();
+	_for(i,0,n)a[i]=read_int();
+	_for(i,0,MAXV){
+		_for(j,0,n)
+		b[j]=cal((a[j]&(MAXV-1))^i);
+		_for(j,1,n)
+		b[j]=b[j]-b[0]+MAXL;
+		Insert(i);
+	}
+	_for(i,0,MAXV){
+		_for(j,0,n)
+		b[j]=cal((a[j]>>15)^i);
+		_for(j,1,n)
+		b[j]=b[0]-b[j]+MAXL;
+		query(i);
+	}
+	puts("-1");
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

页面工具