LOJ2863 「IOI2018」组合动作
LOJUOJ分析首先可以通过二分用两次询问把第一个字符问出来，假设是 $\texttt{A}$，那么接下来不会再出现 $\texttt{A}$。考虑依次确定接下来的字符。有一个显然的 $2$ 次询问的方法，但是实际上可以 $1$ 次询问：设之前的串为 $\texttt{S}$，询问 $\texttt{SBSXBSXXSXY}$，那么如果返回值为 $|S|$ 则这一位为 $\texttt{Y}...
标签 交互题 下的文章
- 首页
- 交互题
洛谷6982 [NEERC2015]Jump
LuoguGym分析我们只能先想办法问一个 $\frac{n}{2}$ 出来。先假设已经问出来了，稍后再来考虑怎么问。规定一个串对应的集合就是它所有 $1$ 的下标集合，下面不再区分串和集合。假设问出来的串是 $I$，考虑求出 $A=S\oplus I$。考虑 $|A\oplus\{u,v\}|=|A|+|\{u,v\}|-2|A\cap\{u,v\}|$，即 $|A\oplus\{u,v\...
JOISC2018 部分题解
高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来，然后树状数组求逆序对数，再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的，所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
JOISC2019 简要题解
官网AtCoderLOJ試験 / Examination三维偏序板子，CDQ 即可。代码ビーバーの会合 / Meetings首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。那么直接递归处理链上每个点剩下的子树...
Codeforces Round #614 简要题解
Div1Div2从一月份一直咕到现在的一场比赛 /kelConneR and the A.R.C. Markland-N暴力往两边找即可。代码JOE is on TV!显然每次淘汰掉刚好一个人是最好的。答案即为 $\sum_{i=1}^n\frac{1}{i}$。代码NEKO's Maze Game维护每个格子是否是岩浆，当一个格子改变时维护一下上下两格都是岩浆的列数即可。代码Aroma's...
AtCoder Regular Contest 078 简要题解
比赛地址Splitting Pile枚举即可。代码Fennec VS. Snuke双方显然是先把对方到自己这边来的路堵上。于是我们只要找到分界点，看看哪边的点多即可。需要注意的是，如果两边的点一样多，那么是后手胜。代码Awkward Response首先可以把 $N$ 的位数确定出来：依次问 $1,10,100,\cdots$ 直到回答是 N，则前一个数和 $N$ 的位数相同。那么可以考虑二...
AtCoder Regular Contest 070 简要题解
比赛地址Go Home因为从 $1\sim n$ 中选若干个数可以拼出 $[1,\frac{n(n+1)}{2}]$ 中的所有数，所以我们只要找到最大的满足 $\frac{n(n+1)}{2}\geq X$ 的 $n$ 即可。因为数据范围小所以可以直接枚举。代码No Need把所有数从小到大排序，则可有可无的数一定是一段前缀。设 $s=\sum_{j=1}^i a_j$，那么 $[1,i]$...
洛谷3641 [APIO2016]最大差分
LuoguLOJUOJ分析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]) 来求出 $a_1...
洛谷6558 [APIO2017]考拉的游戏
LuoguLOJ分析Subtask1在某个物品旁边放上一个蓝色石子，这样子 Koala 就只能得到至多 $99$ 个物品，而没选的那个物品一定是权值最小的。这样子只需要调用一次 playRound，可以得到 $4$ 分。Subtask2先在每个物品旁边放 $1$ 个蓝色石子，这样子 Koala 会选出至多 $50$ 个物品，所以我们可以确定权值前 $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)$。考虑无解的情况。一种情况是出现负环，另一种情况是出现一个全是...