LOJUOJ分析首先可以通过二分用两次询问把第一个字符问出来,假设是 $\texttt{A}$,那么接下来不会再出现 $\texttt{A}$。考虑依次确定接下来的字符。有一个显然的 $2$ 次询问的方法,但是实际上可以 $1$ 次询问:设之前的串为 $\texttt{S}$,询问 $\texttt{SBSXBSXXSXY}$,那么如果返回值为 $|S|$ 则这一位为 $\texttt{Y}...
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\...
高速道路の建設 / Construction of Highway这个操作长得很像 LCT 中的 access。于是我们每次只要 access 一下并把所有颜色段拿出来,然后树状数组求逆序对数,再把对应的边连上并把整条重链的颜色赋值为 $c_v$。因为 access 是均摊 $\mathcal{O}(\log n)$ 的,所以每次颜色段数也是均摊 $\mathcal{O}(\log n)$ ...
官网AtCoderLOJ試験 / Examination三维偏序板子,CDQ 即可。代码ビーバーの会合 / Meetings首先有一个结论:Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。我们先在 $[1,n)$ 中随机一个点 $y$,然后询问 $(0,y,z)$,即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。那么直接递归处理链上每个点剩下的子树...
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...
比赛地址Splitting Pile枚举即可。代码Fennec VS. Snuke双方显然是先把对方到自己这边来的路堵上。于是我们只要找到分界点,看看哪边的点多即可。需要注意的是,如果两边的点一样多,那么是后手胜。代码Awkward Response首先可以把 $N$ 的位数确定出来:依次问 $1,10,100,\cdots$ 直到回答是 N,则前一个数和 $N$ 的位数相同。那么可以考虑二...
比赛地址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]$...
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...
LuoguLOJ分析Subtask1在某个物品旁边放上一个蓝色石子,这样子 Koala 就只能得到至多 $99$ 个物品,而没选的那个物品一定是权值最小的。这样子只需要调用一次 playRound,可以得到 $4$ 分。Subtask2先在每个物品旁边放 $1$ 个蓝色石子,这样子 Koala 会选出至多 $50$ 个物品,所以我们可以确定权值前 $50$ 大的物品。那么可以再在这 $50$...
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)$。考虑无解的情况。一种情况是出现负环,另一种情况是出现一个全是...