2019-Sp047-lyk
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(1.png,700px)]]
[wiki:2019-team2 返回Runespoor]
[https://ac.nowcoder.com/acm/contest/vip-index contest]
== 流水账 ==
== 总结 ==
'''zqq: ''' 我们开场比较顺利，E题做过，签到很快。
但是D题对中国剩余定理不够熟悉，没有想到余数爆的情况，卡了一会。
然后我想了两个小时C题，以为是一个很难的字符串题，然而方向完全偏了。
其实只需要考虑border只会出现在连续一段区间的性质，二分即可。
'''我对题目的直觉很差，老是浪费很多时间去想不太靠谱的算法，自己一个人想出题的能力还是很差。真的要多打codeforces！'''
I是一个巧妙的随机化，lyk一个人写了很久暴搜，但是剪枝不够强。
后期说不定应该三个人一起看C？
还有就是我在最后写代码特别慌。以后训练要多在最后一个小时写题锻炼。
'''Heltion: ''' 唯一还行的地方冷静下来没写python,
== 题解 ==
* A： 可逆背包。先对所有物品做背包以后，撤销一个的方案数： g[n][k] = f[n][k] - g[n - 1][k - x[i]]
* C: 考虑每个border只会在一段连续的区间出现，二分这个时间，hash判断
* D: 中国剩余定理。判断无解：对每个(i,j) 如果 a[i] % gcd(m[i],m[j]) != a[j] % gcd(m[i],m[j]) （本质是模质因数的每个次幂相同）, 则无解。关于爆lim的情况，模数爆了之后直接判当前答案是否合法
* G： 枚举斜率。可能和一对点的连线垂直或平行，然后把投影在这条直线的垂线上，找中位数
(用atan2算出直线和x轴夹角a,把所有点绕原点顺时针旋转a,找旋转后纵坐标y'=-sina x+cosa y中间两个数差/2).
* I: 正解随机化：
把长度为10的环拆成两个长度为5的。为了防止统计重复，把每个点随机黑白染色，要求连线5个白色点和连续5个黑色点组成10元环。（这样最优解合法的概率是10 / 1024, 随机1000次正确率是1 - (1 / e)^10^）
统计长度为5的最长路：
先枚举两个点，求出长度为3的路径的前三大
然后再枚举两端的四个点，直接统计答案。
复杂度： O(T * m^2^)
== 补题 ===
* C :
* I : 
流水账
总结
zqq: 我们开场比较顺利，E题做过，签到很快。
但是D题对中国剩余定理不够熟悉，没有想到余数爆的情况，卡了一会。
然后我想了两个小时C题，以为是一个很难的字符串题，然而方向完全偏了。
其实只需要考虑border只会出现在连续一段区间的性质，二分即可。
我对题目的直觉很差，老是浪费很多时间去想不太靠谱的算法，自己一个人想出题的能力还是很差。真的要多打codeforces！
I是一个巧妙的随机化，lyk一个人写了很久暴搜，但是剪枝不够强。
后期说不定应该三个人一起看C？
还有就是我在最后写代码特别慌。以后训练要多在最后一个小时写题锻炼。
Heltion: 唯一还行的地方冷静下来没写python,
题解
- A： 可逆背包。先对所有物品做背包以后，撤销一个的方案数： g[n][k] = f[n][k] - g[n - 1][k - x[i]]
- C: 考虑每个border只会在一段连续的区间出现，二分这个时间，hash判断
- D: 中国剩余定理。判断无解：对每个(i,j) 如果 a[i] % gcd(m[i],m[j]) != a[j] % gcd(m[i],m[j]) （本质是模质因数的每个次幂相同）, 则无解。关于爆lim的情况，模数爆了之后直接判当前答案是否合法
- G： 枚举斜率。可能和一对点的连线垂直或平行，然后把投影在这条直线的垂线上，找中位数
(用atan2算出直线和x轴夹角a,把所有点绕原点顺时针旋转a,找旋转后纵坐标y'=-sina x+cosa y中间两个数差/2).
- I: 正解随机化：
把长度为10的环拆成两个长度为5的。为了防止统计重复，把每个点随机黑白染色，要求连线5个白色点和连续5个黑色点组成10元环。（这样最优解合法的概率是10 / 1024, 随机1000次正确率是1 - (1 / e)10）
统计长度为5的最长路：
先枚举两个点，求出长度为3的路径的前三大
然后再枚举两端的四个点，直接统计答案。
复杂度： O(T * m2)
== 补题 ===
- C :
- I :
附加文件
- 1.png by zhangqingqi