7.24日 集训第二天
不要问为什么第二天才写，这不重要。
上午模拟赛，先开T1
订正......
T1
先引入逆序对，如果有$1$在$0$前面， 就算一组逆序对。
对于这个题，很容易可以猜想出最后的结果$000....0011..11$。
回看题目中所给的条件，无论是$10$,$100$,$110$还是$1010$，他翻转过去一定能减少逆序对的个数，但是$10$翻转能减少$1$个，剩下的均能减少$2$个。于是，我们充分发挥人类智慧，大胆猜测一个结论：
当字符串中剩余的逆序对个数是$\ge2$的，这个字符串一定存在$100,110,1010$中的至少一个。
如何证明这个东西呢？
我们假设这个序列还没有变成前面全是$0$，后面全是$1$的状态，那么就是这样：$0...0110..0111$，显而易见，一定会存在$110$这个东西，所以$1$和$1$不能挨在一起那么就是这样:$0...0101001..0111$，但是这样又出现了$100$,所以$0$和$0$也不能挨着，就变成了这样:
$0...0101010....01111$,那么这样又出现了$1010$，所以结论成立。
所以原问题就转化成了求原序列的逆序对个数，然后进行一个博弈，就是执行两个操作，一个是把逆序对个数$-2$,一个是$-1$,看谁先删完。
这就很简单了，我们知道“必胜点”这个东西，所以当逆序对个数是$3$的倍数时，那么后手必胜，否则先手必胜。
T2
先对这个问题进行一个分解，显而易见，我们运用一个贪心的思路：对于一组零件，我们肯定是拿的越多，分的这个组越长越好对吧！
那么根据合格值的定义，要快速求出合格值，首先想到的办法肯定是爆搜贪心。
结论：将 S排序，每次取到 S中的最大值和最小值让他们相乘，最后计算出来的结果即为 S的零件值，再跟$K$进行比较即可。
接下来讲讲做法:
$90pts： O(nlog^2n)$ 的倍增算法
首先我们命名一个起点为$start$变量，倍增长度为$len$变量，终点为$ed$变量，接下来只需要将题目的解决分为多个操作：
我们先命名一个起始点$start$和目前的长度$len$还有一个终点$ed$。
接着我们检查$[start,ed+len)$这个区间是否合法，如果合法，将$ed$加上$len$,然后$len$乘上$2$。否则将倍增距离缩短，也就是将$len$变化为$len/2$,继续检查区间，这里要注意一下的是，当$len/2$是等于$0$的，我们就要结束这个循环，跳出就好了。
标签：...,ssy,ed,个数,len,110,暑假,集训,逆序 From： https://www.cnblogs.com/grz0306/p/18321204