Deep_Dark_FAntasy♂

未归档

Codeforces(3) 博弈论(3) 基本数论、组合数学（排列组合，容斥等）(14) 并查集(2) 数据结构(2) 深度优先搜索、广度优先搜索、搜索剪枝(8) 线性dp、背包问题、区间dp(15) 题解(12)

/ 注册

全部文章 / 未归档（共176篇）

(普通gcd&读入技巧)Maximum GCD

每一组没告诉你读多少个，用stringstream。然后对每一组gcd就行，没什么好说的。 #include<cstdio> #include<iostream> #include<sstream> #include<string> using n...

2020-09-23

1 410

Bracket Sequence

1.注意怎么处理输入的数据 2.利用两个栈来实现运算 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 3e6+7; const int mod = 1e9+7; c...

2020-09-23

1 415

[唯一分解定理+素数筛选]Mysterious Bacteria

题目大意：给你一个数x = b^p,求p的最大值分析：x=p1^a1 * p2^a2 . . .pn^an x只有一个因子的p次幂构成所以，本题所求实质上就是求 :a1,a2,a3,a4…an的最大公约数本题有一个坑，就是x可能为负数，如果x为负数的话，x = b^q, q必须使奇数，所...

2020-09-23

1 427

[数论]Prime Time

https://vjudge.net/contest/356798#problem/W 水题，但值得注意的点： 1.本题多组输入，多组输入可以通过打表、前缀和来节省查询时间。 2.memset()不可以初始化数组为非0值 3.int cnt[N]={1}只能使得 cnt[0]=1; #includ...

2020-09-23

1 443

[kuangbin概率]A Dangerous Maze

tag:通过设概率为未知数解题。对期望=概率*结果更深理解题意 n扇门，如两扇门每个分别为 +x +x，则可用 x+x 的时间出去，如为 −x−x，则可用 x+x 的时间回到原点。每次随机选一个，问出去的期望时间。题解由式子可以看出，当n负==n的时候，永远无法离开迷宫。 #incl...

2020-09-23

1 603

[dp+期望]Discovering Gold

参考博客：https://www.cnblogs.com/daydayupacm/p/5788115.html 题意现在有n个格子，每个格子上都有一定的黄金值；还有一个色子（1-6）。起始位置站在格子1上面，若每次投掷色子得到数x,x+i<=n（i表示现处位置的格子编号），则可以到达（x...

2020-09-23

1 467

[dp+期望]Race to 1 Again

题目传送门题目分析传送门看完题目分析后，参考代码注解 #include <bits/stdc++.h> #define eps 1e-10 using namespace std; const int N=1e5+7; double dp[N]; void init() { ...

2020-09-23

1 550

[概率+01背包]Just another Robbery

题目解法新颖，值得拓展思维。优化:将被捕概率转换为安全概率，即将被捕概率小于P的限制条件转换为安全概率大于等于1-P 题解：dp[i]的值是抢了i价值的安全概率，从V(全部都抢的价值总和)开始从大到小地去dp。以最大地安全概率来更新dp[i],最后从V开始从大到小查询dp[v]从而得到满足要求的最...

2020-09-23

1 463

[集卡游戏]几何分布在竞赛中的应用

思考引例： 2000年前后小浣熊干脆面风靡各大校园，每一包干脆面随机附赠一款水浒英雄卡，集齐108张卡即可换钱，请尝试使用数学工具解决集卡这个问题。参考视频：https://www.bilibili.com/video/av59313918?from=search&seid=138...

2020-09-23

1 553

[概率-几何分布] Dice (III)

题目传送门：https://vjudge.net/contest/361424#problem/G 题意：给出一个n面色子，现在扔色子，知道所有面都出现一次，问掷色子次数的期望值。题目解析：假设现在已经掷出了k个不同的面，再掷下一次的过程是一次伯努利实验，即X（首次掷出新面需要的投掷次数）服从参数...

2020-09-23

1 570