2016-C08-team1
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||User||Problem||Result||Memory||Time||Language||Length||Submit Time||
||Siunaus||D||TLE|| || ||C++11 5.3.0||2553||2016-08-08 14:05:08||
||Siunaus||D||TLE|| || ||C++11 5.3.0||2549||2016-08-08 14:04:59||
||Siunaus||D||TLE|| || ||C++11 5.3.0||2549||2016-08-08 14:04:36||
||Siunaus||D||TLE|| || ||C++11 5.3.0||2551||2016-08-08 14:04:20||
||Siunaus||D||TLE|| || ||C++11 5.3.0||2545||2016-08-08 14:02:18||
||Siunaus||D||TLE|| || ||C++11 5.3.0||2469||2016-08-08 14:01:06||
||Siunaus||D||TLE|| || ||C++11 5.3.0||2473||2016-08-08 13:54:56||
||Siunaus||D||TLE|| || ||C++ 5.3.0||2473||2016-08-08 13:54:46||
||Siunaus||A||CE|| || ||C++ 5.3.0||2141||2016-08-08 13:48:27||
||Siunaus||H||AC||0||572||C++ 5.3.0||1585||2016-08-08 12:26:47||
||Siunaus||H||WA|| || ||C++ 5.3.0||1259||2016-08-08 12:17:24||
||Siunaus||A||AC||0||728||C++ 5.3.0||1994||2016-08-08 11:35:05||
||Siunaus||A||WA|| || ||C++ 5.3.0||1998||2016-08-08 11:33:11||
||Siunaus||A||WA|| || ||C++ 5.3.0||1797||2016-08-08 11:26:27||
||Siunaus||J||AC||0||7252||C++11 5.3.0||2312||2016-08-08 11:16:05||
||Siunaus||I||AC||0||63||C++ 5.3.0||1355||2016-08-08 11:14:25||
||Siunaus||J||RE|| || ||C++11 5.3.0||2220||2016-08-08 10:50:44||
||Siunaus||C||AC||0||2492||C++ 5.3.0||971||2016-08-08 10:41:38||
||Siunaus||C||WA|| || ||C++ 5.3.0||964||2016-08-08 10:30:36||
||Siunaus||G||AC||0||363||C++11 5.3.0||641||2016-08-08 10:11:17||
||Siunaus||G||WA|| || ||C++ 5.3.0||536||2016-08-08 09:40:58||
||Siunaus||F||AC||0||3||C++ 5.3.0||574||2016-08-08 09:34:52||
||Siunaus||A||WA|| || ||C++ 5.3.0||1183||2016-08-08 09:32:24||
||Siunaus||E||AC||0||3||C++ 5.3.0||538||2016-08-08 09:15:25||
[http://acm.hust.edu.cn/vjudge/contest/126830 比赛链接] (password: 20160808)
== 流水账 ==
=== sfiction ===
今天中档题比较顺利，想题的时候基本没有阻碍，写题的时候倒是犯了好几次错误。后期一直在做 B，过于自信，没有仔细考虑队友在 D 上的思路……
== 总结 ==
=== sfiction ===
* 前中期有所提高，后期仍然没能越过坎，还是需要继续做/补难题
== 题解 ==
CEFG 略去不表
=== A. Association for Cool Machineries (Part 1) [sfiction] ===
给一个 n*n 的地图和一个长度 <=n 的行动程序，机器人从给定位置出发根据程序行动，求其坐标轨迹是否无限循环，如果是则求循环节长度。
首先考虑坐标+程序位置的循环节，必然是答案的数倍，只需要求出这一循环节的最短重复子串即可。可以用扩展KMP算法或者hash。
=== D. Association of Computer Maintenance [sfiction] ===
给出一个数n的素因数分解，将其分解为a*b使得a+b最小。保证素因数个数不超过700，每个素因数大小不超过100，次数不超过100，n约数个数不超过10^10^。
将n分解为尽可能接近的两个互质数ab，这样div[n]=div[a]*div[b]。只需要贪心分配素因数即可，次数最高不超过100，因此极限情况为分解为1e6和1e4。之后枚举一侧所取的数，另一侧二分出小于等于sqrt(n)的最大值即可，二分部分需要用对数处理运算。
=== H. Association for Convex Main Office [sfiction] ===
在4e7!^2的平面上绘制一个整点凸多边形。
考虑斜率应尽可能均匀分布，处理出所有较小的互质对，再从中选取和最小的数个，视为向量首尾向量即可。为提高速度只求斜率在(0,1)的向量。
=== I. Apples, Cherries, and Mangos [sfiction] ===
给定三种物品的数量，求相邻两项均不同的排列数。
假设物品1将序列分为n段，则其他两种物品在每段中的数量差为-1/0/1，而只要确定其中任意一个的数量，就能推算出另外两种的数量，因此可以枚举其中一类段的数量然后进行计算。
=== J. Association of Cats and Magical Lights [sfiction] ===
给定一棵树(<=3e5)，每个节点有一个颜色，每次查询(q<=1e6)修改一个结点的颜色或询问某棵子树中出现次数为奇数的颜色数。
仅考虑奇偶性，每个节点维护一个bitset按DFS序维护。
== 补题 ==
B ~~D~~ K
=== sfiction ===
* Unaccepted: D
* kmp+Z| User | Problem | Result | Memory | Time | Language | Length | Submit Time |
| Siunaus | D | TLE | C++11 5.3.0 | 2553 | 2016-08-08 14:05:08 | ||
| Siunaus | D | TLE | C++11 5.3.0 | 2549 | 2016-08-08 14:04:59 | ||
| Siunaus | D | TLE | C++11 5.3.0 | 2549 | 2016-08-08 14:04:36 | ||
| Siunaus | D | TLE | C++11 5.3.0 | 2551 | 2016-08-08 14:04:20 | ||
| Siunaus | D | TLE | C++11 5.3.0 | 2545 | 2016-08-08 14:02:18 | ||
| Siunaus | D | TLE | C++11 5.3.0 | 2469 | 2016-08-08 14:01:06 | ||
| Siunaus | D | TLE | C++11 5.3.0 | 2473 | 2016-08-08 13:54:56 | ||
| Siunaus | D | TLE | C++ 5.3.0 | 2473 | 2016-08-08 13:54:46 | ||
| Siunaus | A | CE | C++ 5.3.0 | 2141 | 2016-08-08 13:48:27 | ||
| Siunaus | H | AC | 0 | 572 | C++ 5.3.0 | 1585 | 2016-08-08 12:26:47 |
| Siunaus | H | WA | C++ 5.3.0 | 1259 | 2016-08-08 12:17:24 | ||
| Siunaus | A | AC | 0 | 728 | C++ 5.3.0 | 1994 | 2016-08-08 11:35:05 |
| Siunaus | A | WA | C++ 5.3.0 | 1998 | 2016-08-08 11:33:11 | ||
| Siunaus | A | WA | C++ 5.3.0 | 1797 | 2016-08-08 11:26:27 | ||
| Siunaus | J | AC | 0 | 7252 | C++11 5.3.0 | 2312 | 2016-08-08 11:16:05 |
| Siunaus | I | AC | 0 | 63 | C++ 5.3.0 | 1355 | 2016-08-08 11:14:25 |
| Siunaus | J | RE | C++11 5.3.0 | 2220 | 2016-08-08 10:50:44 | ||
| Siunaus | C | AC | 0 | 2492 | C++ 5.3.0 | 971 | 2016-08-08 10:41:38 |
| Siunaus | C | WA | C++ 5.3.0 | 964 | 2016-08-08 10:30:36 | ||
| Siunaus | G | AC | 0 | 363 | C++11 5.3.0 | 641 | 2016-08-08 10:11:17 |
| Siunaus | G | WA | C++ 5.3.0 | 536 | 2016-08-08 09:40:58 | ||
| Siunaus | F | AC | 0 | 3 | C++ 5.3.0 | 574 | 2016-08-08 09:34:52 |
| Siunaus | A | WA | C++ 5.3.0 | 1183 | 2016-08-08 09:32:24 | ||
| Siunaus | E | AC | 0 | 3 | C++ 5.3.0 | 538 | 2016-08-08 09:15:25 |
比赛链接 (password: 20160808)
流水账
sfiction
今天中档题比较顺利，想题的时候基本没有阻碍，写题的时候倒是犯了好几次错误。后期一直在做 B，过于自信，没有仔细考虑队友在 D 上的思路……
总结
sfiction
- 前中期有所提高，后期仍然没能越过坎，还是需要继续做/补难题
题解
CEFG 略去不表
A. Association for Cool Machineries (Part 1) [sfiction]
给一个 n*n 的地图和一个长度 <=n 的行动程序，机器人从给定位置出发根据程序行动，求其坐标轨迹是否无限循环，如果是则求循环节长度。
首先考虑坐标+程序位置的循环节，必然是答案的数倍，只需要求出这一循环节的最短重复子串即可。可以用扩展KMP算法或者hash。
D. Association of Computer Maintenance [sfiction]
给出一个数n的素因数分解，将其分解为a*b使得a+b最小。保证素因数个数不超过700，每个素因数大小不超过100，次数不超过100，n约数个数不超过1010。
将n分解为尽可能接近的两个互质数ab，这样div[n]=div[a]*div[b]。只需要贪心分配素因数即可，次数最高不超过100，因此极限情况为分解为1e6和1e4。之后枚举一侧所取的数，另一侧二分出小于等于sqrt(n)的最大值即可，二分部分需要用对数处理运算。
H. Association for Convex Main Office [sfiction]
在4e7!^2的平面上绘制一个整点凸多边形。
考虑斜率应尽可能均匀分布，处理出所有较小的互质对，再从中选取和最小的数个，视为向量首尾向量即可。为提高速度只求斜率在(0,1)的向量。
I. Apples, Cherries, and Mangos [sfiction]
给定三种物品的数量，求相邻两项均不同的排列数。
假设物品1将序列分为n段，则其他两种物品在每段中的数量差为-1/0/1，而只要确定其中任意一个的数量，就能推算出另外两种的数量，因此可以枚举其中一类段的数量然后进行计算。
J. Association of Cats and Magical Lights [sfiction]
给定一棵树(<=3e5)，每个节点有一个颜色，每次查询(q<=1e6)修改一个结点的颜色或询问某棵子树中出现次数为奇数的颜色数。
仅考虑奇偶性，每个节点维护一个bitset按DFS序维护。
补题
B D K
sfiction
- Unaccepted: D
- kmp+Z