Summary5
$BH\sim BN$
BH clay17与帝垣琼玉
时间限制：1000ms 内存限制：65536kb
通过率：52/72 (72.22%) 正确率：52/121 (42.98%)
题目描述
clay17闲来无事和青雀一起摸鱼。
桌面上现有A张“摸鱼牌”和B张“普通牌”， 随机打乱顺序后放在桌面上，开始一张一张地翻牌。
翻到摸鱼牌，青雀可以安全的摸鱼，快乐指数$+1$；
翻到普通牌，青雀则会担心这是符玄要来抓自己的不好兆头，快乐指数$−1$。
青雀最初快乐指数为$0$，并且在翻牌过程中可以随时停止翻牌，青雀在最优策略下平均快乐指数$S$是多少。
输入
两个数字$A$，$B$（$A,B≤1000$）
输出
输出一行，表示$S$的值，保留两位小数
输入样例
1 | |
输出样例
1 | |
THINK
开始直接想错了，他这个最优策略指的是按照当前手中的排来决策是否取下一张牌——果然是个赌徒，没输个精光就不肯罢休。
然后有意思的是这个决策过程就可以写成二维的动态规划，一个状态$DP[i][j]$由上两个状态$DP[i-1][j]和DP[i][j-1]$概率决定
BI Sayrafiezadeh 1994
时间限制：100ms 内存限制：65536kb
通过率：350/523 (66.92%) 正确率：350/2455 (14.26%)
描述
如果一年有 $365365365365365365365365$ 天，那么 $365365365365$ 人的生日互不相同的概率是多少？
输入
1 | |
输出
将答案保留 6 位小数输出。
提示
因为输入是固定的，所以你可以自己算出答案后再让提交的程序直接输出你已经算出的答案。
为什么本题是这个名字呢？真的好奇怪哦！
THINK
生日问题，还有其他的一些随机事件，和一些概率分布律是密切相关的。这里搜索题目可知一个生日问题的近似公式手算或者计算机都可以Python处理这种问题就比较方便了
BJ Bubble-sort 2024
时间限制：100ms 内存限制：65536kb
通过率：254/306 (83.01%) 正确率：254/548 (46.35%)
描述
$365365365365365365365365$ 个不同元素在冒泡排序倒数第 $365365365365$ 轮开始时已经有序的概率是多少？
输入
1 | |
输出
将答案保留 $6$ 位小数输出。
提示
因为输入是固定的，所以你可以自己算出答案后再让提交的程序直接输出你已经算出的答案。
为什么本题是这个名字呢？真的好奇怪哦！
说明
不同教材中冒泡排序的定义不完全相同，而在本题中我们认为 $n$ 个元素的冒泡排序共 $n$ 轮。
对于 $3$ 个不同元素的冒泡排序，注意到：
- $(1,2,3)$ 在倒数第 $3$ 轮冒泡排序开始时已经有序。
- $(1,2,3)$ 和 $(1,3,2),(2,1,3),(3,1,2)$ 在冒泡排序倒数第 2 轮开始时已经有序。
- $(1,2,3)$ 和 $(1,3,2),(2,1,3),(3,1,2)$及 $(2,3,1),(3,2,1)$ 在冒泡排序倒数第 11 轮开始时已经有序。
从而 $3$ 个不同元素在冒泡排序倒数第 $x$ 轮开始时已经有序的概率大约是 $\exp(\frac{3x^2-3x}{4x-22})$。
| 倒数第 $3$ 轮开始时 | 倒数第 22 轮开始时 | 倒数第 11 轮开始时 |
|---|---|---|
| $(1,2,3)$ | $(1,2,3)$ | $(1,2,3)$ |
| $(1,3,2)$ | $(1,2,3)$ | $(1,2,3)$ |
| $(2,1,3)$ | $(1,2,3)$ | $(1,2,3)$ |
| $(2,3,1)$ | $(2,1,3)$ | $(1,2,3)$ |
| $(3,1,2)$ | $(1,2,3)$ | $(1,2,3)$ |
| $(3,2,1)$ | $(2,1,3)$ | $(1,2,3)$ |
THINK
其实下面公式都给出来了，上网搜一下也可以找到这个瑞利分布公式
BK clay17与milkteam
时间限制：1000ms 内存限制：65536kb
通过率：15/35 (42.86%) 正确率：15/127 (11.81%)
题目描述
clay17为了喝到新鲜的奶茶，决定建造养牛场。由于她对奶茶的高要求，她决定引入一种新品种牛，由于预算优先，她最多只能引入$n$头新品种奶牛。
好消息是，这种新品种奶牛可以根据与其他奶牛的位置关系进行快速繁殖。具体来说，若在养牛场的格子A处(坐标为$(x,y)$)，以国际象棋中马的走法能走到的8个格子中，只要有至少4头奶牛，那么A处会在下一秒立即生成一头奶牛。
经过$$10^{100}$$秒后，奶牛数目将保持不变，即此时若继续有合法的格子，奶牛也不会生成。
现在，请聪明的你帮帮clay17，编排这$n$头奶牛的位置，使最后场上的奶牛尽可能多。
clay17也没有特别高的期待，你只需要使最后场上的奶牛数目至少为$⌊\frac{n^2}{10}⌋$，便可以通过测试。
输入
一个数$n$，保证$n≤1000$
输出
输出$n$行，每行2个数，第$i$行的两个数，表示最开始第$i$个奶牛的坐标$(x_i,y_i)$
请你保证你的输出满足不会有两头奶牛出现在同一位置，且$−10^8≤x_i,y_i≤10^8$，且输出均为整数。(奶牛多于$n$头时,clay17只会保留前$n$头)
输入样例
1 | |
输出样例
1 | |
THINK
难点在于理解题目，然后就是对各种摆法计算可能的值
- 长条状，必须是两排(两侧都可以)，这样才能最大化复用已有的元素，$l=n/2,h=n/2/4,sum=n+2*(l*h)/2=n+n^2/16$,上限有些差
- 然后是十字形（回想高中生物“五点采样法”这是有统计学原理的），4个凹槽可以复用，理论值$l=n/4,a=l/\sqrt(2),h=a/4,S=l^2/2+l^2/4=3n^2/64$
- $L$形，$l=n/2/2,a=\sqrt 2l,h=a/4,S=n^2/16+n^2/64+2l*l/4/2=9n^2/64$
大于要求的界限，OK
但是下一题需要$[\frac{n^2}{7}]$这就太接近下限了，可能需要精确计算每个点的摆放位置（时间远大于，不需要考虑）
BL milkteam与clay17
时间限制：1000ms 内存限制：65536kb
通过率：5/19 (26.32%) 正确率：5/41 (12.20%)
题目描述
其它相同，除了
clay17也没有特别高的期待，你只需要使最后场上的奶牛数目至少为$⌊\frac{n^2}{7}⌋$，便可以通过测试。
BM Find password
时间限制：1000ms 内存限制：65536kb
通过率：4/17 (23.53%) 正确率：4/45 (8.89%)
题目背景
Koishi擅自给懒鱼的家门口上了一道锁，现在懒鱼没法回家了。为了回家，懒鱼需要想办法解开这把锁。
题目描述
具体来说，这把锁上有一列有 $n$ （$1≤n≤10^3$）个滑块，最初处于解锁状态时，第 $i$ 个位置上的滑块标有数字 $i$。Koishi随意打乱了这些滑块之后，锁定了这把锁。此时，第 $i$ 个位置上的滑块标有的数字变成了 $a_i$，此时所有 $a_i$ 恰好组成一个 $1\sim n$ 的排列。
锁定这把锁之后，你每次可以选择两个位置上的滑块，记其所在位置为 $l,r$（$l<r$），并将其交换，但需要满足两个奇怪的性质：
- 至少存在一个被选定的位置 $pos$ 满足，在最初这把锁锁定的时候，该位置上的滑块标有的数字为 $pos$。
- 在之前的所有操作中，未对位置为 $l,r$ 的滑块进行交换。
当对于所有 $i∈[1,n]$，第 $i$ 个位置上滑块上标有数字 $i$ 时，锁就再次恢复解锁状态，懒鱼就可以回家了。
然而，由规则可知，这把锁的解锁没有什么试错机会，因此懒鱼希望你能够写一个程序，直接输出正确的操作过程。
当然，也许实际上这把锁根本没法解锁，此时请你也务必告知懒鱼。
输入
第一行一个正整数 $n$（$1≤n≤10^3$），表示滑块个数。
第二行一行 $n$ 个正整数，第 $i$ 个正整数 $a_i$（$1≤a_i≤n$）表示从左到右第 $i$ 个滑块上标有的数字。保证所有的 $a_i$ 恰好组成一个 $1 \sim n$ 的排列。
输出
若这把锁无法解锁，输出一行一个整数 $−1$。
否则，第一行输出一个自然数 $k\ (0≤k≤2×10^4)$，表示你接下来会执行的操作个数。可以证明，若这把锁可以解锁，则$ 2×10^4$ 步以内必定能解锁。
接下来 $k$ 行，每行两个正整数 $l,r$（$1≤l<r≤n$），表示选择交换的两个滑块。
输入样例
1 | |
输出样例
1 | |
提示
- 如果一开始满足条件1的位置太少了，那么一定无法还原。但是，实际上你也不需要用到很多位置。
- 在样例里，初始状态时，位置2上的数是5，位置5上的数是3，位置3上的数是2。
Author：一只懒懒懒懒懒鱼
THINK
无
BN J 博弈 (game)
时间限制：1000ms 内存限制：65536kb
通过率：15/42 (35.71%) 正确率：15/117 (12.82%)
题目描述
WIKI 和 NonFriedChips 在玩游戏，一开始序列中有 $n$ 个 1 ( $n$ 为偶数)，
每一轮游戏，wiki 先从序列中取出两个数字 $x,y$ ，然后删掉他们，之后NonFriedChips 要从 $x+y$ 和$|x−y|$ 中选一个添加到序列中。
当序列中存在有某数大于其他数字之和或者所有数都是 0 时结束游戏。
结束后序列中每有一个数字 NonFriedChips 就要给 WIKI 一块薯片，WIKI 希望自己拿到的薯片尽可能多， NonFriedChips 希望自己给的薯片尽可能小，两人都采用最优策略的情况下 WIKI 最多能拿到多少薯片？
输入格式
第一行一个 $t$ 表示游戏轮数
后面 $t$ 行整数 $n$ 表示每轮游戏开始时 1 的个数
输出
$t$ 行整数表示两人在最优策略下 WIKI 最多拿到的薯片
输入样例
1 | |
输出样例
1 | |
数据范围
$1≤t≤10^4$
$1≤n≤10^{18}$
THINK
本题名字就是提示，这是一类博弈游戏
但这里的关键点是删两个，添一个，每一轮如果是奇数则不能完全匹配，导致会余下一个数
样例给的少，自己构建几个就会发现两个对局者的最优策略是：
-