A. Onewan的疑惑
题意：找有多少小于等于\(n\)的\(x\)满足\(x+(19260817)≥n−(114514)\)。
移项可得\(x\)的下界，注意\(x\)最大得有\(1\)。
点击查看代码
void solve() {
i64 n;
std::cin >> n;
i64 m = std::max(1ll, n - 114514 - 19260817);
std::cout << n - m + 1 << "\n";
}
B. 菲菲姐的游戏
把数组分成两个连续的子数组，你可以在左边选至多\(k1\)个数，另一个人可以在右边至多选\(k2\)个数，你的值是选的数的平均数，她的值是选的数的中位数，问有没有一种分数组的方法使得你可以大于她。
显然每个人都最多选一个数，因为多个数的平均值不会大于最大值，中位数也不会大于最大值，所以枚举分开点，比较两边最大值就行了。
点击查看代码
void solve() {
int n, x, y;
std::cin >> n >> x >> y;
std::vector<int> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
std::vector<int> suf(n + 2);
for (int i = n - 1; i >= 0; -- i) {
suf[i + 1] = std::max(suf[i + 2], a[i]);
}
int max = 0;
for (int i = 0; i + 1 < n; ++ i) {
max = std::max(max, a[i]);
if (max > suf[i + 2]) {
std::cout << "Yes\n";
return;
}
}
std::cout << "No\n";
}
C. 猪猪养成计划1
题意：\(n\)个点，\(q\)次操作，会让你从\(l\)挨个遍历到\(r\)，之前遍历过的不会在遍历；或者问你第\(i\)个是第几个被遍历的。
用\(set\)模拟即可，每次找到剩下没遍历的数中大于等于\(l\)的第一个数，然后通过\(set\)迭代器遍历所有小于等于\(r\)的，并记录答案。最后把所有遍历到的数删除即可。
点击查看代码
void solve() {
int n, q;
std::cin >> n >> q;
std::vector<int> ans(n + 1);
std::set<int> s;
for (int i = 1; i <= n; ++ i) {
s.insert(i);
}
int cnt = 0;
while (q -- ) {
int op, x, y;
std::cin >> op >> x;
if (op == 1) {
std::cin >> y;
auto it = s.lower_bound(x);
std::vector<int> b;
while (it != s.end() && *it <= y) {
ans[*it] = ++ cnt;
b.push_back(*it);
++ it;
}
for (auto & z : b) {
s.erase(z);
}
} else {
std::cout << ans[x] << "\n";
}
}
}
D. 猪猪养成计划2k
题意：有\(n\)个猪，每个猪你和他玩耍会花费\(b_i\)，否则花费\(v_i\)，每个猪需要玩耍的时间段是\([a_i, a_i+m-1]\)，你每个时刻只能陪一头猪。问最小花费。
考虑\(dp\)，\(f_i\)表示处理完前\(i\)时刻所有猪的最小花费。那么我们可以枚举每个在\(i\)时刻结束陪伴的猪，那么我们可以得\(f_i = \min\{f_{i-m} + sum_{i-m+1,i}- v_k + b_k\}\)其中\(sum_{l,r}\)表示结束区间在\([l, r]\)内的猪的\(v\)之和，\(v_k, b_k\)表示我们陪伴的这头猪的两个花费。因为我们选择了\([i-m+1,i]\)这个区间陪伴一头猪，那么这个区间内结束的我们都不能陪伴，至于在这个区间开始的，我们无需考虑，因为后面它会考虑到我们。那么因为我们枚举的这只猪也在这个区间内，所以我们要减去\(v_k\)，然后加上\(b_k\)。
除此外，我们也可以一头都不陪伴，那么是\(f_i = f_{i-1}+sum_i-sum_{i-1}\)。
点击查看代码
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<i64> sum(n + 1);
std::vector<std::vector<std::pair<i64, i64> > > op(n + 1);
std::vector<i64> a(n), v(n), b(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
for (int i = 0; i < n; ++ i) {
std::cin >> b[i] >> v[i];
sum[a[i] + m - 1] += v[i];
op[a[i] + m - 1].push_back({b[i], v[i]});
}
for (int i = 1; i <= n; ++ i) {
sum[i] += sum[i - 1];
}
std::vector<i64> f(n + 1, 1e18);
f[0] = 0;
i64 ans = 1e18;
for (int i = 1; i <= n; ++ i) {
for (auto & [b, v] : op[i]) {
int l = std::max(1, i - m + 1);
f[i] = std::min(f[i], f[l - 1] + sum[i] - sum[l - 1] - v + b);
}
f[i] = std::min(f[i], f[i - 1] + sum[i] - sum[i - 1]);
}
std::cout << f[n] << "\n";
}
E. min25筛
题意：给你一个数组，\(f_{ij}\)定义为\(\prod_{k=i}^{j} a_k\)一直除\(25\)直到没有\(25\)这个因子。
求\(\sum_{i=1}^{n}\sum_{j=i}^{n}f_{ij}\)。
观察发现，\(25\)只有两个质因子\(5\)。那么我们可以从后往前计算\(a_i\)的贡献，记\(sum_{i,0/1}\)为以\(i\)开始的区间中有偶数个/奇数个因子\(5\)的区间和的和。
那么如果\(5 \mid a_i\)，则\(sum_{i,0} = sum_{i+1, 1} \times a_i / 5, sum_{i, 1} = sum_{i+1,0} \times a_i + a_i\)。
如果\(5 \nmid a_i\)，则\(sum_{i,0} = sum_{i+1,1} \times a_i + a_i, sum_{i, 1} = sum_{i+1, 1} \times a_i\)。
点击查看代码
const int mod = 1e9 + 7;
i64 pow(i64 a, i64 b, i64 p) {
i64 res = 1;
while (b) {
if (b & 1) {
res = res * a % p;
}
a = a * a % p;
b >>= 1;
}
return res;
}
void solve() {
int n;
std::cin >> n;
std::vector<i64> a(n);
for (int i = 0; i < n; ++ i) {
std::cin >> a[i];
}
i64 sum[2] = {0, 0};
i64 ans = 0, inv = pow(25, mod - 2, mod);
for (int i = n - 1; i >= 0; -- i) {
while (a[i] % 25 == 0) {
a[i] /= 25;
}
if (a[i] % 5 == 0) {
sum[0] = sum[0] * a[i] % mod;
sum[1] = sum[1] * a[i] % mod * inv % mod;
std::swap(sum[0], sum[1]);
sum[1] = (sum[1] + a[i]) % mod;
} else {
sum[0] = sum[0] * a[i] % mod;
sum[1] = sum[1] * a[i] % mod;
sum[0] = (sum[0] + a[i]) % mod;
}
ans = (ans + sum[0] + sum[1]) % mod;
}
std::cout << ans << "\n";
}