JOISC2020 部分题解
先放一点上来，剩下的慢慢更。 ビルの飾り付け 4 / Building 4 不难想到一个 $\mathcal{O}(n^2)$ 的 DP：设 $f_{i, j, 0/1}$ 表示前 $i$ 个数选了 $j$ 个 A，最后一个是 A/B 是否可行，转移显然。最后逆序构造方案即可。 可以发现对于某个 $i, 0/1$，为真的 $j$ 一定是一段区间，因此我们只需要维护这段区间，即可去掉 $j$ ...
标签 交互题 下的文章
- 首页
- 交互题
LOJ2863 「IOI2018」组合动作
LOJ UOJ 分析 首先可以通过二分用两次询问把第一个字符问出来，假设是 $\texttt{A}$，那么接下来不会再出现 $\texttt{A}$。 考虑依次确定接下来的字符。有一个显然的 $2$ 次询问的方法，但是实际上可以 $1$ 次询问：设之前的串为 $\texttt{S}$，询问 $\texttt{SBSXBSXXSXY}$，那么如果返回值为 $|S|$ 则这一位为 $\textt...
洛谷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$ 链上的点以及其它点在链上那个点的子树中。 那么直接递归处理链...
Codeforces Round #614 简要题解
Div1 Div2 从一月份一直咕到现在的一场比赛 /kel ConneR and the A.R.C. Markland-N 暴力往两边找即可。 代码 JOE is on TV! 显然每次淘汰掉刚好一个人是最好的。 答案即为 $\sum_{i=1}^n\frac{1}{i}$。 代码 NEKO's Maze Game 维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即...
洛谷3641 [APIO2016]最大差分
Luogu LOJ UOJ 分析 Subtask1 首先调用 MinMax(0,1e18,&a[1],&a[n]) 来求出 $a_1$ 和 $a_n$。 然后不断调用 MinMax(a[i-1]+1,a[j+1]-1,&a[i],&a[j]) 即可求出整个序列。 Subtask2 首先调用 MinMax(0,1e18,&a[1],&a[n]) ...
洛谷6558 [APIO2017]考拉的游戏
Luogu LOJ 分析 Subtask1 在某个物品旁边放上一个蓝色石子，这样子 Koala 就只能得到至多 $99$ 个物品，而没选的那个物品一定是权值最小的。 这样子只需要调用一次 playRound，可以得到 $4$ 分。 Subtask2 先在每个物品旁边放 $1$ 个蓝色石子，这样子 Koala 会选出至多 $50$ 个物品，所以我们可以确定权值前 $50$ 大的物品。 那么可以...
POI2012 简要题解
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则 若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...
CF1354G Find a Gift
Codeforces Luogu 分析 蓝题都不会做了 /kk 因为 $k\leq \frac{n}{2}$，所以随机一个盒子是石头的概率 $\geq\frac{1}{2}$。 那么我们可以先通过若干次随机来较高正确率地判断第一个盒子是不是石头。 如果不是的话直接输出即可；否则，可以通过倍增找到第一个礼物所在的区间 $[2^k+1,2^{k+1}]$，在这个区间中二分即可。 代码 // ==...