2017-Sp173-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门cjb读了A就上机写A，然后the了，yzc上机写H,'''H1y35'''，cjb改成dij，'''A2y39'''，之后sub上机写E，wa了两发'''E3y62'''，yzc和sub讨论了B，yzc上机'''B1y68'''，cjb上机写I，mle之后改成滚动数组'''I2y91'''。sub把G的做法告诉yzc，yzc上机'''G1y100'''，之后三个人讨论起了J，yzc上机分块，tle了一万年，各种优化预处理，最后sub加了剪枝才'''J7y236'''。cjb想好了F，上机'''F2y260'''。之后三个人想L，sub上机rush，5:00:04交了一发wa。
== 总结 ==
=== chenjb ===
被反杀了....感觉J是我们队的软肋，要好好总结。
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：斯坦纳树裸题，请用dijkstra转移。

 * B：求前缀和，每个人可以从前缀和比自己小的位置转移，用树状数组维护即可。

 * C：

 * D：

 * E：枚举圆位置，枚举圆大小，直接计算即可。

 * F：二分答案，从大到小每次处理2^p^的情况，初始化为假装有高度为0的的瓶子，之后用已有的瓶子往答案基里代替进去，之后降到2^p-1^之后就把一个瓶子拆成两个，注意不要让瓶子数量爆炸，每次和前缀瓶子个数取min即可。

 * G：i到2i连代价为0的边，i到i+1连代价为1的边，跑从0开始的非0最小环，答案是环长度。

 * H：按题意统计即可。

 * I：mask压小于sqrt的16个质数，然后把数字按照最大的质因子分组(如果最大质因子小于sqrt则放进自己那组去)，之后就背包一下。

 * J：询问x>sqrt的时候，显然只有区间的后sqrt个有用，剩余的直接拿出来按照x的值线段树维护即可，加些剪枝才能过。(本队场上做法)

 * J：对于一个询问(l,r,x)，第i天的答案就是a[i]+(i-l+1)*x，这个式子可以斜率优化，把所有询问按照x递增排序，然后用线段树维护斜率优化，复杂度是1个log，把x排序之后，相当于线段树的每个区间维护一个单调队列就行了，每次只会删除单调队列的头元素，元素总数是nlogn个。(by ZYB)

 * K：就是假设原数列是ai，存在一个0-m-1的permutation bi，使得ai+i-bi都是m的倍数，令ci=(ai+i-bi)/m，sigma(ci)=n，然后变成了我要找到一组和为n的ci，然后一组全排列 bi，满足对任意i，ci>0或i>=bi，用二项式反演，可以求出恰好k个i满足i＜bi的全排列的个数，考虑循环节长度为k，段数为d，然后答案是对miu(d)的反演求和，此时满足ai=ai+k=...=ai+(d-1)k，且对应的bi也应该是两两相隔k，也就是说前k项bi%k是一个0~k-1的全排列，然后每个%k=i的位置也恰好有d种rotate的可能，然后我上面用二项式反演已经求出了G[i]表示前k项bi恰好有i个满足bj%k>j的permutation个数，对每个bj%k>j的位置，随着bj,bj+k,...的rotate，满足bj>j的个数分别为1，2，...,d。对每个bj%k<=j的位置，随着bj,bj+k,...的rotate，满足bj>j的个数分别为0，1，...,d-1。后可以做个m^2^的dp，求出恰好有s项bj>j的方案数，意味着对应的cj至少为1，就变成了s个至少为1的数和m-s个至少为0的数，综合为n的方案数了。（by LHY)

 * L：就是可以把u和v看成二进制串，然后每次改变一位，始终不能出现两个相邻的1，然后考虑u xor v每个连续的1段，里面肯定是10101->01010的形式，f(n)表示长度为n的方案数，f(n)=sigma(f(i)*f(n-1-i)*c(n-1,i)) i为奇数 (by ZYB)

流水账

出门cjb读了A就上机写A，然后the了，yzc上机写H,H1y35，cjb改成dij，A2y39，之后sub上机写E，wa了两发E3y62，yzc和sub讨论了B，yzc上机B1y68，cjb上机写I，mle之后改成滚动数组I2y91。sub把G的做法告诉yzc，yzc上机G1y100，之后三个人讨论起了J，yzc上机分块，tle了一万年，各种优化预处理，最后sub加了剪枝才J7y236。cjb想好了F，上机F2y260。之后三个人想L，sub上机rush，5:00:04交了一发wa。

总结

chenjb

被反杀了....感觉J是我们队的软肋，要好好总结。

oipotato

subconscious

题解

  • A：斯坦纳树裸题，请用dijkstra转移。
  • B：求前缀和，每个人可以从前缀和比自己小的位置转移，用树状数组维护即可。
  • C：
  • D：
  • E：枚举圆位置，枚举圆大小，直接计算即可。
  • F：二分答案，从大到小每次处理2p的情况，初始化为假装有高度为0的的瓶子，之后用已有的瓶子往答案基里代替进去，之后降到2p-1之后就把一个瓶子拆成两个，注意不要让瓶子数量爆炸，每次和前缀瓶子个数取min即可。
  • G：i到2i连代价为0的边，i到i+1连代价为1的边，跑从0开始的非0最小环，答案是环长度。
  • H：按题意统计即可。
  • I：mask压小于sqrt的16个质数，然后把数字按照最大的质因子分组(如果最大质因子小于sqrt则放进自己那组去)，之后就背包一下。
  • J：询问x>sqrt的时候，显然只有区间的后sqrt个有用，剩余的直接拿出来按照x的值线段树维护即可，加些剪枝才能过。(本队场上做法)
  • J：对于一个询问(l,r,x)，第i天的答案就是a[i]+(i-l+1)*x，这个式子可以斜率优化，把所有询问按照x递增排序，然后用线段树维护斜率优化，复杂度是1个log，把x排序之后，相当于线段树的每个区间维护一个单调队列就行了，每次只会删除单调队列的头元素，元素总数是nlogn个。(by ZYB)
  • K：就是假设原数列是ai，存在一个0-m-1的permutation bi，使得ai+i-bi都是m的倍数，令ci=(ai+i-bi)/m，sigma(ci)=n，然后变成了我要找到一组和为n的ci，然后一组全排列 bi，满足对任意i，ci>0或i>=bi，用二项式反演，可以求出恰好k个i满足i＜bi的全排列的个数，考虑循环节长度为k，段数为d，然后答案是对miu(d)的反演求和，此时满足ai=ai+k=...=ai+(d-1)k，且对应的bi也应该是两两相隔k，也就是说前k项bi%k是一个0~k-1的全排列，然后每个%k=i的位置也恰好有d种rotate的可能，然后我上面用二项式反演已经求出了G[i]表示前k项bi恰好有i个满足bj%k>j的permutation个数，对每个bj%k>j的位置，随着bj,bj+k,...的rotate，满足bj>j的个数分别为1，2，...,d。对每个bj%k<=j的位置，随着bj,bj+k,...的rotate，满足bj>j的个数分别为0，1，...,d-1。后可以做个m2的dp，求出恰好有s项bj>j的方案数，意味着对应的cj至少为1，就变成了s个至少为1的数和m-s个至少为0的数，综合为n的方案数了。（by LHY)
  • L：就是可以把u和v看成二进制串，然后每次改变一位，始终不能出现两个相邻的1，然后考虑u xor v每个连续的1段，里面肯定是10101->01010的形式，f(n)表示长度为n的方案数，f(n)=sigma(f(i)*f(n-1-i)*c(n-1,i)) i为奇数 (by ZYB)
附加文件