eJOI 做题总结

ISIJ2020 集训的作业，所以就过来做了 ^v^。 截至 $2020.6.9$ 终于做完了。(\*^▽^\*) 个人认为的难度：$2019<2017<2018$。 代码咕一会儿就放 ~ ## eJOI 2017 ### [A. Magic （魔法）](https://www.luogu.com.cn/problem/P6273) JOISC 有一道只有 `J` `O` `I` 三个字母的弱化版（zyk巨神还出到模拟赛过呢。） 先考虑只有两个字母的情况，假设只有字母 `a` 和 `b`，维护它们的前缀和 $sa_i$ 和 $sb_i$。 能对答案产生贡献的一个区间 $[l,r]$ 一定满足 $sa_r-sa_{l-1}=sb_{r}-sb_{l-1}$ 即 $sa_r-sb_r=sa_{l-1}-sb_{l-1}$。那么统计两字母数量之差即可。 字母较多的情况就直接维护相邻字母数量之差的数组即可，可以哈希一下解决。 我比较懒所以就开个 `vector` 扔进 `map` 里面维护好了。 --- ### [B. Six （六）](https://www.luogu.com.cn/problem/P6274) 有点神仙的 dp，我写的是一个状态数上界为 $14^6$ 的做法。 直接维护每个质因子出现次数不是很可做，举个例子： 质因子 $2,3$ 都出现了 $1$ 次，但下面并不能确定能否填 $6$。 考虑到序列的长度最多只有 $12$，所以可以这样定义每个数的状态： $0$ 表示未出现过，$1\sim 12$ 状态满足恰好出现过一次，表示它出现的对应位置，$13$ 表示恰好出现 $2$ 次（因为只要出现过 $2$ 次那么这个质因数就不可能再被选择）。 这样就可以直接 $2^6$ 轻松转移。 $14^6$ 个状态只是个很松的上界，实际上远达不到。 --- ### [C. Particles （粒子）](https://www.luogu.com.cn/problem/P6290) 简单二分。 二分 $k$ 次，每次二分时间点，顺便记录跑到最前面的粒子，二分出答案之后把这回合碰撞的粒子打标记表示不再用了即可。 时间： $\mathcal{O}(nk\log L)$ 当然有个凸包的 $\mathcal{O}(nk)$ 做法，不过上述做法常数优秀些也能过。 --- ### [D. Camel （骆驼）](https://www.luogu.com.cn/problem/P6291) 比较神仙的构造题（%NTF大佬凭自己就爆切此题）。 由于 $5\mid n$，所以假设可以构造出 $5\times 5$ 时候的走法，那么 就可以令 $m=n/5$，把问题改成在 $m\times m$ 的棋盘上走，每次可以往相邻的格子移动一步。 这个转化后的问题就极为简单了。不过 $n$ 为奇数的时候最后一步还需要斜着走一下。 $n$ 为偶数的时候：  $n$ 为奇数的时候：  最后的任务乱构造几个固定的起点和终点的 $5\times 5$ 的走法矩阵即可。 代码写起来就非常的无脑~~且恶心~~，~~我懒得搜 $5\times 5$ 的了所以就直接抄 NTF 的矩阵了/cy~~。 代码 5kb，已经不能看了。。 --- ### [E. Experience （经验）](https://www.luogu.com.cn/problem/P6293) 有意思的树形 dp。 首先很容易想到一个结论：划分出来的每条链的经验一定是单调。证明比较显然。 然后就可以 dp 了： $dp_{u,0}$ 表示满足 $u$ 所在划分出来的链是从最深的位置开始是单调不增的，除去 $u$ 所在链的部分的贡献再加上 $u$ 所在链底的经验值的最大值。 $dp_{u,1}$ 表示满足 $u$ 所在划分出来的链是从最深的位置开始是单调不减的，除去 $u$ 所在链的部分的贡献再减去 $u$ 所在链底的经验值的最大值。 $dp_{u,2}$ 表示 $u$ 所在子树的最大值。 $dp_{u,2}$ 通过 $dp_{u,0}$ 和 $dp_{u,1}$ 转移即可。 转移 $dp_{u,0}$ 可以重开一个链或者继承子树中的一个链，转移 $dp_{u,1}$ 同理。 转移方程： 设 $S=\sum\limits_{v\in son_u}dp_{v,2}$，则： $$dp_{u,2}=\max\{dp_{u,0}-w_u,dp_{u,1}+w_u\}$$ $$dp_{u,0}=\max\left\{S+w_u,\max\limits_{v\in son_u}\{S-dp_{v,2}+dp_{v,0}\}\right\}$$ $$dp_{u,1}=\max\left\{S-w_u,\max\limits_{v\in son_u}\{S-dp_{v,2}+dp_{v,1}\}\right\}$$ 最终答案就是 $dp_{1,2}$。 --- ### [F. Game （游戏）](https://www.luogu.com.cn/problem/P6294) 根据贪心的原则，每个人每次一定会选择当前可选集合中最大的数。 显然有一种直接用 `set` 维护集合的方法，时间： $\mathcal{O}(nk\log n)$，不过只有 $50pts$。 再细想一下，每次需要往集合中加一个数的时候，先不去加，那么这轮选数的人要么选择这个数，要么选择集合中的最大数，所以从开始到结束，集合中的最大数的值一定是单调不增的。 所以只需要把原序列离散化一下，然后维护个 `cnt` 数组代表集合中对应数的出现次数，在弄个指针 `pos` 表示集合中最大数的位置。 显然 $\forall i>pos,\ \ cnt_i=0$。 这样就能做到每次 $\mathcal{O}(1)$ 选数，最后总时间：$\mathcal{O}(n\log n+nk)$。 --- ## eJOI 2018 感觉一道比一道阿巴。 ### [A. Hills （山）](https://www.luogu.com.cn/problem/P6304) 比较裸的 dp。 $dp_{i,j,0}$ 表示前 $i$ 座山建了 $j$ 座房子，第 $i$ 个位置没建房子且没有挖。 $dp_{i,j,1}$ 表示前 $i$ 座山建了 $j$ 座房子，第 $i$ 个位置建房子了。 $dp_{i,j,2}$ 表示前 $i$ 座山建了 $j$ 座房子，第 $i$ 个位置没建房子且被挖到高度小于 $h_{i-1}$。 注意 $dp_{i,j,0}$ 只能从 $dp_{i-1,j,0}$ 和 $dp_{i-1,j,2}$ 转移过来就行了。 转移方程显然，如果还不清楚就直接看我代码好了。 最后别忘了滚动数组优化一波空间。 --- ### [B. Passports （护照）](https://www.luogu.com.cn/problem/P6313) 一看到 $n\leq 22$ 就会往状压 dp 的方向思考。 先考虑只有一个护照的情况，因为每个护照是独立的，所以处理两个护照时把两个 $n$ 个行程划分成两个符合条件的行程即可。 $dp_i$ 表示 $i$ 集合中的行程办完签证的最早日期。 先枚举 $i$ 集合中最后的行程 $j$。 令 $now$ 为最早开始办第 $j$ 个签证的日期，那么最后要求的就是 $now+t_j$。 有两个限制 $now$ 的情况： - 不能有出国时间段包含 $now$。 - $i$ 集合中不能有 $j$ 行程的签证还没办完就出发的行程。 由于两者是相互影响的，所以转移需要双层的循环。 看起来这样做的复杂度是 $\mathcal{O}(2^nn^3)$ 的，不过可以利用一下 $now$ 单调递增的性质就是 $\mathcal{O}(2^nn^2)$（我并不是特别清楚）。 当然，接着是能优化到 $\mathcal{O}(2^nn)$ 的，但是~~我要练习卡常~~所以就硬尝试卡一卡。如何剪枝就要靠人类智慧了。 比如一个简单的：如果目前 $now+t_j\geq dp_i$ 那么就可以直接走人了。 无论如何，最后我卡过去了/cy（loj 上稳过，luogu 上可能还需要开一些奇奇怪怪的东西。。） --- ### [C. AB-Strings （AB 串）](https://www.luogu.com.cn/problem/P6303) 又是神仙构造题。。 首先连续若干个 `a` 或连续若干个 `b` 是可以合并的（可以直接搞成个 pair 记录字符种类和个数） 最后的目标就是把两个串的连续段（一下简称串的长度）变成 $1$。 若两个串的长度均大于 $1$，那么可以这么做： 先讨论一下首字母是否相同。 容易发现，如果首字母相同，那么两串选择的长度 $p$ 和 $q$ 之和为偶数即可消掉两个位置。（当然，$p,q$ 都大于 $0$） 同理，如果首字母不同，那么 $p,q$ 之和就应该是奇数。 但是如果此时有一个串的长度为 $1$，每次只能消掉一个位置，那就非常僵硬了。。 所以不妨把两个串的长度弄得尽量相等，可以只用第一次操作进行调整。 这样就能做到 $70\sim 100$ 分。 通过~~瞎取~~平均数+一些特判，我成功搞到了 $100$ 分（其实如果脑子比较清晰就不需要乱试，像我的脑子这种不是很清晰就只能这样了，后果就是代码根本不能看了qwq。） --- ### [D. Chemical table （元素周期表）](https://www.luogu.com.cn/problem/P5089) eJOI 2018 除 A 以外最可做且最良心的题目了。 并查集维护需要已经合并到一起的列即可，注意最后答案还需要加上空的行的个数并特判 $q=0$ 的情况。 一发就 AC ~ --- ### [E. Prime Tree （互素树）](https://www.luogu.com.cn/problem/P5089) 好 van 的提答。 毒瘤 sys 还放了个 [加强版](https://www.luogu.com.cn/problem/P6590)。 不过我没想到凭我一己之力就能全部玩出来 /xyx。 直接瞅我的题解好了。（别忘了点个赞再走哦/qq） - [普通版](https://www.luogu.com.cn/blog/1445353309froggy/solution-p5090) - [加强版](https://www.luogu.com.cn/blog/1445353309froggy/solution-p6590) 其实两篇一样的啦 /cy。 --- ### [F. Cycle Sort （循环排序）](https://www.luogu.com.cn/problem/P6305) 小司机巨神给我讲了半天才懂qwq。~~退役了退役了。。~~ 先考虑 $a_i$ 中没有相同元素的情况： 每个 $a_i$ 向它应该在的位置连边，这样就能得到若干个环。 对于一个大小为 $k$ 的环，显然只需要 $1$ 次操作，移动 $k$ 个下标即可使它们归位。 为了使操作次数最少，不妨先让所有环合并到一起，最后再把这个大环搞一下，这样 $2$ 次操作就能搞定。 但是这题有一个移动的下标位置之和不能超过 $s$ 的限制非常烦人，这样就不能合并所有环了，只能挑若干个环进行合并。 先考虑一下如果没有 $s$ 的限制，那么需要移动的下标个数就是 **错位个数+环的个数**（显然可以做到合并 $p$ 个环只需要移动 $p$ 个下标）。 如果 $s$ 小于错位个数就无解了，如果 $s$ 大于错位个数+环的个数就直接当做没有 $s$ 的限制。 现在需要处理的是 $s$ 介于两个边界之间的情况。 根据贪心原则，我们需要合并尽量多的环，（而合并的是哪些环是无所谓的，因为最终只用让操作次数最少。） 需要合并的环的个数很好算，就是 $s-\text{错位个数}$。 如果有重复 $a_i$ 那么把 $a_i$ 相同的位置合并成一个点，把下标放到边上，在欧拉图上把所有回路找出来即可。（直接跑个欧拉回路） --- ## eJOI 2019 u1s1，19年的题目是真的良心。 ### [A. XORanges （异或橙子）](https://www.luogu.com.cn/problem/P6225) ~~异或完粽子怎么又来异或橙子。。~~ 每次询问，区间中位置为 $i$ 数被异或的次数是 $(i-l+1)\times(r-i+1)$ 那么可以得到以下结论： 询问的区间长度为偶数时答案显然为 $0$。 否则，把这个序列拆开成奇序列和偶序列，奇序列中下标为奇数的位置的值就是原序列的值，下标为奇数的位置的值就是 $0$。 偶序列的定义类似。 那么 $l$ 为奇数就询问奇序列 $[l,r]$ 的异或和，否则询问偶序列的 $[l,r]$ 的异或和。 直接开两个树状数组分别维护前缀异或和即可。 --- ### [B. Hanging Rack （挂架）](https://www.luogu.com.cn/problem/P6232) 一看到样例解释，啊哈，这 tm 这么像 FFT 蝴蝶变换优化时的数组？！ 如果每个数减一那么就完全是那个数组了。 仔细瞅瞅题然后手乱模几次，发现答案就是 $n-1$ 在二进制下的逆序再加一。 然后。。就做完了。~~真扫兴。~~ --- ### [C. T-Covering （T形覆盖）](https://www.luogu.com.cn/problem/P6234) 不难发现，两个位置会相互影响当且仅当它们两个的曼哈顿距离小于等于 $2$。 那么不妨将把会互相影响的位置看成它们之间右边，然后每个联通块分开考虑。 对于每个联通块，求出能被拼版占用的格子（除去拼板中心位置）$cnt0$，和这些格子（除去拼板中心位置）中的最小值 $mn$，和这些格子（包含中心位置）的权值和 $tot$，以及联通块大小 $cnt1$（即需要放拼板的数量） 然后分类讨论一下： - 如果 $3\times cnt1>cnt0$ 那么显然无解。 - 如果 $3\times cnt1=cnt0$ ，答案增加 $tot$。 - 如果 $3\times cnt1<cnt0$ ，答案增加 $tot-mn$。（因为还可以空出来一个格子，那就把权值最小的格子空出来。） --- ### [D. Tower （塔）](https://www.luogu.com.cn/problem/P6241) eJOI 日常构造题。 先考虑如果需要得到的数是无限大，那么构造的序列的第 $i$ 项就要尽量大，即 $2^{i-2}(i\geq2)$。 不难猜到最优需要操作 $\log_2(n-1)+2$ 次。 令 $k=\log_2(n-1)+2$。 考虑序列中第 $i$ 个数减一后（即生成第 $i$ 个数的时候把原来 $[1,i-1]$ 的求和区间改成 $[2,i-1]$）造成的影响。由于以后每次求和一定都会统计到这个 $-1$，所以这会使最后的数减去 $2^{k-i}$。 易证生成序列中每个数时只决定求和的开头是 $1$ 还是 $2$ 最后一个数就可以取遍 $1\sim 2^{k-1}$ 的所有值。 把 $n$ 二进制拆分后来决定即可。 --- ### [E. Colouring a rectangle （矩形染色）](https://www.luogu.com.cn/problem/P6235) 首先把网格图黑白染色，显然黑色和白色可以分开考虑。 假设从左上到右下的对角线的染色费用分别为 $a_i$，从右上到左下的对角线的染色费用分别为 $b_i$。 这样，不花费 $a_i$ 就需要花费连续的一段 $b_i$，由于 $n,m$ 已经确定，这个区间 $[l_i,r_i]$ 是直接可以预处理出来的。 把这些区间按左端点排序后，考虑 dp。 $dp_{i,j}$ 表示填好了前 $i$ 个对角线，其中 $b$ 填到了第 $j$ 个。 假设从 $dp_{i-1,j}$ 转移，那么有两种情况： - 直接花费 $a_i$，转移到 $dp_{i,j}$。 - 花费 $\sum_{k=\max\{j,l_i\}}^{r_i}b_k$，转移到 $dp_{i,\max\{j,r_i\}}$。 仔细观察发现，每次从 $dp_{i-1}$ 到 $dp_i$，需要的操作只有区间加，区间求最小值，单点修改。 直接用线段树维护即可。 时间复杂度：$\mathcal{O}((n+m)\log(n+m))$ --- ### [F. Awesome Arrowland Adventure （爽极了的箭头国冒险）](https://www.luogu.com.cn/problem/P6233) ~~请不要在意我瞎翻译了个题目名称~~ 乱七八糟的箭头只是迷惑行为，这题的本质就是个最短路。 把网格依次标号，把每个点的箭头分别转 $0\sim3$ 次，然后和它指向的点连边，权值是转的次数。 最后从左上角到右下角跑个最短路就好了！ --- ## 反思： 很多题目不看题解还是思考不出来qwq，还需要继续努力啊！（菜是原罪） 此外，还是有很多细节没有注意，导致本会的题目没法一遍 AC。 --- 对题解有问题欢迎提出哦！