====== 2020牛客暑期多校训练营（第六场） ====== ===== Results ===== ==== Summary ==== * Solved 5 out of 11 problems * Rank 95 / 1120 in official records * Solved 8 out of 11 afterwards

#	Who	=	Penalty	A	B	C	D	E	F	G	H	I	J	K	Dirt
12	大吉大利，今晚吃 mian();	5	516	-2	+1 00:52	+ 00:48		+ 00:13		-5	+1 03:08			+2 02:15	44% 4/9

==== Member Distribution ==== ^ Solved ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ K ^ | Pantw | | √ | | | | | O | | | | √ | | Withinlover | O | | √ | | √ | | | | | O | | | Gary | - | | | | | | | √ | | | | (√ for solved, O for upsolved, - for tried but not solved) ---- ====== Solutions ====== ===== A ===== 没看懂题解的 H 函数自己瞎推一推假设长度为 n 的环需要的代价为 $f(n)$，随机打乱总的情况数是 $n!$，然后计算一下所有情况中长度为 $i$ 的环出现的次数，就可以递推的求了，这个可以前缀和优化。哦对了，最开始把模数写成 $1e9 + 7$了，死活过不了样例哦对了，一开始的式子还推错了，不过看样例可以猜出$f(4) = 34/3$。找对这个就OK了哦对了，如果一开始就看出了 $f(4) = 34/3$，那其实也不太用推公式了，光看手算的过程已经可以把公式猜出来了（题解用了个 $H()$ 函数和 $f()$ 函数递推，然而看不懂，不过这题主要还是看思路吧，当时没想到找环（ UPD: 貌似题假了，上面就当是废话吧 [[https://www.zhihu.com/question/409954876/answer/1365275315|知乎讨论贴]] ===== B ===== 找规律。1 3 21, 2 8 64，就直接猜了。具体证明没看懂，回头补。（大概吧） ===== C ===== 可以证明，取两列的结果一定不优。样例是迷惑人的。把每一列的单独算，然后取个最大值就行了 ===== D ===== ===== E ===== 给定n，k的值是固定的，只要给定的k不对就无解。 n, 1, n - 1, 2, n - 2, ... n, n/2, 1, n - 1, 2, n - 2, ... 这俩看情况选一个就行了 ===== F ===== ===== G ===== {{:2020-2021:teams:mian:nowcoder_training:nowcoder6_g_figure1.png|}} 如图所示，将边按照右/下点的坐标和的奇偶性分成红绿两类。按照蓝色箭头和粉色箭头的顺序加入一个队列里，然后染色的时候从一个队列里取即可，切换颜色的时候需要切换所取的队列。但是这样做会碰见一个问题，那就是有可能最后两个队列各剩 4 条边，但你只剩一个颜色，这个颜色要求 8 条边。那么这就造成了闭合回路。解决方法是我们把红色边的队列倒过来。这个使用 deque 非常方便，因为 ''std::deque::iterator'' 是 $\mathtt{LegacyRandomAccessIterator}$，可以直接使用 ''std::reverse''。倒过来之后，我们会发现，队列中最后剩下来的只会是左上角的一点点红色边和右下角的一点点绿色边，把这些都取上也造不出同色闭合回路。那么这个题就这么做完了。你问我为啥没过？别问，问就是我是傻逼。 1 1 2 1 2 1 2 我居然觉得没问题，我是傻子呜呜呜 ===== H ===== 数位dp，f(i,j)表示后i为和为j的个数，数位dp枚举到两个数第一个出现不同的位置，枚举差值，再通过f数组求解 ===== I ===== ===== J ===== 赛后过题，不愧是我找出约瑟夫变换的数组后，变换x次显然可以快速幂写掉。这个复杂度是$ \log $的，所以瓶颈在于如何求约瑟夫变换的那个数组。我本打算写个暴力找一下然后看题解。然后暴力打着打着发现复杂度好像是对的。（二分 + 树状数组）然后就A了（正解貌似没有二分，想起来在说吧）找的思路类似于约瑟夫问题的那个 $ O(n) $的dp，但是不确定在原数组中的位置，然后我就用树状数组 + 二分暴力了一下。 ===== K ===== 直接维护一个 cnt[i] 表示目前 i 的数量，维护一个 cntcnt[i] 表示目前 cnt[x] 为 i 的 x 的数量，然后扫一遍，即可判断出某区间是否是 1-k 的排列。然后维护一个 Canp[i]，表示 1-i 的前缀是否合法。（Canp : can_this_prefix_be_part_of_permutation） Cans[i] 同理，suffix 版本。然后有了这三个东西，我们就可以直接枚举第一个分点在哪了，这个枚举最多枚举 k 个，判断最多判断 n/k 个点的标记，所以是线性的。啥？你问我元素太大存不下咋办？那我直接 a_i > k 判 NO 就完了 k 也很大咋办？k > n 的时候按照最多两段做就完了，用个 sort 整一整就没了 ------------- ====== Comments ====== ptw: * 别再看错特例了 (G) * 特例可以 double-check 一下，稳一点 (G) * 可以早点想 A 和 J withinlover: * 最后应该早点想A的，稍微推一推其实挺可做的（这个傻子挨个手算了2-8的答案就是想不到去判一下n=1呢）（G） * 最后讲题的时候才知道稍微改改方程就好dp很多。结果让Gary调了半天，这波全责（H） * 中场的时候把每个题挨个看一遍（最近跟榜总会把水题跟漏了） Gary： * H数位dp写的有点麻烦，调了很久 * A题的公式推跑偏了，推得值也奇奇怪怪，思路上没想到dp * 没看J，封榜的时候过的也不多就没注意了 * （↑ P: 好像是赛中数据错了所以 AC 的人少？）