1.璀璨光华
首先固定一号点标 0,那么与一号点相邻的标 2^i,对于一个标号x,如果已经确定了 x-2^a,x-2^b,那么这个点可以被唯一确定。
接下来就相当与这些位可以随便调换,每个位关于这 2^n 个数字是个 01序列,然后排个序即可。
2.电音之王
黑科技 wiki Montgomery modular multiplication/ 现在在 32 位机上跑不过暴力,所以用 long double 试除就能过。
3.萌新拆塔
状压 dp+简单计算。注意有模仿怪所以不要无脑吃宝石即可。
4.奇迹暖婊
对偶费用流,努力卡了很久之比 LP 快了一点点,只好卡内存了。
5.风花雪月
任意不满足的状态对答案的贡献为 1,所以只需要求出每个不够的状态的概率最后加上 1。
我们认为我们总共需要 4*sum c 件衣服,每次抽如果没到达 c,那么贡献为 4,否则贡献为 1。
dp[i][j][k]表示前 i件衣服,抽了 j 件,总贡献为 k 的概率和。
6.双倍掉率
max C(n,a) C(m,b) p^a (1-p)^(n-a) (2p)^b (1-2p)^(m-b) 取对数求导之后解个二次方程或者二分即可。
7.贵族用户
枚举哪一档,然后算一下钱够不够,不够接着氪钱。
8.我不爱她
一个前缀/后缀代价为本身长度-border 长度,hash+kmp 即可。
9.人渣本愿
KM,然后求出每个点删掉之后的最大权匹配,这个只要把顶标和边权改成 0,然后跑一边 KM 中的增光即可,
然后类似一个半平面交的东西,由于范围很小可以枚举每个人跑不等式。
10.友谊巨轮
模拟,用一个 map 记录一下两两之间聊了几句和最近时间,用一个 set 当堆,
然后每次修改的时候就 p_old[x],x,p_new[x]三个点的状态会变。
11.最后战役
c 个人中,相对排名 k,这个人期望是 k(n+1)/(c+1)。
倒着 dp,看选这个人的期望与选后面人的期望,需要一个树状数组统计排名。
12.数论之神
找规律发现一定是 1, 2, 3, ..., x, n/(x-1), n/(x-2), .... x 是 sqrt(n)附近
全部评论
(0) 回帖