先给出比赛链接：
下面说一下难度分层：(同一难度下按字典序排序)
Easy(简单): B H
Medium(中等): D E
Hard(困难): A G
Anti-AK(防AK): C F
A 扣分扣分扣分！扣分！
二维前缀差分板子题
题目要求对二维区间加某个数或者查询二维区间的和
与一维前缀和类似地，我们定义 $ sa[i][j] $ 为区间(1 < x < i, 1 < y < j) 的和
生成二维前缀和：
遍历原二维数组，$ sa[i][j] = a[i][j] + sa[i - 1][j] + sa[i][j - 1] - sa[i - 1][j - 1] $
区间查询：
要得到任意区间的和可以O1求出，
比如(x1, y1) 到 (x2, y2) 区间的和就是
$ sa[x2][y2] - sa[x2][y1 - 1] - sa[x1 - 1][y2] + sa[x1 - 1][y1 - 1] $
区间加：
定义差分数组da，对da求前缀和即可得到a数组，即a是da的前缀和
那么对da的某一位加上v，就能使得这一位后面的a数组全部加上v
类似的，想要实现在a的某个区间加v，只需要在区间的初始位置+v，结束位置的后一个位置-v
就能实现对a数组的区间加
二维前缀和即是
$ da[x1][y1] += v \(
\) da[x1][y2 + 1] -= v \(
\) da[x2 + 1][y1] -= v \(
\) da[x2 + 1][y2 + 1] += v $
Show Code A
int main() {cin.tie(nullptr)->sync_with_stdio(false);cout.tie(nullptr)->sync_with_stdio(false);auto prefix = [&](vector< vector< ll >> &a, int lena, int lenai) {vector< vector< ll >> sa(lena + 1 , vector< ll >(lenai + 1));for (int i = 1; i <= lena; ++ i) {for (int j = 1; j <= lenai; ++ j) {sa[i][j] = a[i][j] + sa[i - 1][j] + sa[i][j - 1] - sa[i - 1][j - 1];}}return sa;};auto get = [&](vector< vector< ll >> &sa, int xb, int yb, int xe, int ye) {ll res = sa[xe][ye] - sa[xe][yb - 1] - sa[xb - 1][ye] + sa[xb - 1][yb - 1];return res;};auto dif = [&](vector< vector< ll >> &a, int lena, int lenai) {vector< vector< ll >> da(lena + 1 , vector< ll >(lenai + 1));for (int i = 1; i <= lena; ++ i) {for (int j = 1; j <= lenai; ++ j) {da[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];}}return da;};auto add = [&](vector< vector< ll >> &da, int si, int sj, int ti, int tj, ll x) {int n = da.size(), m = da[si].size();da[si][sj] += x;if (tj + 1 < m) da[si][tj + 1] -= x;if (ti + 1 < n) da[ti + 1][sj] -= x;if (ti + 1 < n && tj + 1 < m)da[ti + 1][tj + 1] += x;};int n, m, q1, q2;cin >> n >> m >> q1 >> q2;vector< vector< ll >> da(n + 2, vector< ll >(m + 2));while (q1--) {int a1, b1, a2, b2;ll v;cin >> a1 >> b1 >> a2 >> b2 >> v;add(da, a1, b1, a2, b2, v);}vector< vector< ll >> a = prefix(da, n, m);vector< vector< ll >> sa = prefix(a, n, m);while (q2--) {int a1, b1, a2, b2;cin >> a1 >> b1 >> a2 >> b2;cout << get(sa, a1, b1, a2, b2) << "\n";}
}
B 明日方舟设计师！
按题意模拟即可，注意本题卡了pow,故不能直接用pow计算
Show Code B
int main() {cin.tie(nullptr)->sync_with_stdio(false);int tt = 1;cin >> tt;while (tt--) {ll a = 1, b = 1, n, ans = 0, c = 1;ll aq, bq;cin >> aq >> bq >> n;for (int i = 1; i <= n; ++ i) {b *= bq;}for (ll k = 0; k <= n; ++ k) {ans += c * a * b;a *= aq;b /= bq;c = c * (n - k) / (k + 1);}cout << ans << "\n";}
}
C 夕瓜的幻想
我们将小自在造成的伤害和夕造成的伤害分开计算
根据小自在个数的递推公式，我们可以发现小自在的个数满足组合数，即小自在个数等于 $ C_{n}^{k} $
下面给出证明，根据递推公式我们可以发现 $ C_{k} = \frac{n! / (n - k)!}{k!} = \frac{n!}{(n - k)!k!} = C_{n}^{k} $
那么答案就能表示成
\( \sum\limits_{k = 0}^{n} C_{n}^{k} a^{k} b^{n - k} = (a + b)^n ~~~~~ (二项式定理) \)
然后再计算夕的伤害，显然夕的伤害是一个等比数列求和，公比 $ q = \frac{a}{b} $
\( \sum\limits_{k = 0}^{n} a^{k} b^{n - k} \)
\( = b^{n} \frac{1 - \frac{a}{b}^{n + 1}}{1 - \frac{a}{b}} \)
\( = \frac{b^{n} - a^{n}\frac{a}{b}}{1 - \frac{a}{b}} ~~~ (将b^{n}与分子相乘) \)
\( = \frac{b^{n + 1} - a^{n + 1}}{b - a} ~~~ (上下同乘(b)) \)
\( = (b^{n + 1} - a^{n + 1})(b - a) ~~~ (上下同乘(b-a)) \)
故答案即为 $ (a + b)^n + (b^{n + 1} - a^{n + 1})(b - a) $
Show Code C
int main() {cin.tie(nullptr)->sync_with_stdio(false);auto power = [&](ll a , ll b) {ll res = 1;while (b) {if (b & 1) {res = res * a % mod;}a = a * a % mod;b >>= 1;}return res;};int tt = 1;cin >> tt;while (tt--) {ll x, y, n;cin >> x >> y >> n;ll ans = power(x + y, n);ans += (power(y, n + 1) - power(x, n + 1) + mod) % mod * (y - x + mod) % mod;cout << ans << "\n";}
}
D 毛民9527
每有一种关系就能把材料的种类减一，所以直接输出 n - m 即可
Show Code D
int main() {cin.tie(nullptr)->sync_with_stdio(false);int n, m;cin >> n >> m;cout << n - m << "\n";
}
E 最简真分数
先 $ O(n^{2}log(n)) $ 求出最简真分数的个数。然后注意到它们的和就是个数除以二
可以注意到，当(x,y)为互质时，(y-x,y)也互质。那么有这些最简真分数的和就是它们的个数除以2。
Show Code E
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);ll ans1 = 0;ll n = 2e6; cin >> n;for (int i = 1; i <= n; ++ i) {for (int j = i + 1; j <= n; ++ j) {if (gcd(i, j) == 1) {ans1++;}}}double ans2 = (double)ans1 / 2.0;cout << ans1 << " " << fixed << setprecision(9) << ans2 << "\n"; //保留9位
}
F 模意义下的最简真分数
显然有:
\( ans = \sum\limits_{a = 1}^{n} \sum\limits_{b = 1}^{a} ([b < a] * [gcd(a , b) == 1]) = (\sum\limits_{a = 1}^{n} \sum\limits_{b = 1}^{n} [gcd(a , b) == 1]) / 2 \)
那么只需求出n以内的互质对即可。即以1为最大公约数的数对
由容斥原理可以得知，先找到所有以1为公约数的数对，再从中剔除所有以1的倍数为公约数的数对，余下的数对就是以1为最大公约数的数对。即f(k)=以1为公约数的数对个数 - 以1的倍数为 公约数 的数对个数。
可以注意到，当(x,y)为互质时，(y-x,y)也互质。那么有这些最简真分数的和就是它们的个数除以2。
Show Code F
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);auto power = [&](ll a , ll b) {ll res = 1;while (b) {if (b & 1) {res = res * a % mod;}a = a * a % mod;b >>= 1;}return res;};ll ans1 = 0, ans2 = 0; ll nn = 2e6; cin >> nn;vector< ll > f(nn + 1);// f[i] 表示 gcd == i 的情况有几种// 容斥for (ll k = nn; k >= 1; k--) { f[k] = (nn / k) * (nn / k);for (ll i = k + k; i <= nn; i += k) {f[k] -= f[i];}}ans1 = f[1] / 2 % mod;ans2 = ans1 * power(2, mod - 2) % mod;std::cout << ans1 << " " << ans2 << "\n";
}
G 大猿口算
根据克莱默法则
$ x_{i} = \frac{D_{i}}{D} $
当D为0时，则说明无唯一解
当D不为0时，计算出 $ x_{i} $ 的值再判断符号并且约分并输出即可
Show Code G
int main() {cin.tie(nullptr)->sync_with_stdio(false);auto sgn = [&](ll n) {return n < 0 ? 1 : 0;};int tt = 1;cin >> tt;while (tt--) {int n;cin >> n;vector< vector< ll>> a(n + 1, vector< ll >(n + 2));vector< vector< vector< ll >>> d(n + 1, vector< vector< ll >>(n + 1, vector< ll >(n + 1)));vector< ll > D(n + 1);auto com = [&](vector< vector< ll >> det) {if (n == 1) {return det[1][1];} else if (n == 2) {return det[1][1] * det[2][2] - det[1][2] * det[2][1];} else {ll res = 0;res += det[1][1] * det[2][2] * det[3][3];res += det[1][2] * det[2][3] * det[3][1];res += det[1][3] * det[2][1] * det[3][2];res -= det[1][3] * det[2][2] * det[3][1];res -= det[1][1] * det[2][3] * det[3][2];res -= det[1][2] * det[2][1] * det[3][3];return res;}};for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= n + 1; ++ j) {cin >> a[i][j];}}for (int k = 0; k <= n; ++ k) {for (int i = 1; i <= n; ++ i) {for (int j = 1; j <= n; ++ j) {d[k][i][j] = a[i][j];}d[k][i][k] = a[i][n + 1];}}for (int k = 0; k <= n; ++ k) D[k] = com(d[k]);if (D[0] == 0) {cout << "No\n";} else {cout << "Yes\n";for (int k = 1; k <= n; ++ k) {ll g = gcd(D[0], D[k]);if (D[k] != 0 && sgn(D[k]) ^ sgn(D[0])) cout << '-';cout << abs(D[k] / g) << "/" << abs(D[0] / g) << " \n"[k == n];}}}
}
H 这是签到
保留11位输出 $ \pi $ 即可
可以用反三角函数 acos(-1) 得到 $ \pi $ 的值
Show Code H
const double pi = acos(-1);
int main() {std::cout << std::fixed << std::setprecision(11) << pi << "\n";
}
