文章

题意： 给定一个无向有环图（可能有重边），给每一条边编号为 1~m 的不重数值，现在从 1 号节点出发，随机访问相邻节点，得分加上经过的边的编号，到达 n 号节点终止，求通过合理编号，到达 n 号节点时得分期望的最小值。(n<=500) 思路： 1. 对于每一个节点，我们可以通过高斯消元求出它 阅读更多…

题目大意 有一个这样的环：0,1,2…n,n-1,n-2…2,1,0，走 i 步的概率是 p[i], 求终点走到起点的期望。 题目分析 很显然 $$ f[i]= \sum (p[k]*(f[i+k]+k)) $$ 高斯消元搞一搞啊。 代码 #include<iostre 阅读更多…

题目 传送门=￣ω￣= 题解 显然线段树是可以的，搞 m 次区间修改、区间最小值查询即可。 复杂度 $O(mlogn)$ 然而听说普通线段树被卡常，不加读入优化 70 分，加读入优化 95，得用 zkw 线段树。 所以我打了差分，复杂度只有 $O(n+m)$, 理论上不存在更优的做法了，因为输入复杂 阅读更多…

题意：A 和 B 两位战友坐火车经停同一个车站，在 [t1,t2] 间的任意一个时刻，A 的火车会停靠，在 [s1,s2] 间的任意一个时刻，B 的火车会停靠，停靠事件都为 w, 求它们有时间并肩作战的概率。(s1,s2,t1,t2∈[90,1080],w 属于 [1,90]) 思路：如果用二元组 阅读更多…

题意：有 k 只 Tribles , 每一只 Trible 可以恰好活一天，第二天会死，死的时候生下一些小 Tribles, 每只小 Trible 继续活和生仔。现在要知道第 m 天时没有 Trible 的概率是多少。已知每一只 Trible 产下的小 Trible 的数量为 [0,n-1], 概率 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 傻逼出题人毁我青春 你卡空间就算了，题目搞英文也很正常，但你把第一个人和第二个人的血量搞反是几个意思？ 设 $f(i,j)$为第一个人有 $i$点 hp，第二个人有 $j$点 hp 的这个局面出现的几率。 设 $e1$为第一个人在一局内胜利的几率（在任意一局 阅读更多…

//蒟蒻 XZY 原创题 钟氏映射 (zmath) 1. 题目背景 2233 年，CSSYZ 学校的数学老师兼数学竞赛顾问钟 JG 已经 2200+岁啦！ 为了庆生，他或她给广大人民群众出了道题。 2. 题目描述 设集合 $N=M=\{x|x\in N_+,x\leq k,k\in N_+& 阅读更多…

有生以来见过的最恶心的 DP 题目。 题意：n 个人排队激活仙剑奇侠 5. 服务器会按队列顺序进行激活操作。但是在激活队首顾客时，会有以下 4 中情况： 1. 激活失败，重试：概率 p1 2. 链接丢失，队首顾客被扔到队尾：概率 p2 3. 激活成功：队首顾客消失 4. 服务器错误：服务器被关闭，队 阅读更多…

1. 题目 传送门＝￣ω￣＝ 2. 题解 设 $sum$为 $a_i$的和。 首先，如果没有 “再来一次”，那么期望得分为： $sum\div n$ 如果搞到了 $m$个特殊面中的一个，那么第二次掷筛子期望得分（不包括第一次的期望得分）为： $sum\div n\times {(m/n)}$ 以此类 阅读更多…

题目分析 不是很难的区间 dp，用 l[i][j] 表示 i 到 j 这端最后插入的是 a[i] 的方案数,r[i][j] 则表示 i 到 j 这端最后插入的是 a[j] 的方案数，就很容易推出状态转移方程： l[i][j]=l[i+1][j](a[i+1]>a[i])+r[i+1][j](a 阅读更多…