题目链接：AtCoder Beginner Contest 367
总结：发挥很一般，A一直wa。开场有点事，导致D也没debug出来。
A. Shout Everyday
tag：模拟
Solution：注意\(B > C\)与\(B < C\)的不同情况即可。
void solve(){
int a, b, c;
cin >> a >> b >> c;
if (c > b){
if (a >= c || a < b){
cout << "Yes\n";
}
else{
cout << "No\n";
}
}
else{
if (a >= c && a < b){
cout << "Yes\n";
}
else{
cout << "No\n";
}
}
}
B. Shout Everyday
tag：模拟
Solution：从后往前去掉对于的\(0\)，然后看是否需要去掉.。
void solve(){
string s;
cin >> s;
int i;
for (i = s.size() - 1; i > 0; i --){
if (s[i] != '0')
break;
}
if (s[i] == '.'){
for (int j = 0; j < i; j ++)
cout << s[j];
}
else{
for (int j = 0; j <= i; j ++)
cout << s[j];
}
}
C. Enumerate Sequences
tag：dfs
Solution：根据题意模拟即可
void solve(){
int n, k;
cin >> n >> k;
vector<int> a(n + 10);
for (int i = 1; i <= n; i ++)
cin >> a[i];
function<void(int, string)> dfs = [&](int s, string ans) {
if (s == n){
int sum = 0;
for (int i = 0; i < n; i ++)
sum += ans[i] - '0';
if (sum % k == 0){
for (int i = 0; i < n; i ++){
cout << ans[i] << " ";
}
cout << endl;
}
}
else{
for (int i = 1; i <= a[s + 1]; i ++){
dfs(s + 1, ans + char(i + '0'));
}
}
};
dfs(0, "");
}
D. Pedometer
tag：前缀和哈希 + 环形
Solution：很典的前缀和哈希。但是需要处理一个环形，同时注意值的计算，\(i -> i + 1\)的值为\(a_i\)。
- 第一轮循环处理：s < t的情况
- 第二轮循环处理：s > t的情况（注意这里不能重复计算s < t的方案数）
Competing：没注意到从\(i -> i + 1\)是\(a_i\)，而不是\(a_i + a_{i + 1}\)。
void solve(){
cin >> n >> m;
vector<int> a(n + 10);
for (int i = 1; i <= n; i ++)
cin >> a[i];
int ans = 0;
map<int, int> mp;
int t = 0;
for (int i = 1; i <= n; i ++){ // 第一次处理s < t的情况
// 以i为结尾
ans += mp[t];
mp[t] ++;
t = (t + a[i]) % m;
}
int res = 0;
for (int i = 1; i < n; i ++){ // 注意这里小于n
mp[res % m] --;
ans += mp[t % m];
res = (res + a[i]) % m;
t = (t + a[i]) % m; // 这里mp[t]不需要再加了,否则会重复计算s < t的方案数
}
cout << ans;
}
E. Permute K times
tag：倍增
Description：给定两个长度为\(n\)的数组\(x, a\)，需要执行\(k\)次操作，每次操作：
- 先令所有\(b_i = a_{x_i}\), 然后令\(a = b\)。
- 求最后的\(a\)数组。
- \(1 <= n <= 2 * 10^5, 0 <= k <= 10^{18}\)。
Solution：注意到\(x\)数组是不变的，意味着第\(i\)个位置的变化是固定的：$i -> x_i -> x_{x_i}。 - 我们需要知道第\(i\)个数变换\(k\)次之后所在的位置，但是\(k\)的范围很大，考虑预处理。
- 使用倍增预处理：\(f[i][j]\)表示第\(i\)个位置的数，执行\(2^j\)次操作后所在的位置。
- \(f[i][j] = f[f[i][j - 1]][j - 1]\)
int f[N][65];
void solve(){
cin >> n >> k;
vector<int> x(n + 1), a(n + 1);
for (int i = 1; i <= n; i ++)
cin >> x[i];
for (int i = 1; i <= n; i ++)
cin >> a[i];
for (int j = 0; j <= 64; j ++){
for (int i = 1; i <= n; i ++){
if (!j){ // 第i个元素执行2^j操作后的位置
f[i][j] = x[i];
}
else{
f[i][j] = f[f[i][j - 1]][j - 1];
}
}
}
vector<int> t;
for (int i = 0; i < 64; i ++){
if ((k >> i) & 1){
t.push_back(i);
}
}
for (int i = 1; i <= n; i ++){
int tt = i;
for (int j : t){
tt = f[tt][j];
}
cout << a[tt] << " ";
}
}
F. Rearrange Query
tag：哈希
Description：给定两个长度为\(n\)的数组\(a, b\)，执行\(Q\)次查询，每次查询给定：
- \(l1, r1, l2, r2\)，询问\(a[l1, r1], b[l2, r2]\)区间内的数，重新排序后是否能够匹配。
- \(1 <= n, Q <= 2 * 10^5, 1 <= a_i, b_i <= n\)。
Solution：我们需要统计区间内每个数出现的次数，但是每次查询暴力查询显然会超时。 - 类似字符串哈希，我们将每个数哈希为一个\(N\)位\(M\)进制的数。
void solve(){
cin >> n >> k;
vector<ull> p(n + 10);
p[0] = 1;
for (int i = 1; i <= n; i ++)
p[i] = p[i - 1] * 1331;
vector<ull> ha(n + 10), hb(n + 10);
for (int i = 1; i <= n; i ++){
int x;
cin >> x;
ha[i] = ha[i - 1] + p[x];
}
for (int i = 1; i <= n; i ++){
int x;
cin >> x;
hb[i] = hb[i - 1] + p[x];
}
function<bool(int, int, int, int)> query = [&](int l1, int r1, int l2, int r2) {
ull a = ha[r1] - ha[l1 - 1];
ull b = hb[r2] - hb[l2 - 1];
return a == b;
};
while (k --){
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
if (query(l1, r1, l2, r2)){
cout << "Yes\n";
}
else{
cout << "No\n";
}
}
}