补题 Vika and Price Tags

题面翻译

你有两个长度均为 $n(1 \le n \le 10^5)$ 的序列 $a,b(0 \le a_i,b_i \le 10^9)$，每一次操作令所有 $a_i = b_i,b_i = |a_i - b_i|$。问若干次操作后，是否能让所有的 $a_i$ 值都为 $0$。多测。

题目描述

Vika came to her favorite cosmetics store “Golden Pear”. She noticed that the prices of $ n $ items have changed since her last visit.

She decided to analyze how much the prices have changed and calculated the difference between the old and new prices for each of the $ n $ items.

Vika enjoyed calculating the price differences and decided to continue this process.

Let the old prices be represented as an array of non-negative integers $ a $ , and the new prices as an array of non-negative integers $ b $ . Both arrays have the same length $ n $ .

In one operation, Vika constructs a new array $ c $ according to the following principle: $ c_i = |a_i - b_i| $ . Then, array $ c $ renamed into array $ b $ , and array $ b $ renamed into array $ a $ at the same time, after which Vika repeats the operation with them.

For example, if $ a = [1, 2, 3, 4, 5, 6, 7] $ ; $ b = [7, 6, 5, 4, 3, 2, 1] $ , then $ c = [6, 4, 2, 0, 2, 4, 6] $ . Then, $ a = [7, 6, 5, 4, 3, 2, 1] $ ; $ b = [6, 4, 2, 0, 2, 4, 6] $ .

Vika decided to call a pair of arrays $ a $ , $ b $ dull if after some number of such operations all elements of array $ a $ become zeros.

Output “YES” if the original pair of arrays is dull, and “NO” otherwise.

输入格式

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the number of items whose prices have changed.

The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^9 $ ) — the old prices of the items.

The third line contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 0 \le b_i \le 10^9 $ ) — the new prices of the items.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output “YES” if the pair of price arrays is dull, and “NO” otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be accepted as a positive answer.

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
9
4
0 0 0 0
1 2 3 4
3
1 2 3
1 2 3
2
1 2
2 1
6
100 23 53 11 56 32
1245 31 12 6 6 6
7
1 2 3 4 5 6 7
7 6 5 4 3 2 1
3
4 0 2
4 0 2
3
2 5 2
1 3 4
2
6 1
4 2
2
0 0
0 3

样例输出 #1

1
2
3
4
5
6
7
8
9
YES
YES
NO
NO
YES
YES
NO
YES
YES

提示

In the first test case, the array $ a $ is initially zero.

In the second test case, after the first operation $ a = [1, 2, 3], b = [0, 0, 0] $ . After the second operation $ a = [0, 0, 0], b = [1, 2, 3] $ .

In the third test case, it can be shown that the array $ a $ will never become zero.

题解

题目解析

这道题还是一个思维题, 主要是考到了找规律:

1
2
3
4
5
6
7
8
我们举一个例子,例如 6 3 这一组数据:
6 3 -1> 3 3 -2> 3 0 -3> 0 3 -4> 3 3 -5> 3 0 -6> 0 3 -7> ...
上面这一列可以等价为取他们的gcd:
2 1 -1> 1 1 -3> 1 0 -3> 0 1 -4> 1 1 -5> 1 0 -6> 0 1 -7> ...
我们多试几个数就可以发现他们最终都会变成 1 1 / 1 0 / 0 1 这种形式而且这三种情况是循环的.
我们取其 gcd 就可以得到以下 a,b 的三种情况(不可能出现偶-偶的情况,因为取了gcd):
奇数 - 奇数 = 偶数 -1> 奇数 - 偶数 = 奇数 -2> 偶数 - 奇数 = 奇数 -3> 奇数 - 奇数 = 偶数
这里的周期等于3. 并且最后一定会变成 奇数 - 奇数 (也就是 1 - 1) 的这一种情况,并且 1 1 / 1 0 / 0 1 这三种情况也是周期等于3.

所以我们想要最后得到同时等于 $0$ , 仅需要讨论他们 $a,b$ 的奇偶性就可以了. 在看别人的代码是,我也发现了一种压缩状态的方法: 二进制压缩 , 也同时发现了一个内置函数: __builtin_popcount() 来统计二进制位数上有几个 $1$ .

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits\stdc++.h>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(i,a,n) for(int i=a;i<=n;++i)
#define fb(i,a,n) for(int i=a;i>=n;--i)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

MAXN(1e5);
vector<int> a(MAXN),b(MAXN);

int back(int x,int y){
	if(x == y && x == 0) return 0;
	int s = __gcd(x,y);
	x /= s, y /= s;
	if(x % 2 == 0) return 1;//二进制位数 0001
	if(y % 2 == 0) return 2;//二进制位数 0010
	return 4;//二进制位数 0100
}

signed main(){
	T_{
		int n;
		cin >> n;
		fa(i,1,n) cin >> a[i];
		fa(i,1,n) cin >> b[i];
		int s = 0;
		fa(i,1,n){
			s |= back(a[i],b[i]);//只要对应二进制位上有1就是1
		}
		if(__builtin_popcount(s) <= 1){//统计二进制位数上有1的个数,我们仅需要都是同一种情况或者都是0 0.
			cout << "YES" << endl;
		}else{
			cout << "NO" << endl;
		}
	}
	return 0;
}