ABC367(A-F)
A - Shout Everyday¶
题目大意
给你时钟上的三个数字 \(A, B, C(0 \le A, B, C \le 23)\)，问：从 \(B\) 时走到 \(C\) 时的过程中是否经过 \(A\) 时？如果不经过 \(A\) 输出 Yes，否则输出 No
参考代码
#include <iostream>
using namespace std;
int main()
{
int a, b, c;
cin >> a >> b >> c;
int ba = (a - b + 24) % 24;
int bc = (c - b + 24) % 24;
cout << (ba <= bc ? "No" : "Yes") << endl;
return 0;
}
B - Cut .0¶
题目大意
给你一个实数，去除这个实数小数点之后的后导 \(0\)，如果小数点之后所有的后导 \(0\) 都被去掉了，将小数点也去掉。
参考代码
#include <iostream>
#include <string>
using namespace std;
int main()
{
string s;
cin >> s;
while(s.back() == '0')
s.pop_back();
if(s.back() == '.')
s.pop_back();
cout << s << endl;
return 0;
}
C - Enumerate Sequences¶
题目大意
给你一个长度为 \(N(1 \le N \le 8)\) 的序列 \(R = (R_1, R_2, \cdots, R_N)\)，其中 \(1 \le R_i \le 5\)，然后给你一个整数 \(K(2 \le K \le 10)\)。输出所有满足以下条件的长度为 \(N\) 的序列 \(A = (A_1, A_2, \cdots,A_N)\)：
- \(1 \le A_i \le R_i\)
- \(\sum\limits_{i = 1} ^ N A_i\) 是 \(K\) 的倍数。
解题思路
dfs 即可。
参考代码
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
vector<int> r(n);
for (int i = 0; i < n; i++)
cin >> r[i];
vector<int> now(n);
auto dfs = [n, k, &r, &now](auto &self, int i) -> void
{
if (i == n)
{
int sum = accumulate(now.begin(), now.end(), 0);
if (sum % k == 0)
{
for (auto x : now)
cout << x << ' ';
cout << endl;
}
return;
}
for (int x = 1; x <= r[i]; x++)
{
now[i] = x;
self(self, i + 1);
}
};
dfs(dfs, 0);
return 0;
}
D - Pedometer¶
题目大意
有一个环形的湖，湖的外围有 \(N(2 \le N \le 2 \times 10 ^ 5)\) 个休息点。第 \(i\) 个休息点（顺时针方向的）下一个休息点是第 \(i + 1\) 个休息点，特别的，第 \(N\) 个休息点（顺时针方向的）下一个休息点是第 \(1\) 个休息点。从休息点 \(i\) 出发需要（顺时针）走 \(A_i\) 步才能走到下一个休息点。人们只能顺时针走到下一个休息点，而不能逆时针走到上一个休息点。
问：有多少个数对 \((s, t)\) 满足以下条件？
- \(1 \le s, t \le N\) 且 \(s \ne t\)
- 从第 \(s\) 个休息点第一次走到第 \(t\) 个休息点所走的步数是 \(M\) 的倍数。
解题思路
先考虑没有环的情况，即假设 \(N\) 和 \(1\) 不连通。处理一个前缀和
当 \(r\) 固定时，等价于求出满足 \(S[r] \equiv S[l-1] \bmod 0\) 的 \(l\) 的个数。这可以维护哈希表实现，哈希表中记录下 \(S[r] \bmod M\) 的个数即可。
下面考虑有环的情况，开两倍长度的前缀和。由于只需考虑顺时针一个方向，所以遍历的方式仍然是从前往后，但要注意要求的是第一次从 \(s\) 走到 \(t\) 的距离，所以可以维护过去 \(N-1\) 个前缀和中 \(S[r] \bmod M\)，在枚举的时候按照滑动窗口的方式更新即可。
参考代码
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n, m;
cin >> n >> m;
vector<int> s(2 * n + 1);
for (int i = 1; i <= n; i++)
{
cin >> s[i];
s[i + n] = s[i];
}
for (int i = 1; i <= 2 * n; i++)
s[i] = (s[i - 1] + s[i]) % m;
unordered_map<int, int> cnt;
for (int i = 1; i < n; i++)
cnt[s[i]]++;
LL ans = 0;
for(int i = 1, j = n; i <= n; i++, j++)
{
ans += cnt[s[j]];
cnt[s[i]]--;
cnt[s[j]]++;
}
cout << ans << endl;
return 0;
}
E - Permute K times¶
题目大意
给你两个长度为 \(N(1 \le N \le 2 \times 10 ^ 5)\) 的序列 \(X = (X_1, X_2, \cdots, X_N)\) 和 \(A = (A_1, A_2, \cdots, A_N)\)，其中 \(1 \le X_i \le N\)，\(1 \le A_i \le 2 \times 10 ^ 5\)。再给你一个整数 \(K(0 \le K \le 10^{18})\)，你需要执行以下操作 \(K\) 次：
- 根据 \(B_i = A_{X_i}\) 求出新的序列 \(B = (B_1, B_2, \cdots, B_N)\)，然后 \(A \leftarrow B\)，用 \(B\) 序列替换 \(A\) 序列。
求出在执行 \(K\) 次之后的序列 \(A\)。
解题思路
前置知识：置换操作，不懂的可以先看 P5151 HKE与他的小朋友 - 洛谷 | 计算机科学教育新生态
关键还是要理解置换的含义。
置换操作实际是满足结合律的，所以可以用快速幂来加速计算。洛谷这道题的置换是指“将 \(i\) 位置换到 \(P_i\)”，一次运算就是 \(i \rightarrow P_i\)，结合起来的运算就是 \(i \rightarrow P_i \rightarrow P_{P_i}\)。
而 ABC 这道题是置换是指将 \(X_i\) 上的元素换到 \(i\)，一次运算就是 \(X_i \rightarrow i\)，结合起来的运算就是 \(X_{X_i} \rightarrow X_i \rightarrow i\)
参考代码
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
int main()
{
int n;
LL k;
cin >> n >> k;
vector<int> p(n + 1), temp(n + 1), ans(n + 1), a(n + 1);
for (int i = 1; i <= n; i++)
{
cin >> p[i];
ans[i] = i;
}
for (int i = 1; i <= n; i++)
cin >> a[i];
while (k)
{
if (k & 1)
{
for (int i = 1; i <= n; i++)
temp[i] = ans[p[i]];
ans = temp;
}
for (int i = 1; i <= n; i++)
temp[i] = p[p[i]];
p = temp;
k >>= 1;
}
for(int i = 1; i <= n; i++)
temp[i] = a[ans[i]];
for(int i = 1; i <= n; i++)
cout << temp[i] << ' ';
return 0;
}
F - Rearrange Query¶
题目大意
给你两个长度为 \(N(1 \le N \le 2 \times 10 ^5)\) 的序列 \(A = (A_1, A_2, \cdots, A_N)\) 和 \(B = (B_1, B_2, \cdots, B_N)\)，其中 \(1 \le A_i, B_i \le N\)。给你 \(Q(1 \le Q \le 2 \times 10 ^5)\) 个询问，每个询问包括四元组 \((l_i, r_i, L_i, R_i)\)，你需要回答出能否通过重排 \((A_{l_i}, A_{l_i+1}, \cdots, A_{r_i})\) 使其等于 \((B_{L_i}, B_{L_i+1}, \cdots, B_{R_i})\)，如果可以输出 Yes，否则输出 No。
解题思路
重排操作判定序列相等本质上就是判定两个可重集合是否相等。而这个操作是需要 \(O(N)\) 时间的，所以不能直接判定集合是否相等。
本题的正解是将每个数字映射成一个随机的哈希值，用哈希值的区间和代替一个集合，这样判等的时候直接比较区间和即可。在实现如何将数字映射成哈希这一步，可以随机生成数字、也可以用高低位异或法实现。下面的解法用的是随机数。
参考代码
#include <iostream>
#include <random>
#include <unordered_map>
#include <vector>
using namespace std;
using LL = long long;
const LL MOD = (1ll << 61) - 1;
int main()
{
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<LL> dist(1, MOD - 1);
int n, q;
cin >> n >> q;
vector<LL> a(n + 1), b(n + 1);
unordered_map<LL, LL> mp;
auto mapping = [&mp, &dist, &gen](int num) -> LL
{
auto it = mp.find(num);
return it == mp.end() ? mp[num] = dist(gen) : it->second;
};
for (int i = 1; i <= n; i++)
{
cin >> a[i];
a[i] = (mapping(a[i]) + a[i - 1]) % MOD;
}
for (int i = 1; i <= n; i++)
{
cin >> b[i];
b[i] = (mapping(b[i]) + b[i - 1]) % MOD;
}
auto check = [&a, &b](int l1, int r1, int l2, int r2) -> bool
{ return r2 - l2 == r1 - l1 && (a[r1] - a[l1 - 1] + MOD) % MOD == (b[r2] - b[l2 - 1] + MOD) % MOD; };
while (q--)
{
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
cout << (check(l1, r1, l2, r2) ? "Yes" : "No") << endl;
}
return 0;
}
创建日期: 2024-11-07