乌蒙山连着山外山 // 月光洒下了响水滩
有没有人能告诉我 // 可是苍天对你在呼唤
医生问我对药有什么要求吗，我说我宁死不喝冲剂。
然后医生给我开了五盒胶囊，告诉我说一天三次，一次六个。
哈哈哈，我自找的。以此为证，A 一道题磕一片！！！
A. 修改序列
http://222.180.160.110:1024/contest/4268/problem/1
注意到一增一减，全数列的和 \(s\) 不变，考虑这一点带来的提示。
假设最后要求一部分数为 \(p\)，另一部分为 \(p+1\)，那么有 \(p = \lfloor \dfrac sn \rfloor\)，\(p+1\) 的数量 \(c_r=s\bmod n\)，\(p\) 的数量 \(c_l=n-c_r\)。
那么我们让 \(\le p\) 的变成 \(p\)，\(\ge p + 1\) 的变成 \(p + 1\)。直接求两数距离，最后将总和除以二即为答案、
正确性证明…
这样做的最优性毫无疑问，问题无非就在于这么做的正确性，换言之，为什么一定能找到合法的操作序列还原我们的求解过程。
将原数列分为两部分，数值 \(\le p\) 的（记为 \(X\)）和数值 \(\ge p + 1\) 的（记为 \(Y\)）。
再把我们的目标状态分为两部分，数值 \(= p\) 的（记为 \(A\)）和 数值 \(=p + 1\) 的（记为 \(B\)）。
那么有 \(\begin{cases}X+Y=s\\\\A+B=s\end{cases}\)，由等式的基本性质得 \(X-A+Y-B = 0\)，移项得 \(Y-B=A-X\)。也就是说，\(Y\) 部分与 \(p+1\) 的差的总和正好等于 \(X\) 部分与 \(p\) 的差的总和。
这个时候我们的正确性就有了保证。
这个时候你可能就有疑问了，\(X,Y\) 中的元素个数和 \(A,B\) 中的元素个数并不对应，怎么办呢？
我们发现上面的原理式并不会随元素个数的变化而变化，所以依然可以用它来解答这个问题。没有人规定 \(Y-B\) 和 \(A-X\) 不能为负，为负时我们把 \(A\) 中塞不下的 \(X\) 拿到 \(B\) 里面去即可，反之同理。
那么代码还是很好写的。时间复杂度 \(\mathcal O(n)\)。
namespace XSC062 {
using namespace fastIO;
const int maxn = 2e5 + 5;
int a[maxn];
int n, s, p, cl, cg, res;
int main() {
read(n);
for (int i = 1; i <= n; ++i)
read(a[i]), s += a[i];
p = s / n, cg = s - p * n, cl = n - cg;
for (int i = 1; i <= n; ++i) {
if (a[i] <= p) {
if (cl) res += p - a[i], --cl;
else res += p - a[i] + 1, --cg;
}
else {
if (cg) res += a[i] - p - 1, --cg;
else res += a[i] - p, --cl;
}
}
print(res / 2, '\n');
return 0;
}
} // namespace XSC062
B. Knuth 表示法
http://222.180.160.110:1024/contest/4268/problem/2
模拟。输入的数用 map 转化为 \(10\) 的次幂形式，然后幂次直接相加即表示指数相乘。
最后按位数从大到小将次幂形式转化为字符串、再按位数从小到大输出。
注意到开头的字符串不是 one 就是 ten，需要在没有抽出来 ten 的时候补 one。
namespace XSC062 {
using namespace fastIO;
using str = std::string;
const str u[] = { "one", "ten", "hundred", "myriad", "myllion", "byllion", "tryllion",
"quadryllion", "quintyllion", "sextyllion", "septyllion", "octyllion",
"nonyllion", "decyllion" };
str x;
int res = 0;
std::stack<str> s;
std::map<str, int> t;
void get(str &x) {
str y;
std::stringstream p(x);
while (p >> y) {
if (y == "one") continue;
res += 1 << (t[y] - 1);
}
return;
}
int main() {
for (int i = 0; i <= 13; ++i)
t[u[i]] = i;
std::getline(std::cin, x), get(x);
std::getline(std::cin, x), get(x);
for (int i = 13; i; --i) {
if (res & (1 << (i - 1))) {
s.push(u[i]);
res ^= (1 << (i - 1));
}
}
if (s.top() != "ten")
s.push("one");
while (!s.empty()) {
std::cout << s.top() << ' ';
s.pop();
}
return 0;
}
} // namespace XSC062
C. 魔力塔
http://222.180.160.110:1024/contest/4268/problem/3
神奇的线段树优化建图。这拿来放 T3？不合适吧。
很好想到对于 \(a_i\ne -1\)，连边 \(i\to a_i\)；否则，连边 \(i\to x(x\in [i+1,\min(i + k,n+1)])\)。BFS 遍历，复杂度 \(\mathcal O(n\times k)\)。
问题在于无用边太多，例如 \(i\) 和 \(i+1\) 共同可达的点有整整 \(k-1\) 个，造成大量浪费。
考虑到实际进入 BFS 的点只有 \(n\) 个，及由传送门构成的连通块均呈棒棒糖状（即链套环），我们直接优化掉 \(a_i=-1\) 时的连边。使用线段树查询 \([i+1,\min(i + k,n+1)]\) 内的所有剩余点，连边入队并从线段树中删除。
这样，每个点只会入队一次（忽视无用环），时间复杂度控制在 \(\mathcal O(n\log n)\)，\(\log\) 来源于线段树，写得不好就是 \(\log^2\)，写得好一点就只有一个。
然而…
会 T，因为常数太大了。
所以我们需要另一种 \(\log\) 的做法，并且短小精悍。
用 set 存储所有未入队的点，每次 lower_bound 并依次弹出、入队。
用迭代器的话代码很短，美汁汁。
时间复杂度 \(\mathcal O(n\log n)\)，但等我先磕片药先。
namespace XSC062 {
using namespace fastIO;
const int maxn = 5e5 + 5;
int a[maxn];
int n, k, res;
bool vis[maxn];
std::set<int> t;
std::vector<int> g[maxn];
int max(int x, int y) {
return x > y ? x : y;
}
void DFS(int x) {
res = max(res, x);
if (a[x] == -1) {
auto p = t.lower_bound(x + 1);
while (p != t.end() && *p <= x + k) {
g[x].push_back(*p);
t.erase(*p++);
}
}
for (auto i : g[x]) {
if (vis[i])
continue;
vis[i] = 1, DFS(i);
}
return;
}
int main() {
read(n), read(k);
for (int i = 1; i <= n; ++i) {
read(a[i]), t.insert(i + 1);
if (~a[i]) g[i].push_back(a[i]);
}
DFS(1), print(res, '\n');
return 0;
}
} // namespace XSC062
D. 卡牌游戏
http://222.180.160.110:1024/contest/4268/problem/4
怎么说呢，爆搜可以拿 80pts！！！然而正解是区间 DP，哭唧唧。他这个数据范围给得很神奇，让人只会往搜索上面想。
摧毁操作是一换一，不会更改串长，而入栈操作会增加初始串的长度。
所以我们考虑 逆序 DP，从最终状态入手，用 \(f_{x, i, j}\) 表示是否可以使用一个字符 \(x\) 经过一系列操作消掉 \(w_{i\sim j}\)。
那么明显若一条摧毁操作为可用字符 \(a\) 摧毁 \(w_i\)，有 \(f_{a, i, i} = 1\)。
若一条入栈操作为用字符 \(a\) 换字符 \(b,c\)，枚举区间断点 \(k\)，有 \(f_{a, i, j} = f_{b, i, k} \times f_{c, k + 1, j}\)。
最后答案为 \(f_{\texttt S,i,|w_i|}\)。
注意循环顺序，区间的枚举应在字符的枚举之外。最终时间复杂度 \(\mathcal O(T\times |w_i|^3\times N_2)\)，注意到字母的枚举属于常数。胶囊好吃滴捏。
namespace XSC062 {
using namespace fastIO;
const int maxn = 25;
const int maxm = 1e3 + 5;
int n, m, l;
char w[maxn];
bool r1[maxm][maxm];
bool f[maxm][maxn][maxn];
struct { int u, a, b; } r2[maxn];
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%s", w + 1);
r1[(int)w[1]][(int)w[4]] = 1;
}
for (int i = 1; i <= m; ++i) {
scanf("%s", w + 1);
r2[i].u = w[1];
r2[i].a = w[4], r2[i].b = w[5];
}
while (~scanf("%s", w + 1)) {
memset(f, 0, sizeof (f));
l = strlen(w + 1);
for (int i = 'A'; i <= 'Z'; ++i) {
for (int j = 1; j <= l; ++j) {
if (r1[i][(int)w[j]])
f[i][j][j] = 1;
}
}
for (int len = 1; len <= l; ++len) {
for (int i = 1; i <= l - len + 1; ++i) {
int j = i + len - 1;
for (int t = 'A'; t <= 'Z'; ++t) {
for (int k = i; k < j; ++k) {
for (int p = 1; p <= m; ++p) {
if (r2[p].u != t)
continue;
f[t][i][j] |= f[r2[p].a][i][k] && f[r2[p].b][k + 1][j];
}
}
}
}
}
puts(f['S'][1][l] ? "YES" : "NO");
}
return 0;
}
} // namespace XSC062
E. 生长树
http://222.180.160.110:1024/contest/4268/problem/5
一道很菜的题。我们发现有子树操作，第一时间想到树剖，那么接下来要考虑的内容就是线段树如何维护。
题意换句话说就是往下数 0 代是加，数 1 代是减，数 2 代是加，以此类推。那么不难想到奇偶性。
如果起点的深度是奇数，那么子树中所有奇数深度权值增加，偶数深度权值减少，反之同理。
但是我们操作线段树的时候怎么知道点在树中的深度奇偶性呢？我们只能在线段树外才知道呀。
所以观察询问，询问是单点的，所以我们知道了，可以只在线段树外对奇偶性进行处理。简单来说，假设更改起点深度为奇数，那么增加整个子树的「奇加偶减计数器」；反之，增加整个子树的「奇减偶加计数器」。
最后查询的时候，如果该点深度为奇，那么答案为对应的「奇加偶减计数器」减去「奇减偶加计数器」的值，反之同理。
做到最后发现根本不用树剖，就是一个 DFN 上线段树。时间复杂度 \(\mathcal O(m\log n)\)。
胶囊真好吃！！！
namespace XSC062 {
using namespace fastIO;
#define lt (p << 1)
#define rt (lt | 1)
const int maxn = 2e5 + 5;
struct _ {
int l, r;
int u1, u2, d1, d2;
};
_ t[maxn << 2];
int a[maxn], dep[maxn];
std::vector<int> g[maxn];
int n, m, x, y, tot, typ;
int end[maxn], dfn[maxn], tab[maxn];
// u 只用维护最底层信息
// 所以不用打 pushup
// 但维护起来好看一些 所以还是打了
void pushup(int p) {
t[p].u1 = t[lt].u1 + t[rt].u1;
t[p].u2 = t[lt].u2 + t[rt].u2;
return;
}
void pushdown(int p) {
if (t[p].d1) {
t[lt].d1 += t[p].d1;
t[rt].d1 += t[p].d1;
t[lt].u1 += t[p].d1 *
(t[lt].r - t[lt].l + 1);
t[rt].u1 += t[p].d1 *
(t[rt].r - t[rt].l + 1);
t[p].d1 = 0;
}
if (t[p].d2) {
t[lt].d2 += t[p].d2;
t[rt].d2 += t[p].d2;
t[lt].u2 += t[p].d2 *
(t[lt].r - t[lt].l + 1);
t[rt].u2 += t[p].d2 *
(t[rt].r - t[rt].l + 1);
t[p].d2 = 0;
}
return;
}
void bld(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) {
if (dep[tab[l]] & 1)
t[p].u1 = a[tab[l]];
else t[p].u2 = a[tab[l]];
return;
}
int mid = (l + r) >> 1;
bld(lt, l, mid), bld(rt, mid + 1, r);
pushup(p);
return;
}
void add1(int p, int l, int r, int x) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d1 += x;
t[p].u1 += (t[p].r - t[p].l + 1) * x;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
pushdown(p);
if (l <= mid) add1(lt, l, r, x);
if (r > mid) add1(rt, l, r, x);
pushup(p);
return;
}
void add2(int p, int l, int r, int x) {
if (l <= t[p].l && t[p].r <= r) {
t[p].d2 += x;
t[p].u2 += (t[p].r - t[p].l + 1) * x;
return;
}
int mid = (t[p].l + t[p].r) >> 1;
pushdown(p);
if (l <= mid) add2(lt, l, r, x);
if (r > mid) add2(rt, l, r, x);
pushup(p);
return;
}
int ask(int p, int x) {
if (t[p].l == t[p].r)
return t[p].u1 - t[p].u2;
int mid = (t[p].l + t[p].r) >> 1;
pushdown(p);
if (x <= mid) return ask(lt, x);
return ask(rt, x);
}
void DFS(int x, int fa) {
dfn[x] = ++tot, tab[tot] = x;
for (auto i : g[x]) {
if (i == fa)
continue;
dep[i] = dep[x] + 1;
DFS(i, x);
}
end[x] = tot;
return;
}
void add(int x, int y) {
g[x].push_back(y);
return;
}
int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i)
read(a[i]);
for (int i = 1; i < n; ++i) {
read(x), read(y);
add(x, y), add(y, x);
}
dep[1] = 1, DFS(1, -1);
bld(1, 1, n);
while (m--) {
read(typ), read(x);
if (typ == 1) {
read(y);
if (dep[x] & 1)
add1(1, dfn[x], end[x], y);
else add2(1, dfn[x], end[x], y);
}
else {
int res = ask(1, dfn[x]);
if (dep[x] & 1)
print(res, '\n');
else print(-res, '\n');
}
}
return 0;
}
} // namespace XSC062
F. 单词
http://222.180.160.110:1024/contest/4268/problem/6
\(n \le 20\)，考虑状压。用 \(f_x\) 表示状态为 \(x\) 时的最小代价，其中 \(x\) 是字符串合法情况的状态压缩。
对于每一个待满足的串，枚举去满足它的哪一位，那么满足方式分两种情况：
-
把它变成一个新的值
-
把和它重合的变成新的值
我们注意到 \(n \le 20 \le 26\)，所以一定能找到一种方法让每个串的这一位都不一样。
接着，反正我们都要改这一位了，那就贪心地把要改的全部改成完全不一样的。那么这些要改的串也在这一位上满足了条件。
所以，假设对于状态 \(i\)，有串 \(j\) 未满足，枚举位置 \(k\)，有：
f[i | (1 << (j - 1))] =
min(f[i | (1 << (j - 1))], f[i] + a[j][k]);
f[i | lac[j][k]] =
min(f[i | lac[j][k]], f[i] + mx[j][k]);
其中 lac[j][k] 和 mx[j][k] 都是预处理出来的值。lac[j][k] 表示与第 \(j\) 个串的第 \(k\) 位相同串的状态压缩；mx[j][k] 表示通过第二种方式将 \(j\) 串的第 \(k\) 位变得合法的最小费用。
lac[j][k] 的求法没有任何疑问，主要是在 mx[j][k] 上。注意到假设这一位上有 \(x\) 个串与 \(j\) 串的第 \(k\) 位相同（包括其本身），而我们只需要将这当中的 \(x-1\) 个变成两两不同的全新字符就可以同时满足这 \(x\) 串的条件，那我们为什么不把不动的这一个串设置为 \(x\) 个串中改这一位代价最大的那个呢？
那么问题来了。我们枚举状态、枚举状态中的每一个 0，枚举每一个串的每一位，实际上是 \(\mathcal O(n\times m\times 2^n)\) 的。虽然跑不满，但这个时间复杂度仍然是有问题的。我们需要优化。
我们枚举的是状态中的每一个 0，假设我们的状态是 000，我们的解决方案是将三个 0 位置的方案共同处理，表示为 '0--' + '-0-' + '--0'。但实际上，我们只用实际求解一个 0 位置的答案，表示为 '0--' + '-00' 。
也就是说，我们原本需要枚举每一个状态为 0 的 \(j\) 并用 \(\mathcal O(m)\) 的时间进行计算，现在我们碰到一个状态为 0 的 \(j\) 就开始计算，得到完全相同的答案。
很 NB 并且很实用的优化，已加入 下饭操作合集。
namespace XSC062 {
using namespace fastIO;
const int maxn = 205;
const int maxm = (1 << 25) + 5;
int f[maxm];
int n, m, siz;
char s[maxn][maxn];
int lac[maxn][maxn];
int a[maxn][maxn], mx[maxn][maxn];
int min(int x, int y) {
return x < y ? x : y;
}
int max(int x, int y) {
return x > y ? x : y;
}
int main() {
while(~scanf("%d %d", &n, &m)) {
memset(f, 0x3f, sizeof (f));
f[0] = 0, siz = 1 << n;
for (int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
scanf("%d", &a[i][j]);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int sum = 0;
lac[i][j] = mx[i][j] = 0;
for (int k = 1; k <= n; ++k) {
if (s[k][j] == s[i][j]) {
lac[i][j] |=
1 << (k - 1);
sum += a[k][j];
mx[i][j] =
max(mx[i][j],
a[k][j]);
}
}
mx[i][j] = sum - mx[i][j];
}
}
for (int i = 0, j; i < siz - 1; ++i) {
for (j = 1; j <= n; ++j) {
if (!(i & (1 << (j - 1))))
break;
}
for (int k = 1; k <= m; ++k) {
f[i | (1 << (j - 1))] =
min(f[i | (1 << (j - 1))],
f[i] + a[j][k]);
f[i | lac[j][k]] =
min(f[i | lac[j][k]],
f[i] + mx[j][k]);
}
}
print(f[siz - 1], '\n');
}
return 0;
}
} // namespace XSC062
这次暴露出的问题：
- 深度乱求，打代码的时候考虑过要放在递归之前，但是由于精力不集中最后还是放在了递归后面。
没了。这次主要问题出在 T5。T3 估计真的想不到，先不强求自己。
这次学到的新知识：
- 对于
包括但不限于状压DP 的优化
水龙，水龙，别哭啦！