6 空灰冰魂

尚未进行身份认证

我要认证

=NULL

等级
TA的排名 4k+

【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

【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

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

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

2015-06-23 18:17:58

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

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

2015-06-23 14:48:50

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

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

2015-06-23 14:04:49

【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

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

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

2015-06-19 18:12:19

【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

【自用】 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

【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

【模板】斯坦纳树

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

2015-06-15 09:02:50

【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

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

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

2015-06-12 10:27:17

【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

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

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

2015-06-12 08:17:27

【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

【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

【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

【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

【自用】OI计划安排表一轮

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

2015-06-11 11:17:24

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!