PKUSC都是神仙题，蒟蒻我根本做不来。
传送门
真实排名
题解
这道题目还是比较简单的，就是有几个坑。
对于第$i$个人，有两种情况：他的成绩没有翻倍或者他的成绩翻倍了。
没有翻倍：
那么分数在区间$[\lceil \frac{A_i}{2}\rceil,A_i-1]$内的人的分数不能翻倍，设除$i$外有$x$个人的分数不在这个区间内，那么此时的方案数为$\tbinom{x}{k}$。
翻倍了：
那么分数在区间$[A_i,2\cdot A_i-1]$内的人的分数必须翻倍，设有$x$个人的分数在这个区间内，那么此时的方案数为$\tbinom{n-x}{k-x}$。
还有一种特殊情况需要处理：$A_i=0$，此时的方案数为$\tbinom{n}{k}$。
代码
1 |
|
最大前缀和
题解
看到这个数据范围，状压DP肯定是跑不掉了。
一个数列可能有多个最大前缀和，方便起见，我们只关心包含元素个数最大的一个。
设$\sum{i=1}^{j}{a_i}$为最大前缀和，且$j$为所有最大的前缀和中最大的，那么就有$\forall k\in[j+1,n],\sum{i=j+1}^{k}{a_i}<0$。
令$U$为由原序列中所有元素组成的集合，$S$为$U$的一个子集，$F[S]$表示由$S$中所有元素构成的排列中，最大前缀和包含了$S$中所有元素的排列的数量，$G[S]$表示任意一个前缀和都严格小于$0$的排列的数量，$Sum[S]$表示由$S$中所有元素的加和。
如果已经求出了$F$和$G$，那么不难得到答案：
考虑如何求$F$和$G$，假设已经求得了$F[S]$和$G[S]$，考虑如何转移。
枚举$i\notin S$，然后把$i$放到$S$的排列的最前面，如果如果此时$Sum[S]\geq 0$，那么就有转移：
考虑把$i$放在最后面，如果有$a_i+Sum[S]<0$，那么就有转移：
由于一个前缀和至少包含一个元素，所以就有初始值$F[S]=[|S|==1]$。
由于当一个前缀和包含了所有元素之后，最大前缀和之后就没有元素了，所以就有初始值$G[0]=1$。
然后这题就解完了，时间复杂度$O(n\cdot 2^n)$。
代码
1 |
|
主斗地
题解
大模拟。
仔细阅读题目中的规则，不难发现，在这题中很多打法是无用的，顺子、对子、双顺、三张、三顺全都可以拆成单牌来打；飞机带翅膀拆成三带一和三带二打，并且还少了要求数码不同的限制。这样我们需要考虑的出牌方式就只有三带一、三带二、四带二和打单牌了，这对一道大模拟来说真是莫大的好消息。
并且良心出题人把3去掉了，因此吉老师的牌的可能的种类就大大减少了，大概是$10^6$级别。
所以可以暴枚吉老师的牌，然后再考虑，对于一副吉老师的牌，是否存在合法的打法。
可以一开始先确定三带一加上三带二的数量和四带二的数量，最后再枚举三带一的数量以及考虑怎么带（因为对于一个玩家来说，我们只关心三带一的数量和三带二的数量，而并不关心具体是哪些三张牌带了一张，哪些三张牌带了两张）。
对于吉老师，肯定是尽量带大的散牌，对于XX网友，肯定是尽量带小的牌。并且需要先确定带哪些对子，再确定带哪些单牌。
具体实现参加代码。
代码
1 |
|
星际穿越
题解
先考虑这个图有什么性质，以及最短路径有什么特点。
不难发现，肯定存在一条最短路径，向右跳了最多一次，而且是在起点向右跳。
令$tl[i]=\min_{j=i}^{n}l[j]$，如果$i$不是起点，那么区间$[tl[i],i-1]$中的所有点均可以看作可以由点$i$一次穿越到达（实际上可能并未经过点$i$，但是穿越次数和看为从$i$一次穿越到达一样），这样转化之后，每次都向左穿越到此意义下最靠左的位置肯定可以得到一条最短路径（起点除外）。
考虑倍增，设$F[i][j]$表示从$i$开始向左穿越$2^j$次能到达的最靠左的位置，$G[i][j]$表示从$i$出发到区间$[F[i][j],i]$中所有位置的最短路径长度和。
对于$F[i][j]$和$G[i][j]$，有：
然后对于每一个询问，差分一下然后倍增即可求解出答案。倍增的时候每次跳跃记得预先加上前面那部分的贡献。注意起点特殊处理。
代码
1 |
|
神仙的游戏
题解
神仙的游戏蒟蒻我是根本玩不来。
首先需要考虑一下这个题目有什么性质：
自己画几个图之后不难发现，对于一个长度为$len$的前缀，如果他是一个border，那么这个$n-len$必定为这个字符串循环节的长度，并且反过来也成立。
因为?可以随便取，这里就不管它了。我们只需要考虑哪些情况下的，长度为len的前缀不是border。
对于一个$0$，设它的下标为$i$，对于一个$1$，设它的下标为$j$，那么就有：
长度为$len$的前缀不是一个border（中间的竖线表示整除）。
考虑构造两个多项式：
然后用FFT或者NTT将两个多项式卷乘起来，设卷积的结果为$H()$。
此时如果存在一对01，且它们的下标之差为$i$，那么就等价于$[x^{n+1-i}]H(x)+[x^{n+1+i}]H(x)>0$。
此时就可以判断一个长度为$len$是否是一个border了。
然后这题就解决了，复杂度$O(n\log n)$。
1 |
|
PKUSC
题解
计算几何，好讨厌啊。
虽然题面里保证了精度不会卡得很严，比较友好，但是作为一道计算几何，精度问题还是很讨厌的，特别是对于我这种蒟蒻。
由于期望具有线性性，所以可以分开计算每个敌人的贡献，最后再累加起来。
一个敌人的贡献等于多边形匀速转过一圈时，敌人在多边形内的时间与总时间的比值。
考虑如何判断一个点是否在一个可能是凹多边形的多边形内部，我这里用的是引射线法：从需要判断的点引出一条射线，计算这条射线与多边形的边的相交次数。如果相交了奇数次，那么就在多边形内部；如果相交了偶数次，那么就在多边形外部。
然后对于每一个点，计算出它与多边形的每一条边是否可能相交，以及相交时转过的角度。注意在本题中，转多边形和转点本质上是一样的，计算交点的话解一个一元二次方程即可。我们称转过的角度$\alpha$为关键角度当前仅当在转过$\alpha$之后，该点与多边形的某一条边相交。
预处理出所有关键角度并排序之后（注意去重），不难发现当转过角度在某两个相邻的关键角度之间时，该点在多边形的内外情况相同。
所以对于每一个点，我们需要计算出他的所有关键角度，并确定旋转角度在某一个区间内时该点是在多边形内部还是外部，然后累加计算答案。时间复杂度为$O(nm^2)$。
代码
注意由于本蒟蒻很菜，并不怎么会处理计算几何里的精度问题，所以下面的代码仅保证基本思路正确且能通过洛谷、BZOJ以及LOJ的测试数据，但是不保证不存在数据能通过精度问题把代码卡掉。
1 |
|