这里会显示出您选择的修订版和当前版本之间的差别。
后一修订版 | 前一修订版 | ||
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> |