2018-Sp27-lyk

从 Trac 迁移的文章

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

原文章内容如下：

[[Image(1.jpg,500px)]]

[/wiki/2018-team3 返回Helianthus]

[https://www.jisuanke.com/contest/1557?view=challenges]

== 流水账 ==
咕咕
== 总结 ==
=== LYK ===
最后三人写一道E，做法是对的，但是细节一直爆炸。
=== Jhguai  ===

=== Heltion ===

== 题解 ==
 * A: 组合数 容斥  sum,,i=0,,^n-1^C,,i,,^n^2^k(n−i)^(−1)^i^ n为偶数还要加上2^k^
 * B: 博弈 DP 
 * C: 搜索
 * D: f(n,m)=mu(n)sum,,d|n,,mu(d)f(d,m/d) 算f(1,m)用杜教筛
 * E: 没有翻倍可以矩阵快速幂求.翻倍的做法:枚举两个点作为翻倍的起点(s)和终点(e),求出s到e长度至多为T的最大值,建立G'=G,从G'中所有点到G中所有点连边,求出e'到s长度至多为t-T的最大值 [wiki:2018-Sp27-lyk/E 代码]
 * F: map签到
 * G: set签到
 * H: BIT签到
 * I: 签到
 * J: 生成树上两点距离查询
 * K: 快速幂,用bitset或者位运算

== 补题 ==

[/wiki/2018-team3 返回Helianthus]

https://www.jisuanke.com/contest/1557?view=challenges

流水账

咕咕

总结

LYK

最后三人写一道E，做法是对的，但是细节一直爆炸。

Jhguai

Heltion

题解

  • A: 组合数 容斥 sumi=0n-1Cin2k(n−i)(−1)i n为偶数还要加上2k
  • B: 博弈 DP
  • C: 搜索
  • D: f(n,m)=mu(n)sumd|nmu(d)f(d,m/d) 算f(1,m)用杜教筛
  • E: 没有翻倍可以矩阵快速幂求.翻倍的做法:枚举两个点作为翻倍的起点(s)和终点(e),求出s到e长度至多为T的最大值,建立G'=G,从G'中所有点到G中所有点连边,求出e'到s长度至多为t-T的最大值 代码
  • F: map签到
  • G: set签到
  • H: BIT签到
  • I: 签到
  • J: 生成树上两点距离查询
  • K: 快速幂,用bitset或者位运算

补题

附加文件