这个zsy居然更博了？
退役前的做题记录6.0
没写OJ的默认LOJ。
2019.10.10
2401. 「JOISC 2017 Day 4」Dragon 2
先分析一下这类问题的时间复杂度：共\(n\)个元素被分成了\(m\)个集合，\(q\)次询问，每次给出两个集合\(x,y\)，可以\(O(\min(sz_x,sz_y))\)地回答该询问，直接暴力并记忆化即可做到\(O((n+q)\sqrt n)\)的复杂度。考虑若询问集合中一者大小不超过\(\sqrt n\)则复杂度不超过\(\sqrt n\)，否则对于一个集合只会暴力遍历其\(\sqrt n\)次，因此复杂度就是这个。
对于这题可以直接枚举攻击方与被攻击方中数量较少的一方，讨论一下即可发现可贡献的另一方的点是两个村庄极角序的一个区间，二维数点即可。建议把龙哪一边分成两类，这样在讨论过程中会方便一些。
2399. 「JOISC 2017 Day 4」绑架 2
直接\(dfs\)，总状态量是\(O(n)\)的。官方题解里有图可以帮助理解
所以对每行每列开个线段树辅助一下找最近的拐弯点即可。
2336. 「JOI 2017 Final」绳
显然会在折叠绳子之前把绳子染成仅包含两种颜色，然后一直折叠直至长度为\(2\)。那么就只需要考虑什么样的颜色序列可以实现折叠了。
一个结论是除去首尾的连续段外，剩下的所有颜色连续段必须长为偶数。
充分性只需要构造一种合法方案：每次把两端折成\(1\)，然后再沿着第二段长为偶数的连续段对折，即可使连续段数减少\(1\)；必要性只需要能够说明非首尾的奇数长度连续段一定无法消除就行了。
已知结论后考虑计算答案。枚举一种颜色，计算最终答案中包含这种颜色的最小染色代价。上述对颜色序列的要求可以等价于：把序列划分成\(\{1,2\},\{3,4\}...\)或者是\(\{1\},\{2,3\},\{4,5\}...\)，要求在其中一种划分中每个集合内的颜色相同。因此找出这种颜色的所有出现位置，把这些位置属于的集合染成这种颜色，剩下的集合染成一种出现次数最多（代价最小）的颜色即可。
2734. 「JOISC 2016 Day 2」女装大佬
把M视作\(1\)，F视作\(-1\)，要求相当于是序列的最小前缀和不能小于序列总和\(-1\)，而一次操作显然会让所有M都往前移动一位，即恰好会是序列的最小前缀和\(+1\)（当然是在最小前缀和小于\(0\)的情况下），所以求出序列的最小前缀和以及总和后算一下就好了。
2733. 「JOISC 2016 Day 2」三明治
首先显然有一个\(O(n^4)\)的做法：枚举每个位置，记搜求出那些位置是必选的。
可以发现删除一个位置必须先删除其左侧所有位置或右侧所有位置，因此对于同一行，先从左到右搜一遍，再从右往左搜一遍，这样就\(O(n^3)\)了。
2736. 「JOISC 2016 Day 3」回转寿司
（好像loj的题面是简化版题面啊，大致讲下原题面：\(n\)个人围成一圈吃回转寿司，一开始每个人手里有一盘价格为\(a_i\)的寿司，每次有一盘寿司经过\([l,r]\)这个区间，每个人在看见一盘寿司从自己眼前转过去时会根据价格选择什么都不做还是交换自己的和面前的这盘寿司，求每次转出去的那盘寿司的价格）
分块。块内维护一个堆存块内元素，可以实现当一盘寿司进入一个整块时快速求出离开这个块的寿司的价格是多少，同时需要对每个块维护一个标记堆，下放标记等同于这个标记堆里的若干盘寿司同时进入了这个块，那么这个块内的每个人自然就是从这若干盘寿司中选价格最低的那盘寿司和自己的交换了。
注意到\(n,q\)不同级，可以算算最优块大小之类的。
2737. 「JOISC 2016 Day 3」电报
图是一片基环内向树森林，只需要在图中保留若干条不相交的链，最大化权值和即可。
其实也就是对每个点保留其权值最大的那个入点，但要求保留的部分不能包含环。对一个环整体讨论一下就行了吧。
3195. 「eJOI2019」异或橙子
区间长度是偶数则答案为\(0\)，否则答案是区间内所有与左右端点下标奇偶性相同的位置的异或和。
3196. 「eJOI2019」挂架
熟练的老鸽肯定一眼就能发现挂的顺序就是长度为\(n\)的二进制翻转（0-index）。
3197. 「eJOI2019」T 形覆盖
给出的一个标记位置的要求限制等价于：标记位置必选，与标记位置相邻的不超过\(4\)个位置中需要选\(3\)个。用并查集把与标记位置相邻的不超过\(4\)个位置连起来，可以发现每个连通块内要么全都得选，要么可以剩一个不选。对每个连通块维护最小值以及可以有几个不选即可。
3202. 「BalticOI 2019 Day1」潜艇
\(\text{bitset}\)优化即可。复杂度\(O(\frac{RCM}{\omega})\)。
3203. 「BalticOI 2019 Day1」山谷
先判删除的边是不是询问点的祖先，然后找最近的补给点可以枚举询问点与补给点的\(\text{LCA}\)，记\(val_i\)表示\(i\)点子树内最近的补给点到\(i\)的距离，那么相当于是询问一条直链上\(val_i-dep_i\)的最小值，倍增即可。