ARC 067
F - Yakiniku Restaurants
题意
(n) 家饭店，(m) 张餐票，第 (i) 家和第 (i+1) 家饭店之间的距离是 (A_i) ，在第 (i) 家饭店用掉第 (j) 张餐票会获得 (B_{i, j}) 的好感度，可以从任意一个饭店出发，求好感度减经过的距离和的差的最大值。
(2 le n le 5000, 1 le m le 200, 1 le A_{i, j}, B_{i, j} le 10^9)
题解
做题千万条，看题第一条。
显然我们不会走回头路，那么每次我们选择的一定是一段连续区间 ([l, r]) 。
考虑每个 (B_{i, j}) 对于哪些区间有贡献，找到左右第一个比它的 (B_{x, j}, B_{y, j} ge B_{i, j}) ，那么它贡献的区间其实就是 (l in (x, i], r in [i, y)) 。
我们利用单调栈算出端点，然后矩形加利用二维差分实现即可。
(mathcal O(n^2 + nm))
代码
ARC 068
F - Solitaire
题意
有一个双端队列。
首先将 (n) 个数 (1sim n) 从小到大任意前后地添入队列。然后任意前后地弹出队列，求最后弹出来的排列中，第 (k) 个数为 (1) 的排列有多少种。
(1 le k le n le 2000)
题解
一开始添完的序列性质显然是将 (1) 分成两段，左边递减，右边递增。
由于构造合法序列是左右弹元素，那么性质就比较好推了。
- 第 (k) 个数为 (1) ；
- 前 (k - 1) 个数可拆分为至多两个下降子序列；
- 前 (k - 1) 个数的最小值一定大于后 (n - k) 个数的最大值。
先考虑最后 (n - k) 个数的方案，如果我们确定了前 (k) 个数，那么剩下的 (n - k) 个数是由一个单调队列弹出来的，除了最后一次只能弹一个，别的每次都有两种选择，所以方案是 (2^{max(0, n - k - 1)}) 。
然后前面拆分成至多两个下降子序列，这个和 这道题 是一样的。
我们现在只需要满足第一个限制了，由于第 (k) 个数是需要最小值，用至多选 (k) 个和 (k - 1) 个差分一下即可。
然后利用之前那个题的组合数结论就可以做到 (mathcal O(n)) 了。
其实那个组合数有个更优美的形式，也就是 (displaystyle {n + m choose m} - {n + m choose m - 1}) ，意义明显许多。
代码
ARC 070
E - Narrow Rectangles
题意
有 (n) 个高为 (1) 的矩形，第 (i) 个矩形 (y) 轴范围为 ([i - 1, i]) ，(x) 轴范围为 ([l_i, r_i]) 。
需要横向移动一些矩形，使得所有矩形是连通的（角也算），对于一个矩形，横向移动 (x) 距离的代价为 (x) ，求出最小代价。
(1 le n le 10^5, 1 le l le r le 10^9)
题解
首先考虑暴力 (dp) 即令 (f_{i, j}) 为第 (i) 层矩形右端点为 (j) ，前 (i) 层已经联通所需要的最小代价。
令 (len_i = r_i - l_i) ，每次只需要两条线段相交即可。转移十分显然：
我们可以把 (f_i) 看做一个关于 (p) 的函数，设 (g_i(p) = |r_i - p|) ，那么形式为：
不难观察到函数这个图像其实是一个分段一次函数，且斜率从 (-(i - 1), - (i - 2), cdots, 0, cdots, i - 2, i - 1) 递增（拆开重合点）。（不难利用归纳证明）其实也是一个凹函数，最小值在 (k = 0) 处取得。
那么考虑后面那个 (min) 等价于把 (k_x < 0) 的部分向左平移 (len_{i - 1}) （因为我们想尽量向右取），(k_x > 0) 的部分向右平移 (len_i) ，然后最后全局加上 (g_i) 就行了。
我们其实可以用 (Splay) 维护这个凸壳，每次只需要支持区间加一次函数，全局平移即可。
但显然可以更方便地解决，由于最后我们只需要求 (k = 0) 时候的函数值，我们利用对顶堆维护 (k < 0, k > 0) 的位置，每次讨论一下插入的绝对值函数的 (0) 点位置即可。
讨论的时候可以顺便计算一下当前的答案。
总结
对于加绝对值函数，并且取 (min, max) 的 (dp) 都可以考虑是否存在凸壳，然后通过 线段树/ (Splay) / 对顶堆 维护这个 (dp) 值即可。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
typedef long long ll;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("E.in", "r", stdin);
freopen ("E.out", "w", stdout);
#endif
}
const int N = 1e5 + 1e3;
int n, l[N], r[N], len[N];
ll tl, tr, ans;
priority_queue<ll> L;
priority_queue<ll, vector<ll>, greater<ll>> R;
int main () {
File();
For (i, 1, n = read())
l[i] = read(), r[i] = read(), len[i] = r[i] - l[i];
L.push(r[1]); R.push(r[1]);
For (i, 2, n) {
tl -= len[i - 1]; tr += len[i];
ll lp = L.top() + tl, rp = R.top() + tr;
if (lp <= r[i] && r[i] <= rp)
L.push(r[i] - tl), R.push(r[i] - tr);
else if (r[i] >= rp) {
ans += r[i] - rp; R.pop(); L.push(rp - tl);
R.push(r[i] - tr); R.push(r[i] - tr);
} else {
ans += lp - r[i]; L.pop(); R.push(lp - tr);
L.push(r[i] - tl); L.push(r[i] - tl);
}
}
printf ("%lld
", ans);
return 0;
}
F - HonestOrUnkind
题意
有 (n = a + b) 个人，其中有 (a) 个人是诚实的，(b) 个人是不友好的。每次你可以问 (x) ： (y) 是不是一个诚实的人。如果 (x) 是诚实的，那么一定会回答真正的答案。否则，他会随便告诉你一个结果。（交互库有一定策略地回答。）
现在告诉你 (a, b) ，你需要确定是否一定能问出来。如果问不出来输出 Impossible 。如果能问出来，需要在 (2n) 步内问出来。
题解
首先我们考虑什么时候是 Impossible ，显然当 (b ge a) 的时候，(b) 可以很好的隐藏在 (a) 中。因为问任意一个人，(b) 都可以根据 (a) 的决策，来颠倒黑白。只有当 (a) 超过 (n) 的一半的时候，我们问任意一个人都可以根据 ( ext{Y, N}) 中较多的那项确定类别。
接下来，我们不难想到一个乱搞。就是一开始随机问几个人，然后问所有人他的类别，就可以确定类别了。如果是老实人，然后就可以一遍问它就能得到所有人的类别了。我们打乱一下询问顺序，那么这样期望下是 (3n) 的。
我们其实可以继续优化一下乱搞，加上如下几个优化：
- 如果问出当前人的类别，之前回答类别不同的人，肯定不是老实人，之后我们全都跳过不问即可。
- 如果我们当前问的 ( ext{Y, N}) 其中较多的那个个数，大于剩下没有确定的不友好的人数，就可以确定这个人的类别了。
- 如果当前只剩下友好/不友好，我们就可以直接不问，然后确定即可。
期望应该是 (1.5n) 的？然后全都加上。。就可以过啦qwq（我也是交了十几发才艹过的。。）
显然有确定性做法，我们需要基于这样一个结论，如果 (x) 说 (y) 是不友好的，那么 (x, y) 肯定不可能同时是诚实的，如果我们忽略他们，剩下的老实人个数仍然大于一半。
我们用个栈，把每个人放进去，如果栈顶这个人说当前这个人是不友好的，我们把栈顶弹出，然后忽略他们。
然后最后剩下了 (a_0, cdots, a_{k - 1}) 其中每个 (a_i) 都说 (a_{i + 1}) 是诚实的，那么显然 (a_{k - 1}) 一定是诚实的。为什么呢？因为其中一定有个人是老实人，那么在它后面的所有人一定都是老实人，那么最后一个人必是老实人。
然后我们就可以在稳定的 (2n) 次里问出所有人的类别啦。（好妙啊～）
代码
放个瞎JB乱搞。
ARC 072
F - Dam
题意
有一个容量为 (L) 的水库，每天晚上可以放任意体积的水。每天早上会有一定温度和体积的水流入水库，且要保证流入水之后水的总体积不能超过 (L) 。令体积分别为 (V_1,V_2) ，温度分别为 (t_1,t_2) 的水混合后的温度为 (displaystyle frac {V_1 * t_1 + V_2 * t_2} {V_1 + V_2}) 。初始水库为空。现给出 (n) 天流入水的体积和温度，分别最大化每一天中午水库满容量时的水温。
(1 le n le 5 imes 10^5)
题解
一道很有意思的题~
我们可以发现两个性质：
- 当前水温小于以前水温时必然会拉低总水温，所以一定会和前面的水混合，直接向前不断合并即可。
- 当前水温大于前面时，直接将前面舍弃可以得到更高的温度，但要求总量必须为 (L) ，这样有可能出现不够加满水坝的情况，因此还要保留一段。
我们利用一个单调队列（队列中的元素队首到队尾按 (t) 单调递增），每次当前体积 (>L) 我们不断弹掉队首，使得体积变小。然后队尾温度比队尾前一个低，我们就合并，直至不能合并即可。
至于为什么是对的呢？你可以考虑把每个水看做一个向量，我们相当于看向量和的斜率，我们其实就是需要贪心地维护一个下凸壳，本质上是一样的。
代码
ARC 073
E - Ball Coloring
题意
有 (n) 个盒子，每个盒子里面有两个球，分别写了一个数字 (x_i, y_i) 。现在需要把每个盒子其中的一个球染成红色，另外一个染成蓝色。
令 (R_{max}) 为红球数字最大值，其他的同理，求 ((R_{max} - R_{min})(B_{max} - B_{min})) 的最小值。
(n le 2 imes 10^5)
题解
脑子是个好东西，我也想要一个QAQ
令全局 (x_i, y_i) 最大值为 (A_{max}) ，最小值为 (A_{min}) 。显然 (R_{max}, B_max) 其中一个需要取到 (A_max) ，(min) 同理。
我们考虑分两种情况讨论。
-
最大值和最小值被两边分别取到了。
不妨令 (R_max = A_max, B_min = A_min) ，那么我们显然需要最小化 (B_max) ，最大化 (R_min) 。
那么显然对于每个盒子，我们把较小的那个给 (B) ，较大的给 (R) ，显然是最优的。
-
最大值和最小值都给一边取到了。
不妨令 (R_max = A_max, R_min = A_min) ，那么我们就需要最小化 (B_max - B_min) 。
我们考虑从小到大枚举 (B_min) ，然后动态维护 (B_max) 的最小值。
如果当且 (B_min = A_min) ，我们显然 (B_max) 取到所有的 (min{x_i, y_i}) 的最大值是最优的。
然后我们每次把 (B_min) 变大，也就是翻转 (B_min) 的颜色，随便维护一下最值即可。
(mathcal O(n log n))
代码
F - Many Moves
题意
一个长为 (n) 的数轴，一开始上面有两个盒子在 (A, B) ，有 (q) 次要求，每次给出一个坐标 (x_i) ，需要把其中一个盒子移到 (x_i) ，问最少移动的距离和。
(1 le n, q le 2 imes 10^5)
题解
唯一一道自己做出来的 (F) TAT
虽然很水。
假设当前处理第 (p) 个要求。考虑 (dp) ，设 (f_{i, j}) 为当前两个盒子分别在 (i, j) 的最少距离和，转移显然。
但显然每次我们有个盒子的位置一定在 (x_{p - 1}) ，我们只需要记 (f_i) 为其中一个盒子在 (x_{p - 1}) ，另外一个在 (i) 的最少距离和。
显然一次我们不会同时移动两个盒子，这样一定不优。
- (i ot = x_{p - 1}) ，显然不动 (i) ，动 (x_{p - 1}) 即可，所以有 (f'_i = f_i + |x_p - x_{p - 1}|) 。
- 对于 (i = x_{p - 1}) 我们考虑枚举上次的另外一个位置 (j) ，那么有 (f_{x_{p - 1}} = min_{j} {f_j + |x_p - j|}) 。
直接实现是 (mathcal O(n^2)) 的，对于第一个转移就是全局加，对于第二个转移拆绝对值，然后维护 (f_i pm i) 的最小值即可。
都可以用线段树实现 (mathcal O(n log n)) 。
代码
ARC 075
F - Mirrored
题意
定义 $rev(n) $ 为将 (n) 的十进制位翻转的结果，例如 (rev(123) = 321, rev(4000) = 4) 。
给定正整数 (D) ，求有多少个 (N) 满足 (rev(N) = N + D) 。
(1 le D < 10^9)
题解
考虑固定长度为 (L + 1) ，假设从低到高每一位分别是 (b_i) ，那么其实就是
我们等价求把 (0 sim lfloor frac L2 floor) 的每个 (v_i = 10^{L - i} - 10^i) 乘上 (-9 sim 9) 和为 (D) 的方案数。（对于每个 (-9 sim 9) 对应了两个数的一种组合）。
直接 (dfs) 可能会 TLE ，考虑利用性质优化，我们观察到：
那么意味着如果我们确定前 (i) 位，组合出来的数与 (D) 相差 (v_i) 时，显然是以后无论如何也无法恢复的。
那么每一步其实我们的填法从 (18) 降低到只有 (2) 种了。
我们需要枚举的长度应该是 (L_D sim 2L_D) （ (L_D) 为 (D) 十进制的长度），因为我们加减的范围应该是刚好 (L_D) 的，超过 (2L_D) 加减最小数已经超过了 (D) 显然无法得到。
有科学的复杂度为
跑的挺快的。
代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
using namespace std;
typedef long long ll;
template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("F.in", "r", stdin);
freopen ("F.out", "w", stdout);
#endif
}
int D, len, up;
ll Pow[20], v[20];
int Pool[20], *d = Pool + 10;
ll Dfs(ll cur, int dep) {
if (dep == up) return !cur;
int t = cur / v[dep]; ll res = 0;
For (i, t - 1, t + 1) if (abs(i) <= 9 && abs(cur - i * v[dep]) < v[dep])
res += (d[i] - (i >= 0 && !dep)) * Dfs(cur - i * v[dep], dep + 1);
return res;
}
int main () {
File();
for (int tmp = (D = read()); tmp; tmp /= 10) ++ len;
Pow[0] = 1;
For (i, 1, 18)
Pow[i] = 10ll * Pow[i - 1];
Rep (i, 10) Rep (j, 10) ++ d[i - j];
ll ans = 0;
For (i, len, len << 1) {
For (j, 0, up = i >> 1)
v[j] = Pow[i - j - 1] - Pow[j];
ans += (i & 1 ? d[0] : 1) * Dfs(D, 0);
}
printf ("%lld
", ans);
return 0;
}
ARC 079
F - Namori Grundy
题意
给你一个 (n) 个点的有向环套树，需要对于每个点定取值 (a_i ge 0) ，满足。
- 对于所有边 ((i, j)) 有 (a_i ot = a_j) 。
- 对于 (0 le x < a_i) 都存在至少一条边 ((i, j)) 使得 (a_j = x) 。
问是否存在一种合法方案。
(2 le n le 2 imes 10^5)
题解
其实操作本质上其实就是个 (mathrm{mex}) ，对于树上的 (mathrm{mex}) ，每个节点的值应该是确定的。
需要考虑环，处理完所有环上节点的子树，就得出了每个环上节点的取值下界 (b_i) 。
-
所有 (b_i) 相同且环长度为偶数：我们隔一个数就把当前数加 (1) 即可。
-
所有 (b_i) 相同且环长度为奇数：那么隔一加一的就不行了，其实不难发现这样无法构造出合法方案。
-
存在有 (b_i) 不同：找到 (b_i) 最小的点 (v) 把它 (+1) ，然后依次考虑 (u o v) 然后如果 (b_u = b_v + 1) 那么我们继续操作即可，不难发现这样操作一定会在某点停止不会绕圈。
这样我们就在 (mathcal O(n)) 的时间内判断出来了。