A - Jiro (abc371 A)
题目大意
三个人，给定他们相互之间的大小关系。
问谁在中间。
解题思路
排个序，大小结果就是题目给的，因为问的是中间是谁，所以写的时候并没在意是升序排还是降序排。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string a, b, c;
cin >> a >> b >> c;
array<int, 3> id{};
iota(id.begin(), id.end(), 0);
map<pair<int, int>, int> mp;
mp[{0, 1}] = a[0] == '>';
mp[{1, 0}] = a[0] == '<';
mp[{0, 2}] = b[0] == '>';
mp[{2, 0}] = b[0] == '<';
mp[{1, 2}] = c[0] == '>';
mp[{2, 1}] = c[0] == '<';
sort(id.begin(), id.end(), [&](int x, int y) { return mp[{x, y}]; });
string ans = "ABC";
cout << ans[id[1]] << '\n';
return 0;
}
B - Taro (abc371 B)
题目大意
\(n\)个家庭，依次出生 \(m\)个孩子，每个家庭的第一个出生的男婴儿会授予名字 taro。
依次回答每个孩子的名字是不是taro。
解题思路
维护每个家庭是否有男婴儿出生，然后依次判断每个孩子是不是男的，且是第一个男的即可。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> tora(n, 0);
while (m--) {
int f;
string s;
cin >> f >> s;
--f;
if (s[0] == 'F' || tora[f]) {
cout << "No" << '\n';
} else {
tora[f] = 1;
cout << "Yes" << '\n';
}
}
return 0;
}
C - Make Isomorphic (abc371 C)
题目大意
给定两张无向图\(G,H\)。
给定一个操作代价，在图\(H\)中给\((i,j)\)连一条边或删一条边的花费 \(a_{ij}\)。
问最小的代价，使得两张图同构。
解题思路
同构即存在一种点标号的映射关系，使得映射后两张图一模一样（包括点标号和对应的边）。
由于点数只有\(8\)，我们先花 \(O(8!)\)枚举这个映射（即一个排列），然后看这个映射关系下，使得两张图相等所需要的代价。
计算代价即花\(O(n^2)\)的时间，枚举所有的边\((i,j), i < j\)，如果 \(G\)存在该边但\(H\)不存在或\(G\)不存在但 \(H\)存在，进行一次操作。 所有的操作代价累加即为该映射关系的操作代价。
所有的映射关系的代价的最小值即为答案。
时间复杂度为\(O(n!n^2)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
array<int, 2> m{};
array<vector<vector<int>>, 2> edge{vector<vector<int>>(n, vector<int>(n)),
vector<vector<int>>(n, vector<int>(n))};
for (int k = 0; k < 2; ++k) {
cin >> m[k];
for (int i = 0; i < m[k]; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
edge[k][u][v] = edge[k][v][u] = 1;
}
}
vector<vector<int>> a(n, vector<int>(n, 0));
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
cin >> a[i][j];
a[j][i] = a[i][j];
}
vector<int> id(n);
iota(id.begin(), id.end(), 0);
int ans = 1e9 + 7;
auto solve = [&](vector<int> id) {
int res = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (edge[0][id[i]][id[j]] != edge[1][i][j]) {
res += a[i][j];
}
}
}
return res;
};
do {
ans = min(ans, solve(id));
} while (next_permutation(id.begin(), id.end()));
cout << ans << '\n';
return 0;
}
D - 1D Country (abc371 D)
题目大意
一维数轴，给定\(n\)个村落的位置和人口。
\(q\)个询问，每个询问给定 \(l,r\)，问位于\(l,r\)之间的村落人口数量。
解题思路
题意给的村落位置本身有序。
直接维护关于村落的人口前缀和。
对于每个询问，二分找到位于\(l,r\)区间的村落的左右端点，然后通过前缀和求得这期间的人口数量。
时间复杂度是\(O(q\log n)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> x(n);
for (auto& i : x)
cin >> i;
vector<LL> p(n);
for (auto& i : p)
cin >> i;
vector<LL> presum(n);
partial_sum(p.begin(), p.end(), presum.begin());
auto get_sum = [&](int l, int r) {
if (l > r)
return 0ll;
return presum[r] - (l ? presum[l - 1] : 0);
};
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
auto L = lower_bound(x.begin(), x.end(), l) - x.begin();
auto R = upper_bound(x.begin(), x.end(), r) - x.begin();
cout << get_sum(L, R - 1) << '\n';
}
return 0;
}
E - I Hate Sigma Problems (abc371 E)
题目大意
给定\(n\)个数 \(a\)，定义 \(f(l,r)\)表示区间 \([l,r]\)的数的种类。
求 \(\sum_{i=1}^{n}\sum_{j=i}^{n} f(i,j)\)
解题思路
考虑枚举\(j\)的话会发现不太可行，考虑直接的一个排列 \(1,2,3,4,5...\)，对于每个 \(j\)，每个\(i\)都对应了一个不同的\(f(i,j)\) ，感觉无法合并。
考虑答案的来源，即贡献的来源，是每一个数。比如\(2,3,2,5\)， \(f(2,3) = 2 = 1 + 1\)， \(3,2\)分别对答案有 \(1\)的贡献。而 \(f(1,3) = 2 = 1 + 1\)，这里同样是 \(3,2\)对答案有 \(1\)的贡献，但这里有两个 \(2\)，只有其中的一个才有 \(1\)的贡献，我们可以规定最右边的 \(2\)有 \(1\)的贡献。
我们的视角从 求\(f(l,r)\)的值 变成了求 每一个数 \(a_i\) 在多少个区间 \((l,r)\)有 \(1\)的贡献。
很显然，这个\(l\)的取值是 \([1,l]\)， 而\(r\)的取值要满足 \([i,r]\)没有另一个 \(a_i\)，即计 \(nxt_i\)表示下一个 \(a_i\)的位置，那么 \(r\)的取值就是 \([i,nxt_i)\)。因此对于一个\(a_i\)，它有贡献的区间数量即为 \(i \times (nxt_i - i)\) 。所有的\(a_i\)累加即为答案。
而 \(nxt_i\)的求法就倒序扫一遍，维护 \(last_i\)表示上一个数 \(i\)出现的位置即可。
即答案就是 \(\sum_{i=1}^{n} i(nxt_i - i)\)，时间复杂度是\(O(n)\)。
神奇的代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> a(n);
for (auto& i : a) {
cin >> i;
--i;
}
vector<int> r(n);
vector<int> pos(n, n);
for (int i = n - 1; i >= 0; --i) {
r[i] = pos[a[i]];
pos[a[i]] = i;
}
fill(pos.begin(), pos.end(), 0);
LL ans = 0;
for (int i = 0; i < n; ++i) {
int lcnt = i + 1;
int rcnt = r[i] - i;
ans += 1ll * lcnt * rcnt;
}
cout << ans << '\n';
return 0;
}
F - Takahashi in Narrow Road (abc371 F)
题目大意
一维数轴，\(n\)个人，依次完成以下 \(q\)个目标。
对于第 \(i\)个目标，让第 \(t_i\)个人移动到 \(q_i\)位置。
每次操作，可以让一个人向左右移动一格，如果目标位置有人则不能移动，得让对方先移动。
求完成所有目标所需要的最小操作次数。
解题思路
研究G题了这题还没看好像就是一棵珂朵莉树
神奇的代码
G - Lexicographically Smallest Permutation (abc371 G)
题目大意
给定两个排列\(p,a\)。
可进行一种操作任意次，即令 \(a_i = a_{p_i}\)。
问得到的 \(a\)的字典序的最小值。
解题思路
替换操作可以看成是有若干个环的图，有连边\(i \to p_i\)。
问题就是求一个 \(x\)，使得每个点往前走 \(x\)步，得到的新的数组的字典序最小。
由字典序的比较顺序，首先是让第一个数最小。
那就找第一个数所在的环，遍历一遍，找到数最小的位置，得到一个偏移量 \(b\)。记该环的大小为\(a\)。
这样，只要我们最后的偏移量 \(x\)满足 \(x \equiv b (\mod a)\)，这样第一个位置就是最小的情况。
然后考虑下一个数所在的环（如果和\(1\)在同一个环，就忽略，继续找下一个不在之前考虑的环），在该环中，我们同样要找最小的值，但和之前直接遍历环的每个元素不同，由于之前有个限制\(x \equiv b (\mod a)\)，因此在该环里，我们只能看第\(x\)个点，第 \(x + a\)个点，第 \(x + 2a\)个点，...，这哪个点权最小（要保持不破坏之前考虑的环的偏移量）。
假设在有限个点，我们找到数最小的位置 \(B\)，即该环的大小为 \(A\)，那就是说，我们最终的偏移量 \(x\)要满足两个同余等式： \(x \equiv b (\mod a)\)和\(x \equiv B (\mod A)\)，通过扩展中国剩余定理可以将其合并成一个等价的同余式\(x \equiv b_0 (\mod a_0)\)。
然后就继续遍历剩下的环，不断合并同余式，最后偏移量就是\(b_0 \% a_0\)。
据官方题解，\(a,b\)的值会超\(2^{2367}\)，因此下面的\(c++\)代码尽管开了 __in128仍会爆。
c++代码
#include <bits/stdc++.h>
using namespace std;
using LL = __int128;
LL x, y, d;
void exgcd(LL& x, LL& y, LL a, LL b) {
if (!b)
d = a, x = 1, y = 0;
else
exgcd(y, x, b, a % b), y -= a / b * x;
}
LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }
LL a, b, A, B;
void merge() {
exgcd(x, y, a, A);
LL c = B - b;
assert(c % d == 0);
x = x * c / d % (A / d);
if (x < 0)
x += A / d;
LL mod = lcm(a, A);
b = (a * x + b) % mod;
if (b < 0)
b += mod;
a = mod;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
vector<int> p(n), v(n);
for (auto& i : p) {
cin >> i;
--i;
}
for (auto& i : v)
cin >> i;
vector<vector<int>> cir;
vector<int> vis(n);
for (int i = 0; i < n; ++i) {
if (vis[i])
continue;
vector<int> h{i};
for (int j = p[i]; j != i; j = p[j]) {
vis[j] = 1;
h.push_back(j);
}
cir.push_back(h);
}
a = 1;
b = 0;
for (int i = 0; i < cir.size(); ++i) {
auto& h = cir[i];
int id = b % h.size();
vector<int> used(h.size(), 0);
for (int i = id;; i = (i + a) % h.size()) {
if (used[i])
break;
used[i] = 1;
if (v[h[i]] < v[h[id]])
id = i;
}
A = h.size();
B = id;
if (i > 0)
merge();
else
a = A, b = B;
}
LL step = b % a;
vector<int> ans(n);
for (auto& h : cir) {
for (int i = 0, j = step % h.size(); i < h.size();
i++, j = (j + 1) % h.size()) {
ans[h[i]] = v[h[j]];
}
}
for (int i = 0; i < n; ++i) {
cout << ans[i] << " \n"[i == n - 1];
}
return 0;
}
怎么办呢，用chatgpt改成pythonb吧jls的代码貌似没用高精，研究研究
python代码
# 扩展欧几里得算法
def exgcd(a, b):
if b == 0:
return a, 1, 0
d, x1, y1 = exgcd(b, a % b)
x = y1
y = x1 - (a // b) * y1
return d, x, y
# 求最大公约数
def gcd(a, b):
return a if b == 0 else gcd(b, a % b)
# 求最小公倍数
def lcm(a, b):
return a // gcd(a, b) * b
# 初始化全局变量
x, y, d = 0, 0, 0
a, b, A, B = 0, 0, 0, 0
# 合并两个同余方程
def merge():
global a, b, A, B, x, y, d
d, x, y = exgcd(a, A)
c = B - b
assert c % d == 0
x = (x * (c // d)) % (A // d)
if x < 0:
x += A // d
mod = lcm(a, A)
b = (a * x + b) % mod
if b < 0:
b += mod
a = mod
def main():
n = int(input())
p = [int(i) - 1 for i in input().split()]
v = list(map(int, input().split()))
# 寻找环
cir = []
vis = [0] * n
for i in range(n):
if vis[i]:
continue
h = [i]
vis[i] = 1
j = p[i]
while j != i:
vis[j] = 1
h.append(j)
j = p[j]
cir.append(h)
global a, b, A, B
a, b = 1, 0
for i, h in enumerate(cir):
id = b % len(h)
used = [0] * len(h)
j = id
while not used[j]:
used[j] = 1
if v[h[j]] < v[h[id]]:
id = j
j = (j + a) % len(h)
A = len(h)
B = id
if i > 0:
merge()
else:
a, b = A, B
step = b % a
ans = [0] * n
for h in cir:
for i in range(len(h)):
j = (step + i) % len(h)
ans[h[i]] = v[h[j]]
print(" ".join(map(str, ans)))
if __name__ == "__main__":
main()