A - Sigma Cubes
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;int ans = 0;for (int i = 1; i <= n; ++ i) {ans += (i % 2 ? -1 : 1) * i * i * i;}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}
B - Find Permutation 2
题意：构造一个排序，使得\(a_i\)不等于\(-1\)的地方\(p_i = a_i\)。
\(a_i\)中一个不为\(-1\)的数不能出现两次。
然后没出现过的随便填到\(-1\)的位置就行。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];}std::vector<int> cnt(n + 1);for (auto & x : a) {if (x != -1) {if ( ++ cnt[x] > 1) {std::cout << "No\n";return;}}}std::cout << "Yes\n";int k = 1;for (int i = 0; i < n; ++ i) {if (a[i] == -1) {while (cnt[k]) {++ k;}a[i] = k;++ k;}std::cout << a[i] << " \n"[i == n - 1];}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}
C - Rotate and Sum Query
题意：一个数组，两种操作，一种是把数组左移\(c\)次，一种是求区间和。
左移\(n\)次就移回来了。可以开\(2n\)数组记录前缀和，然后记录一下数组的起点，就可以查询了。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, q;std::cin >> n >> q;std::vector<int> a(2 * n);for (int i = 0; i < n; ++ i) {std::cin >> a[i];a[i + n] = a[i];}std::vector<i64> sum(2 * n + 1);for (int i = 0; i < 2 * n; ++ i) {sum[i + 1] = sum[i] + a[i];}int i = 1;while (q -- ) {int op;std::cin >> op;if (op == 1) {int c;std::cin >> c;c %= n;i += c;if (i > n) {i -= n;}} else {int l, r;std::cin >> l >> r;std::cout << sum[i + r - 1] - sum[i + l - 2] << "\n";}}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}
D - Ulam-Warburton Automaton
题意：一个\(n\times m\)的矩阵，每个点有黑白两种颜色，如果一个白色格子旁边恰好有一个黑色格子，则它会变成黑色。求一直蔓延下去有多少黑色格子。
考虑模拟。
记录一个\(cnt[i][j]\)表示\((i, j)\)旁边的黑色格子数，每次从上一轮新增的黑色格子扫描邻格使得邻格的\(cnt\)加一，然后把之前没被判断过的白色格子存下来。下一轮就判断这些格子是不是恰好只有一个黑色邻居。
这样每个格子最多只会入队一次，扫描一次邻格。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;void solve() {int n, m;std::cin >> n >> m;std::vector<std::string> s(n);for (int i = 0; i < n; ++ i) {std::cin >> s[i];}std::vector cnt(n, std::vector<int>(m));std::vector<std::pair<int, int>> a;for (int i = 0; i < n; ++ i) {for (int j = 0; j < m; ++ j) {if (s[i][j] == '#') {cnt[i][j] = 1;a.emplace_back(i, j);}}}const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};while (1) { std::vector<std::pair<int, int>> na;for (auto & [x, y] : a) {if (cnt[x][y] == 1) {s[x][y] = '#';}}for (auto & [x, y] : a) {if (s[x][y] == '#') {for (int i = 0; i < 4; ++ i) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= n || ny < 0 || ny >= m) {continue;}if ( ++ cnt[nx][ny] == 1) {na.emplace_back(nx, ny);}}}}if (na.empty()) {break;}a = na;}int ans = 0;for (auto & t : s) {ans += std::ranges::count(t, '#');}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}
E - Count Sequences 2
题意：第\(i\)个物品有\(C_i\)个，求不同的排列数模\(M\)的答案。\(\sum C_i \leq 5000\)。
这是多重集的排列数：\(\frac{(\sum_{i=1}^{n} C_i)!}{\prod_{i=1}^{n} C_i!}\)。
如果\(M\)是质数，则直接计算即可，可是\(M\)不一定是质数，那么也不一定有逆元。
考虑条件\(\sum C_i \leq 5000\)。考虑分解质因数。计算分母和分子的每个质因子的个数，那么相减就是每个质数的个数。
可以预处理\(f[n][i]\)表示\(n\)的阶乘里第\(i\)个质数出现了多少次。
点击查看代码
#include <bits/stdc++.h>using i64 = long long;int power(int a, int b, int p) {int res = 1;for (;b;b >>= 1, a = (i64)a * a % p) {if (b & 1) {res = (i64)res * a % p;}}return res;
}void solve() {int t, M;std::cin >> t >> M;constexpr int N = 5000;std::vector<int> primes, minp(N + 1);for (int i = 2; i <= N; ++ i) {if (minp[i] == 0) {minp[i] = i;primes.push_back(i);}for (auto & p : primes) {if (p * i > N) {break;}minp[p * i] = p;if (minp[i] == p) {break;}}}int k = primes.size();std::vector<int> id(N + 1);for (int i = 0; i < k; ++ i) {id[primes[i]] = i;}std::vector f(N + 1, std::vector<int>(k));for (int i = 2; i <= N; ++ i) {f[i] = f[i - 1];int x = i;while (x > 1) {++ f[i][id[minp[x]]];x /= minp[x];}}while (t -- ) {int n;std::cin >> n;int sum = 0;std::vector<int> cnt(k);for (int i = 1; i <= n; ++ i) {int x;std::cin >> x;sum += x;for (int j = 0; j < k; ++ j) {cnt[j] -= f[x][j];}}for (int i = 0; i < k; ++ i) {cnt[i] += f[sum][i];}int ans = 1;for (int i = 0; i < k; ++ i) {ans = (i64)ans * power(primes[i], cnt[i], M) % M;}std::cout << ans << "\n";}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);int t = 1;// std::cin >> t;while (t -- ) {solve();}return 0;
}