未命名文档
我在中关村的星巴克里面趴在桌上睡着了。
现时两点半。高铁八点半才开。最早六点半才能进站。通勤需半个小时。
前事已毕后事未接的这四个小时，我终于没有什么迫切的任务需要应对了。
已经可以了，不需要再努力了。
然后陷入消极情绪。在一个没人注意的小角落我悄无声息。我知道我被世界抛弃。
外面阳光热烈，人群来往，嬉笑脸上。里面朋友聚会，对饮谈话，相视而笑。
这世界与我无关。
陷入了循环往复的低落情绪之中
结束了
DEL 至少作为一个 OIer 已经死去了。
省选退役。
第一天代码版本没有核对好，交了个一半的，丢了100.
第二天读入优化写错。windows 拍不出错 linux RE. 200 全没有.
我的竞赛生涯就是笑话。
有了这 400 分会怎样？
那么多“如果”漏了出来。如果我把那天的咖喱全都吃光是不是好一点。
抱歉。真的抱歉。
只能走到一半，就走不下去了。
我尽力了可是运气不站在我这边。当时我在逞能。现在我也是。
有几十篇存货一起放上来吧。排版大概是不会排的了。更新也不会更了。
为了方便都设为了前一天的日期。也算是纪念至少在一天前 DEL 还是一个 OIer 吧。
不过这里大概很快就被人忘记了吧。
雅礼省赛集训 2018 Sol.
雅礼省赛集训 2018 Sol.
3.23
T1
给一棵以 1 号点为根的树。每一个点有一些怪，移动速度和在 1 号点的人一样。
对每一个终点，问最多碰到多少怪。
Sol.
裸的长链剖分。
听了题解以及跟 @whj 讨论了一下，其实只需两遍 dfs。一遍收集深度$\times2$，另一遍收集深度$\times2-2$.
#include <bits/stdc++.h>
using namespace std;
template<class T>
inline void read(T&x)
{
T p = 1, n = 0; char c = getchar();
while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T, class U>inline void read(T&x,U&y){read(x), read(y);}
template<class T,class U,class V>inline void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e5 + 10;
struct E{int v, n;}e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v)
{
e[ec] = (E){v, h[u]};
h[u] = ec++;
e[ec] = (E){u, h[v]};
h[v] = ec++;
}
int depth[maxn], size[maxn], hson[maxn], maxd[maxn];
void dfs(int u = 1, int f = 0)
{
size[u] = 1; hson[u] = 0;
maxd[u] = depth[u];
for(int i = h[u], v = e[i].v ;i; i = e[i].n, v = e[i].v)
if(v != f)
{
depth[v] = depth[u] + 1, dfs(v, u);
size[u] += size[v];
if(maxd[v] > maxd[hson[u]]) maxd[u] = maxd[v], hson[u] = v;
}
}
int w[maxn], a[maxn];
bool flag[maxn];
void collect(int u, int f)
{
w[depth[u]] += a[u];
for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
if(v != f && !flag[v])
collect(v, u);
}
int ans[maxn];
void dfs2(int u = 1, int f = 0, bool ff = false)
{
for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
if(v != f && v != hson[u])
dfs2(v, u, true);
if(hson[u])
{
dfs2(hson[u], u, false);
flag[hson[u]] = 1;
}
collect(u, f);
ans[u] = w[depth[u] * 2 - 2] + w[depth[u] * 2 - 1];
if(ff)
{
memset(w, 0, sizeof w);
memset(flag, 0, sizeof flag);
}
}
void dfs3(int u = 1, int f = 0)
{
for(int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v) if(v != f)
ans[v] += ans[u], dfs3(v, u);
}
int main()
{
freopen("escape.in", "r", stdin);
freopen("escape.out", "w", stdout);
int n; read(n);
for(int i = 1; i <= n; ++i) read(a[i]);
for(int i = 1, u, v; i < n; ++i) read(u, v), add_edge(u, v);
depth[1] = 1; dfs();
dfs2();
dfs3();
for(int i = 1; i <= n; ++i) printf("%d\n", ans[i]);
return 0;
}T2
定义 $ f_k(n)=f_{k-1}*1(n)=\sum_{d|n} f_{k-1}(d) $ . 给 $ x,k,f_0 $ ， 求 $ f_k(n) $ .
Sol.
卷积满足结合律，考虑使用快速幂计算 $ 1^k $ ，其中乘法定义为卷积。要注意到只求某一项的值，这一项的因数级别在 $ O(n^{3/4}) $ （@whj 语），所以可以过。
还有一种使用牛顿级数的做法。
注意到 $ 1^k=\sum_i{k\choose i}(\Delta^i1^x)^0 $ ，$ k $ 很小且 $ (\Delta^i1^x)^0(v) $ 是很容易预处理出来的。
#include <bits/stdc++.h>
using namespace std;
template<class T>
inline void read(T&x)
{
T p = 1, n = 0; char c = getchar();
while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T, class U>inline void read(T&x,U&y){read(x), read(y);}
template<class T,class U,class V>inline void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1e5 + 10, mod = 998244353;
int f[maxn], a[maxn], tmp[maxn], ret[maxn], t2[maxn], ac;
int calc(int k)
{
for(int i = 0; i < ac; ++i) ret[a[i]] = 0;
ret[1] = 1;
for(int i = 0; i < ac; ++i) t2[a[i]] = 1;
for(; k; k >>= 1)
{
if(k & 1)
{
for(int i = 0; i < ac; ++i) tmp[a[i]] = 0;
for(int i = 0; i < ac; ++i) for(int j = 0; j <= i; ++j) if(a[i] % a[j] == 0)
(tmp[a[i]] += 1ll * ret[a[j]] * t2[a[i] / a[j]] % mod) %= mod;
for(int i = 0; i < ac; ++i) ret[a[i]] = tmp[a[i]];
}
for(int i = 0; i < ac; ++i) tmp[a[i]] = 0;
for(int i = 0; i < ac; ++i) for(int j = 0; j <= i; ++j) if(a[i] % a[j] == 0)
(tmp[a[i]] += 1ll * t2[a[j]] * t2[a[i] / a[j]] % mod) %= mod;
for(int i = 0; i < ac; ++i) t2[a[i]] = tmp[a[i]];
}
}
int main()
{
freopen("machine.in", "r", stdin);
freopen("machine.out", "w", stdout);
int n; read(n);
for(int i = 1; i <= n; ++i) read(f[i]);
int m; read(m);
while(m--)
{
int k, x; read(k, x);
ac = 0;
for(int i = 1; i * i <= x; ++i) if(x % i == 0)
{
a[ac++] = i;
if(i * i != x) a[ac++] = x / i;
}
sort(a, a + ac);
calc(k);
int ans = 0;
for(int i = 0; i < ac; ++i) (ans += 1ll * f[a[i]] * ret[x / a[i]] % mod) %= mod;
printf("%d\n", ans);
}
return 0;
}T3
交互题。
一棵二叉树，每条边有颜色，告诉你现在的起点深度。你可以调用 move 使用某一颜色的边，query 查询当前点深度，你要跳到深度为 0 的点。
100 分初始深度为 $10^5$ 要求 query 调用不超过 $51000$ 次， move 调用不超过 $ 10^6 $ 次。
Sol.
每次走 $ 6 $ 步，分类讨论 $ 2^6=64 $ 种情况。期望每次询问能跳 $ 63\over32 $ 步，能过。其实写丑了，根本不必要手写讨论。
#include "maze.h"
int seed = 20180323, x = 3;
int rrand()
{
return (x = (x + seed + x % 41 * seed % 41) % 41) % 32;
}
int excl(int i, int j)
{
if(i != 0 && j != 0) return 0;
if(i != 1 && j != 1) return 1;
if(i != 2 && j != 2) return 2;
}
int fi[100], se[100], th[100], fo[100], fif[100], six[100];
void findpath(int initialDeep, int T)
{
if(!query()) return;
int last = -1; bool flag = false;
for(int i = 0; i < 2; ++i)
{
if(move(i)) return;
if(query() > initialDeep) move(i);
else {last = i; flag = true; break;}
}
if(!flag) move(2), last = 2;
int curdep = initialDeep - 1;
while(curdep > 4)
{
int cnt = 0;
for(int i = 0; i <= 2; ++i) if(i != last)
{
for(int ii = 0; ii < 32; ++ii)
fi[cnt + ii] = i;
for(int j = 0; j <= 2; ++j) if(j != i)
{
for(int jj = 0; jj < 16; ++jj)
se[cnt + jj] = j;
for(int k = 0; k <= 2; ++k) if(k != j)
{
for(int kk = 0; kk < 8; ++kk) th[cnt + kk] = k;
for(int l = 0; l <= 2; ++l) if(l != k)
{
for(int ll = 0; ll < 4; ++ll) fo[cnt + ll] = l;
for(int m = 0; m <= 2; ++m) if(m != l)
{
for(int mm = 0; mm < 2; ++mm) fif[cnt + mm] = m;
for(int n = 0; n <= 2; ++n) if(n != m)
six[cnt++] = n;
}
}
}
}
}
int pa = rrand();
move(fi[pa]); move(se[pa]); move(th[pa]); move(fo[pa]); move(fif[pa]); move(six[pa]);
int d = query();
if(d == curdep + 6)
move(six[pa]), move(fif[pa]), move(fo[pa]), move(th[pa]), move(se[pa]), move(fi[pa]), move(last = excl(fi[pa], last)), curdep -= 1;
else if(d == curdep + 4)
move(six[pa]), move(fif[pa]), move(fo[pa]), move(th[pa]), move(se[pa]), move(last = excl(se[pa], fi[pa])), curdep -= 2;
else if(d == curdep + 2)
move(six[pa]), move(fif[pa]), move(fo[pa]), move(th[pa]), move(last = excl(th[pa], se[pa])), curdep -= 3;
else if(d == curdep)
move(six[pa]), move(fif[pa]), move(fo[pa]), move(last = excl(fo[pa], th[pa])), curdep -= 4;
else if(d == curdep - 2)
move(six[pa]), move(fif[pa]), move(last = excl(fif[pa], fo[pa])), curdep -= 5;
else if(d == curdep - 4)
move(six[pa]), move(last = excl(six[pa], fif[pa])), curdep -= 6;
else
last = six[pa], curdep -= 6;
}
if(curdep == 0) return;
for(int i = curdep; i; --i)
{
bool flag = false;
for(int j = 0; j < 2; ++j) if(j != last)
{
move(j);
if(query() > i)
{
move(j);
if(last == 2) {move(1), last = 1, flag = true; break;}
}
else {last = j; flag = true; break;}
}
if(!flag) move(2), last = 2;
}
}3.25
即便是原题大战又怎样。。还是菜到打不出来QAQ
A
给出一个长度为 m 的序列 A, 请你求出有多少种 1..n 的排列, 满足 A 是它的一个 LIS.
$ 1\le m\le n\le15 $ .
Sol.
考虑需要的信息。保证合法性需要对答案有贡献的序列的 LIS 信息（A 在 LIS 的信息显然包括其中），转移需要局部已处理的集合的信息。
LIS 数组满足单调性，可以将之压为二进制状态。
$ f_{S, S_0} $ 表示考虑了集合 $ S $ ，LIS 信息为 $ S_0 $ 的合法方案数。又注意到恒有 $ S_0\subset S $ ，所以用一个三进制描述这个状态即可。复杂度 $ O(n^23^n) $ .
要注意使用了标准化技术后转移拓扑序和下标的顺序是不一致的。要用个队列保存转移。
转移时精致一点。。打错了好多。。
#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 20, maxm = 1.5e7;
int a[maxn], A[maxn], pow3[maxn], log3[maxm];
bool flag[maxn];
long long dp[maxm] = {0};
queue<int> q[maxn];
int main()
{
freopen("arg.in", "r", stdin);
freopen("arg.out", "w", stdout);
int n, m; read(n, m);
for(int i = 0; i < m; ++i) read(a[i]), --a[i], flag[a[i]] = 1;
pow3[0] = 1; for(int i = 1; i <= n; ++i) pow3[i] = pow3[i - 1] * 3;
for(int i = 1; i < pow3[n]; ++i) log3[i] = log3[i / 3] + 1;
int N = pow3[n];
dp[0] = 1; q[0].push(0);
long long ans = 0;
for(int i = 0; i < n; ++i)
{
while(!q[i].empty())
{
int S = q[i].front(); q[i].pop();
bool f = false;
for(int j = 0; j < n; ++j) if((S / pow3[j]) % 3 == 0)
{
f = true;
int T = S + 2 * pow3[j];
for(int k = j + 1; k < n; ++k) if((T / pow3[k]) % 3 == 2)
{
T -= 1 * pow3[k];
break;
}
int cnt = 0, ac = 0;
for(int k = 0; k < n; ++k)
{
if((T / pow3[k]) % 3 == 2) ++cnt;
if((S / pow3[k]) % 3 != 0 && k == a[ac]) ++ac;
}
if(!flag[j])
{
if(cnt <= m)
{
if(!dp[T]) q[i + 1].push(T);
dp[T] += dp[S];
}
}
else
{
if(cnt > m || a[ac] != j) continue;
if(!dp[T])q[i + 1].push(T);
dp[T] += dp[S];
}
}
}
}
while(!q[n].empty()) ans += dp[q[n].front()], q[n].pop();
printf("%lld\n", ans);
return 0;
}B
给定一个正 n 边形及其三角剖分, 共 2n − 3 条边 (n 条多边形的边和 n − 3 条对角线), 每条边
的长度为 1.
共 q 次询问, 每次询问给定两个点, 求它们的最短距离.
Sol.
强烈抗议出原题。当时还跟 mhx 讨论了一个下午。思路实在太妙就记了下来。
平面图、网格图上很多特殊性质可以利用。分治是其中要考虑的。
3.30
table
program
path
4.2
c
一棵树上 A 和 B 轮流给结点对应染红色蓝色。A 要使红蓝联通块差大， B 使小。问最后整棵树的联通块差。
Sol.
记 $ S_A/S_B/E_A/E_B $ 为各颜色点数和同色边数，则联通块数有 $ S_A $
计蒜客20180415 Sol.
计蒜客20180415 Sol.
……把福利赛打成退役赛吗……
B
无向图，判断五元环。$ |V|\le200 $ .
一直在往 dfs 树的返祖边考虑……但其实不能这么做。
枚举一个点和一条边后，剩下就是要看这个点和这条边的两个端点是否各存在一个公共邻点。这个可以用 bitset 加速判定。据说不用也可以过。复杂度是 $ \mathcal O({n^4\over 64}) $ .
实现的时候要注意两个端点都要有一条连出去的点且不能是对方。
其实这个问题我在之前辗转反侧的夜晚考虑过数次。但今天刚好忘了得出来的结论是返祖边不能做或者至少不好做。而判断三元环、四元环这些经典问题都是直接用 bitset 。我似乎对经典题毫无察觉。学到了学到了。
考虑一下六元环怎么做？三元环计数怎么做？
C
给出一个集合，可重复抽三个数。已知最后各个数的组成方案数，求复原原集合或不可能。$ |U|\le6 $ .
注意这是一个集合异或卷积的三次方…… FWT 一下看看原幂级数合不合法存不存在就可以了……
细节很多。比方说域的特征不能为 $ 2 $ ，最后所有数的和要为 $ n $ ，不能出现负数，行末不能有空格，立方根可能不是整数。
想到这个思路应该很简单的啊……应该说意识还不够……不熟练？一直往 DP 方向想，可是要是写出状压式子不久完了吗…………菜爆。
G
求所有点对的最小瓶颈路径。$ |V|\le10^5 $ .
套路 MST. 然后我建出这棵树后就开始取最大边来边分了……T爆。
实际上由一个技巧，就是注意到连接两个连通块时我们并不关心是哪两个点具体连边。那么在并查集上直接维护子树 tag 即可。不带路径压缩比较好写，但是每次加边多带一个 $ \log $ . 总的时间是 $ \mathcal O(n\log n) $ ，全部瓶颈在于排序。