小编点评

The code solves the problem by using two HashMaps to keep track of the occurrences of numbers in the sequence and the number of elements that satisfy the conditions. **HashMap of occurrences of numbers:** * `cntn` stores the count of each number that appears in the sequence. * `cntx` stores the count of elements that satisfy the conditions for each number. **Algorithm:** 1. Iterate through the sequence and for each number, check if it has appeared previously in the sequence. 2. If it has appeared, add the count of elements that satisfy the conditions to the `res` variable. 3. If it has not appeared, add the count of elements that satisfy the conditions to the `cntx` HashMap. 4. Update the `cntx` HashMap by adding the count of elements that satisfy the conditions to the count of that number in the `cntx` HashMap. 5. After the loop, add the value of `res` to the output variable and print it. **Time complexity:** O(n), where n is the length of the sequence. **Space complexity:** O(n), since we need to store the counts of occurrences and the counts of elements that satisfy the conditions for each number.

正文

第一次ak周赛，写篇题解纪念一下

第一题

给定两个长度为 $n$ 的整数序列 $a_1,a_2,\dots ,a_n$ 以及 $b_1,b_2,\dots ,b_n$。

设 $A=a_1\text{or}{a}_2\text{or}\dots \text{or}{a}_n$，
$B=b_1\text{or}{b}_2\text{or}\dots \text{or}{b}_n$。

请你计算并输出 $A+B$ 的值。

$\text{or}$ 表示按位或运算。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$。

第三行包含 $n$ 个整数 $b_1,b_2,\dots ,b_n$。

输出格式

一个整数，表示 $A+B$ 的值。

数据范围

前 $3$ 个测试点满足 $1\le n\le 10$。
所有测试点满足 $1\le n\le 1000$，$0\le a_i,b_i\le 10^9$。

输入样例1：

5
1 2 4 3 2
2 3 3 12 1

输出样例1：

22

输入样例2：

10
13 2 7 11 8 4 9 8 5 1
5 7 18 9 2 3 0 11 8 6

输出样例2：

46

思路

签到题，直接模拟即可。
代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

long long a[N], b[N];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++ i ) cin >> a[i];
    for (int i = 1; i <= n; ++ i ) cin >> b[i];
    long long A = a[1], B = b[1];
    for (int i = 2; i <= n; ++ i ) {
        A |= a[i], B |= b[i];
    }
    
    cout << A + B << '\n';
    
    return 0;
}

第二题

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots ,a_n$。

你可以对该序列进行任意次倍增操作（也可以不进行任何操作）。

每次倍增操作可以任选序列中的一个元素，并将其乘以 $2$ 或乘以 $3$。

我们的目标是让序列中所有元素的值都相等。

请你判断，目标是否能够实现。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$。

输出格式

如果可以让序列中所有元素的值都相等，则输出 Yes，否则，输出 No。

数据范围

前 $6$ 个测试点满足 $2\le n\le 10$。
所有测试点满足 $2\le n\le 10^5$，$1\le a_i\le 10^9$。

输入样例1：

4
75 150 75 50

输出样例1：

Yes

输入样例2：

3
100 150 250

输出样例2：

No

思路

我们可以将每个数的2和3的因子都除掉，再判断是否全部相等就可以了，很水的一道数论题。
代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n;
int a[N];

bool judge() {
	for (int i = 1; i <= n; ++ i ) {
		while (a[i] % 2 == 0) a[i] /= 2;
		while (a[i] % 3 == 0) a[i] /= 3;
		//  把所有数的2和3的因数除掉
	}
	
	for (int i = 2; i <= n; ++ i ) 
		if (a[i] != a[i - 1]) //    每次比较相邻两个
			return false;
	
	return true;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i ) scanf("%d", &a[i]);
	
	if (judge()) puts("Yes");
	else puts("No");
	
	return 0;
}

第三题

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\dots ,a_n$ 和一个整数 $k$。

请你计算有多少个三元组 $(x,y,z)$ 同时满足以下所有条件：

1. $1\le x<y<z\le n$
2. $a_x\times k=a_y$
3. $a_y\times k=a_z$

输入格式

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$。

输出格式

一个整数，表示满足所有条件的三元组的数量。

数据范围

前 $6$ 个测试点满足 $1\le n\le 10$。
所有测试点满足 $1\le n,k\le 2\times 10^5$，$-10^9\le a_i\le 10^9$。

输入样例1：

5 2
1 1 2 2 4

输出样例1：

4

输入样例2：

3 1
1 1 1

输出样例2：

1

输入样例3：

10 3
1 2 6 2 3 6 9 18 3 9

输出样例3：

6

思路

我们拿两个哈希表，分别记录数列中每个数的出现个数与满足条件的y的个数，如果当前枚举到的x合法，就累加答案；最后输出答案。
注意：本题的$a_i$范围很大，需要开long long
代码：

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 2 * 1e5 + 10;

int n, k;
int a[N];

signed main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; ++ i ) cin >> a[i];
	
	unordered_map<int, int> cntn, cntx;
	int res = 0;
	
	for (int i = 1; i <= n; ++ i ) {
		if (cntx.count(a[i])) res += cntx[a[i]];
		if (cntn.count(a[i])) cntx[a[i] * k] += cntn[a[i]];
		++ cntn[a[i] * k] ;
	}
	
	cout << res << '\n';
	
	return 0;
}