NOIP 模拟赛十三

A

先把所有的数字捡到 \(0\) 后重新分配显然是最优的操作，要求两两之间互质，和最小的要求即为全部都是质数。
判断总和是否大于前 \(n\) 个质数的和，如果不够，减去最小的数再次判断，一直到合法。
注意 \(n=1\) 的时候一定合法。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) std::max(a, b)
#define cmn(a, b) std::min(a, b)
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 4e5 + 7;
const int LM = 6e6 + 7;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;
int T, n, a[LN]; ll f[LN], sum;
std::bitset <LM> np; std::vector <int> p;
bool ENDPOS;int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock();lep(i, 2, LM - 1) {if (!np[i]) p.push_back(i);for (int j : p) if (1ll * i * j < LM) {np[i * j] = true;if (i % j == 0) break;} else break;}lep(i, 1, LN - 1) f[i] = f[i - 1] + p[i - 1];std::cin >> T;while (T--) {std::cin >> n; sum = 0;lep(i, 1, n) std::cin >> a[i], sum += a[i];std::sort(a + 1, a + 1 + n);int ans = 0;while (ans < n - 1 and sum < f[n - ans]) ++ans, sum -= a[ans];std::cout << ans << '\n';}
#ifdef DEBUGstd::cerr << clock() - c1 << '\n';std::cerr << std::fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << "MB\n";
#endifreturn 0;
}

B

在二维笛卡尔坐标系上，向右看作向右，向左看作向上。
终止条件即为接触到 \(y=x-n\) 这条线。
枚举接触点，方案约束即为不能碰触 \(y=x-n\) 这条线。
经典的 \(\boldsymbol{反射容斥}\) Link 。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) std::max(a, b)
#define cmn(a, b) std::min(a, b)
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 1e6 + 7;
const int mod = 1e9 + 7;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;
int n, fac[LN], inv[LN];
bool ENDPOS;il int add(int u, int v) { return u + v >= mod ? u + v - mod : u + v; }
il void upa(int& u, int v) { u = add(u, v); }
il int mul(ll u, ll v) { return u * v >= mod ? u * v % mod : u * v; }
il void upm(int& u, int v) { u = mul(u, v); }
il int MyPow(int a, int b) { int ans = 1; for (; b; b >>= 1, upm(a, a)) if (b & 1) upm(ans, a); return ans; }
il int C(int n, int m) { if (n < 0 or m < 0 or n < m) return 0; return mul(fac[n], mul(inv[m], inv[n - m])); }int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock();std::cin >> n;fac[0] = 1; lep(i, 1, 2 * n) fac[i] = mul(fac[i - 1], i);inv[2 * n] = MyPow(fac[2 * n], mod - 2);rep(i, 2 * n, 1) inv[i - 1] = mul(inv[i], i);int ans = 1, y;rep(x, (3 * n - 2) / 2, n) y = x - n + 1, upa(ans, C(x + y, y)), upa(ans, mod - C(x + y, x - n));std::cout << ans << '\n';
#ifdef DEBUGstd::cerr << clock() - c1 << '\n';std::cerr << std::fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << "MB\n";
#endifreturn 0;
}

C

Record

D

一种倍增做法是，预处理向右儿子跳 \(2^i\) 步能够到达的节点和中途经过的长度。
但是这样每次需要向左跳时倍增就会被截停，最劣查询 \(x=1\) 时会被卡到 \(O(n)\) 。
我们借助启发式的思想，每次向较长的一个子树预处理倍增数组，这样每次被截停 \(x\) 都至少减半。
复杂度 \(O(qlog^2q)\) 。

点击查看

#include <bits/stdc++.h>
#define lep(i, a, b) for (int i = a; i <= b; ++i)
#define rep(i, a, b) for (int i = a; i >= b; --i)
#define il inline
#define cmx(a, b) std::max(a, b)
#define cmn(a, b) std::min(a, b)
#define gmx(a, b) a = cmx(a, b)
#define gmn(a, b) a = cmn(a, b)template <typename T>
void _debug(const T& t) { std::cerr << t << '\n'; }
template <typename T, typename... Args>
void _debug(const T& t, const Args&...res) { std::cerr << t << ' '; _debug(res...); }
#define debug(...) _debug(#__VA_ARGS__ " =", __VA_ARGS__)const int LN = 1e6 + 7;
typedef long long ll;
typedef std::pair<int, int> PII;bool FIRPOS;
int Q, l[LN], r[LN], to[LN][21]; ll len[LN], st[LN][21], inf = 1e18;
bool ENDPOS;int main() {std::ios::sync_with_stdio(false),std::cin.tie(nullptr), std::cout.tie(nullptr);int c1 = clock(); ll x;std::cin >> Q; len[0] = len[1] = 1;lep(i, 2, Q + 1) {std::cin >> l[i] >> r[i] >> x, len[i] = cmn(len[l[i]] + len[r[i]], inf);if (len[l[i]] >= len[r[i]]) to[i][0] = l[i];else to[i][0] = r[i], st[i][0] = len[l[i]];lep(j, 1, 20) to[i][j] = to[to[i][j - 1]][j - 1],st[i][j] = cmn(st[i][j - 1] + st[to[i][j - 1]][j - 1], inf);int p = i;while (p > 1) {rep(j, 20, 0) if (to[p][j] > 1 and x > st[p][j] and x <= st[p][j] + len[to[p][j]]) x -= st[p][j], p = to[p][j];if (x <= len[l[p]]) p = l[p]; else x -= len[l[p]], p = r[p];}std::cout << p << '\n';}
#ifdef DEBUGstd::cerr << clock() - c1 << '\n';std::cerr << std::fabs(&ENDPOS - &FIRPOS) / 1024 / 1024 << "MB\n";
#endifreturn 0;
}