空灰冰魂-CSDN博客

原创【SPOJ】SPCQ - GOPU AND DIGITS DIVISIBILITY 数位处理

题意题解一点测试代码题意T组数据，每组数据输入一个n，求最小的不小于n的x，满足x的各位加一起可以整除x。题解暴力。直接从n开始枚举x判断各位加一起是否能整除该数。一点测试自己跑程序随机测试1000w个数，最多的一个需要判断436次,平均判断次数28.1396078。所以认为这种暴力在随机数据下可以跑得飞快，而即便全是此次测试的极限数据213994575384292455，在题目的1000

2017-09-21 15:54:31 728 1

原创【BZOJ2395】【Balkan 2011】Timeismoney 最小乘积生成树

题解：裸最小乘积生成树。最小乘积生成树定义：有一张n个点m条边的无向图，每条边有k个权值。现在要取一个边集M使得其将所有点连通，并使 ∏ki=1(∑j∈Mjcost(j,vali))\prod_{i=1}^k (\sum_j^{j\in M} cost(j,{val_i}) ) 最小即个边集的每一种边权的总和的乘积最小。比如： k=1时，就是裸最小生成树。 k=2时，

2015-07-10 11:22:50 4902

原创【BZOJ3707】圈地计算几何旋转坐标系

题解：对于一个点对，如果它的连线的方程的 xx 为定值，即为一条竖线，那么我可以把所有点以 xx 为第一键值， yy 为第二键值排序，然后这条线两端的第一个点与这条线段做个三角形，其面积都可能更新答案。。然后我们可以先把所有线按照斜率排个序，然后发现每次按序修改y轴，可以 O(1)O(1) 得到旋转坐标系后的点的序列。可以观察此图（这是个小特例福利哦）：呃。就是每次旋转到一条

2015-06-23 18:17:58 2083

原创【BZOJ1132】【POI2008】Tro 计算几何叉积求面积

题解：首先暴力是 O(n3)O(n^3) 求每个三角形面积！可是三角形面积怎么求？一般我们都是用叉积……等等？那一个叉积不是被算了很多遍？好了，正解出来了，先有序地把点排排序保证不重，然后算一下每个叉积的贡献，也就是每条边的贡献，，然后因为排序啥的，时间复杂度 O(n2logn)O(n^2logn) 。然后这道题。呃，卡精度……？！求叉积嘛，最后得到的东西都需要除以2，，先不除

2015-06-23 14:48:50 1938

原创【BZOJ2823】【AHOI2012】信号塔最小圆覆盖计算几何

题解之前：首先最小圆覆盖虽然有三层 forfor 循环，但是它是期望 O(n)O(n) 的。什么？你问我为啥？那我只能呵呵了，50W的 O(n3)O(n^3) 高速跑过。后交的是不求凸包直接跑的，先交的是求了凸包再跑的。。并没有什么差距。题解：这道题我们可以先写一份求凸包来缩减点的规模，如果点是随机生成的，那么期望有不到100个点在凸包上，然后就可以乱搞了（其实毛用没有23

2015-06-23 14:04:49 2209

原创【BZOJ1069】【SCOI2007】最大土地面积凸包单调性

题解：先求凸包，然后：枚举点 ii ，然后对于点 jj 得到的 ii 与 jj （有序）中间的点，以及 jj 与 ii （有序）中间的点，都是单调的。代码：#include <cmath>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 2050#define ep

2015-06-22 10:14:09 2445

原创【BZOJ1043】【HAOI2008】下落的圆盘计算几何

题解：给每个圆求一下： 1. 它是不是被之后的某圆整体覆盖。 2. 它的圆周上有哪些弧段被覆盖了。然后对于每个圆求一下还剩多少周长即可。上述的“2.”可以用圆的圆心角区间来表示哪些弧段被覆盖。然后圆心角大小可以用余弦定理求，位置可以取两圆心连线的角度加减其圆心角的一半。代码：#include #include #include #include #inc

2015-06-19 18:12:19 1562

原创【BZOJ1007】【HNOI2008】水平可见直线

