[ABC254Ex] Multiply or Divide by 2 Solution

更好的阅读体验戳此进入

题面

给定大小为 $n$$n$ 的集合 $A$$A$ 和 $B$$B$，你可以对集合 $A$$A$ 中的元素 $a_i$$a_i$ 进行两种操作，分别为 $a_i\leftarrow \lfloor {\displaystyle \frac{a_i}{2}}\rfloor$$a_i \leftarrow \lfloor \dfrac{a_i}{2} \rfloor$，和 $a_i\leftarrow a_i\times 2$$a_i \leftarrow a_i \times 2$。你需要操作集合 $A$$A$ 直至集合 $A,B$$A, B$ 完全相同。求最小操作次数，若无解输出 -1。

Solution

感觉这题的难度感觉完全不够 Ex，也完全不够紫，说这是 D 题我都信。。。

首先考虑转化两种操作，不难想到可以认为是在二进制中，前者即为右移一位，后者为左移一位。或者说前者是在二进制的末尾追加一个 $0$$0$，后者则是在二进制的末尾去掉一个数（可以为 $1$$1$ 也可以为 $0$$0$）。然后发现，这样的操作即缩小又放大没什么好性质，于是考虑转化。可以想到，对于将 $A$$A$ 集合中某个元素末尾追加一个 $0$$0$，可以转化为在 $B$$B$ 集合中某个元素末尾去掉一个 $0$$0$，同时注意这里去掉的只能为 $0$$0$.

综上我们题意转化为了，操作可以在 $A$$A$ 集合中去掉末尾一个属，也可以在 $B$$B$ 集合中去掉末尾一个 $0$$0$。于是想到维护两个优先队列，每次在两个集合中各取一个最大值，令其为 $x,y$$x, y$，若 $x=y$$x = y$，那么这两个数显然可以直接消除。若 $x>y$$x \gt y$，那么显然 $x$$x$ 会大于 $y$$y$ 中所有的数，而我们的操作又只能缩小一个数，不能增大，所以为了达到目标，一定需要对 $x$$x$ 进行一个缩小的操作，即 $x\leftarrow \lfloor {\displaystyle \frac{x}{2}}\rfloor$$x \leftarrow \lfloor \dfrac{x}{2} \rfloor$，于是进行这个操作，$ans\leftarrow ans+1$$ans \leftarrow ans + 1$，然后把剩下的值丢回优先队列。若 $x<y$$x \lt y$，我们显然也要将 $y$$y$ 缩小，而此时我们还有个限制，对 $B$$B$ 集合的操作只能去掉 $0$$0$，所以如果这个值最后一位为 $1$$1$ 那么显然无解，反之进行对应操作即可。

思路明显且代码实现极为简单。

Code

xxxxxxxxxx
59
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
ll ans(0);
27
priority_queue < int, vector < int >, less < int > > a, b;
28

29
int main(){
30
    N = read();
31
    for(int i = 1; i <= N; ++i)a.push(read());
32
    for(int i = 1; i <= N; ++i)b.push(read());
33
    while(!a.empty() && !b.empty()){
34
        int x = a.top(), y = b.top(); a.pop(), b.pop();
35
        if(x > y)a.push(x >> 1), b.push(y), ++ans;
36
        else if(x < y){
37
            if(y & 1)printf("-1\n"), exit(0);
38
            else a.push(x), b.push(y >> 1), ++ans;
39
        }
40
    }printf("%lld\n", ans);
41
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
42
    return 0;
43
}
44

45
template < typename T >
46
inline T read(void){
47
    T ret(0);
48
    int flag(1);
49
    char c = getchar();
50
    while(c != '-' && !isdigit(c))c = getchar();
51
    if(c == '-')flag = -1, c = getchar();
52
    while(isdigit(c)){
53
        ret *= 10;
54
        ret += int(c - '0');
55
        c = getchar();
56
    }
57
    ret *= flag;
58
    return ret;
59
}

UPD

update-2022_12_06 初稿