====== 2020牛客暑期多校训练营（第四场） ====== ===== Results ===== ==== Summary ==== * Solved 5 out of 10 problems * Rank 28/1159 in official records * Solved 5 out of 10 afterwards ==== Virtual Participation ====
#Who=PenaltyABCDEFGHIJDirt
5大吉大利，今晚吃 mian();5815+5
00:41		+2
04:36		-3+1
00:16		+
01:26		+1
03:36		64%
9/14
==== Member Distribution ==== ^ Solved ^ A ^ B ^ C ^ D ^ E ^ F ^ G ^ H ^ I ^ J ^ | Pantw | | | | - | | √ | | √ | √ | | | Withinlover | | √ | | - | | | | | | | | Gary | | | √ | | | | | | | | (√ for solved, O for upsolved, - for tried but not solved) ---- ====== Solutions ====== ===== A ===== ===== B ===== 简单推导一下，发现最多可以乘约束个数次。预处理出所有数字最小的质因子然后$O(\log n)$的计算就可以了 ===== C ===== 统计变形后的所有子串个数，所有后缀变形后的子串即为所求，后缀的从右至左每次改变的次数不并不多且只改变连续的几位，对所有后缀变形后的串建SAM,记录每个位置结尾的串在SAM中的节点，每次改变跳回到对应的节点，统计即为所有节点$ans=\sum_{\forall i\in SAM}lenth[i]-lenth[parent[i]]$; ===== D ===== 将数字拆成一位数会得到最大值≤9； 若最优结果的各数字位数相同，只需要对n的所有约数长度的答案进行判断； 若位数不同，则一定存在1000x形式的数字，在串中找出满足条件的最长串，因为最大值≤9，符合条件的串一定为999x和1000x的形式，暴力匹配即可 ===== E ===== ===== F ===== 水题。 ===== G ===== ===== H ===== 从大到小枚举质数 p，每次拿出未匹配的 p 的倍数，把这些数按照最小质因子从大到小排序，然后直接从头两个两个选。 ===== I ===== 读题发现错误率最高 5%，那么我们直接枚举当前未匹配的第一个点，拎出其所有邻接点，判断所有未匹配点到拎出来的点集中的点的连边数，设置一下允许浮动范围，迭代两次。最后全局重判一下，根据字典序调整一下标号，就卡过去了。 ===== J ===== ------------- ====== Comments ====== ptw： - 简单题尽量少错点（B / F），罚时很贵的 - 写之前想好细节（D / I） - 调参的时候要冷静合理调参，不要太莽（I） Gary： - 不盲目跟榜（E） - 有思路尽快分享讨论，码不出来浪费很多时间（D） Withinlover: - 习惯改好点，别用cin, cout（B） - 想好了再写，写了一半在改很花时间（D）