赛时通过：D、A、B、G、H
补题：M、J
同时打开 13 个题目，我谨慎地做出了选择……
成功发现签到题！用一个 map 维护数组信息即可。
不难注意到一个可行的答案是 $\text{lcm}(a)+1$。同时如果数组里面有 $1$ 的话就无解。
赛后发现好像随便找一个比 $10^9$ 大的质数就行……
典中典之欧拉回路。
计算度数为奇数的节点数量，如果不为 $2$ 就输出 $-1$（因为题目给出的是树），否则输出度数为奇数的两个节点即可。
首先判断数组的和是否为排列的和，若否则输出 $-1$。不然就先排序数组，再计算每个元素与其下标之差的绝对值之和。答案就是这个和除以二（向下取整）。
感觉和 Codeforces 中的某道题很像，只不过那道题是求第 $i$ 个元素是否是唯一的。
不过其实都是一个区间覆盖的问题。按区间右端点排序后模拟即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
void solve() {
int n;
cin >> n;
vector<pair<pair<int, int>, int>> a(n);
for (int i = 0; i < n; i ++) {
int l, r;
cin >> l >> r;
a[i] = {pair(l, r), i};
}
ranges::sort(a, [](const auto &x, const auto &y) {
return x.first.second < y.first.second;
});
set<int> nums;
for (int i = 1; i <= n; i ++)
nums.insert(i);
vector<int> ans(n);
for (const auto &[pr, idx] : a) {
auto [l, r] = pr;
auto it = nums.lower_bound(l);
if (it == nums.end() or *it > r) {
cout << -1;
return;
}
ans[idx] = *it;
nums.erase(it);
}
for (int i = 0; i < n; i ++)
cout << ans[i] << " ";
cout << "\n";
}
|
我已经忘了我赛时怎么想的了……呃呃。
总而言之，我们可以发现这个第 $k$ 小值到第 $k+1$ 小值是一个区间，而且这个区间是连续的，因此我们可以模拟这个区间扩张的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
vector<pair<int, int>> b;
multiset<int> st;
for (int i = 1; i <= n; i ++) {
cin >> a[i];
b.push_back({a[i], i});
st.insert(a[i]);
}
ranges::sort(b);
auto [l, r] = b[0];
st.extract(l);
st.insert(l * 2);
int ans = *st.rbegin() - *st.begin();
l = r;
for (auto &[_, i] : b) {
if (i >= l and i <= r)
continue;
for (int j = l - 1; j >= i; j --) {
st.extract(a[j]);
st.insert(a[j] * 2);
ans = min(ans, *st.rbegin() - *st.begin());
}
l = min(l, i);
for (int j = r + 1; j <= i; j ++) {
st.extract(a[j]);
st.insert(a[j] * 2);
ans = min(ans, *st.rbegin() - *st.begin());
}
r = max(r, i);
}
cout << ans << "\n";
}
|
我们可以枚举每个因数的倍数，统计满足条件的即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
void solve() {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) {
cin >> x;
}
int m = *ranges::max_element(a);
vector<int> cnt(m + 1);
for (auto &x : a)
cnt[x] ++;
int ans = 0;
for (int g = 1; g <= m; g ++) {
for (int i = g; i <= m; i += g) {
int j = i ^ g;
if (i < j and gcd(i, j) == g and j <= m) {
ans += cnt[i] * cnt[j];
}
}
}
cout << ans << "\n";
}
|