目录
Contest InfoSolutions A. Drinks ChoosingB. Sport MafiaC. Basketball ExerciseD1. Submarine in the Rybinsk Sea (easy edition)D2. Submarine in the Rybinsk Sea (hard edition)E. OpenStreetMapPractice Link
SolvedABCD1D2EF6/7OOOOOØ- O 在比赛中通过Ø 赛后通过! 尝试了但是失败了- 没有尝试题意: 有\(n\)个人，每个人喜欢吃第\(k_i\)种糖果，现在商店售卖的糖果是一盒两个的，要买最少数量的盒数，即\(\left\lceil \frac{n}{2} \right\rceil\)盒，并且使得尽量多的人吃上自己喜欢吃的糖果
思路： 将喜欢吃同一种糖果的人放在一起，每次贪心取两个给他们一盒，这样他们的贡献是满的。 剩下的肯定是每种糖果最多只有一个人喜欢吃，那么贡献就是剩余的盒数。
代码：
#include <bits/stdc++.h> using namespace std; #define N 1010 int n, k, a[N]; int main() { while (scanf("%d%d", &n, &k) != EOF) { memset(a, 0, sizeof a); for (int i = 1, x; i <= n; ++i) { scanf("%d", &x); ++a[x]; } int res = 0; int num = n / 2 + (n & 1); for (int i = 1; i <= k; ++i) { while (a[i] >= 2 && num > 0) { --num; a[i] -= 2; res += 2; } } printf("%d\n", res + num); } return 0; }题意： 有两种操作：
如果当前盒子里还有糖果，那么可以去掉一个糖果放入盒子一些糖果，糖果的数量是上次放入的数量$ + 1$ 问最终给出操作次数\(n\)以及最终盒子里的糖果数量\(k\)，问在操作过程中有多少种操作是第一种操作。思路： 答案显然是\(i \in [1, n]\)，并且满足：\[ \begin{eqnarray*} \frac{i * (i + 1)}{2} - (n - i) = k \end{eqnarray*} \] 相当于求\[ \begin{eqnarray*} \frac{i^2}{2} + \frac{3i}{2} - n - k = 0 \end{eqnarray*} \] 的方程的根。 显然该二次方程的对称轴在\(-\frac{3}{2}\)，所以在\([1, n]\)范围内的根只有一个。 所以直接暴力即可，因为\(i\)的枚举量大概在\(\mathcal{O}(\sqrt{n})\)
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long ll n, k; ll f(int x) { return 1ll * x * (x + 1) / 2; } int main() { while (scanf("%lld%lld", &n, &k) != EOF) { for (int i = 1; i <= n; ++i) { if (f(i) - (n - i) == k) { printf("%lld\n", n - i); break; } } } return 0; }题意： 有两排人，每排\(n\)个人，现在要求在这两排人中选出一些人，使得他们身高和最高，并且满足以下限制：
每一排中被选中的人数不能相邻选择的下标要是递增的代码： 考虑\(f[i][0/1/2]\)表示到第\(i\)个列位置，选择的是第一排的人，还是第二排的人，还是这一列不选。 转移即可。
思路：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 100010 int n; ll h[N][2], f[N][2]; int main() { while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) { scanf("%lld", &h[i][0]); } for (int i = 1; i <= n; ++i) { scanf("%lld", &h[i][1]); } memset(f, 0, sizeof f); f[1][0] = h[1][0]; f[1][1] = h[1][1]; ll res = 0; for (int i = 2; i <= n; ++i) { f[i][0] = h[i][0] + f[i - 1][1]; f[i][1] = h[i][1] + f[i - 1][0]; if (i > 2) { f[i][0] = max(f[i][0], h[i][0] + max(f[i - 2][0], f[i - 2][1])); f[i][1] = max(f[i][1], h[i][1] + max(f[i - 2][0], f[i - 2][1])); } } for (int i = 1; i <= n; ++i) { for (int j = 0; j < 2; ++j) { res = max(res, f[i][j]); } } printf("%lld\n", res); } return 0; }题意： 定义拼接函数\(f(a_1a_2 \cdots a_p, b_1b_2 \cdots b_q)\)：\[ f(a_1 \cdots a_p, b_1 \cdots b_q) = \left\{ \begin{array}{cccc} a_1a_2 \cdots a_{p - q +1}b_1a_{p - q + 2}b_2 \cdots a_{p - 1}b_{q - 1}a_pb_p && p \leq q \\ b_1b_2 \cdots b_{q - p}a_1b_{q - p + 1}a_2 \cdots a_{p - 1}b_{q - 1}a_pb_q && p < q \end{array} \right. \] 再给出一个序列\(a_i\)，询问：\[ \begin{eqnarray*} \sum\limits_{i = 1}^n\sum\limits_{j = 1}^n f(a_i, a_j) \bmod 998244353 \end{eqnarray*} \] 在这里保证\(a_i\)的位数相同。
思路： 既然位数相同，那么我们就知道\(f(a_i, ?)\)时\(a_i\)的贡献，以及\(f(?, a_i)\)时\(a_i\)的贡献，分别计算即可。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 100010 const ll p = 998244353; int n, a[N], len; int getlen(int x) { int res = 0; while (x) { ++res; x /= 10; } return res; } ll f(ll x) { ll tot = 0; vector <int> vec; while (x) { vec.push_back(x % 10); x /= 10; } reverse(vec.begin(), vec.end()); for (auto it : vec) { tot = tot * 10 + it; tot = tot * 10 + it; tot %= p; } return tot * n % p; } int main() { while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } len = getlen(a[1]); ll res = 0; for (int i = 1; i <= n; ++i) { res += f(a[i]); res %= p; } printf("%lld\n", res); } return 0; }题意： 同\(D1\)，但是不保证\(a_i\)位数相同。
思路： 位数最多只有\(10\)位，直接暴枚\(a_i\)对应的\(a_j\)的不同位数的贡献即可。\(10^9\)是一个十位的数字。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 100010 const ll p = 998244353; int n, a[N], num[N]; vector <vector<int>> vec; int sze[20]; int getlen(int x) { int res = 0; while (x) { ++res; x /= 10; } return res; } ll f(ll x, int a, int b, int n) { vector <int> vec, A(22, 0); while (x) { vec.push_back(x % 10); x /= 10; } reverse(vec.begin(), vec.end()); int len = a + b; if (a >= b) { auto it = vec.begin(); for (int i = 1; i <= a - b + 1; ++i) { A[i] = *it; ++it; } for (int i = a - b + 3; i <= len; i += 2) { A[i] = *it; ++it; } } else { auto it = vec.begin(); for (int i = b - a + 1; i <= len; i += 2) { A[i] = *it; ++it; } } // for (int i = 1; i <= len; ++i) printf("%d%c", A[i], " \n"[i == len]); ll tot = 0; for (int i = 1; i <= len; ++i) { tot = tot * 10 + A[i]; tot %= p; } return tot * n % p; } ll g(ll x, int b, int a, int n) { vector <int> vec, A(22, 0); while (x) { vec.push_back(x % 10); x /= 10; } reverse(vec.begin(), vec.end()); int len = a + b; if (a >= b) { auto it = vec.begin(); for (int i = a - b + 2; i <= len; i += 2) { A[i] = *it; ++it; } } else { auto it = vec.begin(); for (int i = 1; i <= b - a; ++i) { A[i] = *it; ++it; } for (int i = b - a + 2; i <= len; i += 2) { A[i] = *it; ++it; } } ll tot = 0; for (int i = 1; i <= len; ++i) { tot = tot * 10 + A[i]; tot %= p; } return tot * n % p; } int main() { while (scanf("%d", &n) != EOF) { vec.clear(); vec.resize(20); for (int i = 1; i <= n; ++i) { scanf("%d", a + i); vec[getlen(a[i])].push_back(a[i]); } for (int i = 1; i <= 10; ++i) sze[i] = (int)vec[i].size(); ll res = 0; for (int i = 1; i <= 10; ++i) if (sze[i]) { for (auto it : vec[i]) { for (int j = 1; j <= 10; ++j) if (sze[j]) { res += f(it, i, j, sze[j]); res %= p; res += g(it, i, j, sze[j]); res %= p; } } } printf("%lld\n", res); } return 0; }题意： 求\(n \cdot m\)的矩形中\(a \cdot b\)的所有小矩形的最小值之和。
思路： 二维\(RMQ\)是过不去的。。 考虑复杂度肯定为\(\mathcal{O}(nm)\)。 我们可以竖着枚举矩形右下角，然后再横着枚举。 考虑用\(3000\)个单调队列维护每一行枚举到的最小值，再用一个单调队列维护\(a \cdot b\)矩形内的最小值。 注意加点的时间以及删点的判断。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 3010 int n, m, a, b; ll g[N * N], x, y, z; int B[N][N], l[N], r[N], que[N], L, R; int get(int x, int y) { return (x - 1) * m + y - 1; } int main() { while (scanf("%d%d%d%d", &n, &m, &a, &b) != EOF) { L = 1, R = 0; for (int i = 1; i <= n; ++i) l[i] = 1, r[i] = 0; scanf("%lld%lld%lld%lld", g, &x, &y, &z); for (int i = 1; i <= n * m; ++i) g[i] = (g[i - 1] * x + y) % z; for (int i = 1; i <= n; ++i) { for (int j = 1; j < b; ++j) { while (l[i] <= r[i] && g[get(i, j)] < g[B[i][r[i]]]) { --r[i]; } B[i][++r[i]] = get(i, j); } } ll res = 0; for (int i = 1; i <= a; ++i) { while (L <= R && g[B[i][l[i]]] < g[que[R]]) --R; que[++R] = B[i][l[i]]; } for (int j = b; j <= m; ++j) { for (int i = 1; i <= n; ++i) { while (l[i] <= r[i] && abs(B[i][l[i]] - get(i, j)) >= b) ++l[i]; while (l[i] <= r[i] && g[get(i, j)] < g[B[i][r[i]]]) --r[i]; B[i][++r[i]] = get(i, j); } L = 1, R = 0; for (int i = 1; i < a; ++i) { while (L <= R && g[B[i][l[i]]] < g[que[R]]) --R; que[++R] = B[i][l[i]]; } for (int i = a; i <= n; ++i) { while (L <= R && abs(que[L] - get(i, j)) >= (a - 1) * m + b) ++L; while (L <= R && g[B[i][l[i]]] < g[que[R]]) --R; que[++R] = B[i][l[i]]; res += g[que[L]]; } } printf("%lld\n", res); } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11204775.html
