仍然是没有做通信题。
JOISC2016 Day1 Matryoshka 俄罗斯套娃
转化错了，转化成上升子序列了，然后就变成了区间 LIS。
实际上是 LDS，那么就可以直接做了。
https://qoj.ac/submission/99648
JOISC2016 Day1 Memory2 神经衰弱
我们对数进行两两配对，然后把每一对都问出来。如果不存在相同的，那么一定是每对的两个数都是一样的，就可以直接返回答案了。否则我们选出两对相同的，设它们问出来的答案是 \(x\)，那么 \(x\) 一定是这四个数中的最小值，并且这四个数中有两个 \(x\)。我们可以使用三次问询把答案给问出来，并且配对最多会改变一对。于是总问询次数 \(5n\)。
https://qoj.ac/submission/99657
JOISC2016 Day1 Solitaire 棋盘游戏
想不到 DP 的状态设计。个人感觉是 JOISC2016 中最好的一道题。
判掉无解。首先我们可以划分成一些中间行无棋子的连续段。对于每个连续段，进行 DP。\(f(i,j,0/1)\) 表示仅考虑前 \(i\) 列，钦定第 \(i\) 列的中间元素的插入位置为 \(j\)，且钦定这列中间行是在上下填完了之后/之前填的。
然后就发现很好转移了。
https://qoj.ac/submission/99742
JOISC2016 Day2 Employment 雇佣计划
我们考虑把统计 \(\ge B\) 的连续段，转化成统计形如 \(a_{i-1}<B\le a_i\) 的 \(i\) 的数量。这样我们就可以动态维护 \(f_B\) 了（\(i\) 处相当于一个 \(f[a_{i-1}+1,a_i]\) 的区间加减操作）。
https://qoj.ac/submission/99821
JOISC2016 Day2 Sandwich 三明治
首先我们对于一个点，它有两种方式被达到。然后我们发现，如果这个点被到达的方式确定了，那么剩下的所有需要的点被到达的方式也就随之确定了。如果成环那么就无解了，然后就是一个 DAG 后继数问题了。这样就可以做到 \(O(n^4)\) 或者 \(O(\frac{n^4}{w})\)。
我们不妨往回退一步，考虑直接搜索，看怎么最大化利用之前的状态。我们注意到对于 \((x,y)\)，如果决定它是从左边走过来，那么它左边的所有点都会被走到且都是从左边走过来。于是我们保留 \((x,y-1)\) 的结果，然后搜一下它的上/下（根据它是 N 还是 Z）。从右往左也是一样的。复杂度 \(O(n^3)\)。
https://qoj.ac/submission/100229
JOISC2016 Day2 Toilets 女装大佬
从左往右匹配，如果队首是男生那么就可以任意配上之后的一个女生，如果队首是女生那么就直接和下一个人匹配。然后我们发现题面中”原本在后面，现在在前面的个数“的最大值一定在女生处取到。于是我们考虑一种贪心：我们让男生去匹配女生，可以发现一定是从右到左顺次匹配最后面的女生是更优的，然后再把男生往前移动，直到一个 F-M 的匹配中不存在 F。而对于 F 来说，它的变化值一定就是跨过它的 F-M 匹配个数，即后缀 M 个数减去 F 个数。
然后我们再看原题中要求的，从后往前考虑，发现一个串中的最大值要么在（从后往前的）第一次出现中出现（串中 F 数量更多），要么在最后一次出现（串中 M 数量更多）。然后就可以直接做了。
https://qoj.ac/submission/100248
JOISC2016 Day3 Dungeon2 地牢2
考虑把这张图给确定了。我们首先先 dfs 一次，确定出图的 dfs 树，然后点上的标记表示未被访问/已经被访问且在栈中/已经被访问且已不在栈中。这样我们就能确定出图的 dfs 树，并且给返祖边定向。
然后我们考虑三进制分组。由于只有 \(200\) 个点，于是只需要 \(5\) 位。我们每次 DFS，将这个点的第 \(x\) 位标记在这个点上，这样我们每次走返祖边就能直到返祖边指向的那个点的其中一位，\(5\) 次 dfs 之后就能确定了。每次 dfs 需要 \(2m\) 次 Move，并且第一次 dfs 由于返祖边会访问 \(2\) 次所以需要 \(4m\) 次 Move，所以总共 \(14m\) 次 Move。
https://qoj.ac/submission/100264
JOISC2016 Day3 Sushi 回转寿司
首先考虑 \(L=1,R=N\) 怎么做。我们永远都是会弹出最大值，然后把 \(A\) 给放到某个位置（如果 \(A\) 小于最大值的话）。于是开一个大根堆维护就行了。
然后考虑分块。整块的情况我们已经会做了，于是我们考虑如何进行块重构。模拟可以发现（猜测），对于一个块，如果有施于这个块的若干个操作，那么这些操作的相对顺序是不重要的。于是我们考虑使用如下的算法：维护一个小根堆，扫描这个块，每次取出堆顶，比较当前位置和堆顶。如果堆顶更小，那么就更新当前位置，并把当前位置的值塞入堆中。于是我们就 \(O(B\log B)\) 时间完成了块重构。纵谷复杂度 \(O(n\sqrt n\log n)\)。
https://qoj.ac/submission/100449
JOISC2016 Day3 Teleport 电报
考虑做一个转化，我们发现我们可以保留一些边，剩下的边再去连。而保留的这些边合法，当且仅当这些边不成环，形成一些不交的链。（特判掉答案为 0 的情况）。然后我们就在基环树上做 DP。树可以直接做，环需要 \(f(x,0/1,0/1)\) 表示 \(x\) 是否被选择，且之前是否有过被选择的点。最后需要 \(f(x,0,1)\) 或 \(f(x,0,0)\)。
https://qoj.ac/submission/100458
JOISC2016 Day4 Dangerous Skating 危险的滑冰
模拟赛打到过，现在才发现是 JOISC 题。考虑转化成一个等价的最短路：建图，相邻两个点边权为 \(2\)，然后再加上可以直接撞墙的那些边权为 \(1\)。显然这样子走出的最短路一定是符合要求的，且一定是最短的。
https://qoj.ac/submission/100575
JOISC2016 Day4 Worst Reporter 2 最差记者2
考虑一种贪心：我们每次按 \(b\) 从大到小先贪心地配国籍已经相同的，每次配比它大的最小的 \(d\)。然后我们会得到一些多出的配不上的东西，这显然是下届。然后这些人的国籍就已经不重要了，我们可以直接贪心地配。我们对 \(b\) 维护一个堆，每次取出堆顶。但是有时候我们发现会配不上。这时候我们考虑拆散那些在之前配上的国籍相同的。我们需要找 \(d\) 满足要求的，\(b\) 最小的，拆散后这个 \(b\) 塞入堆中。这个贪心在这层显然是对的。而由于我们在一开始贪心的时候已经满足大的 \(b\) 配尽可能小的 \(d\)，所以那层的贪心对这层的影响是包容的。
https://qoj.ac/submission/100563
标签：JOISC2016,submission,题解,ac,我们,https,qoj From： https://www.cnblogs.com/TetrisCandy/p/17357239.html