马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
x
A. Fibonacciness
标题大意
给你四个数字abde，让你找到一个中间值c，问 a + b = c a + b = c a+b=c ， b + c = d b + c = d b+c=d ， c + d = e c + d = e c+d=e 最多能有几个式子创建
解题思绪
显然最多就六种情况，暴力枚举即可
代码实现
- for _ in range(int(input())):
- a1, a2, a4, a5 = map(int, input().split())
- t1 = a1 + a2
- t2 = a5 - a4
-
- ans = [0, 0]
-
- ans[0] += a1 + a2 == t1
- ans[0] += a2 + t1 == a4
- ans[0] += t1 + a4 == a5
-
- ans[1] += a1 + a2 == t2
- ans[1] += a2 + t2 == a4
- ans[1] += t2 + a4 == a5
-
- print(max(ans))
标题大意
给你一个n行m列的排列，请你给出一个长度为n的排列，使得这n行每次出一个数字，执行m次，能按序次出完这 n ∗ m n*m n∗m 个数字
解题思绪
对于同一行来说，下一次要出的数字会和本次相差n，全部只必要看排序后相邻是否相差n即可，每一行最小的数字就是他们的初始序次
代码实现
- #include <bits/stdc++.h>
- using i64 = long long;
- int main() {
- std::ios::sync_with_stdio(false);
- std::cin.tie(0);
- std::cout.tie(0);
- int t;
- std::cin >> t;
- while (t--) {
- int n, m, f = 1;
- std::cin >> n >> m;
- std::vector<int> ans(n + 1);
- std::vector<std::vector<int>> v(n, std::vector<int>(m));
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- std::cin >> v[i][j];
- }
- std::sort(v[i].begin(), v[i].end());
- for (int j = 1; j < m; j++) {
- if (v[i][j] - v[i][j - 1] != n) {
- f = 0;
- }
- }
- ans[v[i][0]] = i + 1;
- }
- if (f) {
- for (int i = 0; i < n; i++) {
- std::cout << ans[i] << " \n"[i == n - 1];
- }
- } else {
- std::cout << "-1\n";
- }
- }
- }
标题大意
有n个数字（保证n是偶数），执行n/2次操纵，每次Alice先选一个数字a，Bob再选一个数字b，如果满足 a + b = k a + b = k a+b=k，则可以加一分。 Alice会最小化分数，Bob会最大化分数，二者都接纳最优计谋，问末了得分会是多少
解题思绪
由于是Alice先手，全部Bob每次总能找到一个数字与Alice挑选的数字匹配（如果存在可以匹配的数字），因此只必要计算有多少数对满足等式即可
代码实现
- #include <bits/stdc++.h>
- using i64 = long long;
- int main() {
- std::ios::sync_with_stdio(false);
- std::cin.tie(0);
- std::cout.tie(0);
- int t;
- std::cin >> t;
- while (t--) {
- int n, k;
- std::cin >> n >> k;
- std::vector<int> f(n + 1);
- for (int i = 0; i < n; i++) {
- int x;
- std::cin >> x;
- f[x]++;
- }
- i64 ans = 0;
- for (int i = std::max(1, k - n); i < std::min(n + 1, (k + 1) / 2); i++) {
- int j = k - i;
- if (j >= 1 && j <= n && j > i) {
- ans += std::min(f[i], f[j]);
- }
- }
- if (k % 2 == 0) {
- int mid = k / 2;
- if (mid >= 1 && mid <= n) {
- ans += f[mid] / 2;
- }
- }
- std::cout << ans << "\n";
- }
- }
标题大意
有n个数字，可以多次执行 a i − m i n ( a i , a i − 1 ) a_i - min(a_i, a_{i - 1}) ai−min(ai,ai−1)， a i − m i n ( a i − 1 , a i − 1 ) a_i - min(a_{i - 1}, a_{i - 1}) ai−min(ai−1,ai−1)，问末了能否让序列单调不递减
解题思绪
对于一个单调不递减的序列，显然不绝执行操纵之后除了末了一位都会变成0，因此只必要不绝的执行操纵，末了检查前n-1位是不是0即可
代码实现
- #include <bits/stdc++.h>
- using i64 = long long;
- int main() {
- std::ios::sync_with_stdio(false);
- std::cin.tie(0);
- std::cout.tie(0);
- int t;
- std::cin >> t;
- while (t--) {
- int n, f = 0;
- std::cin >> n;
- std::vector<int> a(n);
- for (int i = 0; i < n; i++) {
- std::cin >> a[i];
- }
- for (int i = 1; i < n; i++) {
- int minn = std::min(a[i - 1], a[i]);
- a[i - 1] -= minn;
- a[i] -= minn;
- }
- for (int i = 0; i < n - 1; i++) {
- f += a[i];
- }
- if (f) {
- std::cout << "NO\n";
- } else {
- std::cout << "YES\n";
- }
- }
- }
标题大意
给你两张图F和G，每次操纵可以在F中删或者加一条边，末了要求让F和G联通性相同，问最小操纵次数是多少
解题思绪
按照题意模拟，对F中联通但是G不联通的部门直接删边ans++，对F中不联通G中联通的部门加边，末了加上二者连通块数量即可
代码实现
- #include <bits/stdc++.h>
- using i64 = long long;
- class DSU {
- public:
- int cnt;
- std::vector<int> fa, rank, siz;
- DSU(int n) : cnt(n), fa(n + 1), rank(n + 1, 0), siz(n + 1, 1) {
- for (int i = 1; i <= n; i++) {
- fa[i] = i;
- }
- }
- int find(int x) {
- if (fa[x] != x) {
- fa[x] = find(fa[x]);
- }
- return fa[x];
- }
- void merge(int x, int y) {
- int X = find(x), Y = find(y);
- if (X != Y) {
- if (rank[X] >= rank[Y]) {
- fa[Y] = X;
- siz[X] += siz[Y];
- if (rank[X] == rank[Y]) {
- rank[X]++;
- }
- } else {
- fa[X] = Y;
- siz[Y] += siz[X];
- }
- cnt--;
- }
- }
- int size() {
- return cnt;
- }
- int count(int x) {
- return siz[find(x)];
- }
- };
- int main() {
- std::ios::sync_with_stdio(false);
- std::cin.tie(0);
- int t;
- std::cin >> t;
- while (t--) {
- i64 n, m1, m2, ans = 0;
- std::cin >> n >> m1 >> m2;
- std::vector<std::pair<int, int>> F(m1);
- for (int i = 0; i < m1; i++) {
- std::cin >> F[i].first >> F[i].second;
- }
- DSU dsuG(n);
- for (int i = 0; i < m2; i++) {
- int u, v;
- std::cin >> u >> v;
- dsuG.merge(u, v);
- }
- DSU dsuF(n);
- for (auto [u, v] : F) {
- if (dsuG.find(u) != dsuG.find(v)) {
- ans++;
- } else {
- dsuF.merge(u, v);
- }
- }
- std::cout << ans + dsuF.size() - dsuG.size() << "\n";
- }
- }
标题大意
给你两个数字nk，问有多少个长度不超过n且最大元素不超过k的数组满足累乘后的值为x，输出x=1~k时的方案数，对最方案数模998244353
解题思绪
1是一个很特殊的数字，他可以让长度增加而累乘的值不增加，首先考虑最大值是1的情况发现只有n种，再考虑最小值不为1的情况，可以发现末了数组长度不会特殊长，而对于有1的情况基于没有1的情况填充即可
代码实现
- #include <bits/stdc++.h>
- using i64 = long long;
- const int MOD = 998244353;
- i64 ksm(i64 a, i64 n) {
- i64 res = 1;
- a %= MOD;
- while (n) {
- if (n & 1) res = res * a % MOD;
- a = a * a % MOD;
- n >>= 1;
- }
- return res;
- }
- int main() {
- std::ios::sync_with_stdio(false);
- std::cin.tie(0);
- std::cout.tie(0);
- int t;
- std::cin >> t;
- while (t--) {
- i64 k, n;
- std::cin >> k >> n;
- if (k == 1) {
- std::cout << (n % MOD) << "\n";
- continue;
- }
- i64 p2 = 0;
- while ((1ll << (p2 + 1)) <= k) {
- p2++;
- }
- // 当序列只有一个大于1的数字时
- i64 C = ((n + 1) % MOD) * (n % MOD) % MOD;
- C = C * ksm(2, MOD - 2) % MOD;
- std::vector<i64> ans(k + 1), last(k + 1);
- for (int i = 2; i <= k; i++) { // 选取方案不包含1
- last[i] = 1;
- }
- for (int i = 1; i <= k; i++) {
- ans[i] = (ans[i] + last[i] * C) % MOD;
- }
- for (int len = 2; len <= std::min(p2, n); len++) {
- // 先填入大于1的数字
- std::vector<i64> now(k + 1);
- for (int i = 2; i <= k; i++) { // 填入一个新数字i
- for (int j = i; j <= k; j += i) { // 更新乘积
- now[j] = (now[j] + last[j / i]) % MOD;
- }
- }
- // 剩下的长度用1填充
- C = C * ((n + 1 - len) % MOD + MOD) % MOD;
- C = C * ksm(len + 1, MOD - 2) % MOD;
- for (int i = 1; i <= k; i++) {
- ans[i] = (ans[i] + now[i] * C) % MOD;
- }
- last = now;
- }
- ans[1] = n % MOD;
- for (int i = 1; i <= k; i++) {
- std::cout << ans[i] << " \n"[i == k];
- }
- }
- }
|
