前情提要
这个菜鸡CF上了 \(\color{darkcyan}Specialist\)，心情大好，正好赶上放假，决定打一场CF。
赛时记录
A
上来脑子抽了，吃了一发罚时。发现写错了一种情况，改过来就过了。
感觉并不是一个好的开始。
B
竟成为本人唯一一遍过的题，虽然写的时候有点慌。
C
DP。一开始认为空间不够，但发现可以用滚动数组。遂开写。
写挂了。debug一番后认为是清除先前数据的锅，于是写了一个自认为好用的方法，交上去吃了一发罚时。
认为是没有memset的锅，于是写了memset，交上去吃了一发罚时。因为TLE了。
于是删掉memeset，把填表改成刷表，交上去AC了。此时时间01:21:32。
D
看了一下，决定去掉不变的部分并对变化的部分进行处理，然后当成合并果子做。
期间对着 \(|x-y|\le 1\) 这个条件产生了一些想法，但是与我当时的做法无关。
交上去，吃了两发罚时。此时时间为02:06:38。
感觉不对劲，自己搓了个样例一测发现不对，紧接着发现自己假得很彻底。
有点慌。
忽然想起来之前的想法，觉得可写，于是开写。
新的做法写起来比合并果子屎山好写多了。交上去过了。
后记
要是能少吃几发罚时就好了
没掉rating。
A
容易看出，每加入一个数，最终 \(s\) 都会是奇数。
如果有偶数那么答案为奇数的个数 \(+1\)，否则为奇数的个数 \(-1\)。
赛时多讨论了一种情况。
B
排序，找到一对相等的边，删除。这对边是腰。
找到一对差小于二倍腰长的边，这对边是底。
赛时想的是找最长的一对相等的边，但是如果有两对及以上相等的边，那么一定可以组成梯形。而如果只有一对，那么只能选它。
C
赛时甚至写了滚动数组，然而并没有建liar数量那维的必要。因为一个人左边的liar数量由它左侧两人的左边的liar数量控制。
如果一个人 \(i\) 是liar，那么他左边的人 \(i-1\) 一定是诚实的人，所以他左边的人左边一定有 \(a[i-1]\) 个liar，也就是说到他这里就有 \(a[i-1]+1\) 个liar。
如果 \(i\) 是诚实的人，那么他左边一定有 \(a[i]\) 个liar。
因此，令 \(dp[i]\) 表示 \(i\) 是诚实的人的方案数。
需要考虑两种情况：
如果 \(i-1\) 是诚实的人，那么应当满足 \(a[i]=a[i-1]\)，此时将 \(dp[i-1]\) 加入答案。
如果 \(i-1\) 是liar，那么\(i-2\)一定是诚实的人，因此应当满足 \(a[i]==a[i-2]+1\)，此时将 \(dp[i-2]\) 加入答案。
最终的答案即为 \(dp[n]+dp[n-1]\)，即 \(n\) 为诚实的人和 \(n\) 为liar这两种情况。
D
一开始以为像合并果子一样，优先把小的数合并，然而这样做没有考虑到，一个数可以先与比自己大\(1\)的数合并而不与跟自己相等的数合并。于是它假了。
由于 \(|x-y|\le 1\)，对于一个由 \(a\) 中数字合并而成的数，它的拆分方案是唯一的。
即：\(x=\lfloor\frac{x+1}{2}\rfloor+\lceil\frac{x+1}{2}\rceil\)。
因此，我们递归处理 \(b\) 中的每一个数 \(b[i]\)。
如果 \(b[i]\) 在 \(a\) 中出现，那么是可以得到的；
如果 \(b[i]\) 在 \(a\) 中没有出现，那么把它拆分成 \(\lfloor\frac{b[i]+1}{2}\rfloor\) 和 \(\lceil\frac{b[i]+1}{2}\rceil\) 两部分，对每一部分进行如上判断。
如果一个数的两部分都是可以得到的，那么这个数也是可以得到的；
如果一个数的两部分至少有一部分不可以得到，那么这个数是不可以得到的。这是显然的。
注意判边界条件 \(x=1\) 。此时如果没有出现则不能继续拆分。
\[\huge End \] 标签：那么,liar,交上去,999,Codeforces,诚实,罚时,Round,dp From： https://www.cnblogs.com/neat-isaac/p/18682752/cf2061