先给出比赛链接：
下面说一下难度分层：(同一难度下按字典序排序)
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";
}
标签：第六场,ZZJC,int,题解,ll,det,cin,da,vector From： https://www.cnblogs.com/Proaes/p/18490008