题解：呃。把直线随便排下序，然后扫一遍，类似栈一样删掉被覆盖的直线。代码：#include #include #include #include #include #define N 501000#define eps 1e-10#define inf 0x3f3f3f3fusing namespace std;struct Point{ doubl

2015-06-18 19:14:16 1265

原创【自用】 memset对于int、long long、float、double 的极值怎么清

int极大值：0x7f 较大值：0x3f 较小值：0xc0 极小值：0x80long long极大值：0x7f 较大值：0x3f 较小值：0xc0 极小值：0x80float7f以上一直到be都是-0 (实际上是一个很小的>-1.0的负数) 极大值：0x7f 较大值：0x4f 较小值：0xce 极小值：0xfe 0xff是 -1.#QNAN0000

2015-06-17 20:12:08 7500

原创【BZOJ3572】【Hnoi2014】世界树虚树

题解：首先构建虚树，然后在虚树上DP。过程很简单。先找出每个虚树节点 ii 旁边最近的询问节点 nearinear_i （因为有一些lca也被加入了虚树所以虚树节点不全是询问节点，呃怕你们不懂，但其实这是废话Qwq。）然后对于每条链 [l,r][l,r]，找出 [nearl,nearr][near_l,near_r] 中点，然后两边随便给一给就好了。。代码：#inclu

2015-06-15 19:18:21 2324

原创【模板】斯坦纳树

题目:斯坦纳树 Time Limit: 1 Sec Memory Limit: 128 MB Description 现在有一个n*m的矩阵,某些元素为0,剩下的元素大于0. 现在你要选择一些元素,使得任意两个为0的元素都能够通过选中的元素四连通. (注意,若想达到要求,所有的0自身必须被选中.) 那么请问选中元素的和的最小值是多少?Input 第一行两个整数n,m,表示矩

2015-06-15 09:02:50 2518 1

原创【BZOJ3450】【Tyvj1952】Easy 概率DP

题解：设 LL 为当前期望后缀 oo 长度。出现一个 xx 时， LL 归零，对答案没有任何贡献。出现一个 oo 时，这段 oo 的长度由 LL 变为 L+1L+1 ，这段的答案由 L2L^2 变为 L2+2L+1L^2+2L+1 ，对答案贡献为 2L+12L+1 。出现一个 ?? 时，这段 oo 的长度有可能变成 00 ，也可能变成 L+1L+1 ，所以期望 L+12\frac

2015-06-12 14:28:50 1850

原创【BZOJ1426】收集邮票概率DP 论文题推公式题

题解：并没有什么卵用，首先有一个神思路，然后神推公式。下面这篇博客写得很详尽、、 =a800”>http://blog.csdn.net/pygbingshen/article/details/24852081?=a800 如果是考试，我宁可各种随机然后打表，好歹能过30%的小数据？代码：#include #include #include #include #defi

2015-06-12 10:27:17 1968

原创【BZOJ2318】【spoj4060】game with probability Problem 概率DP

题解：fif_i 表示剩 ii 个石头、 AA 先手的获胜概率。 gig_i 表示剩 ii 个石头、 AA 后手的获胜概率。如果想选，对于 fif_i：有 pp 的概率进入 gi−1g_{i-1} ；有 1−p1-p 的概率进入 gig_i 所以 fi=p∗gi−1+(1−p)∗gif_i=p*g_{i-1}+(1-p)*g_i如果想选，对于 g(i)g(i)：有 qq 的

2015-06-12 09:40:39 2438

原创【BZOJ3270】博物馆概率DP 高斯消元

题解：同BZOJ3143 游走 http://blog.csdn.net/Vmurder/article/details/44542575代码略

2015-06-12 08:17:27 1989

原创【BZOJ3036】绿豆蛙的归宿概率DP

题解：呃，拓扑图上从后往前扫就好了Qwq代码：#include #include #include #include #include #define N 101000using namespace std;struct Eli{ int v,l,n; bool f;}e[N1];int head[N],cnt,d[N],D[N];inli

2015-06-12 07:54:14 2104 1

原创【BZOJ4008】【HNOI2015】亚瑟王概率DP

