4 Flaze_

尚未进行身份认证

一只蒟蒻【扑通扑通跪laekov 扑通扑通跪yjqqqaq 扑通扑通跪mhy12345 扑通扑通跪zms_

等级
TA的排名 5w+

BZOJ 4709: [Jsoi2011]柠檬【斜率优化

发现……每一段的开头结尾应该是同一个颜色才会最优于是……就是个naive的斜率优化dp了,斜率单增,对于每种颜色,点的横坐标也有序,要最大化截距…于是…单调栈……#include#define MAXN 100005#define MAXS 10004using namespace std ; int n ;const double eps = 1e-7 ;const

2017-02-28 09:47:51

BZOJ 3672 [Noi2014]购票【点分+斜率优化

先扔到序列上看看……dp式子写出来一眼斜率优化……dp[i] = ……因为有个l……所以决策看起来好像不单调啊……斜率也不单调……cdq啊稳啊分块之后先处理前面那段,然后用前面的结果更新后面的;反正都分治了,就把需要被更新的点按照 dis[i] - l[i] 从大到小排个序,然后把左边用来更新的dp值……从右往左把可以用来更新的值加进去,维护个凸包;【第一次

2017-02-20 15:31:08

BZOJ 2152: 聪聪可可【树形dp

……煞笔树形dp看错题调了一年怎么办QAQ…直接上代码了没什么好说的码风越来越丑我也很绝望啊【#include#define MAXN 20005using namespace std ; int n ;inline int read() { register int ch = getchar() ; while (!isdigit(ch)) ch = getchar()

2017-02-14 18:35:03

CCF ONI WC2017 冬假令营 面基(姬)记

DAY 1...七点的飞机四点起床整个人都狗了早饭在机场吃的....一碗粉相当于四顿最大环 亏成狗啊qwq十一点到绍兴一中,志愿者妹子们好可爱【捂脸】但是为什么突然念诗23333【突然兴奋】于是吃了午饭后寂寞的Flaze独守空房等到四点等来了新疆妹子.....吃完饭六点见到了云南妹子和noip锤爆我的南山妹子【本来担心她好高冷的结果超可爱【还和曾有妹是初中同学?好像有乐山的独特气场

2017-02-04 15:24:49

BZOJ 3052: [wc2013]糖果公园【树上带修莫队

是这样的……几天前Flaze:我要学莫队QAQ我觉得整个机房只有我不会莫队QAQ花花:那你去写糖果公园吧,写了就会了Flaze【突然兴奋】:吼啊资瓷啊!…………然后………………在颓了一万年后#include#define MAXN 200005using namespace std ; int n , m , Q ;inline int read() { r

2017-01-26 19:26:58

BZOJ 2120: 数颜色 && 2453: 维护队列 【带修莫队版题【也可以学黄学长分块

……学莫队QwQ    好神啊QwQ复杂度什么的xjb讨论一下感觉好像挺对的23333加个修改就相当于变成三维的查询……直接用三个指针,维护当前记录的左端点右端点和时间,先把询问按照    第一关键字:左端点所在的块    第二关键字:右端点所在的块    第三关键字:前一个修改操作的时间分块,yy一下可以证明……块大小是N^(2/3)的时候最优  于是就这么写咯……和

2017-01-18 15:33:56

BZOJ 3343: 教主的魔法【分块基础题

……应该是第一次好好写分块的题2333333好暴力23333……总觉得写的好丑23333【以后分块就用yjq和laekov这两个变量名了,感觉稳得不行#include#include#include#include#include#define MAXN 1000005using namespace std; int n,m;inline int read(){ regis

2017-01-16 21:55:03

BZOJ 4559: [JLoi2016]成绩比较【计数dp,容斥,组合数

听说王队长的题解特别妙【摔好吧的确挺♂妙先yy出求每个人相对排名不同的方案数(用f来记录)因为是有顺序的……所以不能直接容斥……就用 f[i] 表示 有刚好 i 个人被碾压的方案数 , 再用 至少 i 个人被碾压的方案数 减掉不合法的看代码吧,还是挺好懂的,或者前两篇题解也写的很稳【王队长的题解啊exciting然后求在每种排名下 分数不同的方案数……自

2017-01-12 18:00:47

BZOJ 3864: Hero meet devil【dp套dp

把LCS当成子串 看样例看了一年这几天特别颓废啊【滑稽…先考虑LCS的求法,以及给出的字符串长度,显然是需要状压的对于求LCS的时候用的数组 dp[i][j]       把dp[i]差分之后,差分数组里只会有0和1,显然可以把这个东西状压了然后又发现,对于每个 i ,dp数组只与dp[i-1]有关于是可以用trans[s][ch] 表示在s状态的dp数组后

2016-12-25 21:36:57

BZOJ 3812: 主旋律【状压dp+容斥

