2017-Sp273-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
出门各自看题，cjb上机'''C1y9'''。之后sub骗cjb wa了F，自己上机'''F2y17'''。yzc写了个H，'''H1y26'''。cjb丢了个two-pointer给yzc，'''J2y58'''。之后sub上机三分套三分wa了A，换了写法还是wa。cjb和yzc开了K，'''K1y112'''。之后sub '''A1y123'''，再之后sub '''I1y147'''。cjb多年前丢给yzc的E终于有空写了，顺便又丢了个D给yzc，'''E2y175'''。sub '''B1y225'''，yzc '''D2y270'''。三个人一起理论G，感觉状压复杂度不太对，理论到了最后打出GG。
=== chenjb ===
感觉这个G理论来理论去自爆了啊....其实很对的说，好像要用力压状态。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：分类讨论，分为垂直，直接走到交点，镜像再镜像三种情况。

 * B：f[i][j]代表最后一个落在i，一共用了j个有多少种方案，要求相邻两个不能同时有(fib进制的性质)，在dp数组上走。

 * C：每个式子的m的最大值显然是a-b，gcd合并即可。

 * D：注意到下雪是全局的，因此一个区间里最厚的显然是最晚被清0时刻最小值，用线段树维护，取出来后直接计算即可。

 * E：跑出MST，对于非树边，答案是覆盖的树边最大值；对于树边，答案是覆盖的非树边最小值，用启发式合并和倍增维护。

 * F：本质上判断sqrt(p)+sqrt(d)和sqrt(t)的关系，要全整数运算，平方再平方即可。

 * G：yzc

 * H：暴力枚举。

 * I：考虑取最小割，转化成网格上dp，树状数组维护。

 * J：two-pointer维护，显然一个区间都归成中位数最优。

 * K：最大值是按+0-的优先级尝试，最小值是按-0+，从前往后能放就放贪心即可。

 * L：sub

 * M：cjb

 * [https://codeforces.com/blog/entry/63109 Codeforces]

 * [https://www.cnblogs.com/clrs97/p/9954169.html Claris]

流水账

出门各自看题，cjb上机C1y9。之后sub骗cjb wa了F，自己上机F2y17。yzc写了个H，H1y26。cjb丢了个two-pointer给yzc，J2y58。之后sub上机三分套三分wa了A，换了写法还是wa。cjb和yzc开了K，K1y112。之后sub A1y123，再之后sub I1y147。cjb多年前丢给yzc的E终于有空写了，顺便又丢了个D给yzc，E2y175。sub B1y225，yzc D2y270。三个人一起理论G，感觉状压复杂度不太对，理论到了最后打出GG。

chenjb

感觉这个G理论来理论去自爆了啊....其实很对的说，好像要用力压状态。

oipotato

subconscious

题解

• A：分类讨论，分为垂直，直接走到交点，镜像再镜像三种情况。
• B：f[i][j]代表最后一个落在i，一共用了j个有多少种方案，要求相邻两个不能同时有(fib进制的性质)，在dp数组上走。
• C：每个式子的m的最大值显然是a-b，gcd合并即可。
• D：注意到下雪是全局的，因此一个区间里最厚的显然是最晚被清0时刻最小值，用线段树维护，取出来后直接计算即可。
• E：跑出MST，对于非树边，答案是覆盖的树边最大值；对于树边，答案是覆盖的非树边最小值，用启发式合并和倍增维护。
• F：本质上判断sqrt(p)+sqrt(d)和sqrt(t)的关系，要全整数运算，平方再平方即可。
• G：yzc
• H：暴力枚举。
• I：考虑取最小割，转化成网格上dp，树状数组维护。
• J：two-pointer维护，显然一个区间都归成中位数最优。
• K：最大值是按+0-的优先级尝试，最小值是按-0+，从前往后能放就放贪心即可。
• L：sub
• M：cjb
• Codeforces
• Claris

附加文件

• 1.png by chenjb