题解：f(i,j)f(i,j) 表示分配给第 [i,ni,n] 张牌 jj 次机会的期望。然后 f(i,j)=f(i−1,j)∗(1−pi−1)j)+f(i−1,j+1)∗(1−(1−pi−1)j+1)f(i,j)=f(i-1,j)*{(1-p_{i-1})}^j)+f(i-1,j+1)*(1-{(1-p_{i-1})}^{j+1})代码：#include #include #

2015-06-11 20:37:09 2684

原创【BZOJ3566】【SHOI2014】概率充电器树形DP 概率DP

题解：首先无根树转化为有根树。 fi:f_i: 表示 ii 节点由其子树内节点充【不上】电的概率。 gi:g_i: 表示 ii 节点由其父亲节点充【不上】电的概率。 hi:h_i: hi=fi+(1−fi)∗(1−其父到其的导线的充电概率)h_i=f_i+(1-f_i)*(1-其父到其的导线的充电概率) 表示对父亲 fif_i 的贡献。先dfs一遍， fi=(1−自己直接来电的概率

2015-06-11 17:53:25 2193

原创【BZOJ1415】【Noi2005】聪聪和可可概率DP 记忆化搜索

题解：记忆化搜索、 f(i,j)f(i,j) 表示猫在 ii 、鼠在 jj 时的期望。然后显然它是拓扑的，然后先枚举起点n遍bfs算出 f(i,j)f(i,j) 时猫只走一步应该到哪个节点，然后对于 f(i,j)f(i,j) 枚举 kk 表示鼠往哪走，然后 f(totoi,j,j，k)f(to_{to_{i,j},j}，k) 的期望求个平均值就是 f(i,j)f(i,j) 。代码：

2015-06-11 15:01:19 1605

网络流上下界最大流线性规划转费用流RMQ优化建图单纯形字符串相关hash扩展KMP最小表示法回文自动机数据结构平衡树启发式合并替罪羊树LCT树套树KD-Tree二分答案分数规划贪心动态规划背包斜率优化数位DP概率DP插头DP图论差分约束floyd求最小环连通分量相关强连通分量点双连通分量边双连通分量割点割边最小生成树Matrix-Tree定理斯坦纳树最小树形图树上问题Prufer序列虚树dfs序树分

2015-06-11 11:17:24 1431

原创【BZOJ1026】【SCOI2009】windy数数位DP

题解：f(i,j)f(i,j) 表示最高 ii 位，此位为 jj ，的方案数。注意此数组存在前导零，比如 f(i,0)f(i,0) 。 f(i,j)f(i,j) 从 f(i−1,k)f(i-1,k) 随便转移。代码：#include #include #include #include #define N 15using namespace std;long

2015-06-10 20:53:40 1381

原创【BZOJ1833】【ZJOI2010】数字计数数位DP

然而并没有DP。题解：[1，R]的答案减去[1,L]的答案。对于一个数 X ，求 [1,X] 的答案，我是先处理出 [1,999……9] 的答案（那个999……9 然后按位往下扫，计算最高位为 i 的数有多少个、i在非最高位出现了多少次。明明每天睡得很多，为什么还是困呢Qwq 一定是蚊子有毒。剧毒。代码：#include #include #include #

2015-06-10 17:54:00 1405

原创【POJ3155】Hard Life 分数规划+最小割

题解：如题。先算出那个分数值，然后看有哪些人还与源点相连。最小割建图：原图每个点对应一个点，原图每条边对应一个点。每条边对应点向两端点对应点连边，注意要单向边。这道题卡精度：所以一些细节问题扒代码吧Qwq eps：1e-5 因为是double网络流，所以二分上界别太大，边数就好。代码：#include #include #include #include

2015-06-10 09:35:51 1376

原创【BZOJ1293】【SCOI2009】生日礼物单调性

题解：首先我们把所有元素排一下序，然后枚举最小值，那么最大值是非严格单调上升的，就是一个珠子换成其后第一个的同颜色珠子时，将更新一下最大值，而最小珠子则刚好是其后第一个（反之则有空下来的永远用不上的珠子，不合逻辑。。2333）结束。代码：狂野的long long 和开大数组啊……#include #include #include #include #define

2015-06-05 13:56:54 1439

原创【BZOJ1690】【Usaco2007 Dec】奶牛的旅行分数规划判断负环

题解：分数规划+判断负环。代码：#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 1010#define M 5050#define eps 1e-8using namespace std;double mid,fun[N];str

2015-06-03 20:29:50 1671

原创【BZOJ1486】【HNOI2009】最小圈分数规划 dfs判负环。

题解：分数规划Qwq。然而它卡判点入n次的那种spfa判断负环。于是有了一种黑科技：我们从枚举点 i 开始 dfs ，然后扫到点 j 时，保持 i~j 这一条链上的点被标记，然后强行判断再扫一个点 k 时，是否会到这个链上，然后是不是能重新更新此点 k 与 i 的距离。。。这个东西是指数级别时间复杂度的，然而却可以过这道题。代码：#include #inclu

2015-06-03 17:22:53 1544

原创【BZOJ2803】【Poi2012】Prefixuffix hash+推性质

题解：首先我们如果设原串为串[ 1,n1,n ] 然后 fif_i 表示串[ i+1,n−ii+1,n-i ]中最长的串长使得串[ i+1,i+fii+1,i+f_i ]==串[n−i−fi+1,n−in-i-f_i+1,n-i] 这时存在一个性质 fi−1=fi+2f_{i-1} 然后就可以线性递推啦！证明：现在让我们来反证一下这个性质：下图有四种情况，f[i]为红色

2015-05-16 15:46:23 1926 1

原创【BZOJ2085】【Poi2010】Hamsters AC自动机bfs+倍增floyd

题解：首先我们搞个 ACAC 自动机，然后每个串在 ACAC 自动机上 bfsbfs 求出 f(i,j)f(i,j) 表示串 ii 后面最少接 f(i,j)f(i,j) 个字母能搞出来串 jj 。然后把每个串当成一个点，倍增 floydfloyd 求两点之间恰好走 mm 步的最短路。代码：#include #include #include #include #includ

2015-05-15 17:12:04 1636

原创【BZOJ1071】【SCOI2007】组队利用单调性的双指针

链接：#include int main(){ puts("转载请注明出处[vmurder]谢谢"); puts("网址：blog.csdn.net/vmurder/article/details/43407071");}题解：三个定义：高度h，v速度，Ah+Bv为s 首先我们在外圈枚举来固定其中一个权值，姑且枚举v吧。每次枚举值大写为V。然后在内圈就可

2015-05-15 16:11:17 1675 1

原创【BZOJ2081】【Poi2010(17th)】Beads RKhash+hash表请记住这个神一样的数：200019

题解：枚举串长，数据范围20W。然后串长为 ii 时需要枚举 ⌊ni⌋\lfloor \frac{n}{i}\rfloor 次。加一起是 O(nlogn)O(nlogn) 我们把每个串hash一下就好了。然后自然溢出就好了，，，。我无限WA啊。。最后wyfcyx给我提供了一个种子：200019…… Qwq。。。。。。。。。。。。。。。。。。。。。。。。。。代码：

2015-05-15 13:57:49 1768

原创【BZOJ1125】【POI2008】Poc 原名：Train hash+离散化+平衡树(splay)

题解：首先我们发现对于每个串，我们把它hash一下，然后建一棵平衡树来支持“插入”、“删除”、“下传标记”这三种操作就可以记录并更新一个点的答案了。然后每个串的串长都较小，修改字符时可以暴力重新hash。注意：一对互相交换字符的字符串要先一起删掉再一起往平衡树里加。可能是同一个串的俩字符交换，此时不能从平衡树中删两遍。德莱文初始攻速接斧头之间只能再A一下（雾，呃觉得两条太

2015-05-15 08:35:05 1866

原创【BZOJ2827】千山鸟飞绝离散化+splay

题解：首先先把坐标离散化一下，然后对于每个坐标点我们建一棵平衡树，每次插入操作后给整颗平衡树下传一下需求的两个标记。注意：splay有的人（比如我）习惯每棵都先建-inf、inf两个节点以便于查找前驱后继。然后这道题的数据是爆0x3f3f3f3f的……呵呵，怪不得我跑了千组极限数据都没挂，然后vfk的数据我直接爆零……（我的点权值随机的[1,10086]）代码：#i

2015-05-14 15:17:42 2234

原创【BZOJ1142】【POI2009】Tab 乱搞

注：我没用hash。题解：首先我们发现无论如何变换，该在一行的还是会在一行，该在一列的还是会在一列。拿行举例：我们交换行，在一行的一定还同一行，不在一行的一定还不在同一行；我们交换列，则一个元素的行标号不会被改变，行上的【(在/不在)同一行】这条性质一定不会改变。然后这样我们扫两遍矩阵。第一遍我们把每行内元素排序，然后再把矩阵的每一行排下序， O(nm)O(nm) 比较两个矩阵

2015-05-13 08:28:05 1460

原创【BZOJ3207】花神的嘲讽计划Ⅰ hash+可持久化线段树

题解：首先因为嘲讽长度固定，所以我们可以给每个点固定一个hash值（不固定的话我还真不会做）。然后用可持久化线段树实现一段区间内有哪些数，然后查询一段区间是否有要的那个数就行了。代码：#include #include #include #include #define N 401000#define LOGN 20#define base 107#define

2015-05-13 08:13:06 1476

原创【BZOJ3265】志愿者招募加强版线性规划单纯形法对偶原理

题解：这道题是线性规划求目标函数最小值，对偶原理转一下就成了单纯形算法求线性规划最大值。单纯形法：首先这篇博客缺失了很多证明，只能讲述单纯形法的实现。 // N个变量 M个限制double a[M][N]; // 这m个限制里变量的系数double b[M]; // 第i个限制加和 double c[N]; // 目标函数里变量系数double ans; // 目标函

2015-05-12 18:20:00 2175 3

原创【BZOJ3998】【TJOI2015】弦论后缀自动机

题解：首先我们可以建一个后缀自动机。然后每条路径走到每个点都是一个串，它们是有字典序的。我们只需要统计出往每个点走之后都有多少串就好了。 fi=(∑fson)+numif_i = (\sum {f_{son}})+num_i 对于不计重复的情况下，numi=1num_i=1 对于计算重复的情况下，每个节点都有多种走到最后的方式，numinum_i 就是看有这个种数。比如 ab

2015-04-29 17:37:55 2651

原创【BZOJ4010】【HNOI2015】菜肴制作

题解：把所有入度为0的点入优先队列，每次取出标号最大的，并将此点取走后入度为0的点入优先队列，最后反序输出。代码：#include #include #include #include #include #define N 101000#define M 101000using namespace std;struct Eli{ int v,next;}

2015-04-29 14:07:51 1369

原创【BZOJ4011】【HNOI2015】落忆枫音拓扑图DP，

题解：如果没有后加的边，那么 ans=∏ni=2dians = \prod_{i=2}^n di ，可以回忆构建树形数据的普遍方法——点 ii 连一条 [1,i-1] 的边即可。然后后加边了以后，有且仅有一些方案会形成环是错误方案。拓扑图DP就好啦~， f(i)f(i) 表示从 yy 到 ii 时的方案。发现对于一条 y→iy \rightarrow i 的路径，再加上一条 i→y

2015-04-29 09:15:39 1641

原创【BZOJ4029】【HEOI2015】定价模拟

题解：枚举后面有几个 00，然后每次(当前求 kk 个后导 00 )算出第一个比 LL 大的 10k10^k 的倍数，和第一个比 LL 大的 5×10k5\times 10^k 的倍数。然后把所有这些数都比较一下就好啦。代码：#include #include #include #include #define inf 0x3f3f3f3fusing namesp

2015-04-28 13:34:39 1603

原创【BZOJ4027】【HEOI2015】兔子与樱花贪心

题解：贪心策略步骤一：如果有多个儿子，那么显然（这里是真的显然，真的不给证明了）我们肯定要先合并小儿子后合并大儿子。贪心策略步骤二：因为所有节点的载重是相同的，所以我们要先合并叶子节点，不能合并就把父亲的权值+1然后叶子就可以去掉啦~（若父亲要被合并上去，那么爷爷就会多出若干被计数为1的儿子）。证明1：为什么一定先合并叶子？因为： 1.如果合并完父亲叶子还能合并，

2015-04-27 20:12:14 2037

空空如也

空空如也