AC. 梦想

动态规划目录下的文章

[APIO 2014] Beads and wires

题意简述 有n个点。现在你可以选择一个点x开始,执行若干操作。 1. 选择一个未被加入的点x和一个已经加入的点y,在x,y之间连一条红边。 2. 选择一个未被加入的点x和两个连有红边的点y, z,删去y, z之间的红边,并在x, y和x, z之间分别连一条蓝边。 现在给你一棵带边权的树,作为……
17/04/16 | 暂无评论 | 635阅读 阅读详情

[ZJOI 2017] 树状数组

题意简述 有一个人在写树状数组题,模2意义。 题目需要支持单点加,求区间和。 写的时候把所有x的变化方向都写反了。 现在你需要执行两种操作: 1 l r : 在[l, r]中等概率随机一点x执行单点加。 2 l r : 询问在此时调用错误的代码求答案有多大的概率出错。 输出概率时要求对9982……
17/03/25 | 暂无评论 | 686阅读 阅读详情

[ZJOI 2017] 仙人掌

题意简述 给定n点m边的简单无向连通图。 现在要在图上加若干边,要求加边后还是一个简单无向连通图,且每条边至多属于一个简单环。 求加边方案数对998244353取模的值。 1 \le n \le 5 \times 10 ^ 5, 1 \le m \le 10 ^ 6 算法讨论 考后再写一遍的时候发现写的好快啊QAQ 先判一下……
17/03/25 | 暂无评论 | 699阅读 阅读详情

[ZJOI 2012] 波浪

题意简述 定义一个n元排列P的权值v(P)如下v(P) = \sum_{i=1} ^ {n-1} {|P_i - P_{i+1}|} 求等概率随机一个n元排列求出的权值\ge m的概率。输出保留q位小数。 n \le 100, m \le 2 ^ {31} - 1, q \le 30 算法讨论 感觉如果不卡常数不卡空间不卡精度的话就是一道十分优美的题了! ……
17/03/02 | 暂无评论 | 578阅读 阅读详情

[ZJOI 2013] 蚂蚁寻路

题意简述 给定一个n \times m的带权网格。 要求在网格中选出一个封闭图形。具体可以用一条路线描述。 开始位置在某一格点上,方向朝向北。接着右转两次,左转两次,右转两次,左转两次…… 最后再右转一次。规定这条路线上,不能连续旋转两次,不能经过重复的点,最后需要回到起始……
17/03/02 | 暂无评论 | 303阅读 阅读详情

[ZJOI 2013] 丽洁体

题意简述 给定一个串s。 现在你需要删去尽量少的字符,让其可以和模板串a*b*c匹配。 其中a,b,c是三个串,*可以匹配0个或多个字符。 1 \le |s|, |a|, |b|, |c| \le 50000,保证每个字符出现不超过500次。 算法讨论 难得的清真题。 考虑一个暴力。设f(i,j)为考虑到s的第i个字符,……
17/03/01 | 暂无评论 | 396阅读 阅读详情

[ZJOI 2013] 抛硬币

题意简述 有一枚硬币,抛出正面的概率是\frac{a} {b},反面的概率就是1 - \frac{a} {b}。 现在给定一个硬币序列S(正面/反面)。现在开始连续抛硬币,当某一枚硬币抛完后,若S作为一段连续子序列出现在了抛出的硬币序列中,则停止。 求到停止的期望步数。输出一个最简分数。 1 \……
17/03/01 | 暂无评论 | 582阅读 阅读详情

[ZJOI 2013] 话旧

题意简述 有一个长度为n+1的序列A_0, A_1, ..., A_n,满足下列条件。 1. A_0 = A_n = 0。 2. 对于0 \le i \le n - 1,|A_i - A_{i+1}| = 1。 3. 对于所有极小值点k,有A_k = 0。 我们还规定了A的m个位置的值。 求满足条件的序列个数 和 序列最大值的最大值。第一问的答案对19940……
17/03/01 | 暂无评论 | 455阅读 阅读详情

[BZOJ 2784] 时间流逝

题意简述 有n种能量圈,第i种能量是a_i。开始你没有能量圈。对于每一天,你有p的概率失去一个能量最小的能量圈,有1-p的概率可以等概率得到一个能量不大于你现有最小能量圈的能量圈。如果你现在没有能量圈,则不存在概率失去能量圈。 求第一次能量总和超过T的期望天数。 1 \le n……
17/01/22 | 暂无评论 | 400阅读 阅读详情

[NOI 2015] 寿司晚宴

题目描述 为了庆祝 NOI 的成功开幕,主办方为大家准备了一场寿司晚宴。小 G 和小 W 作为参加 NOI 的选手,也被邀请参加了寿司晚宴。 在晚宴上,主办方为大家提供了n-1种不同的寿司,编号1,2,3,...,n-1,其中第i种寿司的美味度为i+1(即寿司的美味度为从2到n)。 现在小 G 和小 W……
16/05/24 | 暂无评论 | 989阅读 阅读详情