2 QYQYQYQYQYQ

尚未进行身份认证

暂无相关描述

等级
博文 33
排名 26w+

点分治 水题集合

由于考场上想出点分治可是不会写(2333蒟蒻花了一天写点分治qwq3365:[Usaco2004Feb]DistanceStatistics路程统计TimeLimit:10Sec  MemoryLimit:128MBSubmit:389  Solved:224[Submit][Status][Discuss]Descript...

2018-04-04 20:12:33

概率期望动态规划

原文地址:https://www.cnblogs.com/Paul-Guderian/p/7624039.html虽然概率DP有许多数学期望的知识,但是终究无法偏离动态规划的主题。动态规划该有的特点继续保留,另外增添了一些概率期望的神秘色彩。1~8题出处:hdu4576  poj2096  zoj3329 &...

2018-03-21 11:05:26

[JXOI2018模拟]攻略世界树 网络流+建图

BackgroundT3Description这是在ALO世界线上。为了帮助桐子救出本子娜,ALfheimOnline的多个工会展开了针对世界树的攻略活动。但是在攻略之前,必须策划好进攻方案。策划进攻方案之前也要先完成基础人员分组。在ALO中的小组分配中大致有四种定位,队长,战士,牧师,法爷。一个标准的小队应当拥有这四种人至少...

2018-03-16 10:33:49

[JXOI2018模拟] way 树形dp+启发式合并

题目大意:给n个点的有根树,每个点有个权值和大小,q个询问,每个询问为x,s,意为在x子树中,选出大小之和不超过s的点,其中最大权值和是多少。考场上写个暴力,考后顺便就学了启发式合并。启发式合并也就是一种思想,即把小的合并到大的上去,可以优化时间复杂度。每次直接把重儿子的dp数组赋给该点,然后再对轻儿子进行背包#include<bits/stdc++.h>#def...

2018-03-14 09:20:39

[CF600E] Lomsat gelral 树上启发式合并

树上启发式合并qwq,一听就是很高级的算法,其实也不难。这个算法主要也只能应用于:子树统计无修改操作算法实现过程首先进行轻重链剖分,和树剖不同的是,我们每次先dfs轻儿子,暴力统计答案大小,并且暴力删除轻儿子产生的影响。最后dfs重儿子,就是为了保留下重儿子的影响。那时间复杂度为什么是对的呢?只有dfs到轻边时,才会将轻边的子树中合并到上一级的重链,树链剖分...

2018-03-14 07:50:06

[BZOJ1503]郁闷的出纳员 动态开点权值线段树模板

自己摸索着写的指针版动态开点权值线段树,也没有那么毒瘤。。对于提高或者降低工资,我们可以移动最低工资线,同时记录工资变化多少用于对新人的处理,那么就不用对每个人的工资进行操作了。特别的,对于减工资的操作,我们可以写一个clear函数,把[-N,最低工资线-1]的所有节点全部赋为0,意思是把所有低于工资线的员工删掉。最终离职的员工=总的加入的员工-最终剩下的员工#include&lt...

2018-03-10 09:22:08

priority_queue 优先队列 STL

C++优先队列的基本使用方法 #include<iostream>#include<functional>#include<queue>usingnamespacestd;structnode{    friendbooloperator<(noden1,no...

2018-02-22 10:58:33

期望&概率dp总结

原文地址:http://blog.csdn.net/qq_31759205/article/details/54730101总算刷完kuangbin期望&概率专题了,下面总结一下心得和题解!1.期望dp期望dp通常逆推,即从结果推向初始状态,也可以用记忆化搜索进行dp;E=Σp1*(E1+X1)+Σp2*(E+X2)其中E为当前状态的期望,E1为下一个状态的期望,p...

2018-02-13 10:32:51

贪心法求树的最小支配集,最小点覆盖,最大独立集

原文地址(转自Ashly的博客)定义:最小支配集:对于图G=(V,E)来说,最小支配集指的是从V中取尽量少的点组成一个集合,使得V中剩余的点都与取出来的点有边相连.也就是说,设V’是图的一个支配集,则对于图中的任意一个顶点u,要么属于集合V’,要么与V’中的顶点相邻.在V’中除去任何元素后V’不再是支配集,则支配集V’是极小支配集.称G的...

2018-02-08 14:46:36

[BZOJ3262]陌上花开 三维偏序 CDQ分治+树状数组 模板

cdq分治似乎是一种特殊的分治,一般的分治中[l,mid]与[mid+1,r]是基本上没有关系的,然而cdq分治中[l,mid]中可能会对[mid+1,r]的答案造成影响。我们可以运用排序、数据结构或者cdq来进行降维操作。cdq分治的框架(下文代码转自Dirge的博客):voidcdq(intl,intr){if(l==r)return;intmid=(...

2018-02-06 11:30:58

[BZOJ3155]Preprefix sum

题目要求的是∑i=1n∑j=1iaj'>∑i=1n∑j=1iaj∑i=1n∑j=1iaj\sum\limits_{i=1}^n\sum\limits_{j=1}^ia_j原式=∑j=1n∑i=jnaj=∑j=1n(n−j+1)∗aj=n∗∑j=1naj−&

2018-01-30 20:12:01

[BZOJ2179]大整数乘法 快速傅里叶变换

看了下menci大佬的博客,虽然看那么一点懂,然而还是毅然决然地决定背代码2333qwq模板源自hzwer神犇,50行多厉害!#include#defineN131072#definepiacos(-1)#definelllonglongusingnamespacestd;typedefcomplexdouble>E;intn,m,L;charch

2018-01-30 18:18:15

[BZOJ1174] Toponyms 字典树模板

刚刚学字典树,于是乎打了一个模板。不得不说好像会卡空间。。反正写了一个错误的代码2333Trie树数组版:#include#definemaxn500010usingnamespacestd;inttrie[maxn][53],f[maxn],sz=1,ans,n;strings;voidadd(){intrt=0;for(inti=0

2018-01-24 11:09:13

[BZOJ1305] dance 最大流+二分

据说这是一种套路qwq(雾首先拆点,把每一个人拆成‘喜欢点’和‘不喜欢点’,从每个男生的‘喜欢点’向自己的‘不喜欢点’连接容量为k的边,从每个女生的‘不喜欢点’向每个女生连接容量为k的边。对于男生i喜欢男生j,由男生i的‘喜欢点’向女生j的‘喜欢点’连接容量为1的点(因为两人只能跳1首歌)。对于男生i不喜欢女生j,由男生i的’不喜欢点’向女生j的‘不喜欢点’连接一条容量为1的边。接下来,从

2018-01-23 20:40:16

[BZOJ2427] 软件安装 tarjan缩点+树形背包

这题显然是背包,然而我们发现连边后会存在强连通分量,而由于有奥妙重重的依赖关系,所以当我们选择强连通分量中某个点的时候,整个强连通分量都要选。所以我们缩点,用一虚拟源点向入度为0的点连边,跑树形背包就行了#include#include#include#include#include#include#definemaxn120#definemaxm510using

2018-01-19 10:35:25

[BZOJ1452] Count 二维树状数组

随便翻一道题目,然后是二维树状数组实际上和普通的树状数组也是差不多的也是对两维进行lowbit然后操作求某一个矩形容斥一下就行了#include#definemaxn310#definemaxc110usingnamespacestd;intn,q,m,co[maxn][maxn];intlowbit(intv){returnv&(-v);}str

2018-01-19 08:28:06

[BZOJ1565]植物大战僵尸 最大权闭合图

BZOJ1565题目有点长qwq,读了很久才看懂。这似乎是一道最大权闭合图的裸题,但是我们发现存在植物互相保护这种情况,即建出来的图不一定是DAG。那么我们可以拓扑排序找环,然后把环忽略。然后把不可攻击的点(即环上的点)不与虚拟源点和虚拟汇点连边,那么就不会影响答案了。这题也更加加深了对该建模方式的理解,即如果需要获得正权的收益,且该点通过奇妙重重的方式连接到对面(负权点),那么一定要

2018-01-18 15:59:18

[BZOJ1468]Tree 点分治模板

点分治是针对树上路径所提出的算法.首先先找重心,重心指的是把该点删去使得各连通块大小最大值最小的点.每一条路径都有且只有两种情况:1.经过重心,这里我们直接每次更新deep值,直接算.如果存在某个i,j其到重心的路径有重合,即这是一条非简单路径,那么我们递归子问题然后减去就行,也算是一种容斥吧2.不经过重心,直接递归求解了.BZOJ1468#include#inclu

2018-01-12 10:55:00

[DP]斜率优化学习小结

蒟蒻花了一个晚上研究斜率优化qwq不过大概还是搞明白了.斜率优化是啥其实是一种优化动态规划的方法.我认为斜率优化是建立在决策单调性的基础上的.如对于形如这样的状态转移方程f[i]=min/max(f[j]+xxx(ji))f[i]=min/max(f[j]+xxx(j其复杂度为O(n2)O(n^2)而我们通过化式子来得到无论对于哪一个i,在j点进行决策一定要比k点进行决策更优,可以

2018-01-08 09:26:45

[BZOJ1497] 最大权闭合子图+最小割+最大流

BZOJ1497好吧,看到ARC085的E题好像是个最大权闭合子图,于是就去学习了一下,顺便复习一下dinic,最大流最小割定理。每个客户群向需要选的两个类型连边,然后由原点向客户连边权为获利的边,基站向汇点连边权为所需消耗价格的边,所有正权值之和减去最小割就是答案了,画图显然。最小割可以转化为最大流,于是乎跑一个dinic模板就行了#include#incl

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