CF1427E Xum 题解

· · 题解

学校比赛的时候考了这道题，我当然是一分没得。

这是一道好构造题。

先不说正解，我看别的题解都没有说怎么拿部分分，但是如果赛时不会正解，那么拿部分分就是很必要的一件事了，所以我在这里说一说。想直接看正解的可以跳过部分分讲解。

注：下文中的 “⊕” 指的是异或运算。

算法一 暴力枚举 (30pts)

我们考虑在什么情况下能够合成一。因为加和运算是始终使数增加的，所以是用异或运算来合成 1，并且当且仅当一对相邻的奇数偶数时才能异或出来 1。

也就是在类似这种情况下再进行一步异或即可合成 1：

00010110101
00010110100

可以称此局面为出解局面。

考虑如何枚举。设 S 为已经合成的数的集合，那么可以枚举每一个 S 里的元素然后对 S 里的元素全部进行相加和异或操作，得到的新数再次扔到 S 里，继续枚举，直到出现出解局面为止。

关于如何判断出解局面是否出现，可以用一个 map 记录出现了哪些数，然后在合成了新的数 w 时 \text{check} 一下 w+1\text{、}w-1 有没有出现过，出现的话了判断一下异或出来是否为 1 ，如果为 1 则输出答案。

算法二 随机化 (40 \sim 96pts)

随机化还是比较好用的，我们学校 \text{OJ} 上有人 \text{40pts}，也有人 \text{96pts}，得分高低主要看你写的丑不丑以及你是怎样随机化的了。

分数相对低一点的做法( 一般在 \text{80pts} 以下)，可在已经 S 里随机选一个出来，然后对 S 里的元素全部进行相加和异或操作，把新的数再扔到 S 里，如此往复直到达到出解局面。当然了如果你写的足够好也可以获得接近 \text{90pts} 的高分。

对于写数字次数不超过 10^5 这个限制，显然我们在得到答案的路上是有很多无用的数被合成的，对存答案的结构体一趟 dfs 把这些数从答案中删掉即可。也可以 dfs 查找答案是怎样被合成的。

分数较高一点的做法( \text{80pts} 以上)是 \text{Delov} 大佬想出来的，考虑样例是怎样构造的：+ ⊕ + + ⊕，两个样例都是这样，这似乎昭示了什么规律。大胆猜测这种构造方式可以构造出答案，那么就按照他这个操作去进行随机化，也就是循环这个操作数列，然后每次在 S 里随机选一个数出来对 S 中的数进行当前循环到的操作( + 或者 ⊕ )，相应判断是否达到出解局面。可以获得 \text{85pts} 左右的高分。

提高出解率的方法是构造如下的操作数列并执行：

+++\ ...++\ ⊕\ ++++...

也就是随机在操作数列里插入一些 ⊕，使得 + 的操作次数要较多于 ⊕。这样目前测得最高可以获得 \text{93pts}。

还有一种可以获得最高 \text{96pts} 的随机化，涉及到 \text{exgcd}，这里不再赘述，因为并不是正解。

算法三 构造 (100pts)

正解其实挺简单的。考虑如何将数字 9 合成为1：

9: 0000 1001

因为题目保证给出的 x 是奇数，所以 x 的最低位一定是 1。

考虑如何运用这个性质。观察到对于相同的数 w 进行加和运算就是使 w 乘上一个 2，也就等同于 w 左移一位，那么就可以通过左移来用 x 最低位的 1 去消去较高位的 1，不妨每次去消掉 x 最高位的 1。考虑如何实现。

首先另取一个数 y=x，令 y 最低位的 1 与 x 最高位的 1 对齐：

x: 0000 1001
y: 0100 1000

之后令 x ⊕ y 得到 z：

x: 0000 1001
y: 0100 1000
z: 0100 0001

再令 y + z 得到 a：

x: 0000 1001
y: 0100 1000
z: 0100 0001
a: 1000 1001

再令 a ⊕ (y<<1) ⊕ x 得到 b：

x: 0000 1001
y: 0100 1000
z: 0100 0001
a: 1000 1001
   1001 0000 ←(y<<1)
b: 0001 0000

这时候发现 b 只剩下一位了，但并不是 x 的最高位；不过因为 y 的最低位即为 x 的最高位，容易想到用 b 依次左移把 y 较高位的 1 通过异或操作消掉，直到 y 仅剩 x 的最高位(也就是把 y 的非最低位全部消掉)，再用 y 去异或消掉 x 的最高位，此时便达到了我们消掉 x 最高位的目的。

如此循环消掉 x 最高位直到 x=1 即可。

代码实现：

#include <iostream>
#include <bitset>
#define GMY (520&1314)
#define FBI_OPENTHEDOOR(x, y) freopen(#x ".in", "r", stdin), freopen(#y ".out", "w", stdout);
#define re register int
#define char_phi signed
#define N 100005
using namespace std;
inline void Fastio_setup(){ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL);}

struct Answer{int opt; long long x, y;};

long long x, y, z, a, tmp, plc, anscnt, b, c, d;
struct Answer ans[N];

#define lowbit(x) ((x) & (-(x)))
inline void Xiao(){
    tmp = x; y = x;
    while (tmp != 0)// 取出来x的最高位
        plc = lowbit(tmp), tmp ^= plc;
    while (lowbit(y) != plc)
        {ans[++ anscnt] = (Answer){1, y, y}; y <<= 1;}// 得到y
    // 对齐之后另其与x异或
    ans[++ anscnt] = (Answer){2, x, y};
    z = x ^ y;
    // 另z与y相加得到a
    ans[++ anscnt] = (Answer){1, y, z};
    a = y + z;
    // y左移
    ans[++ anscnt] = (Answer){1, y, y};
    d = y + y;
    // a与y与x异或
    ans[++ anscnt] = (Answer){2, a, d};
    ans[++ anscnt] = (Answer){2, a^d, x};
    b = a ^ d ^ x;
    // 用b去消y
    c = b>>1;
    while (y != c){
        if ((y & b) == b)
            {ans[++ anscnt] = (Answer){2, y, b}, y = y ^ b;}
        ans[++ anscnt] = (Answer){1, b, b}; b <<= 1;
    }
    // 此时剩下的y就是x最高位了
    ans[++ anscnt] = (Answer){2, y, x};
    x = x ^ y;
}

inline void work(){
    cin >> x;

    while (x != 1)
        Xiao();

    cout << anscnt << '\n';
    for (re i = 1 ; i <= anscnt ; ++ i){
        cout << ans[i].x;
        cout << ((ans[i].opt == 1) ? (" + ") : (" ^ "));
        cout << ans[i].y << '\n';
    }
}
// #define IXINGMY
char_phi main(){
    #ifdef IXINGMY
        FBI_OPENTHEDOOR(a, a);
    #endif
    Fastio_setup();
    work();
    return GMY;
}