摘要：
"题目链接" 不难看出矛盾关系可以构成一棵树，如果取一个节点，那么它的父节点就不能取，树形DP就行了。 这不是没有上司的舞会吗。。 但是漏了一种情况，即这个关系可能形成一个环(从n条边和样例能看出来)，且有多个连通块，每个连通块一定且仅在根节点处有一个环。 在环上选择一条边断开，把端点分别作为根节点 阅读全文
posted @ 2018-04-02 08:15
SovietPower
阅读(213)
评论(0)
推荐(0)
摘要：
"题目链接" 求最大的存活概率，DP+记忆化。 用f[s][x][y][hp]表示在s状态，(x,y)点，血量为hp时的存活概率。 s是个三进制数，记录每个陷阱无害/有害/未知。 转移时比较容易，主要是在陷阱未知时需要知道当前状态这个陷阱为有害/无害的概率，并用这两个概率相加。 如何求某个状态下未知 阅读全文
posted @ 2018-04-01 21:44
SovietPower
阅读(227)
评论(0)
推荐(0)
摘要：
"题目链接" $Description$ 设$sum_i$表示$i$的二进制表示中$1$的个数，求$$\prod_{i=1}^nsum_i\ mod\ 10000007$$ $Solution$ 因为$n$的二进制有$logn$位，所以我们考虑枚举x，求满足$sum_i=x$的$i$的个数，然后就可 阅读全文
posted @ 2018-04-01 20:06
SovietPower
阅读(200)
评论(0)
推荐(0)
摘要：
"题目链接" $Description$ 求$[l,r]$中$0,1,\cdots,9$每个数字出现的次数(十进制表示)。 $Solution$ 对每位分别DP。注意考虑前导0: 在最后统计时，把0的答案减掉对应位的即可，在第$i$位的前导0会产生额外的$10^{i 1}$个答案。 cpp incl 阅读全文
posted @ 2018-04-01 17:01
SovietPower
阅读(193)
评论(0)
推荐(0)
摘要：
"题目链接" $Description$ 求$[1,n]$中十进制表示包含"13"这个子串，且能整除13的数的个数。 $Solution$ 数位DP: dp[位][s(pre/have"13")][remainder],上界由DFS状态记录. cpp //15MS 1520K include int 阅读全文
posted @ 2018-04-01 16:13
SovietPower
阅读(184)
评论(0)
推荐(0)
摘要：
"BZOJ" "洛谷" $Solution$ 很显然的建二分图后跑最大费用流，但有个问题是一个数是只能用一次的，这样二分图两部分都有这个数。 那么就用两倍的。如果$i$可以向$j'$连边，$j$也向$i'$连边，如果上一次走了$i j'$，那么这一次一定走$j i'$。 每次跑最大费用流，直至有一次 阅读全文
posted @ 2018-04-01 14:19
SovietPower
阅读(253)
评论(0)
推荐(0)
摘要：
题目链接 一个长度为$n$的循环节，在$k\times n(k\geq 1)$次之后一定会回到原样。 用$a_i$表示每个循环节$i$的长度，那么所有$n$个数字的排数为$lcm(a_1,a_2,\cdots,a_k)(+1)$，其中$a_i$满足$\sum_{i=1}^ka_i=n$. 所以题目实 阅读全文
posted @ 2018-03-31 17:30
SovietPower
阅读(189)
评论(0)
推荐(0)
摘要：
"题目链接" 状态只与黑、白两点的颜色有关，于是用 $f[x][i][j]$表示当前以x为根节点，有$i$个黑点$j$个白点，使得x子树满足该条件的最小花费。 最后答案就是 $min\{f[root][0][j],f[root][i][0/1]\}$。 把 $i\geq 1$的状态都看做 $i=1$ 阅读全文
posted @ 2018-03-31 16:52
SovietPower
阅读(391)
评论(0)
推荐(2)
摘要：
题目链接 \(Description\) 给定一张有向图，从S随机游走，输出到T的期望步数（可能无穷大）。 \(n\leq 10^4,\ m\leq 10^6\)，保证每个强连通分量大小$\leq 100$。 \(Solution\) 一个点到达终点的期望步数 \(E_i=\sum_{(i,j)\i 阅读全文
posted @ 2018-03-31 13:46
SovietPower
阅读(307)
评论(0)
推荐(0)
摘要：
"题目链接" 如题目中的公式，我们只要把做对每个题的概率加起来就可以了(乘个1就是期望)。 做对第i道题的概率 $$P_i=\frac{1}{max(a_{i 1},a_i)}$$ 原式是 $P_i=\frac{min(a_{i 1},a_i)}{a_{i 1}\times a_i}$，化简后得到上 阅读全文
posted @ 2018-03-31 09:11
SovietPower
阅读(178)
评论(0)
推荐(0)
摘要：
"题目链接" 之前做很早了没写这篇，补上。 记录当前ex[]最大的回文中心id和最远延伸范围mx！ 关于串的构造: 应该是 ，而不是 比如 ，答案应是$max\{ex[i]\} 1$，而第二种很多情况下答案是$max\{ex[i]\}$. ~~最优解不改串分奇偶讨论感觉sxbk。。其实也没什么~~ 阅读全文
posted @ 2018-03-30 18:38
SovietPower
阅读(234)
评论(0)
推荐(0)
摘要：
"题目链接" 参考： "浅谈期望的线性性（可加性）" "Codeforces 280C Game on Tree 概率dp 树上随机删子树 求删完次数的期望" (这个的前半部分分析并没有看。。) $Description$ 给你一棵有$n$个白点的有根树，每次随机选择一个点，将它和它的子树中所有点染 阅读全文
posted @ 2018-03-30 10:25
SovietPower
阅读(317)
评论(0)
推荐(0)
摘要：
"题目链接" 一条边不变其它边减少可以看做一条边增加其它边不变。 假设要加的边lab为(A B,v)，那么肯定是要使除这条边外，A B的每条路径上的最小权值都$ v$，这样在连通A,B时(即Kruskal中Union())才一定会选择这条边。 要求路径上最小边的权值$ v$，即要求在路径上有任意一边 阅读全文
posted @ 2018-03-30 09:57
SovietPower
阅读(199)
评论(0)
推荐(0)
摘要：
做(+颓)了4个晚自习后的1h终于写完了(这道模板题) 阅读全文
posted @ 2018-03-29 23:22
SovietPower
阅读(237)
评论(0)
推荐(0)
摘要：
题目链接 参考 远航之曲 \(Description\) 给定无向连通图，从$1$开始随机游走，到点$n$结束。每走过一条边会获得其编号对应的分数（可重复获得）。安排每条边的编号，使得分的期望值最小。输出最小值。 \(n\leq 500\)。 \(Solution\) 把走每条边的概率乘上分配的标号 阅读全文
posted @ 2018-03-29 20:29
SovietPower
阅读(243)
评论(0)
推荐(0)
摘要：
这里是摘要 阅读全文
posted @ 2018-03-29 17:40
SovietPower
阅读(201)
评论(0)
推荐(0)
摘要：
"题目链接" 不会搜索了。。 DFS()中两个参数，枚举每两个队伍的比赛结果(分配当前队伍的分数)。 可以发现方案数量与具体哪只球队得了多少分无关，只与当前比赛的队伍数量和得分序列的组成有关。可以记忆化搜索。 DFS()中是从某支队伍和它后面的队伍一一进行比赛 分配得分，分配完当前后将其它队伍的得分 阅读全文
posted @ 2018-03-29 16:09
SovietPower
阅读(226)
评论(0)
推荐(0)
摘要：
"题目链接 BZOJ" "洛谷" 真的题意不明啊。。 $Description$ 你有k次选择的机会，每次将从n种物品中随机一件给你，你可以选择选或不选。选择它会获得这种物品的价值；选择一件物品前需要先选择某些种物品每种至少一件。 物品价值可能有负。问在最优策略下期望得分。 $Solution$ 并 阅读全文
posted @ 2018-03-28 20:59
SovietPower
阅读(279)
评论(0)
推荐(0)
摘要：
水题ing 阅读全文
posted @ 2018-03-28 17:07
SovietPower
阅读(308)
评论(0)
推荐(0)
摘要：
刷水题ing 阅读全文
posted @ 2018-03-28 16:08
SovietPower
阅读(306)
评论(0)
推荐(0)
摘要：
"题目链接 BZOJ" "洛谷" ~~以为裸点分治，但数据范围怎么这么小？快打完了发现不对。。~~ n^2做的话其实是个水题。。 枚举每一个点为根，为了不重复计算，我们要求所求的三个点必须分别位于三棵子树上。 考虑当前前3棵子树深度为deep的点分别有a,b,c个，新增的子树深度为deep的点有d个 阅读全文
posted @ 2018-03-28 14:53
SovietPower
阅读(248)
评论(0)
推荐(0)
摘要：
这几天做的最舒服的。。没有什么5K的暴力。。就没有过百行的代码 阅读全文
posted @ 2018-03-28 12:56
SovietPower
阅读(341)
评论(0)
推荐(0)
摘要：
"题目链接" $Description$ 有n(n include define gc() getchar() const int N=12; int n,num[N]; double p[N],f[N][103],g[N][103]; inline double FP(double x,int k 阅读全文
posted @ 2018-03-28 07:45
SovietPower
阅读(262)
评论(0)
推荐(0)
摘要：
"题目链接 BZOJ" "洛谷" 题意: 将树划分为k个连通块，要求每个连通块大小相同。输出可能的大小。 结论: 满足条件时颜色的连通块数为k，当且仅当有 $n/k$ 个节点满足它的子树是k的倍数(显然还有 $k|n$ )。 证明就不证了，说下理解(然而也说不清楚。。)。 比如一个点的子树大小为 $ 阅读全文
posted @ 2018-03-27 20:51
SovietPower
阅读(190)
评论(0)
推荐(0)
摘要：
[TOC] 2018.3.27 Test 时间：7:30~11:50 期望得分：(50+)+0+20=70 实际得分：52+5+20=77 总结 T1 看错一点题，暴力也废了很长时间。 T2 期望DP没写过不敢写，然而50分和期望没有关系，贪心什么的就行。没细看。 T3 建图死活建不出来，没想明白费 阅读全文
posted @ 2018-03-27 20:19
SovietPower
阅读(282)
评论(0)
推荐(0)
摘要：
"题目链接 BZOJ" "洛谷" 区间第k小，我们可以想到主席树。然而这是静态的，怎么支持修改？ 静态的主席树是利用前缀和+差分来求解的，那么对于每个位置上的每棵树看做一个点，拿树状数组更新。 还是树状数组的过程，区间加时，每到一个位置在这棵主席树中插入这个数。 查询时，将所有询问要访问到的主席树存 阅读全文
posted @ 2018-03-26 21:13
SovietPower
阅读(372)
评论(0)
推荐(0)
摘要：
"题目链接" f定义和下面的思路一样，转移时枚举填什么字符，去更新f并算出有哪些字符串可以匹配某个状态(见code吧...)。 预处理出有哪些字符串在第i位可以转移到某个字符c，dp时&一下状态即可。 以下是错误思路(题意理解错，如果是'?'则无论如何都已匹配且要求恰好K个。。)： f[i][s]表 阅读全文
posted @ 2018-03-26 20:13
SovietPower
阅读(276)
评论(2)
推荐(0)
摘要：
"题目链接" 题意: 在给定矩形区域内找出最少的数，满足和 =k。输出数的个数。两种数据范围。 0~50 注意到(真没注意到...)P[i,j]=v的个数，val[i][j][v]表示(1,1)~(i,j)值 =v的所有数的和。(不要被什么 =v坑，和二维前缀和一样，只是一个点的初始值为A[i,j] 阅读全文
posted @ 2018-03-26 16:43
SovietPower
阅读(223)
评论(0)
推荐(0)
摘要：
"题目链接" 阅读全文
posted @ 2018-03-26 10:22
SovietPower
阅读(199)
评论(0)
推荐(0)
摘要：
"题目链接" 对于这一区间的操作，我们可以想到差分+前缀和(感觉也没什么别的了。。)。 同时对于本题我们能想到主席树，而主席树正是利用前一个节点建树的。 所以离散化、按时间排序，把操作拆成单点加和减即可。 另外优先级会有重，权值线段树是去重后的，所以要记录sz "" 并根据这个算出k个。 但是对于同 阅读全文
posted @ 2018-03-26 09:17
SovietPower
阅读(236)
评论(0)
推荐(0)
浙公网安备 33010602011771号