CF Round 760

好像有了些体验感……

已经是第二次打 cf 了，第一次一道题都没过，这次过了四道题，大概确实是有些了体验感。（虽然别人几分钟就过题了，但我十分稳定地半小时过一道，从开头做到结尾

来补题

F Reverse

Problem Restatement

给两个正实数 , 问能不能经过下面的操作将 变成 。

操作：将 转化成二进制数（无前导0），在它的后面加上一个 0 或 1 ，然后前后反转得到新的 。

思路

加 0 其实是没有意义的，所以我们只需要讨论加不加 1 。对于一个二进制末尾有 0 的 , 不加 1 相当于去掉末尾连续的 0 ；加 1 相当于保留末尾的 0 ，并在末尾加 1 后反转。仔细思考以后，我们可以发现，在第一次操作之后， 中 0 的个数就确定了。故问题转化为经过变化的 是否是 的二进制的子串，且 在中 中所有的 是否都被该子串覆盖。

故我们需要考虑 4 种 ，看看是否存在符合上述条件的 。即去掉原来 的后缀 0 ，去掉后缀 0 后翻转，在原来 后加 1 ，加 1 后翻转。

代码

#include<bits/stdc++.h>
#define N 10007
using namespace std;
typedef long long ll;

inline ll rd() {
  ll x = 0;
  bool f = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar()) f |= (c == '-');
  for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
  return f ? -x : x;
}

int a[67], b[67], c[67], m, n, len;

bool check(int pos){
    for(int i = 1; i < pos; ++i)
        if(b[i] == 0) return 0;
    for(int i = pos + len; i <= m; ++i)
        if(b[i] == 0) return 0;
    for(int i = 1; i <= len; ++i)
        if(b[pos + i - 1] != c[i]) return 0;
    return 1;
}

int main() {
    ll x = rd(), y = rd();
    if(x == y) {puts("YES"); return 0;}
    while(x != 0){
        a[++n] = x % 2;
        c[n] = a[n];
        x /= 2;
    }
    while(y != 0){
        b[++m] = y % 2;
        y /= 2;
    }
    reverse(a + 1, a + 1 + n);
    reverse(b + 1, b + 1 + m);
    reverse(c + 1, c + 1 + n);
    len = n;
    while(c[len] == 0) len--;
    for(int i = 1; i <= m - len + 1; ++i){
        if(check(i)) {puts("YES"); return 0;}
    }
    reverse(c + 1, c + 1 + len);
    for(int i = 1; i <= m - len + 1; ++i){
        if(check(i)) {puts("YES"); return 0;}
    }
    a[++n] = 1;
    for(int i = 1; i <= n; ++i) c[i] = a[i];
    len = n;
    for(int i = 1; i <= m - len + 1; ++i){
        if(check(i)) {puts("YES"); return 0;}
    }
    reverse(c + 1, c + 1 + len);
    for(int i = 1; i <= m - len + 1; ++i){
        if(check(i)) {puts("YES"); return 0;}
    }
    puts("NO");
    return 0;
}