回归高考后的这学期，我和同桌Circle Lin大大经过一些思维的碰撞和脑洞的大开，得到了很多灵感。再加上friendi老师曾经教导我应该多多帮助学弟，于是我就凑了一套省选模拟题，拿来给学弟们测(tu)试(cao)。
最后的结果呢……分数还是比较正常的，分布均匀。NKC(commomc)270分怒拿第一，太神辣！然而friendi老师让我准备奖品，差评。
【题目描述】
时如风逝，岁似骥驰。转眼间到了高三，Mia也早已离开了我们。但是摆脱了繁重的英语作业后，我们却突然想念起了那段抄课文的时光。英语大练习开始了，看，又一道超难的七选五阅读摆在了面前，面对着不明觉厉的文章，小宸毫无头绪，经过两秒钟的思想斗争，他决定弃疗，随机选择五个答案填进去。但是显然这样正确率是比较低的，小宸想知道，这样做有多少种可能正好蒙对了$k$道呢？
为了增加难度，假设这道阅读题有$n$个选项，$m$道小题$(n\geq m)$，要从$n$个选项里选出$m$个不同的选项按顺序填入$m$个空内。且正确答案只有一种。一道题的答案和正确答案一样才算对。你要做的是计算恰好对$k$道的方案数，结果对$1000000007$取模。
【输入格式】
一行三个整数，$n,m,k$。
【输出格式】
一行一个整数，方案数取模后的值。
【样例输入】
4 2 1
【样例输出】
4
【数据范围】
对于$30$%的数据，$1≤m≤n≤15$。
对于$60$%的数据，$1≤m≤n≤2000$。
对于$100$%的数据，$1≤m≤n≤2000000$。
【样例解释】
四个选项ABCD，假设答案是AB，那么有AC、AD、CB、DB四种。
这道题本来我和Circle Lin研究得很麻烦……但是变成了签到题，所有人全切掉了……就这水平也来出题？
题目大意：$m$道题$n$个选项，正确答案只有一种且选项都不同，求恰好做对$k$道的方案数。
首先在$m$道题里选出$k$道做对，$C_{m}^{k}$。则其余$m-k$道题就变成了一个全错的问题，也就是从$n-k$个选项里选$m-k$个全错，我们可以用容斥原理解决。
从$p$个选项中选$q$个全错$(p≥q)$的方案数怎么求呢？
$A_{p}^{q}×C_{q}^{0}-A_{p-1}^{q-1}×C_{q}^{1}+A_{p-2}^{q-2}×C_{q}^{2}……$
$A_{p-i}^{q-i}×C_{q}^{i}$就是从$q$道题中先选$i$个做对，然后剩下$q-i$道题用其余$p-i$个选项随便填的方案数，不太好描述，大家感受一下。
所以就是$\sum_{i=0}^{q}(A_{p-i}^{q-i}×C_{q}^{i}×(-1)^i)$ 。
因此本题的答案就是$C_{m}^{k}×\sum_{i=0}^{m-k}(A_{n-k-i}^{m-k-i}×C_{m-k}^{i}×(-1)^i)$。
|
|
【题目描述】
Ω国王拥有一支豪华的军队，由无数骁勇善战的骑士组成。这些骑士的军衔有$m$种，可以用数字$1$到$m$表示。现在国王要挑选$n$个骑士组成一支所向披靡的王者之师，排成一字长蛇阵。整个王者之师可以被分为若干个从左到右军衔依次递增或递减的小队，在这样的小队中，管理或下达命令的方向可以统一，因此越长的小队战斗力越强。比方说：一个长度为$7$的王者之师组成为$2,8,4,3,6,9,3$，它就可以看作是$(2,8)、(8,4,3)、(3,6,9)、(9,3)$四个小队组成，长度分别为$2,3,3,2$。此外，为了维持队伍的稳定，任何两个相邻位置的骑士军衔不能相同。
现在国王想知道，他随机挑选$n$个骑士组成这支王者之师，所有不同的王者之师中的所有小队长度平均值是多少？两支王者之师相同当且仅当所有位置的骑士军衔都相同。
【输入格式】
一行一个整数$n$和一个整数$m$，表示王者之师的骑士数。
【输出格式】
一个实数，表示所有$n$个骑士组成的王者之师小队所有长度平均值，保留五位小数。
【样例输入一】
2 10
【样例输出一】
2.00000
【样例输入二】
3 5
【样例输出二】
2.14286
【数据范围】
对于$30$%的数据，$2≤n≤10, 2≤m≤10$。
对于$50$%的数据，$2≤n≤1000, 2≤m≤15$。
对于$100$%的数据，$2≤n≤100000,2≤m≤15$。
这是今年百度之星初赛的最后一道题，当时有两个问，我把第一问去掉了，增加了一点难度，然而xuruifan和commonc还是毫不留情地A掉了！跪跪跪跪跪跪……
题目大意： $n$个数的序列，每个数为$1$到$m$，相邻两个数不能一样，求所有这样的序列中所有单调区间长度的平均值。
首先看到题很容易想到是一个DP。最终求的就是$\frac{长为n的序列单调区间总长}{长为n的序列单调区间总数}$。但是题中定义的单调区间是共用端点的，也就是说两个不同的单调区间端头是有重叠的，对于分子的计算非常不利。于是我们就想了， 如果没有重叠的话，岂不美哉？
因此，我们不妨更改一下定义方式，把每个单调区间最右边的端点去掉，这样单调区间彼此就没有重叠了。这样每个序列刨除右端点都会被单调区间完整覆盖。然后我们就很容易发现，最终要求的变成了$\frac{(n-1)×序列个数}{单调区间总数}$。
我们先解决这样一个问题： 长度为 n 的序列共有多少个？
$n=1$显然都满足，$1$到$m$一共$m$个。
$n=2$则是$m×m$再减去$(1,1),(2,2),……,(m,m)$这$m$个，共$m×(m-1)$个。
$n=3$呢？我们可以在$n=2$的序列后面添一个数，因为相邻两个数不能一样，每个两位数就会有$m-1$种添法。因此三位数有$m×(m-1)^2$个。
以此类推，$n≥2$时，长为$n$序列的个数就是长为$n-1$序列的个数乘以$(m-1)$。
我们再次变换所求式，变成$\frac{n-1}{\frac{单调区间总数}{序列个数}}+1$，也就是$\frac{n-1}{单调区间期望个数}+1$。因为变换了单调区间的定义方式，所以最后应该$+1$，把刨掉的右端点加回去。关键就是求这个分母。
考虑题中的限制，我们可以用$f[i][j][0]$和$f[i][j][1]$表示第$i$个数是$j$，目前的趋势是上升$(0)$/下降$(1)$的数个数与$i$位数个数的比值。用$num[i][j][0]$和$num[i][j][1]$表示第$i$位填的数是$j$，目前的趋势是上升$(0)$/下降$(1)$的所有数单调区间数之和与$i$位数个数的比值。 即$f$表示个数的期望，$num$表示单调区间数的期望。首先预处理出$i=2$的情况，如果上升，那么上一位就比$j$小，共有$j$个，于是$f[2][j][0]=\frac{j}{m×(m-1)}$；下降同理，上一位比 j 大， 共有$(m-1-j)$个，$f[2][j][1]=\frac{m-1-j}{m×(m-1)}$.这里每个数都为答案贡献了一个单调区间，因此$num[2][j][0]=f[2][j][0]$, $num[2][j][1]=f[2][j][1]$。
当$i≥3$时，我们可以从$i-1$位数的答案进行转移。由于上面已经得出了“$n$位数的个数就是$n-1$位数的个数乘以$(m-1)$”，因此从$i-1$转移到$i$时，每个数值都要除以$(m-1)$。 考虑$f[i][j][0]$和$f[i][j][1]$， 当上一位数为$last$的时候，有以下几种情况：
| 上一位递增 | 上一位递减 | |
|---|---|---|
| $j>last$ | 依然递增，区间数不变 $f[i][j][0]+=\frac{f[i-1][last][0]}{m-1}$ $num[i][j][0]+=\frac{num[i-1][last][0]}{m-1}$ |
变为递增，区间数加一 $f[i][j][0]+=\frac{f[i-1][last][1]}{m-1}$ $num[i][j][0]+=\frac{num[i-1][last][1]+f[i-1][last][1]}{m-1}$ |
| $j<last$ | 变为递减，区间数加一 $f[i][j][1]+=\frac{f[i-1][last][0]}{m-1}$ $num[i][j][1]+=\frac{num[i-1][last][0]+f[i-1][last][0]}{m-1}$ |
依然递减，区间数不变 $f[i][j][1]+=\frac{f[i-1][last][1]}{m-1}$ $num[i][j][1]+=\frac{num[i-1][last][1]}{m-1}$ |
最后的分母就是$\sum_{j=1}^{m}{(num[n][j][0]+num[n][j][1])}$。
|
|
【题目描述】
这星期，元首在和斯大林搞比利的时候学了一个游戏：毛子方块！感觉好棒好棒的。
这个游戏的界面是一个宽为$6$，长无限的棋盘。一开始棋盘里什么也没有，但是每个时刻都会从上空掉落一些图形，图形一共$7$种，各占$4$个格（如下图）。它们都可以任意旋转，如果恰好能用掉下来的这些图形拼成一个宽为$6$的矩形，就可以获得胜利。
一共会掉落$n$个图形（保证$n$一定是$3$的倍数，这样所有图形所占的方格数加起来可以被列数$6$整除），我们用一个只包含“L”、“J”、“I”、“O”、“T”、“S”、“Z”的长为$n$的字符串来表示先后掉落的图形。一个图形能放到某个位置的条件：①这个图形形状所占的每一个方格都没有被其他图形所占用；②放入后该图形底部不悬空；③被放入的位置四周没有被封死，即与上空通过空格相连。（你可以认为即使一条很小的缝隙，也可以供任何图形从中下落或移动，这点与真实游戏不同。）但是摆放的顺序一定是严格按照下落顺序，不能出现先下落的图形放在后下落的图形上面这种情况。如果安排合理，最终会恰好拼出一个$m×6$的矩形（$m=\frac{n×4}{6}$）。
然而大多数的情况，很难通过给定的图形获胜。现在想要知道的是，通过它们所能拼成的图形，与这个$m×6$的矩形最少差几个方格？（此矩形一定是整个棋盘最下面的$m$行。答案既代表这个$m×6$的矩形中的空方格数，也代表其上方多出来的方格数）
【输入格式】
一个字符串，由“L”、“J”、“I”、“O”、“T”、“S”、“Z”组成，长度为$n$。
【输出格式】
一行一个整数，代表最终的答案。
【样例输入一】
JLOIST
【样例输出一】
1
【样例输入二】
OTZLJS
【样例输出二】
1
【数据范围】
对于$100$%的数据，$3≤n≤15$。
听说标程400多行之后，小朋友们都吓跪了……于是各种骗分，输出0得30分，输出1得40分，输出2得20分，输出3得10分……本来样例特意设计的OTZLJS，结果LJS本人也直接跪掉了，最后commonc凭借此题超越xuruifan登顶！果然想虐场就得把骂出题人的时间用来写题啊。
题目大意：给你$n$个俄罗斯方块，他们按顺序掉落，你要把它们恰好拼成一个$m×6$的矩形。最后输出拼出的图形和这个矩形最少差几块。特别地，如果某个空位与上方空气不连通，那就不能把方块放进去。
这道题来自于Circle Lin大神的创意，标程也是他亲手写的。我也写了一个但是没他的跑得快，所以用了他的程序作为标程。
此题的真正瓶颈在于：考虑到出题人的水平。
因此直接爆搜即可。
方法：枚举每个图形旋转后各种放法的左下角的位置（注意左下角有可能是空气），由对称性，“ L”、“ J”和“ T” 各有四种放法，“ I”、“ S”和“ Z”有两种，“ O”则只有一种。判断每种放法是否合法， 首先判断有方块的几个格子是否被占用，然后判断下面一行是否不悬空， 最简单的是深搜，也可以尝试采用迭代加深搜素，或广度优先搜索，如果加上估价函数或者随机化效果更佳。
关于与上空连通这个问题，还有一个技巧可以尝试一下：一共不会超过$n×4=60$个块，所以用一个long long就能记录下所有格子和上空是否联通，然后每放一个块，考虑改变了哪些格子的连通状态，再进行转移。
这道题标程也比较虚，也不一定就能完美通过，我人为把数据降低了强度，这样只要暴力写得稍微好点就能得很高的分数。另外，如果你发现有很多情况答案都是$1$，得分就更加容易了。
代码过长就不贴了……