Henan Mengxin League 2024, Game (5): Information Engineering University
preamble
A bit of water this one, the original question and board seems a bit much.
A-Calendar Game_Henan Mengxin League 2024, Game (5): Information Engineering University ()
reasoning
First of all, without looking at the year, it's obvious\(8/1\) Defeat.\(7/31\) Sheng.\(7/30\) Defeat.\(7/29\) Sheng.\(\dots\), and so on to find a\((m+d)\bmod 2=0\) \((m is month, d is day)\) When, surely.\((m+d)\bmod 2=1\) The law of the hour must fail, but note that there are two special dates that are\(9/30\) cap (a poem)\(11/30\)，\(9/30\rightarrow 10/1\ or\ 10/1,11/30\rightarrow 12/1\ or \ 12/30\), which can control the next count parity, and in the optimal strategy can control for sure wins.
coding
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int x, y, z;
cin >> x >> y >> z;
if ((y == 9 && z == 30) || (y == 11 && z == 30) || (y + z) % 2 == 0)
cout << "YES\n";
else
cout << "NO\n";
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
B-Student Grouping_Henan Mengxin League 2024, Game (5): Information Engineering University ()
reasoning
The first thing to do is to determine if the average is in\([L,R]\) of the interval.
Then it's just a matter of comparing all the numbers less than\(L\) greater than\(R\) You can just fill in whichever part of the section is the largest, the largest on the other side, and the rest to fill in the average.
coding
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
(nullptr);
int n;
cin >> n;
i64 sum = 0;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++) {
cin >> a[i];
sum += a[i];
}
i64 l, r;
cin >> l >> r;
if (sum / n < l || (sum + n - 1) / n > r) {
cout << "-1\n";
return 0;
}
i64 x = 0, y = 0;
for (int i = 1; i <= n; i ++) {
if (a[i] < l) x += l - a[i];
else if (a[i] > r) y += a[i] - r;
}
cout << max(x, y) << '\n';
return 0;
}
C-Xiaomei wants to collect_Henan Mengxin League 2024, Game (5): Information Engineering University ()
reasoning
A template for the type (extended domain) and check set.
Greedily sort the conflicting values from largest to smallest, and then maintain the two sets with a concatenated set of\(x\) cap (a poem)\(x+n\) represents its own set and its relative set, assuming that the\(a,b\) conflict, then we'll put\(a,b+n\) The concatenated representation is placed in a set.\(b,a+n\) Put a collection.
When enumerating to the\(a,b\) If they have been assigned to a set in a previous allocation, then their conflict value is the maximum at this point, and the output is sufficient.
Dichotomous + dichotomous graph coloring can also be written, so check out the specificsP1525 [NOIP2010 Improvement Group] Im*ment of CriminalsThe solution to this question.
coding
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct UFS {
int sz;
vector<int> rank, p;
void link(int x, int y) {
if (x == y)
return;
if (rank[x] > rank[y])
p[y] = x;
else
p[x] = y;
if (rank[x] == rank[y])
rank[y]++;
}
void init(int n) {
sz = n;
(n + 1);
(n + 1);
for (int i = 0; i <= sz; i++) {
p[i] = i;
rank[i] = 0;
}
}
int find(int x) {
return x == p[x] ? x : (p[x] = find(p[x]));
}
void unin(int x, int y) {
link(find(x), find(y));
}
void compress() {
for (int i = 0; i <= sz; i++)
find(i);
}
};
//species parallelism set (math.) merge(y + n, x),merge(x + n, y)
int main() {
ios::sync_with_stdio(false);
(nullptr);
int n, m;
cin >> n >> m;
vector<tuple<i64, int, int>> g;
for (int i = 0; i < m; i ++) {
i64 u, v, w;
cin >> u >> v >> w;
g.push_back({w, u, v});
}
sort((), (), greater<>());
UFS ufs;
(2 * n);
i64 ans = 0;
for (int i = 0; i < m; i ++) {
auto [w, u, v] = g[i];
if ((u) == (v) || (u + n) == (v + n)) {
ans = w;
break;
}
(u + n, v);
(v + n, u);
}
cout << ans << '\n';
return 0;
}
D-Interval Problem 1_Henan Mengxin League 2024, Game (5): Information Engineering University ()
reasoning
Ordinary line segment tree board questions with tree array differencing are fine.
It is said that directly\(O(qn)\) People have passed with poor scores.
coding
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
template<class Node>
struct SegmentTree {
#define lc u<<1
#define rc u<<1|1
const int n, N;
vector<Node> tr;
SegmentTree(): n(0) {}
SegmentTree(int n_): n(n_), N(n * 4 + 10) {
(N);
(N);
}
SegmentTree(vector<int> init) : SegmentTree(()) {
function<void(int, int, int)> build = [&](int u, int l, int r) {
tr[u].l = l, tr[u].r = r;
init_lazy(tr[u]);
if (l == r) {
tr[u] = {l, r, 0, init[l]};
return ;
}
i64 mid = (l + r) >> 1;
build(lc, l, mid);
build(rc, mid + 1, r);
pushup(tr[u], tr[lc], tr[rc]);
};
build(1, 1, n);
}
void cal_lazy(Node & fa, Node & ch) {
i64 b = ;
+= b;
}
void tag_union(Node& fa, Node& ch) {
i64 b = ;
+= b;
}
void init_lazy(Node& u) {
= 0;
}
void pushdown(i64 u) {
if (tr[u].add != 0) {
cal_lazy(tr[u], tr[lc]);
cal_lazy(tr[u], tr[rc]);
tag_union(tr[u], tr[lc]);
tag_union(tr[u], tr[rc]);
init_lazy(tr[u]);
}
}
void pushup(Node& U, Node& L, Node& R) { //upload
= + ;
}
void modify(int u, int l, int r, int k) {
if (tr[u].l >= l && tr[u].r <= r) {
tr[u].add += k;
tr[u].sum += k;
return ;
}
pushdown(u);
int mid = (tr[u].l + tr[u].r) >> 1;
if (l <= mid)
modify(lc, l, r, k);
if (r > mid)
modify(rc, l, r, k);
pushup(tr[u], tr[lc], tr[rc]);
}
Node query(int u, int l, int r) { //inspect
if (l <= tr[u].l && tr[u].r <= r)
return tr[u];
i64 mid = tr[u].l + tr[u].r >> 1;
pushdown(u);
i64 res = LLONG_MIN >> 1;
if (r <= mid)
return query(lc, l, r);
if (l > mid)
return query(rc, l, r);
Node U;
Node L = query(lc, l, r), R = query(rc, l, r);
pushup(U, L, R);
return U;
}
};
struct Node { //Line Tree Definition
i64 l, r, add, sum;
};
int main() {
ios::sync_with_stdio(false);
(nullptr);
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
SegmentTree<Node> tr(a);
int q;
cin >> q;
while (q--) {
int op;
cin >> op;
if (op == 1) {
int l, r, d;
cin >> l >> r >> d;
(1, l, r, d);
} else {
int x;
cin >> x;
auto ans = (1, x, x);
cout << << '\n';
}
}
return 0;
}
E-Goldbach's Conjecture_Henan Mengxin League 2024 (5th): Information Engineering University ()
reasoning
first sift out\(5e4\) The prime numbers are enumerated, and then two numbers are enumerated, and a third number is maintained with set to determine it.
coding
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
//Euler function (math.),prime number
vector<int> euler_range(int n) {
vector<int> phi(n + 1), prime;
vector<bool> is_prime(n + 1, true);
is_prime[1] = 0, phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) prime.push_back(i), phi[i] = i - 1;
for (int j = 0; j < (int)() && i * prime[j] <= n; j++) {
is_prime[i * prime[j]] = 0;
if (i % prime[j]) phi[i * prime[j]] = phi[i] * (prime[j] - 1);
else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
return prime;
}
constexpr int N = 5e4 + 10, M = N - 5;
auto pr = euler_range(N);
set<int> s((), ());
void solve() {
int n;
cin >> n;
for (auto &i : pr) {
for (auto &j : pr) {
if (i + j >= n) break;
if ((n - i - j)) {
cout << i << ' ' << j << ' ' << n - i - j << '\n';
return ;
}
}
}
cout << "-1\n";
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
F-Xiaomei wants to run_Henan Mengxin League 2024, Game (5): Information Engineering University ()
reasoning
The sample can be found by drawing a map, in fact, is for you to find in the directed graph to the shortest distance to other points, and other points to the starting point of the shortest distance, when the edge is forward stock, you can use dijkstra to run to the distance to other points, the reverse stock edge to run dijkstra is the other points to the starting point of the shortest distance.
So run dijkstra twice forwards and backwards.
coding
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct DIJ {
using i64 = long long;
using PII = pair<i64, i64>;
vector<i64> dis;
vector<vector<PII>> G;
DIJ() {}
DIJ(int n) {
(n + 1, 1e18);
(n + 1);
}
void add(int u, int v, int w) {
G[u].emplace_back(v, w);
}
void dijkstra(int s) {
priority_queue<PII> que;
dis[s] = 0;
({0, s});
while (!()) {
auto p = ();
();
int u = ;
if (dis[u] < -) continue;
for (auto [v, w] : G[u]) {
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
({ -dis[v], v});
}
}
}
}
};
int main() {
ios::sync_with_stdio(false);
(nullptr);
int n, m;
cin >> n >> m;
DIJ dij1(n), dij2(n);
for (int i = 0; i < m; i ++) {
int u, v, w;
cin >> u >> v >> w;
(u, v, w);
(v, u, w);
}
(1);
(1);
i64 ans = 0;
for (int i = 2; i <= n; i ++) {
ans += [i] + [i];
}
cout << ans << '\n';
return 0;
}
G-Climbing Stairs_Henan Mengxin League 2024, Game (5): Information Engineering University ()
reasoning
Basic Dynamic Programming, Classic Stair Climbing Problem.
coding
int main() {
ios::sync_with_stdio(false);
(nullptr);
int n;
cin >> n;
vector<Z> dp(n + 10, 0);
dp[1] = 1, dp[2] = 2, dp[3] = 4;
for (int i = 4; i <= n; i ++) {
dp[i] += dp[i - 1] + dp[i - 2] + dp[i - 3];
}
cout << dp[n] << '\n';
return 0;
}
H-Interval Problem 2_Henan Mengxin League 2024, Game (5): Information Engineering University ()
reasoning
Kachan is honestly a bit anticlimactic.
It looks like the only way to get past it is to have a quick read + ST table, and the ST table can't be encapsulated yet.
Anyway, I'm stuck with a dog in a line tree
coding
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int maxn = 1e6 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while (c < '0' || c > '9') {if (c == '-')f = -1; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return x * f;
}
int Max[maxn][21];
int main() {
int n = read();
for (int i = 1; i <= n; i++) Max[i][0] = read();
for (int j = 1; j <= 20; j++)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
int l, r;
int m = read();
for (int i = 1; i <= m; ++i) {
scanf("%d %d", &l, &r);
int renk = log2(r - l + 1);
int temp = max(Max[l][renk], Max[r - (1 << renk) + 1][renk]);
printf("%d\n", temp);
}
return 0;
}
I-Xiaomei wants to play sound game_Henan Mengxin League 2024, Game (5): Information Engineering University ()
reasoning
It's about choosing a\(a\), which minimizes the distance of so number to its absolute value, has this theorem:
Changes all elements of a to aupper quartileis optimal.
It seems to be called median greed, and the proof should be searchable online.
coding
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
ios::sync_with_stdio(false);
(nullptr);
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++) {
cin >> a[i];
}
sort(() + 1, ());
i64 avg = a[(n + 1) / 2];
i64 ans = 1;
for (int i = 1; i <= n; i ++) {
ans += abs(a[i] - avg);
}
cout << ans << '\n';
return 0;
}
J-Square Root_Henan Mengxin League 2024, Game (5): Information Engineering University ()
reasoning
Check-in.
coding
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
i64 n;
cin >> n;
cout << (i64)sqrt(n) << '\n';
}
int main() {
ios::sync_with_stdio(false);
(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
K-Xiaomi wants to swim_Henan Mengxin League 2024, Game (5): Information Engineering University ()
reasoning
Using heap-optimized dijkstra in transferring the\(dis\) Just use it to maintain the maximum value of the path when the array is used.
coding
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
struct DIJ {
using i64 = long long;
using PII = pair<i64, i64>;
vector<i64> dis;
vector<vector<PII>> G;
DIJ() {}
DIJ(int n) {
(n + 1, 1e18);
(n + 1);
}
void add(int u, int v, int w) {
G[u].emplace_back(v, w);
}
void dijkstra(int s) {
priority_queue<PII> que;
dis[s] = 0;
({0, s});
while (!()) {
auto p = ();
();
int u = ;
if (dis[u] < -) continue;
for (auto [v, w] : G[u]) {
if (dis[v] > max(dis[u], w)) {
dis[v] = max(dis[u], w);
({ -dis[v], v});
}
}
}
}
};
int main() {
ios::sync_with_stdio(false);
(nullptr);
int n, m;
cin >> n >> m;
DIJ dij(n);
for (int i = 0; i < m; i ++) {
int u, v, w;
cin >> u >> v >> w;
(u, v, w);
(v, u, w);
}
int s, t;
cin >> s >> t;
(s);
cout << [t] << '\n';
return 0;
}