2018-Reconquista-T46
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
== Contest Information ==
''' Petrozavodsk Winter 2012 - Andrew Stankevich Contest 41 '''
[http://codeforces.com/gym/100496 CF Gym]
== 流水账 ==
== 总结 ==
=== lsmll ===
总体还是不错，但是最后jsb写G的时候我和lzw搞B和F都没搞出来，水平可能还需提高..最后全力搞G是个正确的决定，最后搞出来了。
=== jsb ===
感觉这场ASC相对简单一些？前期我们打得挺好的，机位转换也不错，基本没怎么卡题。
2h53min过了E后，剩下的题感觉都不太可做？强开了类似于机器学习的G，初期没有考虑到一个细节正确率被一些特殊情况拉低了。
然后苦逼造数据……这数据好麻烦，造的我都意识模糊了，还好最后还是能check的……遇到了一个奇怪的问题，队友三个人各种尝试，最后随便fix了个东西使过去了……
=== lzw ===
总体感觉没有太大的失误，后面的三个题确实难度比较大，最后如果早点放弃想F题帮助jsb搞出G题也许罚时可以优秀一些。
== Solution ==
A：手构n=2,3,4发现无解，以为n>1都无解……事实上，跑一跑爆搜，发现n=5是有解的。仔细观察一下，每一行都是上一行循环位移两位。然后我们猜测解可能是每次对上一行循环位移K位。写一个check，会发现如果有解,一定有一组解K=2。所以我们就直接构一个每次位移2的幻方，再check一下输出。最后发现，合法的n是质数和部分5的倍数。感觉可能有神秘的判别方法（UPD：[http://www.cnblogs.com/jiangshibiao/p/8955409.html 5.14处]）。
B：正确性和复杂度存疑。观察了一下过的程序，都采用了一种看起来复杂度比较高的贪心算法。我们以一个点为根搞出一个bfs序，依次决策每个点的颜色。到某点时，如果存在某种颜色一次都没用过，就优先使用它；否则在还能染一次的颜色中，暴力找到一种不冲突的颜色染上去。每次染完后，把父亲颜色和它的颜色的pair记录一下，以供后来判断颜色组是否已经被用过。做法看起来很靠谱，对于某种颜色，必然是靠的越远越好，所以优先使用没染过的颜色、采用bfs序都是有一定道理的。但是不会证明，复杂度也存疑。别的代码找不冲突颜色时，甚至是从小到大枚举的……我加了个并查集，这样每次就能O(1)定位到目前还能染一次的颜色了。（[http://www.cnblogs.com/jiangshibiao/p/8955409.html 5.14处]）。
D：对于一段区间[l,r]，考虑贪心地映射过去：第i个出现的数字换成i。所以我们只需支持两个操作：①找到[l,r]中最靠前的a[x]=a[r]的位置x。②询问[l,x]里有几种不同的数字。前者可以开一个vector二分一下，后者是线段树经典题，记每一个位置的前驱，然后可持久化主席树询问一下。
E：对于每个人，先枚举他保护哪一堆，剩下两堆(x, y) x < y, 的时候分类讨论一下，如果x = y, 那么肯定分成(1, x - 1, y) 如果 x < y / 2 (x, y / 2, y - y / 2), 否则(x. 1, y - 1). 选最优的一种就好了。
G：首先，最大值偏小的一定是没有任何操作的。那我们可以先按最大值排序，取前20%~30%组，将它们取一个平均值，就可以大致估计出原题的p[i]。不妨设为ave[i]。[[br]]
分别考虑0,1,2的特征。对于一组询问a[i]：如果a[i]约等于ave[i]，即为0；如果<=0.15的点降幅((ave[i]-a[i])/a[i])很大（理论上至少75%），但>0.15的点降幅很小，则是2；如果除了最大值，全体都有降幅，那就是1。[[br]]
当然这只是大致的感性讨论。具体地，可以对ave[i]<0.15和ave[j]>0.15中选出有代表性的几组i和j，计算它们降幅的平均值，比较一下即可。
H: 经典树形DP，上下两次DP即可，先算出每个点子树的贡献，第二次再算出上面部分的贡献
I：直接爆搜即可。为了大幅度剪枝，对于形如x^a^*(1-x)^b^的项，我们从小到大枚举a，每次固定它，再暴力搜b。每搜完一层，我们必须保证x^a^前面的系数必须是0（因为之后搜的项都是至少x^a+1^)；整合所有合法解继续搜下去即可。速度很快，不打表也可以过。
J:暴力枚举刚开始放哪里，然后判断一下。需要预处理两两格子能否看见，有些细节特别是视线和角相切，我没有用实数避免精度问题
== 补题 ==
B [jsb]
C []
F []Contest Information
Petrozavodsk Winter 2012 - Andrew Stankevich Contest 41
流水账
总结
lsmll
总体还是不错，但是最后jsb写G的时候我和lzw搞B和F都没搞出来，水平可能还需提高..最后全力搞G是个正确的决定，最后搞出来了。
jsb
感觉这场ASC相对简单一些？前期我们打得挺好的，机位转换也不错，基本没怎么卡题。
2h53min过了E后，剩下的题感觉都不太可做？强开了类似于机器学习的G，初期没有考虑到一个细节正确率被一些特殊情况拉低了。
然后苦逼造数据……这数据好麻烦，造的我都意识模糊了，还好最后还是能check的……遇到了一个奇怪的问题，队友三个人各种尝试，最后随便fix了个东西使过去了……
lzw
总体感觉没有太大的失误，后面的三个题确实难度比较大，最后如果早点放弃想F题帮助jsb搞出G题也许罚时可以优秀一些。
Solution
A：手构n=2,3,4发现无解，以为n>1都无解……事实上，跑一跑爆搜，发现n=5是有解的。仔细观察一下，每一行都是上一行循环位移两位。然后我们猜测解可能是每次对上一行循环位移K位。写一个check，会发现如果有解,一定有一组解K=2。所以我们就直接构一个每次位移2的幻方，再check一下输出。最后发现，合法的n是质数和部分5的倍数。感觉可能有神秘的判别方法（UPD：5.14处）。
B：正确性和复杂度存疑。观察了一下过的程序，都采用了一种看起来复杂度比较高的贪心算法。我们以一个点为根搞出一个bfs序，依次决策每个点的颜色。到某点时，如果存在某种颜色一次都没用过，就优先使用它；否则在还能染一次的颜色中，暴力找到一种不冲突的颜色染上去。每次染完后，把父亲颜色和它的颜色的pair记录一下，以供后来判断颜色组是否已经被用过。做法看起来很靠谱，对于某种颜色，必然是靠的越远越好，所以优先使用没染过的颜色、采用bfs序都是有一定道理的。但是不会证明，复杂度也存疑。别的代码找不冲突颜色时，甚至是从小到大枚举的……我加了个并查集，这样每次就能O(1)定位到目前还能染一次的颜色了。（5.14处）。
D：对于一段区间[l,r]，考虑贪心地映射过去：第i个出现的数字换成i。所以我们只需支持两个操作：①找到[l,r]中最靠前的a[x]=a[r]的位置x。②询问[l,x]里有几种不同的数字。前者可以开一个vector二分一下，后者是线段树经典题，记每一个位置的前驱，然后可持久化主席树询问一下。
E：对于每个人，先枚举他保护哪一堆，剩下两堆(x, y) x < y, 的时候分类讨论一下，如果x = y, 那么肯定分成(1, x - 1, y) 如果 x < y / 2 (x, y / 2, y - y / 2), 否则(x. 1, y - 1). 选最优的一种就好了。
G：首先，最大值偏小的一定是没有任何操作的。那我们可以先按最大值排序，取前20%~30%组，将它们取一个平均值，就可以大致估计出原题的p[i]。不妨设为ave[i]。[[br]]
分别考虑0,1,2的特征。对于一组询问a[i]：如果a[i]约等于ave[i]，即为0；如果<=0.15的点降幅((ave[i]-a[i])/a[i])很大（理论上至少75%），但>0.15的点降幅很小，则是2；如果除了最大值，全体都有降幅，那就是1。[[br]]
当然这只是大致的感性讨论。具体地，可以对ave[i]<0.15和ave[j]>0.15中选出有代表性的几组i和j，计算它们降幅的平均值，比较一下即可。
H: 经典树形DP，上下两次DP即可，先算出每个点子树的贡献，第二次再算出上面部分的贡献
I：直接爆搜即可。为了大幅度剪枝，对于形如xa*(1-x)b的项，我们从小到大枚举a，每次固定它，再暴力搜b。每搜完一层，我们必须保证xa前面的系数必须是0（因为之后搜的项都是至少xa+1)；整合所有合法解继续搜下去即可。速度很快，不打表也可以过。
J:暴力枚举刚开始放哪里，然后判断一下。需要预处理两两格子能否看见，有些细节特别是视线和角相切，我没有用实数避免精度问题
补题
B [jsb]
C []
F []