2016-C10-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||Run ID||Time||Size||Problem||Language||Result||
||271||5:38:27||2845||H||g++0x||Wrong answer||
||266||4:52:22||2612||C||g++0x||Wrong answer||
||256||4:27:01||1592||C||g++0x||OK||
||218||2:42:00||1123||B||g++0x||OK||
||200||1:59:18||2069||E||g++0x||OK||
||199||1:42:26||1909||E||g++0x||Time-limit exceeded||
||196||0:45:25||1721||A||g++0x||OK||
||195||0:36:55||1641||A||g++0x||Wrong answer||
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001465
== 流水账 ==
== 总结 ==
=== sfiction ===
* 不论有没有榜都要把题目看完
== 题解 ==
=== A. Senseless and Merciless [sfiction] ===
给定一棵树(<=1e5)和m(<=1e5)个询问(u,v)，计算树上所有点到路径(u,v)的距离与编号乘积之和。
计算LCA(u,v)到所有点的乘积和，再减去路径上点所在子树多计算的贡献。O(n+qlogn)或O(n+q)，取决于LCA。
=== B. Multithreading [sfiction] ===
有n(<=1e5)个线程，每个有ai(<=5000)条指令，每次从所有未结束线程中随机选择一个执行一条指令，求每个线程的期望结束顺位。
两两之间的先后顺序可以递推或组合数预处理，多线程的情况只需将两两相比的期望求和即可。O(a^2^)。
=== C. Polynomial [sfiction] ===
给定一个模p意义下的多项式A(deg<=100)，将其分解为\mul_{i=1}!^{k}{pi(x)!^i}的形式。求k以及pi(x)的次数。
考虑求A和A'的最大公因式，是\mul_{i=2}!^{k}{pi(x)!^(i-1)}，于是可以知道pi(x)的次数之和，再对这个公因式重复求解，即可知道pi(x)次数的后缀和。多项式除法。比较松的上界是O(n!^4)。但因为n次gcd过程中A的次数单调减，复杂度为O(n^3^)。
=== D. Openspaces [sfiction] ===
给定n(<=400)个凸包，每个凸包的大小和所有点的数量均满足<=1e5，求两两之间（可能相交）的外公切线，凸包之间不共点，凸包内无三点共线。
对两个凸包，可以求出整体的凸包，然后检查凸包上每条边是否有不同来源的点，有即可组成外公切线。考虑n^2^次凸包，如果对n个点集进行排序，在用水平法求凸包前对两个凸包点集做归并，即可将单次复杂度降为O(n+m)，总体为O(slogs+ns)。
=== E. Game [sfiction] ===
用f[mask]表示已选取mask后所得局面的全部必胜初始值，用区间表示。f[mask]可以通过枚举所有行动，将下层解求交后取补（非交集的初始值都存在至少一个必胜策略）。求交后集合数量不增，取补最多增加1，因此f[mask]不超过n个区间，维护有序后区间交和区间补都可以O(n)完成。O(n^2^*2^n^)。
=== G. Random Shuffle Ranking [sfiction] ===
给定一个长为2^k^(<=17)的序列a[]，定义b[i][]为交换所有a[j]和a[j!^i]所得序列，求b[i][]的大小关系。
用类似后缀数组倍增法的方法求解。注意到对于一个给定i<=k，j可以与所有大小为2^i^的区间一一对应。f[0][j]=a[j]，f[i][j]=f[i-1][j]+f[i-1][j!^1<<i-1]。即高于i位的表示其位置，第i位表示两个子区间是否发生交换，0-i-1位表示子区间的shuffle方式。
== 补题 ==
~~D~~ F ~~G~~H
=== sfiction ===
* Unaccepted: DG| Run ID | Time | Size | Problem | Language | Result |
| 271 | 5:38:27 | 2845 | H | g++0x | Wrong answer |
| 266 | 4:52:22 | 2612 | C | g++0x | Wrong answer |
| 256 | 4:27:01 | 1592 | C | g++0x | OK |
| 218 | 2:42:00 | 1123 | B | g++0x | OK |
| 200 | 1:59:18 | 2069 | E | g++0x | OK |
| 199 | 1:42:26 | 1909 | E | g++0x | Time-limit exceeded |
| 196 | 0:45:25 | 1721 | A | g++0x | OK |
| 195 | 0:36:55 | 1641 | A | g++0x | Wrong answer |
比赛链接: http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001465
流水账
总结
sfiction
- 不论有没有榜都要把题目看完
题解
A. Senseless and Merciless [sfiction]
给定一棵树(<=1e5)和m(<=1e5)个询问(u,v)，计算树上所有点到路径(u,v)的距离与编号乘积之和。
计算LCA(u,v)到所有点的乘积和，再减去路径上点所在子树多计算的贡献。O(n+qlogn)或O(n+q)，取决于LCA。
B. Multithreading [sfiction]
有n(<=1e5)个线程，每个有ai(<=5000)条指令，每次从所有未结束线程中随机选择一个执行一条指令，求每个线程的期望结束顺位。
两两之间的先后顺序可以递推或组合数预处理，多线程的情况只需将两两相比的期望求和即可。O(a2)。
C. Polynomial [sfiction]
给定一个模p意义下的多项式A(deg<=100)，将其分解为\mul_{i=1}!{k}{pi(x)!i}的形式。求k以及pi(x)的次数。
考虑求A和A'的最大公因式，是\mul_{i=2}!{k}{pi(x)!(i-1)}，于是可以知道pi(x)的次数之和，再对这个公因式重复求解，即可知道pi(x)次数的后缀和。多项式除法。比较松的上界是O(n!4)。但因为n次gcd过程中A的次数单调减，复杂度为O(n3^)。
D. Openspaces [sfiction]
给定n(<=400)个凸包，每个凸包的大小和所有点的数量均满足<=1e5，求两两之间（可能相交）的外公切线，凸包之间不共点，凸包内无三点共线。
对两个凸包，可以求出整体的凸包，然后检查凸包上每条边是否有不同来源的点，有即可组成外公切线。考虑n2次凸包，如果对n个点集进行排序，在用水平法求凸包前对两个凸包点集做归并，即可将单次复杂度降为O(n+m)，总体为O(slogs+ns)。
E. Game [sfiction]
用f[mask]表示已选取mask后所得局面的全部必胜初始值，用区间表示。f[mask]可以通过枚举所有行动，将下层解求交后取补（非交集的初始值都存在至少一个必胜策略）。求交后集合数量不增，取补最多增加1，因此f[mask]不超过n个区间，维护有序后区间交和区间补都可以O(n)完成。O(n2*2n)。
G. Random Shuffle Ranking [sfiction]
给定一个长为2k(<=17)的序列a[]，定义b[i][]为交换所有a[j]和a[j!^i]所得序列，求b[i][]的大小关系。
用类似后缀数组倍增法的方法求解。注意到对于一个给定i<=k，j可以与所有大小为2i的区间一一对应。f[0][j]=a[j]，f[i][j]=f[i-1][j]+f[i-1][j!^1<补题
D F GHsfiction