2020-2021:teams:legal_string:jxm2001:contest:cf_705_div._2

差别

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

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:contest:cf_705_div._2 [2021/03/07 10:46]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:contest:cf_705_div._2 [2021/03/24 20:37] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-====== Codeforces Round #704 (Div. 2) ======
+====== Codeforces Round #705 (Div. 2) ======
 [[https://codeforces.com/contest/1493|比赛链接]]
@@ 行 11: / 行 11: @@
 ==== 题解 ====
-设 $R$ 的长度为 $n$，从低位到高位依次编号 $0,1,2\cdots n-1$。假设 $L$ 的第 $n-1$ 位为 $0$，取 $r=10\cdots 0$
+设 $R$ 的长度为 $n$，从低位到高位依次编号 $0,1,2\cdots n-1$。若 $L$ 的第 $n-1$ 位为 $0$，取 $l=2^{n-1}-1,r=2^{n-1}$，得 $F(l,r)=2^n-1$。
+若 $L$ 的第 $n-1$ 位为 $1$，下面证明若 $R$ 为偶数且 $R-L\ge 2$ 时答案为 $R+1$，否则答案为 $R$。
+首先考虑 $R-L\gt 2$ 的情况，不难发现答案一定是 $R$。
+接下来考虑 $R$ 是奇数的情况，考虑数学归纳法。
+对固定的 $L$，$[L,L]$ 答案为 $L$，$[L,L+1]$ 答案为 $L+1$，同时 $L,L+1$ 其中一定有一个为奇数，满足数学归纳法边界条件。
+假设 $[L,R]$ 答案为 $R'$，考虑 $[L,R+2]$ 的答案，对 $r\le R$，根据归纳法有 $F(l,r)\le R$。
+对 $F(l,R+1)$，假设有 $F(l,R+1)\gt R+2$，不妨假设 $F(l,R+1)$ 从高到低首个与 $R+2$ 不同的位为 $k$。
+此时有 $F(l,R+1)$ 第 $k$ 位为 $1$，$R+2$ 第 $k$ 位为 $0$，由于 $R+2$ 是奇数，所以 $k\gt 0$。
+不妨假设 $[l,R+1]$ 中最大的且第 $k$ 位为 $1$ 的数是 $t$。
+于是有 $[t+1,R+1]$ 第 $k$ 位为 $0$，$[t-2^k+1,t]$ 第 $k$ 位为 $1$，$[t-2^{k+1}+1,t-2^k]$ 第 $k$ 位为 $0\cdots$
+由于 $t$ 的末尾一定是 $111\cdots 1$，于是 $t$ 一定是奇数，于是 $[t+1,R+1]$ 长度为 $R-t+1$ 为奇数。
+于是 $[l,R+1]$ 中有奇数个数第 $k$ 位为 $1$ 和 $[l,R+1]$ 中有奇数个数不能同时满足，即 $F(l,R+1)$ 第 $k$ 位和第 $n-1$ 位不能同时为 $1$，矛盾。
+对 $F(l,R+2)$，有 $F(l,R+2)=F(l,R)\oplus 1\le R+1$。
+综上，$R$ 为奇数时，答案不超过 $R$，同时 $F(R,R)$ 取到上界。
+$R$ 为偶数时，区间 $[L,R]$ 的答案一定不超过 $[L,R+1]$ 的答案。
+由于 $R+1$ 是奇数，所以$[L,R+1]$ 答案为 $R+1$，于是 $R+1$ 是 $[L,R]$ 的答案上界，同时 $F(R-2,R)=R+1$ 取到上界。
 <hidden 查看代码>
 <code cpp>
+const int MAXN=1e6+5;
+int n;
+char L[MAXN],R[MAXN];
+void add(char *s){
+	int pos=n-1;
+	while(s[pos]=='1')s[pos]='0',pos--;
+	s[pos]='1';
+}
+int main()
+{
+	n=read_int();
+	scanf("%s%s",L,R);
+	if(L[0]!=R[0]){
+		_for(i,0,n)
+		putchar('1');
+	}
+	else if(strcmp(L,R)==0||R[n-1]=='1')
+	puts(R);
+	else{
+		add(L);
+		if(strcmp(L,R)==0)
+		puts(R);
+		else{
+			add(R);
+			puts(R);
+		}
+	}
+	return 0;
+}
 </code>
 </hidden>

2020-2021/teams/legal_string/jxm2001/contest/cf_705_div._2.1615085190.txt.gz · 最后更改: 2021/03/07 10:46 由 jxm2001