2017-Sp289-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
=== chenjb ===

=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：数位dp。

 * B：对于每个人，考虑每个能取的左边界对应的能取的上边界，向左移动的时候，上边界只会变化log次，每次可用线段树二分找到，对于左右边界的各log个变化点，枚举即可。

 * C：预处理对于每一种质因子目前最小留下的数是谁，nlogn。

 * D：对于每个点前缀和即可以做到O(n)转移，状态在边上，6n^2^logn。

 * E：f(i)=(k+2)/2*f(n/k)，记搜即可。

 * F：对于环，枚举根的左边断开，右边断开，都不断开三种情况，都是环dp。

 * G：式子是pn+qn-2pq=k，如果n小，直接n^2^暴力算出所有可能，n大就枚举然后n*t。

 * H：a=x/2,b=x-a。

 * I：看做2*n个位置填数字，权值不同。f[mask]表示轮到选数字了，剩下mask位置可填的最大值，g[mask][k]表示轮到选位置，被选了k这个数字的最小值，嵌套dp并记录最优值选法即可。

 * J：

流水账

chenjb

oipotato

subconscious

题解

• A：数位dp。
• B：对于每个人，考虑每个能取的左边界对应的能取的上边界，向左移动的时候，上边界只会变化log次，每次可用线段树二分找到，对于左右边界的各log个变化点，枚举即可。
• C：预处理对于每一种质因子目前最小留下的数是谁，nlogn。
• D：对于每个点前缀和即可以做到O(n)转移，状态在边上，6n²logn。
• E：f(i)=(k+2)/2*f(n/k)，记搜即可。
• F：对于环，枚举根的左边断开，右边断开，都不断开三种情况，都是环dp。
• G：式子是pn+qn-2pq=k，如果n小，直接n²暴力算出所有可能，n大就枚举然后n*t。
• H：a=x/2,b=x-a。
• I：看做2*n个位置填数字，权值不同。f[mask]表示轮到选数字了，剩下mask位置可填的最大值，g[mask][k]表示轮到选位置，被选了k这个数字的最小值，嵌套dp并记录最优值选法即可。
• J：