目录
Contest InfoSolutions A. DIY Wooden LadderB. PillarsC. Array SplittingD. Yet Another Subarray ProblemE. Culture CodePractice Link
SolvedABCDEF5/6OOOOØ- O 在比赛中通过Ø 赛后通过! 尝试了但是失败了- 没有尝试签到题。
#include <bits/stdc++.h> using namespace std; #define N 100010 int n, a[N]; int main() { int T; scanf("%d", &T); while (T--) { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", a + i); sort(a + 1, a + 1 + n); int res = 0; for (int i = 2; i < n; ++i) { res = max(res, min(a[i] - 1, i - 1)); } printf("%d\n", res); } return 0; }题意： 有\(n\)根柱子，每根柱子上有一个磁盘，一个磁盘能从第\(i\)根柱子移动到第\(j\)根柱子的前提是：
第\(j\)根柱子上没有磁盘或者第\(i\)根柱子上的磁盘半径颜色小于第\(j\)根柱子的磁盘 现在给出每根柱子上磁盘的半径，问能够存在一种方案使得将所有的磁盘都移动的一根柱子上思路： 考虑假设能将所有磁盘移动到一根柱子上，那么最终肯定是移动到初始磁盘半径最大的那根柱子上。 那么考虑从这个柱子开始，每次往两边扩展，取大的贪心往这根柱子上移动。 如果不能移动就是不行。 因为考虑最后那根柱子上的磁盘半径肯定是递增的，所以不可能存在跨越移动的情况。
代码：
#include <bits/stdc++.h> using namespace std; #define N 200010 int n, a[N]; int main() { while (scanf("%d", &n) != EOF) { for (int i = 1; i <= n; ++i) scanf("%d", a + i); int pos = 1; for (int i = 2; i <= n; ++i) { if (a[i] > a[pos]) pos = i; } int l = pos - 1, r = pos + 1; bool F = 1; int lst = a[pos]; while (l >= 1 || r <= n) { if (l < 1) { if (a[r] >= lst) { F = 0; break; } lst = a[r]; ++r; } else if (r > n) { if (a[l] >= lst) { F = 0; break; } lst = a[l]; --l; } else { if (a[l] > a[r]) { if (a[l] >= lst) { F = 0; break; } lst = a[l]; --l; } else { if (a[r] >= lst) { F = 0; break; } lst = a[r]; ++r; } } } puts(F ? "YES" : "NO"); } return 0; }题意： 有一个长度为\(n\)的序列\(a_i\)，要将序列分成\(k\)段，使得下式最小：\[ \begin{eqnarray*} \sum\limits_{i = 1}^k (max(i) - min(i)) \end{eqnarray*} \] 其中\(max(i)\)表示第\(i\)段中最大的数，\(min(i)\)表示第\(i\)段中最小的数，保证\(a_i\)是单调非降序的。
思路： 考虑\(a_i\)是单调非降的，那么\(max(i) - min(i)\)这个东西肯定是区间的末尾减去区间的开头，那么注意到区间的末尾的下一个数即为下一个区间的开头，变换式子有：\[ \begin{eqnarray*} a_n - a_1 + \sum\limits_{i = 1}^{k - 1} a_{b_i} - a_{b_i + 1} \end{eqnarray*} \] 其中\(b_i\)表示第\(i\)段末尾的下标。 然后这个东西用堆维护一下，贪心取\(k - 1\)个即可。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 300010 int n, k, a[N]; int main() { while (scanf("%d%d", &n, &k) != EOF) { for (int i = 1; i <= n; ++i) { scanf("%d", a + i); } ll res = a[n] - a[1]; vector <int> vec; for (int i = 1; i < n; ++i) { vec.push_back(a[i] - a[i + 1]); } sort(vec.begin(), vec.end()); for (int i = 0; i < k - 1; ++i) { res += vec[i]; } printf("%lld\n", res); } return 0; }题意： 有一个序列\(a_i\)，定义一个子区间的价值：\[ \begin{eqnarray*} \sum\limits_{i = l}^r a_i - k \left\lceil \frac{r - l + 1}{m} \right\rceil \end{eqnarray*} \] 问所有子区间中最大的价值是多少?
思路： 维护一个前缀和\(S\)，那么变换式子有：\[ \begin{eqnarray*} S_r - S_l - k \left\lceil \frac{r - l}{m} \right\rceil \end{eqnarray*} \] 我们希望将\(\left\lceil \frac{r - l}{m} \right\rceil\)拆开成\(\left\lceil \frac{r}{m} \right\rceil - \left\lceil \frac{l}{m} \right\rceil\)，但是这样是不行的。 注意到\(m\)很小，所以可以通过分类讨论一下将\(\left\lceil \frac{x}{m} \right\rceil\)按\(x \bmod m\)进行分类，然后讨论一下合并即可。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define N 300010 int n, m, k; ll a[N]; ll f[20]; int main() { while (scanf("%d%d%d", &n, &m, &k) != EOF) { for (int i = 1; i <= n; ++i) scanf("%lld", a + i); ll res = 0; for (int i = 0; i < m; ++i) f[i] = 0; f[0] = -k; for (int i = 1; i <= n; ++i) { a[i] += a[i - 1]; for (int j = 0; j < m; ++j) { if (m - i % m >= m - j) { res = max(res, a[i] - f[j] - 1ll * k * (i / m + 1)); } else { res = max(res, a[i] - f[j] - 1ll * k * (i / m + 2)); } } f[i % m] = min(f[i % m], a[i] - 1ll * k * (i / m + 1)); } printf("%lld\n", res); } return 0; }题意： 有\(n\)个俄罗斯套娃，每个套娃有内径\(in_i\)和外径\(out_i， out_i > in_i\)，一个套娃\(i\)能套在套娃\(j\)里面，当且仅当\(out_i \leq in_j\)。 定义一组套在的额外空间为\[ \begin{eqnarray*} in_1 + (in_2 - out_1) + (in_3 - out_3) + \cdots + (in_k - out_{k - 1}) \end{eqnarray*} \]
其中\(in_k\)为最外成那个套娃的内径。 定义一组套娃是个极大套娃组：当且仅当不能再有另外一个套娃套在他们身上了。 询问有多少种极大套娃组的额外空间最小。
思路： 先将套娃分成两类：
第一类：没有另外一个套娃能套在它头上第二类：至少存在一个套娃能够套在它头上那么考虑把方案数全都算在第一类套娃头上。 那么先将所有套娃按内径从小到大排序，那么定义\(f[i]\)表示第\(i\)个套娃产生最小额外空间时的方案数，那么它能从第\(j\)个套娃转移过来当且仅当第\(out_j <= in_i\)。 那么再考虑变换额外空间的式子：\[ \begin{eqnarray*} in_k + \sum\limits_{i = 1}^{k - 1} out_i - in_i \end{eqnarray*} \] 这样就变成了极大套娃组的额外空间中除了第一个套娃，其他套娃的贡献独立，为\(out_i - in_i\)。 那么转移的时候维护一下最小额外空间，如果最小额外空间相同就合并方案数，否则更新方案数。
代码：
#include <bits/stdc++.h> using namespace std; #define ll long long #define INFLL 0x3f3f3f3f3f3f3f3f #define N 400010 #define pii pair <ll, ll> #define fi first #define se second const ll p = 1e9 + 7; int n, tot; pii a[N]; int b[N]; ll c[N], d[N]; struct SEG { struct node { ll Min, sum; node() { sum = 0; Min = INFLL; } node(ll Min, ll sum) : Min(Min), sum(sum) {} node operator + (const node &other) const { node res = node(); if (Min == other.Min) { res.Min = Min; res.sum = (sum + other.sum) % p; } else if (Min < other.Min) { res.Min = Min; res.sum = sum; } else { res.Min = other.Min; res.sum = other.sum; } return res; } }t[N << 2], res; void build(int id, int l, int r) { t[id] = node(); if (l == r) return; int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); } void update(int id, int l, int r, int pos, node x) { if (l == r) { t[id] = t[id] + x; return; } int mid = (l + r) >> 1; if (pos <= mid) update(id << 1, l, mid, pos, x); else update(id << 1 | 1, mid + 1, r, pos, x); t[id] = t[id << 1] + t[id << 1 | 1]; } void query(int id, int l, int r, int ql, int qr) { if (l >= ql && r <= qr) { res = res + t[id]; return; } int mid = (l + r) >> 1; if (ql <= mid) query(id << 1, l, mid, ql, qr); if (qr > mid) query(id << 1 | 1, mid + 1, r, ql, qr); } }seg; int id(int x) { return lower_bound(b + 1, b + 1 + tot, x) - b; } int main() { while (scanf("%d", &n) != EOF) { tot = 0; for (int i = 1; i <= n; ++i) scanf("%lld%lld", &a[i].fi, &a[i].se); for (int i = 1; i <= n; ++i) { b[++tot] = a[i].fi; b[++tot] = a[i].se; } sort(b + 1, b + 1 + tot); tot = unique(b + 1, b + 1 + tot) - b - 1; sort(a + 1, a + 1 + n, [](pii x, pii y) { if (x.se != y.se) return x.se < y.se; return x.fi > y.fi; }); ll Min = INFLL; ll res = 0; seg.build(1, 1, tot); for (int i = 1; i <= n; ++i) { seg.res = SEG::node(); seg.query(1, 1, tot, 1, id(a[i].se)); if (seg.res.Min == INFLL) { seg.res = SEG::node(-a[i].fi + a[i].se, 1); seg.update(1, 1, tot, id(a[i].fi), seg.res); c[i] = a[i].se; d[i] = 1; } else { c[i] = a[i].se + seg.res.Min; d[i] = seg.res.sum; seg.res.Min += -a[i].fi + a[i].se; seg.update(1, 1, tot, id(a[i].fi), seg.res); } if (a[i].fi > a[n].se) { Min = min(Min, c[i]); } } for (int i = 1; i <= n; ++i) { if (a[i].fi > a[n].se && c[i] == Min) { res = (res + d[i]) % p; } } printf("%lld\n", res); } return 0; }转载于:https://www.cnblogs.com/Dup4/p/11229974.html