题解我就服这个大佬QAQ   http://blog.miskcoo.com/2015/05/bzoj-3812简洁明了还赏心悦目,miskcoo家的题解超棒啊【跪在地上表白大佬忽然很想自己搭blog【趴良心样例啊我怀疑是因为前几天立的flag233333 当时磕了【k个连通块】就表示,磕主旋律…………于是肝了几天,被坐在右边颓废的jq挂起来裱233

2016-12-20 21:08:51

HDU 5713 K个联通块【状压计数dp……补集转化?

显然可以f[s][i] 表示点集s有i个连通块的方案数,枚举子集的时候,令其中一个的i=1,并强行把lowbit(s)表示的节点塞在i=1的子集里面,就避免了算重然后考虑如何计算对于点集s 全部连通的方案数,发现好麻烦2333 转化一下 用选边的所有方案数 - 不连通的方案数不连通的方案数……继续枚举子集,其中一个连通另一部分任选,并把lowbit(s)表示的节点放在联通的那个块里

2016-12-16 00:02:54

BZOJ 1975: [Sdoi2010]魔法猪学院【K短路,A*

就用dijkspfa这种玄学东西啊……看题显然就是从最短路开始从小往大选择,于是就是求前k短路考虑对于一个节点i,维护dis[i]表示从i到n的最短路长度,d1[i]表示从1到i当前走过的路径长度,用priority_queue维护这两个的和,每次取最小的显然最优…………谁说priority_queue要卡空间啊……明明没卡嘛QAQ,辣鸡flaze xjb写了个配对堆MLE了一年233

2016-12-15 09:56:43

BZOJ 1047 [HAOI2007]理想的正方形【单调队列

显然就是扫一下所有n*n的矩阵的最大值和最小值只差取min,单调队列横着扫一遍竖着扫一遍就好了好好取名字,少用ctrl+C ctrl+V【因为这个我调了一年233333#include#define MAXN 1006using namespace std; int n,m,k;inline int read(){ register char ch = getchar();

2016-12-14 16:29:57

帝都八十中几日游来着……(16.12.02-16.12.10)

DAY0上午的飞机于是果断地集体翘掉星期五的课滚去机场……发现只有flaze穿了校服莫名尴尬2333川航飞机餐有毒23333 吃完之后第一次有了晕机的感觉【滑稽……帝都出太阳还是不算冷……不过暖气还真是腐败啊哼八十中设备真是太高端了23333发现寝室里只有我和另一只山西妹子【鏼鏼发抖】而且整个宿舍的右半边似乎只有我们这个房间有人【鏼鏼发抖】2333妹子怕鬼诶好可怜哈哈哈

2016-12-12 23:55:42

BZOJ 4668: 冷战【并查集

……按秩合并的并查集高度是log的,直接暴力走就是了#include#define MAXN 500005using namespace std; int n,m;inline int read(){ register char ch = getchar(); while(!isdigit(ch)) ch = getchar(); register int rtn = 0; wh

2016-12-12 17:23:06

BZOJ 4424: Cf19E Fairy【强行树链剖分

显然二分图只要没有奇环就好了于是随便搞一棵生成树然后找出所有只包含一条非树边的环就好了……发现求的就是所有奇环的交中不被任一偶环覆盖的边注意如果只有一个奇环的话那条非树边也是合法答案树链求交参考NOIP2015D2T3#include#define INF 0x3f3f3f3f#define MAXN 1000005using namespace

2016-12-12 16:32:53

1411: [ZJOI2009]硬币游戏【xjb找规律

xjb手玩找规律,并发现这个规律很靠谱然后把操作次数拆成2的次幂之和,完了#include#define MAXN 200005using namespace std; long long n,T;inline long long read(){ register char ch = getchar(); while(!isdigit(ch)) ch = getchar();

2016-12-12 16:15:26

BZOJ 1176: [Balkan2007]Mokia【CDQ分治+树状数组

CDQ裸题,和2683基本一样……于是我就naive地直接粘了根本没看题……GG#include#define MAXA 200005#define MAXT 2000006using namespace std; int N,S;inline int read(){ register char ch = getchar(); while((ch^'-')&&!isdigit(ch

2016-12-12 16:00:41

BZOJ 1142: [POI2009]Tab【并查集/hash

有一万种写法2333可以hash可以并查集,反正xjb写写就好【并查集虚的不行2333竟然没有T#include#define MAXN 1005#define base 1000000#define MAXZ 2000006using namespace std; int T,n,m;inline int read(){ register char ch = getcha

2016-12-12 15:56:33

BZOJ 4726: [POI2017]Sabota?【树形dp

…………我……手贱………………特么……忘了……我的队列…………下标是从……0开始的…………拍了……5k组…………没出错…………………………出题人造数据辛苦了233333显然最坏情况是 初始节点在叶子上  然后直接xjbdp一下#include#define MAXN 700005using namespace std; int n , k;inline int read(

2016-12-07 15:09:49

查看更多

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