是不是可以叫CSP-S模拟了
Day1
出题人：liu_runda
我要死了。
NOI Plus?
NOI Professional?
Not Ordinary and Interesting Programmers?
××这有点可笑啊。
预审题：
T1
高精度题？
T2
又是序列题，只想到暴力
T3
概率题，可能是dp
达哥也喜欢校内的猫猫么……
话说，为啥不用火腿肠？
（猫真的吃干脆面？）
最后，这和公西华有啥关系？
做题：
T1
高精度魔法
我还真……
我以前想过，但是没写。
就是辗转相除的$gcd$
复杂度是$Theta(log Nk)$的.
$100<k<500$
大概1e5的样子。
$log 10^{100} = 100 log 10$
T2
又红又专系列
先暴力。
我们也许可以分开计算每个数个合法区间，
然后求交。
这个数据范围明显是$Theta(N)$的
$Theta(N log N)$也不失为一种好办法
T3
像个背包。
设gyz在第k只猫处，总计用了i包香爆脆干脆面，j包劲仔豆干的最大期望：$dp_{k,i,j}$
首先k是可以滚起来的。
然后在每只猫处将其捕获的概率就是1-无法捕获的概率。
$$dp_{k,i,j}+=dp_{k-1,i+a,j+b}+1-prod(1-qi) imes prod(1-pi)$$
可以做一下小点（复杂度惊人$Theta(N^5)$）。
不过可以写个快速幂（$N^4logN$）
4 1 3 0.100 0.500 0.500 0.600 0.100 0.500 0.900 0.400 3 2 2 1.000 0.000 0.500 0.000 1.000 0.500 3 2 0 0.412 0.198 0.599 0.612 0.987 0.443
仿佛正确但是过不了样例（没状态）
样例1的想法：
我不给第一只猫
然后给第二只猫 一包劲仔 +0.5
然后给第三只猫 一包劲仔 +0.9
最后把剩下的给第四只 +1-0.6×0.4=0.76
最后我就有了 2.16只猫猫
我的暴力程序的想法：
我不给第一只猫
然后给第二只猫 两包劲仔 +1-0.5×0.5=0.75
然后给第三只猫 一包劲仔 +0.9
最后把剩下的给第四只 +0.6
最后我就有了 2.25只猫猫（嘿，我多0.09只猫
我迷茫了，我感觉我也没审错题啊QAQ
等会……猫喜欢一包劲仔和两包劲仔好像是一样的……
我×，我竟然改过来了
Day2
出题人：ρ
话说我真不知道这是谁……
看起来很难的样子
话说内个“----------1/4”是说出题人是1/4,还是这是四套题中的一个？
困（没睡醒）
预审题：
T1
这……感觉有柿子。
1s
T2
这开××O2有××用？
2s
T3
令人坐藕的数学题？
0.5s，我×￥#￥%×%×%……
看完三题，觉得作者好有心（●﹏●）
感觉每个题都有许多部分分，但是可能想不到正解。
做题过程：
T1
先打表$Theta(N*M)$
感觉像个二项式。
$$egin{array}{rcl}f_{i,j}&=&a imes f_{i-1,j}+b imes f_{i,j-1} \ f_{i,j}&=&a^2*f_{i-2,j}+2ab imes f_{i-1,j-1}+b^2 imes f_{i,j-2}end{array}$$
所以我们现在需要系数。
如果可以有$Theta(N)$左右的系数求解
那么就可以$Theta(N+M)$解决。
如果用杨辉三角还不如暴力。
求阶乘及逆元！
复杂度$Theta(N log Mod)$
解决了！
两个样例都过了
疯狂对拍，AAA (<请记住这句话)
T2
像是个dp
我们可以把所有权值下放到X点。
然后在X点上进行状压。
这里的问题在于开不出来一个$1 ll 100000 imes 100000$的数组
（滑稽
20%
或者，我们也许可以想一下贪心？？
用堆优化一下，让它反悔？
先撂下了
T3
这××是人说的话？？
不过ρ很善良,他认为这道题绝对不用随机化,不用打表,不用剪枝,不用高精,不用取模。
这样这道题就显得一点也不玄学了。
等下，好像本来也不用……但是还是很玄学
Result - 结果
|
5
|
Miemeng | 100
03:11:32
|
30
03:11:05
|
10
03:18:42
|
140
03:18:42
|
|
43
|
Miemeng | 60
03:17:43
|
0
03:18:59
|
0
03:26:01
|
60
03:26:01
|
| Total: | 200 | ||||
身败名裂。
我还要更加努力……
原因竟是：
我阶乘没求够……