2019-team2/Sp059

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[[Image(1.png,700px)]]

[[Image(2.png,700px)]]

[[Image(3.png,700px)]]

[wiki:2019-team2 返回Runespoor]


[https://codeforces.com/gym/102040 contest]

== 流水账 ==


== 总结 ==

'''zqq: ''' 这套题很需要板子，F题是树链求交的板子，I是三维几何的基本板。没有板子就会很痛苦，我们I没有

            H卡了很久不太应该，仔细想想想到形状不变，即循环节是置换环大小的lcm

            题目很良心，时限很大，不卡常。

            A题没有想到不太应该，利用性质缩小范围的思路挺常见的。

            B题虽然代码短，但是写错了讨论一下可能调得更快。

            '''这个月去把模板整理全面，巩固一些基本的知识点，比学新的东西更重要'''

=== 题解 ===

* A : 观察到有用的数不会很多，可以写一个搜索或者猜一下，发现上界是72。然后n^4^ dp，求出长度和平均数之后，字典序从前到后贪心。

* D : 暴搜。首先发现有些阶乘可以表示成更小阶乘的积，因此不需要考虑这些数(4,6,8,9,10,12,16,24)。之后按字典序贪心选，每选一次用暴搜check一下可行性，暴搜从大的阶乘开始选，要加很多优化(题解还加了LP整数规划的优化，我没加)。成功选出一种后可能跟原串相同，因此字典序贪心选的过程也要写成暴搜的形式。字典序暴搜写的时候也有技巧。举两个例子，aazz的答案是azaz，aq的答案是bbp。只有aazz这种本身最优解恰好与自己重合的串，最后答案才有可能不是非递减的，并且最后逆序对为1。暴搜的时候先非递减，搜到一个答案发现重合之后，再去掉非递减的限制一次。（事实上我跑的最快的一次是：小串使用上述做法，大串跑出相同串的话直接交换最后相邻不同的字母，反例随便就能造出来比如aaaaaaaaaaaaaaaq，但是测试数据恰好没有）。

* G : 点分，对每个点分中心是一个区间RMQ，但是要先二分求左右端点，复杂度O(n * logn^2^) , 常数很小

=== 补题 ===

 * A : [zqq]

 * D : [lyk]

返回Runespoor

contest

流水账

总结

zqq: 这套题很需要板子，F题是树链求交的板子，I是三维几何的基本板。没有板子就会很痛苦，我们I没有

H卡了很久不太应该，仔细想想想到形状不变，即循环节是置换环大小的lcm

题目很良心，时限很大，不卡常。

A题没有想到不太应该，利用性质缩小范围的思路挺常见的。

B题虽然代码短，但是写错了讨论一下可能调得更快。

这个月去把模板整理全面，巩固一些基本的知识点，比学新的东西更重要

题解

A : 观察到有用的数不会很多，可以写一个搜索或者猜一下，发现上界是72。然后n⁴ dp，求出长度和平均数之后，字典序从前到后贪心。
D : 暴搜。首先发现有些阶乘可以表示成更小阶乘的积，因此不需要考虑这些数(4,6,8,9,10,12,16,24)。之后按字典序贪心选，每选一次用暴搜check一下可行性，暴搜从大的阶乘开始选，要加很多优化(题解还加了LP整数规划的优化，我没加)。成功选出一种后可能跟原串相同，因此字典序贪心选的过程也要写成暴搜的形式。字典序暴搜写的时候也有技巧。举两个例子，aazz的答案是azaz，aq的答案是bbp。只有aazz这种本身最优解恰好与自己重合的串，最后答案才有可能不是非递减的，并且最后逆序对为1。暴搜的时候先非递减，搜到一个答案发现重合之后，再去掉非递减的限制一次。（事实上我跑的最快的一次是：小串使用上述做法，大串跑出相同串的话直接交换最后相邻不同的字母，反例随便就能造出来比如aaaaaaaaaaaaaaaq，但是测试数据恰好没有）。
G : 点分，对每个点分中心是一个区间RMQ，但是要先二分求左右端点，复杂度O(n * logn²) , 常数很小

补题

A : [zqq]
D : [lyk]