Fork me on GitHub

普转提撒花

版权原因,题面不公开(但是我还是要说一句周队🐮🍺!)

完结撒花qwq….

嘴强王者

首先可以设一个$k=\frac{n}{m}$表示每一组的人数.
然后我们把所有队伍按照队长的能力值从小到大排序(即根据队长的排名从大到小排序).然后我们考虑能力值排名最大的队长怎么取.
发现显然只能去取排名比$a_i$靠后的,方案为 $\dbinom{n-a_i}{k-1}$
然后我们再去考虑能力值排名第二大的队伍,发现不仅只能去取排名比$a_i$靠后的,而且也不能去取已经被排名第一大的队伍取过的人,那么方案为$\dbinom{n-a_i-k}{k-1}$
同样的,以此类推,最后的答案就是$\prod\limits_{i=1}^n\dbinom{n-a_i-k \times (i - 1) }{k-1}$

数组

发现题目中有一个突破点就是只有$1$和$2$两种数字.
然后我们发现如下一个结论:我们找到某一个$1$,然后设它的位置为$i$,那么$[1,sum_n-sum_{i-1}]$范围内的数字都一定可以被取到.所以我们可以从左到右再从右到左分别找到第一个$1$,然后把可以到达的数标记起来.
然后我们再找到之前没有被$1$之后的数字标记过的$2$的数量$num$,那么所有能到达的数的并集就是

又因为权值很小,所以我们可以预处理之后直接$O(1)$统计答案.

曼哈顿抉择

我们发现对于每次操作,我们可以把这张图分为三个部分:一部分距离第一个点更近,一部分距离第二个点更近,还有一部分离两个点距离相等.
那么所有的情况大概可以归为以下两种情况:

  • 对角线通过这两个点:
    sat1

  • 对角线不通过这两个点:
    sat2

对于这两种情况,我们在计算的时候可以做如下划分(类似下图):划分成两个大三角形,然后角落里有四个小三角形(也有可能是梯形,但是莫得区别),然后我们求出这些部分中的点的个数就能通过一些找规律的加加减减算出答案.
divi1

首先考虑对大三角形中点的数量的计算,发现其实就是划一条$x-y=c$($c$为常数)的直线,然后统计$x-y>c$和$x-y<c$的点的数量即可.显然可以对每个点根据$x-y$进行排序然后二分即可.
然后我们来考虑下对于小三角形(或者梯形)中点的计算方法,我们发现我们可以写出两个类似于$y=k \times x + b$的约束,然后就是一个经典的二维偏序的问题,可以一维排序+二维树状数组解决.但是需要注意要把询问离线出来.
时间复杂度为$O((n+m) \times logn )$

开关灯

首先发现如果对于某条路径翻转了两次之后还不如不反转(确信).
那么就会有一个结论:对于某种翻转路径的方案,一定存在某种确定的翻转方案,使得翻转的路径不相交.根据这个结论,我们可以只翻转需要翻转的边,而对于现在状态和需要状态相同的边可以忽略不记.
那么我们的任务就变成了用最少的不相交的路径去覆盖所有需要翻转的边.然后对于某个点,我们发现如果从它出发(不包括到父亲节点)的边中有偶数条需要被翻转,那么显然这两条边可以通过一条路径连接,如果有奇数条边需要被翻转的话,那么就是要标记一下这个点(因为一条路径中最少需要两个端点),然后在它的父亲枚举到它的时候把这个点向它父亲连接的边当成需要翻转的边(因为无所谓亮暗的边翻转还是不反转都无所谓).这样递归的进行下去,直到到达深度最小的节点.这时候需要特判每次$dfs$时的根节点是否只连接了需要继续向上连边的路径,如果有的话,需要把这条路径向下拆分(因为可以证明最少有$3$个不同深度的节点才会出现需要向上继续连边的节点)成两条,这时候就要多用一条路径

因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:普转提撒花

文章作者:KRrrrrrrrr

发布时间:2019年11月03日 - 16:11

最后更新:2019年11月05日 - 09:11

原始链接:http://krrrr.xyz/2019/11/03/普转提撒花/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。