2017-Sp267-team2

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==
出门读了B，yzc飞速上机'''B1y15'''，cjb上机写H，'''H2y43'''。之后下机cjb发现大家不是很会做G，就口胡了一波，yzc上机wa了三发。sub上机写J，'''J1y80'''。之后发现了G的corner case，'''G4y86'''。yzc和sub理论A，得到了SAM做法后'''A3y127'''。之后sub上机写C，'''C1y149'''。cjb会了D，丢给yzc。然后先写了个'''E3y221'''。之后yzc写D，wa了几发后，拍出错，发现是误解了cjb的做法，改完变tle，查了半天发现swap了数组。之后sub rush D，赛后获得通过。
=== chenjb ===
今天出门卡G有点不应该。之后我给yzc丢D做法的时候也出现了失误，然后就是yzc的那个swap两个数组(O(n))的血淋淋的事故，不然这个F时间应该是够的。I好像真的高中做过啊，很神秘。
=== oipotato ===

=== subconscious  ===

== 题解 == 

 * A：满足题意的串等价于合法括号序列。判断括号序列的条件为前缀和相等，区间最小值等于前缀和，这件事情在右端点确定的时候是可以二分的。所以枚举SAM上每个点，二分出长度范围内的最长合法串即可。

 * B：枚举左右shift的中点，预处理一些前后缀求最优。

 * C：枚举和为10的数对，注意0可以有额外偶数个，f[5][1000]dp。

 * D：枚举一堆9之后第一个匹配位置，分为不进位(<=8)和进位(>=10)考虑，注意先特判全为9的情况。枚举之后，前面尽可能构造9，之后如果进位则构造最小，反之构造最大。

 * E：exgcd，答案是2*(|x|+|y|-1)，注意特判x或y=0。

 * F：手指型构造，预处理40*40内的向量，注意mod 3的三种情况，特判小点。

 * G：考虑如果跨值，则所有该值都会取掉，实际上规约为一个特殊的最大子段和，注意特判如果只有两种权值，可能凑出两块皆不完整的最优解。

 * H：二分答案后贪心判定。

 * I：将(i,a[i])和(i,b[i])分别构出下凸壳，然后双指针贪心在上面走，每次选择较缓的一段走一步即可。可以证明最优方案的斜率不减，且一定在凸壳上走。

 * J：答案是q|(p-1),q|N的方案数，直接暴力枚举。

流水账

出门读了B，yzc飞速上机B1y15，cjb上机写H，H2y43。之后下机cjb发现大家不是很会做G，就口胡了一波，yzc上机wa了三发。sub上机写J，J1y80。之后发现了G的corner case，G4y86。yzc和sub理论A，得到了SAM做法后A3y127。之后sub上机写C，C1y149。cjb会了D，丢给yzc。然后先写了个E3y221。之后yzc写D，wa了几发后，拍出错，发现是误解了cjb的做法，改完变tle，查了半天发现swap了数组。之后sub rush D，赛后获得通过。

chenjb

今天出门卡G有点不应该。之后我给yzc丢D做法的时候也出现了失误，然后就是yzc的那个swap两个数组(O(n))的血淋淋的事故，不然这个F时间应该是够的。I好像真的高中做过啊，很神秘。

oipotato

subconscious

题解

  • A：满足题意的串等价于合法括号序列。判断括号序列的条件为前缀和相等，区间最小值等于前缀和，这件事情在右端点确定的时候是可以二分的。所以枚举SAM上每个点，二分出长度范围内的最长合法串即可。
  • B：枚举左右shift的中点，预处理一些前后缀求最优。
  • C：枚举和为10的数对，注意0可以有额外偶数个，f[5][1000]dp。
  • D：枚举一堆9之后第一个匹配位置，分为不进位(<=8)和进位(>=10)考虑，注意先特判全为9的情况。枚举之后，前面尽可能构造9，之后如果进位则构造最小，反之构造最大。
  • E：exgcd，答案是2*(|x|+|y|-1)，注意特判x或y=0。
  • F：手指型构造，预处理40*40内的向量，注意mod 3的三种情况，特判小点。
  • G：考虑如果跨值，则所有该值都会取掉，实际上规约为一个特殊的最大子段和，注意特判如果只有两种权值，可能凑出两块皆不完整的最优解。
  • H：二分答案后贪心判定。
  • I：将(i,a[i])和(i,b[i])分别构出下凸壳，然后双指针贪心在上面走，每次选择较缓的一段走一步即可。可以证明最优方案的斜率不减，且一定在凸壳上走。
  • J：答案是q|(p-1),q|N的方案数，直接暴力枚举。
附加文件