用户工具

站点工具


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|比赛链接]] [[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 查看代码>​ <hidden 查看代码>​
 <code cpp> <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>​ </​code>​
 </​hidden>​ </​hidden>​
2020-2021/teams/legal_string/jxm2001/contest/cf_705_div._2.1615085190.txt.gz · 最后更改: 2021/03/07 10:46 由 jxm2001