2018-Sp18-lyk

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2018-team3 返回Helianthus]

[http://acm.hdu.edu.cn/search.php?field=problem&key=2018+Multi-University+Training+Contest+8&source=1&searchmode=source upsolving]
== 流水账 ==
heltion看到签到题E，丢给lyk，打错WA一发，'''E2y13'''。之后看到A题，一眼是NTT，发现数据范围不对。jhguai和heltion看到J题，想到做法，'''J2y110'''。lyk看到B题几何，想了好一会儿，因为情况没考虑全WA一发，之后暴力求MAX过了，'''B2y159'''。看到构造题D，lyk想到D的其中一种构造，交了一发WA，怀疑交错，又交一发WA，终于在heltion无意的提醒下想到正解，'''D3y236'''。全队想A题，没想到，卒。

== 总结 ==
=== LYK ===
今天又打了个J8，又在A题这个看似NTT实则容斥的题目上卡死。D题构造题一直在想固定一维最大下的情况，其实早就也很容易就能证明出来在这种情况下这种构造是对的。所以应该早点想到前提条件是错的。
如果放弃A题，去做L题，其实这个贪心不难想。

=== Jhguai  ===

=== Heltion ===


== 题解 ==
 * A: 题意:将k个物品分成可区分的n份,每份小于m的方案数. 答案是sum ,,0<=i<=n,i*m<=k,, (-1)^i^C,,k-i*m+n-1,,^m-1^C,,m,,^i^.

== 补题 ==
 * ~~A~~：容斥 排列组合 heltion
 * F：burnside heltion (做出这题你差不多就毕业了）
 * G：基环树DP lyk
 * I：广义后缀自动机 jhguai
 * ~~K~~：状压DP lyk nm3^m^ 3进制分别表示：该行未选；该行之前有遗漏气球且未选；该行已选 注意最后答案*factorial的时候爆ll了处理一下
 * L：堆贪心 口胡

[/wiki/2018-team3 返回Helianthus]

upsolving

流水账

heltion看到签到题E，丢给lyk，打错WA一发，E2y13。之后看到A题，一眼是NTT，发现数据范围不对。jhguai和heltion看到J题，想到做法，J2y110。lyk看到B题几何，想了好一会儿，因为情况没考虑全WA一发，之后暴力求MAX过了，B2y159。看到构造题D，lyk想到D的其中一种构造，交了一发WA，怀疑交错，又交一发WA，终于在heltion无意的提醒下想到正解，D3y236。全队想A题，没想到，卒。

总结

LYK

今天又打了个J8，又在A题这个看似NTT实则容斥的题目上卡死。D题构造题一直在想固定一维最大下的情况，其实早就也很容易就能证明出来在这种情况下这种构造是对的。所以应该早点想到前提条件是错的。

如果放弃A题，去做L题，其实这个贪心不难想。

Jhguai

Heltion

题解

• A: 题意:将k个物品分成可区分的n份,每份小于m的方案数. 答案是sum ,,0<=i<=n,i*m<=k _(-1)ⁱCk-i*m+n-1_^m-1Cm,,ⁱ.

补题

• A：容斥 排列组合 heltion
• F：burnside heltion (做出这题你差不多就毕业了）
• G：基环树DP lyk
• I：广义后缀自动机 jhguai
• K：状压DP lyk nm3^m 3进制分别表示：该行未选；该行之前有遗漏气球且未选；该行已选 注意最后答案*factorial的时候爆ll了处理一下
• L：堆贪心 口胡