JOISC2020 部分题解
先放一点上来，剩下的慢慢更。 ビルの飾り付け 4 / Building 4 不难想到一个 $\mathcal{O}(n^2)$ 的 DP：设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A，最后一个是 A/B 是否可行，转移显然。最后逆序构造方案即可。 可以发现对于某个 $i, 0/1$，为真的 $j$ 一定是一段区间，因此我们只需要维护这段区间，即可去掉 $j$ ...
标签 随机 下的文章
- 首页
- 随机
洛谷6982 [NEERC2015]Jump
Luogu Gym 分析 我们只能先想办法问一个 $\frac{n}{2}$ 出来。先假设已经问出来了，稍后再来考虑怎么问。 规定一个串对应的集合就是它所有 $1$ 的下标集合，下面不再区分串和集合。 假设问出来的串是 $I$，考虑求出 $A=S\oplus I$。 考虑 $|A\oplus\{u,v\}|=|A|+|\{u,v\}|-2|A\cap\{u,v\}|$，即 $|A\oplus...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway 这个操作长得很像 LCT 中的 access。 于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。 因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n...
JOISC2019 简要题解
官网 AtCoder LOJ 試験 / Examination 三维偏序板子，CDQ 即可。 代码 ビーバーの会合 / Meetings 首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。 我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。 那么直接递归处理链...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
洛谷3517 [POI2011]WYK-Plot
Luogu LOJ 分析 首先要会最小圆覆盖而且知道它是期望 $\mathcal{O}(n)$ 的。 显然可以二分答案，于是我们只要想办法判定能否分成最小圆覆盖半径都 $\leq mid$ 的 $\leq m$ 段即可。 显然最小圆覆盖半径是随着点的增多而不降的，所以每段的点越多越好。于是可以想到暴力找每段的右端点，然而可以卡成 $\mathcal{O}(n^2)$。还有一个想法是二分右端点...
CF1354G Find a Gift
Codeforces Luogu 分析 蓝题都不会做了 /kk 因为 $k\leq \frac{n}{2}$，所以随机一个盒子是石头的概率 $\geq\frac{1}{2}$。 那么我们可以先通过若干次随机来较高正确率地判断第一个盒子是不是石头。 如果不是的话直接输出即可；否则，可以通过倍增找到第一个礼物所在的区间 $[2^k+1,2^{k+1}]$，在这个区间中二分即可。 代码 // ==...
BZOJ3837 [Pa2013]Filary
BZOJ 分析 首先我们可以得到 $k$ 至少为 $\frac{n}{2}$，构造方式是令 $m=2$。 也就是说，在最优解中每个数被选中的概率是 $>\frac{1}{2}$ 的。 考虑 rand() 一个在最优解中的数 $x$，我们把其它的 $\neq x$ 的数与 $x$ 作差并分解质因数，那么所有质因数中出现次数的最大值加上 $=x$ 的数的数量就是当前最大的 $k$。 这里有...
洛谷4581 [BJOI2014]想法
Luogu 分析 看到这个巨大的误差允许范围，可以考虑乱搞。 我们给所有入度为 $0$ 的点赋一个随机权值，然后将每个点的权值设为所有能到达这个点的点权的最小值。 经过一番推导后可以发现，这个权值的期望是 $\frac{\mathrm{RAND\_MAX}}{k}$，这里的 $k$ 是能到达这个点的入度为$0$的点的个数。那么这样子就能够估算出 $k$ 了。 代码 //It is made ...