1 C 夜色亵渎者

这夜将亵渎灯的色。
亵渎美与好，
亵渎安眠，亵渎长息，
亵渎她心中所知的每一首摇篮曲。
从此之后，之后的之后，
漫漫长夜，再无安宁。

Alice 参加了一场考试。这场考试共有 $n^2$ 道题，题目在答题卡上排列成了一个 $n\times n$ 的矩阵。

Alice 聪明地找到了题目答案的规律。具体地，$(i,j)$ 位置上的答案为 $ai\oplus bj$。其中，$\oplus$ 代表按位异或。

然而，Alice 把答题卡的行列涂反了。即第 $i$ 行第 $j$ 列的答案填涂到了第 $j$ 行第 $i$ 列。

请问 Alice 能答对多少道题。

1 输入描述:

第一行一个整数 𝑛。

第二行 𝑛 个整数 $a_1,a_2,\dots ,a_n$ ​。

第三行 𝑛 个整数 $b_1,b_2,\dots ,b_n$​。

2 输出描述:

输出为一个数，即 $Alice$ 答对的题目数量。

3 示例 1

3.1 输入

4
1 2 3 4
2 4 3 4

3.2 4 输出

6

4 说明

题目的答案依次为：
3525
0616
1707
6070
Alice 的填涂为：
3016
5670
2107
5670
正确的位置一共有 6 个。

5 备注

对于所有数据，$1\le n\le 3\times {10}^5,0\le a_i,b_i\le {10}^9$。

考察异或的性质
异或：\bigoplus --- $⨁$ \oplus --- $\oplus$
我们直接对答案进行移动会发现 $a_i\oplus b_j=a_j\oplus a_i$ 我们移动一下就是 $(a_i\oplus b_i)\oplus (a_j\oplus b_j)=0$ 异或的性质

接着就用 map 来处理即可

6 代码

#include<bits/stdc++.h>
using namespace std;
int n,a[300010], b[300010];
long long ans = 0;
map<int, long long> mp;
int main()
{
    cin>>n;
    for (int i = 1; i <= n;i++) cin >> a[i];
    for (int i = 1; i <= n;i++) cin >> b[i];
    for (int i = 1; i <= n;i++) mp[a[i] ^ b[i]]++;
    for(auto v:mp) ans += v.second * v.second;
    cout << ans << '\n';
}

2 D 在仙境之外

兔子，兔子，拿饼干。
帽匠，帽匠，倒茶水。
柴郡猫将长桌铺整齐，
爱丽丝端来小茶杯；
旧访客啊，别哭泣，
茶会的准备已就绪。

给定一个长度为 $n+1$ 的序列 $a$ 的前 $n$ 项和一个数 $S$。$A_{n+1}$ ​ 初始为 $0$。将一次操作定义为 $a_i=a_j\oplus a_k$ ​，其中 $\oplus$ 为加减乘除（下取整）的一种。问是否能通过若干次操作使得 $a_{n+1}=S$。输出方案。

注意不要求 $i$, $j$, $k$ 互不相同。

1 输入描述:

第一行两个整数 $𝑛$, $𝑆$.

第二行 $𝑛$个整数，表示序列 $𝑎$.

2 输出描述:

第 1 行一个整数 𝑥,表示操作次数。

接下来 𝑥行，每行先输出三个整数 $i,j,k(1\le i,j,k\le n+1)$，含义同题目描述。再输出操作的符号 $+,-,\times ,/$ 其中之一，以一个空格分隔。

请保证运算过程中 $a_1,\dots ,a_{n+1}$ 时刻处于 $[0,2e18]$ 之间，操作次数不超过 $200$。

3 示例 1

3.1 输入

5 17
1 2 3 4 5

3.2 输出

2 2 4 *
6 6 1 +
6 6 2 +
6 6 3 +
6 6 5 +

4 说明

$a_2=a_2\times a_4=2\times 4=8$
$a_6=a_6+a_1=0+1=1$
$a_6=a_6+a_2=1+8=9$
$a_6=a_6+a_3=9+3=12$
$a_6=a_6+a_5=12+5=17$

5 备注:

对于所有数据，$1\le n\le {10}^5，1\le a_i,S\le {10}^{18}$。

首先通过自身与自身相除可以构造出 $1$,然后用类似于快速幂的方式即可构造出任意的 $S$。操作次数 $\le 2logV<200$。

6 代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, s;
vector<array<int, 4>> ans;
signed main()
{
    cin>>n>>s;
    ans.push_back({1, 1, 1, '/'});
    for (int i = 0; i < 60; i++)
    {
        if (s >> i & 1)
            ans.push_back({n + 1, 1, n + 1, '+'});
        ans.push_back({1, 1, 1, '+'});
    }
    cout << ans.size() << '\n';
    for (auto [a, b, c, d] : ans)//c++17
        cout << a << ' ' << b << ' ' << c << ' ' << char(d) << '\n';
}
// for (auto& arr : ans)//c++11
// {
//     int a, b, c, d;
//     tie(a, b, c, d) = make_tuple(get<0>(arr), get<1>(arr), get<2>(arr), get<3>(arr));
//     cout << a << ' ' << b << ' ' << c << ' ' << char(d) << '\n';
// }