Table of Contents
Problem B. Bars
n 个人排成一排开酒吧，每个人可以选择开或不开，且每个人会去自己以外的左右最近 2 个开业酒吧各 1 次（没有则不去），第 i 个人的酒吧每招待一个顾客得 p_i 元，最大化总利润。
先写个暴力压压惊。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(1e6) + 9;
LL f[N]; int p[N];
int n;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
Rush {
RD(n); REP(i, n) RD(p[i]);
fill(f, f+n, 0);
FOR(i, 1, n) {
REP(j, i) checkMax(f[i], f[j] + (LL)(p[i]+p[j]) * (i-j));
}
cout << f[n-1] << endl;
}
}
第一反应是凸壳 dp… 但是经过一番化简貌似我们需要求一个三维向量的点积的最值。。
这个就给我整不会了。。。
看了一下 maspy 的题解，原来这个东西可以类比梯形求和。。。（这堆东西叠起来的形状大概像是《魔神英雄传》里的创界山。。）
然后只要保留外面的凸壳就可以了。。做法也和求凸包类似。。。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(1e6) + 9;
int p[N], s[N], sn;
int n;
LL w(int j, int i) {
return (LL)(p[i]+p[j])*(i-j);
}
bool bad(int a, int b, int c) {
return w(a, b) + w(b, c) <= w(a, c);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
Rush {
RD(n); REP(i, n) RD(p[i]);
sn = 0; REP(i, n) {
while (sn > 1 && bad(s[sn-1], s[sn], i)) --sn;;
s[++sn] = i;
}
LL z = 0; REP_1(i, sn) z += w(s[i-1], s[i]);
cout << z << endl;
}
}
Problem C. Ctrl+C Ctrl+V
给定一个字符串，问至少修改几个字符，使得字符串中不存在 “ania” 模式串。
签到题。可以 kmp 不过没必要（因为模式串太短且固定）。
每次匹配到 ania 时，直接把末尾的 a 修改成一个不存在的字符即可。
也可以记录连续匹配的段数 c，然后每次增加 (c+1) / 2。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(1e6) + 9;
char p[5] = "ania";
char s[N];
int n, z, c;
int main() {
#ifndef ONLINE_JUDGE
// freopen("in.txt", "r", stdin);
#endif
Rush {
n = strlen(RS(s));
z = 0; c = 0;
int j = 0;
for (int i=0;i<n;++i) {
if (s[i] == p[j]) {
++j; if (j == 4) {
++c;
j = 1;
}
}
else {
z += (c+1)/2; c = 0;
if (s[i] == 'a') j = 1;
else j = 0;
}
}
z += (c+1)/2;
cout << z << endl;
}
}
Problem D. Dazzling Mountain
给定一颗有根数，问有哪些满足条件的 x，使得所有子树 size 等于 x 的节点向下覆盖了所有的叶子。
显然根节点满足，最后所有的叶子节点也满足，
我们不妨枪坦推进，开个 map<int, VI> 记录当前每种不同覆盖面积的根节点。
每次取出面积最大的 VI 依次取出并往孩子移动，当每层扇形的面积都相等时，既此时 map 的 size 恰好为 1 时，则得到一组符合条件的答案，如果此时扇形面积为 1, 说明已经到了叶子，算法结束。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(1e6) + 9;
VI adj[N]; int sz[N], fa[N];
int n;
void dfs(int u = 1, int p = 0) {
sz[u] = 1;
for (auto v: adj[u]) if (v != p) {
fa[v] = u; dfs(v, u);
sz[u] += sz[v];
}
}
int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
Rush {
RD(n); REP_1(i, n) adj[i].clear();
DO(n-1) {
int a, b; RD(a, b);
adj[a].PB(b);
adj[b].PB(a);
}
dfs(); VI z; z.clear();
map<int, VI> H; H[sz[1]].PB(1);
while (true) {
int s = H.begin()->fi; z.PB(s); if (s == 1) break;
do {
auto it = H.end(); --it;
VI U = it->se; H.erase(it);
for (auto u: U) {
for (auto v: adj[u]) if (v != fa[u]) {
H[sz[v]].PB(v);
}
}
} while (SZ(H) != 1);
}
SRT(z); cout << SZ(z) << endl;
for (auto zi : z) printf("%d ", zi);
puts("");
}
}
Problem E. Euclidean Algorithm
如果 a, b 在，且 2a-b>0，则 2a-b 也在，重复这个操作得到的最小的数是 gcd 的 1-n 内的整数 pair有多少个。
不会。
Problem G. Great Chase
警察抓小偷。小偷出生在数轴原点，开始向右以速度 v0 移动，它左右分别有一些警察 (pi, vi)，pi 表示警察的位置，vi 表示警察的速度，左边的警察向右追，右边的警察向左追，保证小偷的速度大于所有警察，且数轴两边都存在警察。当小偷遇上警察时，小偷会向反向移动，直到被两个警察包夹。问被包夹时，小偷移动的总距离。
小偷的运动相对比较复杂，我们考虑不管，直接二分时间，看两边的警察是否能相遇即可。
Problem I. Investors
给定 n 个数列，你可以从中筛选出 m 段连续的子序列，将它们整体 offset 一段数，最小化最后的逆序对。
显然最优解一定是每次都选一些后缀进行操作，让原序列分割成 m+1 段互不干扰的区间，分别统计这些段的逆序对和，代价函数即为每一段的逆序对。
那么显然逆序对函数符合经典四边形不等式，由此推出决策单调性。
利用队列维护当前可行决策，并用二分计算出相邻决策的分割点即可（决策不劣的最早时刻）。
（参考诗人小 G）
似乎还存在很多神奇的做法，例如 直接二分每一段代价的上界？
另外瞄了一眼 maspy 的代码，什么，这居然也有 板子？
#include <lastweapon/io>
#include <lastweapon/fenwicktree>
using namespace lastweapon;
const int N = int(6e3) + 9;
int a[N], f[2][N], w[N][N]; VI A; int p = 0, q = 1;
int Q[N], P[N]; int cz, op;
int n, m;
int calc(int l, int r) {
return f[q][l] + w[l+1][r];
}
int left(int a, int b) {
int l = a, r = n;
while (l < r) {
int m = (l + r) / 2;
if (calc(b, m) <= calc(a, m)) {
r = m;
} else {
l = m + 1;
}
}
return l;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
Rush {
RD(n, m); A.clear(); REP(i, n) A.PB(RD(a[i]));
if (m >= n-1) {
puts("0");
continue;
}
UNQ(A); REP(i, n) a[i] = LBD(A, a[i]);
REP(i, n) {
fenwick_tree<int> T(SZ(A));
FOR(j, i+1, n) {
T.add(a[j-1], 1);
w[i][j] = w[i][j-1] + (j-i) - T.sum(a[j]+1);
}
}
FOR(i, 1, n) f[p][i] = w[0][i];
REP_1(s, m) {
swap(p, q); cz = 0, op = 0; Q[0] = s-1;
FOR(i, s, n) {
//f[p][i] = INF; FOR(j, s-1, i) checkMin(f[p][i], calc(j, i))；
while (cz < op && P[cz] <= i) ++cz;
f[p][i] = calc(Q[cz], i);
int j = left(Q[op], i);
while (cz < op && j <= P[op-1]) j = left(Q[--op], i);
P[op] = j; Q[++op] = i;
}
}
cout << f[p][n-1] << endl;
}
}
Problem M. Minor Evil
给定 1 到 n，n 个数和 m 组操作（ai, bi），每组操作表示，当序列中存在 ai 时，可以删除 bi，你必须按照顺序决定每个操作是否执行，问是否能将给定集合中的数都删除。
每个数要尽可能久的做跳板，我们应该要找到它能被删除时的最晚时刻。
第一反应可以类比 Dijkstra()，做法也确实如此。
(上次遇到类似的套路应该是在 Codeforces Round #800 (Div. 1+2) 的 C 题。)
d[i] 现在定义为：i 位置可被删除的最晚时刻。
那么对于所有不需要被删除的位置，初始 d[i] = k+1 即可。
最后只要没有 d[i] = 0 说明所有的点都可以在某个时刻被删除。
所以和原版 Dijkstra 相比，只是变成了时光倒流，以及边多了时间的限制而已。。。
#include <lastweapon/io>
using namespace lastweapon;
const int N = int(1e6) + 9;
set<int> Q[N]; VII adj[N]; char s[N]; int d[N];
int n, k;
bool dijkstra() {
REP_1(i, k+1) Q[i].clear();
REP_1(i, n) if (d[i] == k+1) Q[k+1].insert(i);
DWN_1(i, k+1, 2) {
for (auto u: Q[i]) {
for (auto e: adj[u]) {
int v = e.fi, w = e.se;
if (d[v] < w && w < i) {
if (d[v]) Q[d[v]].erase(Q[d[v]] .find(v));
Q[d[v] = w].insert(v);
}
}
}
}
REP_1(i, n) if (!d[i]) return 0;
return 1;
}
int main() {
#ifndef ONLINE_JUDGE
//freopen("in.txt", "r", stdin);
#endif
Rush {
RD(n, k); REP_1(i, n) adj[i].clear();
REP_1(i, k) {
int a, b; RD(a, b);
adj[a].PB({b, i});
}
REP_1(i, n) d[i] = k+1;
Rush d[RD()] = 0;
if (!dijkstra()) {
puts("NIE");
} else {
puts("TAK");
REP(i, k) s[i] = 'N';
REP_1(i, n) s[d[i]-1] = 'T'; s[k] = 0;
puts(s);
}
}
}
