当前位置：首页 > news >正文

AtCoder Beginner Contest 367 A~F

news 2025/11/29 15:41:33

A.Shout Everyday（枚举）

题意：

在 $A tC o d er$ 王国，居民们每天都要在 $A$ 点大声喊出他们对章鱼烧的热爱。

住在 $A tC o d er$ 王国的高桥每天 $B$ 点睡觉， $C$ 点起床（ $24$ 小时钟）。他醒着的时候可以喊出对章鱼烧的爱，但睡着的时候却不能。判断他是否每天都能喊出对章鱼烧的爱。这里，一天有 $24$ 小时，而他的睡眠时间小于 $24$ 小时。

分析：

直接从 $A$ 枚举到 $B$ ，观察是否遍历到 $C$ 即可。

代码：

#include <bits/stdc++.h>
using namespace std;int main() {int a, b, c;cin >> a >> b >> c;int flag = 1;for (; a != b; a = (a + 1) % 24) {if (a == c) {flag = 0;break;}}if (flag)cout << "Yes" << endl;elsecout << "No" << endl;return 0;
}

B.Cut .0（模拟）

题意：

一个实数 $X$ 已精确到小数点后第三位。
请在下列条件下打印实数 $X$ 。

小数部分不能有尾数 “0”。
小数点后不能有多余的尾数。

分析：

按照题意模拟即可。

代码：

#include <bits/stdc++.h>
using namespace std;int main() {string s;cin >> s;while (s.size() > 2 && s.back() == '0') {s.pop_back();}if (s.back() == '.') {s.pop_back();}cout << s << endl;return 0;
}

C.Enumerate Sequences（dfs）

题意：

按升序排列打印所有满足以下条件的长度为 $N$ 的整数序列。

第 $i$ 个元素介于 $1$ 和 $R_i$ 之间。
所有元素之和是 $K$ 的倍数。

什么是序列的词序？如果下面的 1. 或 2. 成立，那么序列 $(A_1, \ldots, A_{|A|})$ 在词法上小于 $(B_1, \ldots, B_{|B|})$ ：

$∣ A ∣ < ∣ B ∣$ 和 $(A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|})$ .
存在一个整数 $1\leq i\leq \min\{|A|,|B|\}$ ，使得下面两个条件都成立：
- $(A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})$
- $A_i < B_i$

分析：

我们用 $df s$ 按照要求依次搜索即可。

代码：

#include<bits/stdc++.h>
using namespace std;int n, k, r[15], a[15];void dfs(int x, int sum) {if (x == n + 1) {if (sum % k == 0) {for (int i = 1; i <= n; i++) {cout << a[i] << ' ';}cout << endl;}return;}for (int i = 1; i <= r[x]; i++) {a[x] = i;dfs(x + 1, sum + i);}
}int main(){cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> r[i];}dfs(1, 0);return 0;
}

D.Pedometer （思维）

题意：

一个湖周围有 $N$ 个休息区。
这些休息区按顺时针顺序编号为 $1$ 、 $2$ 、…、 $N$ 。
从休息区 $i$ 顺时针走到休息区 $i + 1$ 需要 $A_i$ 步（其中休息区 $N + 1$ 指的是休息区 $1$ ）。
从休息区 $s$ 顺时针走到休息区 $t$ （ $\neq t$ ）所需的最小步数是 $M$ 的倍数。
求 $(s, t)$ 的可能对数。

分析：

当 $\rightarrow t$ 有两种路径， $s < t$ 时，我们有 $\equiv 0(mod M)$ 。当 $s > t$ 时，我们有 $\equiv 0(mod M)$ 。移项后有 $\equiv pre[s] - pre[n] (mod M)$

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;int main() {int n, m;cin >> n >> m;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}vector<LL> pre(n + 1);for (int i = 0; i < n; i++) {pre[i + 1] = pre[i] + a[i];}LL ans = 0;map<int, int> mp;for (int i = 0; i < n; i++) {ans += mp[((pre[i] - pre[n]) % m + m) % m];ans += mp[pre[i] % m];mp[pre[i] % m]++;}cout << ans << endl;return 0;
}

E.Permute K times （倍增）

题意：

给你一个长度为 $N$ 的序列 $X$ ，其中每个元素都在 $1$ 和 $N$ 之间（包括首尾两个元素），以及一个长度为 $N$ 的序列 $A$ 。请输出在 $A$ 上执行以下操作 $K$ 次的结果。

用 $B$ 替换 $A$ ，使得 $B_i = A_{X_i}$ .

分析：

将题目转化成给定基环森林，点有点权。问从每个点出发，走了 $k$ 步后的点的点权。其中边是 $\rightarrow x_i$ ，点权 $a_i$ 。问第 $k$ 步后到达的点。我们预处理出倍增数组 $t m p [i] [j]$ 表示从点 $j$ 出发走了 $2^i$ 步后到达的点。然后对于每个点用倍增数组求 $k$ 次后的结果即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;int main() {int n;LL k;cin >> n >> k;vector<vector<int> > tmp(64, vector<int>(n));for (int i = 0; i < n; i++) {int v;cin >> v;v--;tmp[0][i] = v;}vector<int> a(n);for (auto &x: a)cin >> x;for (int i = 1; i < 64; i++) {for (int j = 0; j < n; j++) {tmp[i][j] = tmp[i - 1][tmp[i - 1][j]];}}for (int i = 0; i < n; i++) {LL cnt = k;int cur = i;for (int j = 0; j < 64; j++) {if (cnt & (1LL << j)) {cur = tmp[j][cur];}}cout << a[cur] << " ";if (i == n - 1)cout << endl;}return 0;
}

F.Rearrange Query （哈希）

题意：

给你长度为 $N$ 的正整数序列： $A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$ .

给你 $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})$ ，则输出Yes，否则输出 No。

分析：

如果 $A [l, r]$ 序列的能通过重排得到 $B [L, R]$ ，首先要满足 $r - l = R - L$ ，再观察每个数的出现次数是否一致。存在一个降低计算代价的必要条件是 $sum_a[l,r]=sum_b[L,R]$ ，但不是充分条件，会有误判的概率，
但是因为我们只要求数量相等，所以我们事先对所有数进行一个随机映射，那么这个误判的概率将极大减小。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;
typedef unsigned long long ULL;ULL rnd() {static ULL A = 1 << 16 | 3, B = 333333331, C = 2341;return C = A * C + B;
}int main() {int n, q;cin >> n >> q;vector<LL> a(n);vector<LL> b(n);map<LL, LL> mp;for (auto &x: a) {cin >> x;if (mp.find(x) == mp.end()) {mp[x] = rnd();}}for (auto &x: b) {cin >> x;if (mp.find(x) == mp.end()) {mp[x] = rnd();}}auto presum = [&](vector<LL> &a) {int n = a.size();vector<LL> s1(n + 1);for (int i = 0; i < n; ++i) {s1[i + 1] = (s1[i] + mp[a[i]]);}return s1;};auto pa1 = presum(a);auto pb1 = presum(b);auto sum = [&](vector<LL> &s, int l, int r) { return (s[r] - s[l - 1]); };auto check = [&](int l, int r, int L, int R) {auto PA = sum(pa1, l, r);auto PB = sum(pb1, L, R);return PA == PB;};while (q--) {int l, r, L, R;cin >> l >> r >> L >> R;if (r - l == R - L && check(l, r, L, R)) {cout << "Yes" << endl;} else {cout << "No" << endl;}}return 0;
}