洛谷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)$。考虑无解的情况。一种情况是出现负环，另一种情况是出现一个全是...
CF1354G Find a Gift
CodeforcesLuogu分析蓝题都不会做了 /kk因为 $k\leq \frac{n}{2}$，所以随机一个盒子是石头的概率 $\geq\frac{1}{2}$。那么我们可以先通过若干次随机来较高正确率地判断第一个盒子是不是石头。如果不是的话直接输出即可；否则，可以通过倍增找到第一个礼物所在的区间 $[2^k+1,2^{k+1}]$，在这个区间中二分即可。代码// ==========...