Atcoder Beginner Contest 367 C-F
C - Enumerate Sequences
题意
按字典序升序输出所有满足下列条件的序列数量。
-
长度为 \(N\)。
-
第 \(i\) 个元素介于 \(1\) 与 \(R_i\) 之间。
-
所有元素之和是 \(K\) 的倍数。
思路
搜索即可。搜索时记录当前选了哪些数和元素之和，最后搜完了判断一下即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, k, a[N], R[N];
void dfs(int x, int sum) {
if (x == n + 1) {
if (sum % k) return ;
for (int i = 1; i <= n; i ++) {
cout << a[i] << " ";
}
cout << "\n";
return ;
}
for (int i = 1; i <= R[x]; i ++) {
a[x] = i;
dfs(x + 1, sum + i);
}
}
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i ++) cin >> R[i];
dfs(1, 0);
cout << "\n";
}
int main() {
int T = 1;
// cin >> T;
while (T --) solve();
return 0;
}
D - Pedometer
题意
一个湖周围有 \(N\) 个休息区。
从休息区 \(i\) 顺时针走到休息区 \(i+1\) 需要 \(A_i\) 步，其中休息区 \(N+1\) 指的是休息区 \(1\)。
从休息区 \(s\) 顺时针走到休息区 \(t(s \ne t)\) 所需的最小步数是 \(M\) 的倍数。
求 \((s,t)\) 的可能对数。
思路
容易想到把原序列复制一遍破环成链。
把原 \(A\) 数组做一遍前缀和，得到 \(S\)。
\(s\) 到 \(t\) 的距离为 \(S_t-S_s\)，其中 \(s < t < s + n\)。
若 \(t \ge s + n\) 相当于绕了整个湖一圈，不符合题意。
原问题转化为了有多少对 \((i,j)\) 满足 \((i<j<i+n)\) 且 \(S_j-S_i \equiv 0\pmod{M}\)。
转化一下即 \(S_j \equiv S_i \pmod{M}\)。
使用一个桶维护 \(S_i\) 对 \(M\) 取余的结果。
倒序枚举 \(i\)，把 \(S_{i+n}\) 从桶中删除，在桶里查询有多少个 \(j\) 满足条件，并把 \(S_i\) 加入桶中。
预处理时把 \(S_{n+1}\) 到 \(S_{2n}\) 都加入桶中。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int n, m, a[N], c[N];
ll ans;
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i ++)
cin >> a[i + 1], a[i + n + 1] = a[i + 1],
a[i + 1] %= m, a[i + n + 1] %= m;
for (int i = 1; i <= 2 * n; i ++) a[i] += a[i - 1], a[i] %= m;
for (int i = n + 1; i <= 2 * n; i ++) c[a[i]] ++;
for (int i = n; i >= 1; i --) {
c[a[i + n]] --;
ans += c[a[i]];
c[a[i]] ++;
}
cout << ans << "\n";
}
signed main() {
int T = 1;
// cin >> T;
while (T --) solve();
return 0;
}
E - Permute K times
题意
给你一个长度为 \(N\) 的序列 \(X\)，其中每个元素的都在 \(1\) 和 \(N\) 之间。
以及一个长度为 \(N\) 的序列 \(A\)。
输出在 \(A\) 上执行以下操作 \(K\) 次的结果。
用 \(B\) 替换 \(A\)，其中 \(B_i = A_{X_i}\)。
思路
因为 \(1 \le K \le 10^{18}\)，暴力枚举肯定不行，考虑使用倍增。
\(f_{i,j}\) 表示 \(i\) 变换 \(2^j\) 次后变成的数，\(i\) 和 \(j\) 均为下标。
\[f_{i,j} = f_{f_{i, j-1},j -1} \]计算答案时对于每个 \(i\) 计算最后变成的下标 \(j\)，输出 \(A_j\)。
计算时若 \(K\) 二进制下第 \(p\) 位为 \(1\)，则将 \(i\) 变为 \(f_{i,p}\)。
即将 \(i\) 做 \(2^p\) 次转换，最后合起来即 \(K\) 次转换。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, k, a[N], f[N][70], b[N];
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i ++) cin >> f[i][0];
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= 59; i ++)
for (int j = 1; j <= n; j ++)
f[j][i] = f[f[j][i - 1]][i - 1];
for (int i = 1; i <= n; i ++) {
int now = i;
for (int j = 0; j <= 59; j ++)
if (k >> j & 1) now = f[now][j];
cout << a[now] << " ";
}
}
signed main() {
int T = 1;
// cin >> T;
while (T --) solve();
return 0;
}
F - Rearrange Query
题意
给你长度为 \(N\) 的正整数序列：\(A\) 和 \(B\)。
您需要依次处理 \(Q\) 个查询。
给定正整数 \(l_i,r_i,L_i,R_i\)。如果可以重新排列子序列 \((A_{l_i},A_{l_i+1},\ldots,A_{r_i})\) 以匹配子序列 \((B_{L_i},B_{L_i+1},\ldots,B_{R_i})\)，则打印是，否则打印否。
思路
若 \((A_{l_i},A_{l_i+1},\ldots,A_{r_i})\) 中每个数出现的次数和 \((B_{L_i},B_{L_i+1},\ldots,B_{R_i})\) 中每个数出现的次数一样，则一定可以完成匹配，证明显然。
如何比较数的出现次数呢？我们想到了哈希，把每个数的出现次数哈希起来。
相当于把数的出现次数转化成一个 \(N\) 位 \(M\) 进制的数，每位存放 \(i\) 出现的次数，使用自然溢出即可。统计时运用前缀和快速计算哈希值。
进制可以乱设，但尽量大于 \(N\) 并且最好为质数。
可以使用双哈希以提高正确率。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
const int N = 2e5 + 5;
int n, q, a[N], b[N];
ull ha[N], hb[N], pw[N];
ull getHA(int l, int r) {
return ha[r] - ha[l - 1];
}
ull getHB(int l, int r) {
return hb[r] - hb[l - 1];
}
ui ha2[N], hb2[N], pw2[N];
ui getHA2(int l, int r) {
return ha2[r] - ha2[l - 1];
}
ui getHB2(int l, int r) {
return hb2[r] - hb2[l - 1];
}
void solve() {
cin >> n >> q;
pw[0] = 1, pw2[0] = 1;
for (int i = 1; i <= n; i ++) pw[i] = pw[i - 1] * 19260817;
for (int i = 1; i <= n; i ++) pw2[i] = pw2[i - 1] * 998244353;
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 ++)
ha[i] = ha[i - 1] + pw[a[i]],
ha2[i] = ha2[i - 1] + pw2[a[i]];
for (int i = 1; i <= n; i ++)
hb[i] = hb[i - 1] + pw[b[i]],
hb2[i] = hb2[i - 1] + pw2[b[i]];
while (q --) {
int l, r, L, R;
cin >> l >> r >> L >> R;
ull HA, HB;
HA = getHA(l, r);
HB = getHB(L, R);
ui HA2, HB2;
HA2 = getHA2(l, r);
HB2 = getHB2(L, R);
if (HA == HB && HA2 == HB2) cout << "Yes\n";
else cout << "No\n";
}
}
int main() {
int T = 1;
// cin >> T;
while (T --) solve();
return 0;
}