牛客练习赛119

1 C 夜色亵渎者

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

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

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

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

请问 Alice 能答对多少道题。

1 输入描述:

第一行一个整数 𝑛。

第二行 𝑛 个整数 \(a_1​,a_2​,…,a_n\) ​。

第三行 𝑛 个整数 \(b_1​,b_2​,…,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≤n≤3×10^5,0≤a_i​,b_i​≤10^9\)。

考察异或的性质 异或：--- \(\bigoplus\) --- \(\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​⊕a_k\) ​，其中 \(⊕\) 为加减乘除（下取整）的一种。问是否能通过若干次操作使得 \(a_{n+1}​=S\)。输出方案。

注意不要求 \(i\), \(j\), \(k\) 互不相同。

1 输入描述:

第一行两个整数 \(𝑛\), \(𝑆\).

第二行 \(𝑛\)个整数，表示序列 \(𝑎\).

2 输出描述:

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

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

请保证运算过程中 \(a_1​,…,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≤n≤10^5，1≤a_i​,S≤10^{18}\)。

首先通过自身与自身相除可以构造出 \(1\),然后用类似于快速幂的方式即可构造出任意的 \(S\)。操作次数 \(≤2 logV<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';
// }