Flaze_-CSDN博客

原创存档……【假装自己会刷题【怎么写着写着成了日记啊

--------S------------2016.05.06POJ 1330 裸的tarjan求LCABZOJ2815 裸的灭绝树都是口胡了很久终于才写的题……而且都是一遍过感觉自己萌萌哒x【好嘛代码能力似乎的确大概可能有点提高真是好开心【依然弱成狗orz

2016-05-06 21:12:46 3272

原创 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 1842 1

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

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

2017-02-20 15:31:08 888

原创 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 645

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

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

2017-02-04 15:24:49 4271 2

原创 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 650 1

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

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

2017-01-18 15:33:56 536 1

原创 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 393

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

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

2017-01-12 18:00:47 1103

原创 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 755

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

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

2016-12-20 21:08:51 1015

原创 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 647

原创 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 445

原创 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 308

原创帝都八十中几日游来着……（16.12.02-16.12.10）

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

2016-12-12 23:55:42 642

原创 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 555

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

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

2016-12-12 16:32:53 594

原创 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 761

原创 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 366

原创 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 476

原创 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 369

原创 BZOJ 2683: 简单题【CDQ分治 + 树状数组

……今天终于学了CDQ分治……感觉挺有趣T+WA*2T：强行把nlog^2 写成 n^2log，2333WA1：按照x和y排序的时候，忘了x相同的应该是先修改再询问WA2（不白，不膜，不清真（？））：………………我…………排序…………数组从1开始的，然而sort(tmp,tmp+cnt_tmp,cmp);………………没看出来2333……顺便吐槽这个题解

2016-12-05 23:04:36 361

原创 BZOJ 2553: [BeiJing2011]禁忌【ACAM + 期望dp + 矩快优化

……反正瞎瘠薄搞搞，都是显然的#pragma GCC optimize(3)#include#define MAXN 80using namespace std; int n,m,ji;struct Matrix{ long double d[MAXN][MAXN]; int x,y; Matrix():x(0),y(0){memset(d,0,sizeof d);} M

2016-12-04 10:52:44 364

原创 BZOJ 4466 [Jsoi2013]超立方体【模拟

发现n维超立方体有2^n个定点，2^(n-1)*n条棱，每个点的度数为n发现只有在二进制表示下只有一位不同的两个点之间才有边于是check上面那三个点可以先判断-1用id[i] 表示 i 号点的标号然后进行标号把原来的0号点标为0，与它相邻的点分别标为2,4,8,16....从与0号点相邻的点开始bfs，每个点记录dis[i]，表示i号点与0号点的距离

2016-12-01 16:09:21 606

原创 BZOJ 1799 [Ahoi2009]self 同类分布【数位dp

枚举数字总和为多少（设为mod），f[i][j][k][0..1]表示算到第i位，前i位的和为j，这个数的数值%mod=k，是否顶上界转移就是f[i+1][j+x][(k*10+x)%mod] += f[i][j][k]这样的（顶上界的特判一下嘛，上面那个公式就省略0..1那一维了【滑稽手癌把i打成了x，调了一年2333#includeusing namespace st

2016-12-01 10:04:13 401

原创 BZOJ 1367 [Baltic2004]sequence【脑洞+可并堆

在黄学长博客看到似乎是某国集大爷的论文例题？先考虑不严格递增的考虑对于一段数，如果是递增的，那么应该z[i]=t[i]最优，如果是递减显然应该区间中的z都等于这个递减区间的中位数最优，于是可以把整个数列分成一堆递减的，用堆维护中位数；对于得到的中位数序列重复上面的操作，显然可以不断合并相邻的堆直到全部递增然后发现并不需要每次把整个数列分割成递减区间，可以直接把每个数当成

2016-11-30 14:31:22 381

原创 BZOJ 1455 罗马游戏【可并堆+并查集

对于每个集合维护一个堆，merge就合并，注意已经死了的不会被操作……【因为这个wa了一年2333总觉得1e6跑起来很虚？结果快的飞起#include#define MAXN 1000005using namespace std; int n,m;inline int read(){ register char ch = getchar(); while(!isdigit(ch)

2016-11-29 17:31:32 346

原创 BZOJ 2809 [Apio2012]dispatching【可并堆（贪心

开了很久的坑，显然对于每个节点，选择以它为根的最小的那几个最优，于是每个节点开一个大根堆，从叶子往上合并就好，如果不合法就弹掉最大的元素#include#define MAXN 100005using namespace std; int n,m;inline int read(){ register char ch = getchar(); while(!isdigit(ch))

2016-11-29 17:29:33 414

原创 BZOJ 3531: [Sdoi2014]旅行【树剖+动态开点线段树【听说有人写平衡树？【滑稽

刚开始看成了子树/链修改……想了一年23333然后……手贱打错变量名，调了一年…………发现…………是1A【233333对于每个宗教开一棵树就好了删除直接赋值为0，反正不卡空间【滑稽#pragma GCC optimize(3)#include#define MAXV 4000005#define MAXN 100005using namespace std;

2016-11-26 20:27:31 400

原创 BZOJ 3831 [Poi2014]Little Bird【单调队列优化dp

显然每次转移最多+1，于是单调队列维护一下前面的答案就好， f[i] 单增，如果 f 相同，则比较 h 的大小【正确性显然【看第一句话】#include#define MAXN 1000005using namespace std; int n,q,k;inline int read(){ register char ch = getchar(); register int

2016-11-24 20:06:47 504

原创 BZOJ 1071: [SCOI2007]组队【单调性扫一遍

……显然可以枚举minh和minv，然后扫一扫，n^3的T的起飞考虑扫的时候可以考虑单调性，复制一遍队员数据，一个按照a*h+b*v+c升序排列，另一个按照h升序排列计算的时候两个队列分别扫，外层循环枚举v，内层枚举h（按照升序），显然在h递增的时候对于两个序列上，合法区间都在单调右移，于是可以用两个指针分别扫，对于v不合法的就不进行计算（不入&&不出）考虑会不会有没有入队就直

2016-11-23 21:15:10 701

原创 BZOJ 3083: 遥远的国度（codevs 4804）【链剖序+线段树

……喵的WA了两把，第一把是……倍增查询是否为lca的时候……忘记赋值anc[i][0] = father[i]了………………第二把……………………我……INF开小了…………GGGGGGG#include#define MAXN 100005#define INF INT_MAXusing namespace std; int n,m;inline int read(){ cha

2016-11-22 19:38:51 491

原创 BZOJ 1419: Red is good【期望

看了眼数据范围……n^2啊……不怂了似乎要炸空间？滚一下可以随时终止的话每个状态和0取个max就好f[i][j]表示i个红j个黑的期望收益，显然可以通过算下一个拿的是红还是黑来转移代码：#include#define MAXN 5005using namespace std; int n,m;long double f[2][MAXN];int main(){ s

2016-11-21 20:14:33 453

原创 BZOJ 3450: Tyvj1952 Easy【期望

几周前挖的期望坑233填坑2333用f[i]表示前i位的期望得分，l[i]表示当前位往前数连续1的期望长度。如果第i位为1的概率为p[i]，f[i] = f[i-1] + ( l[i-1] * 2 + 1 ) * p[i]……反正…第i位如果是1，那么f[i] 比起 f[i-1] 多出来的就是 l[i]^2 - l[i-1]^2 的分数…………意会一下啦QAQ反正期望的转

2016-11-21 16:38:33 319

原创 BZOJ 4318: OSU!【期望

……考noip2016前……想着反正noip不会考期望于是就把这题坑了……考完填坑……看了Q巨的题解忽然觉得期望很好玩2333题解看Q巨的blog好了，考虑每一位为1的贡献，直接考虑从上一位的答案转移到现在的答案，于是类似差分一下……？？【不会描述了2333可以试试看代码x#include#define MAXN 100005using namespace std; int n

2016-11-21 16:24:55 381

原创 NOIP2016游记【XM bless all

DAY0 上午考了一把yjq出的yoip信心题，三道水题【虽然T3推了一会儿23333一边推一边躺在椅子上和yjq及妹子们谈笑风生get了很多大佬的感♂情史】然后发现竟然T2写挂了？？？拿头来T？？？【并查集没有路径压缩【因为直接压着行写了233333就忘了奇奇怪怪的东西x 于是强行改改交强行AK涨rating掉RP 正好是ingress周年庆双倍经验，中

2016-11-19 22:59:18 1408

原创 NOIP 2015 D2 T1T2T3【写着玩

……去年去考D2似乎只有二十分来着……【捂脸于是今天晚上就补补进度【T1：二分答案【去年不会于是写的贪心【跪地#include#define MAXN 50005using namespace std; int l,n,m;int a[MAXN];bool check(int x){ for(int pre = 0,cnt = 0,i = 1;i<=n;++i){ if

2016-11-16 23:41:22 402

原创 BZOJ 3181: [Coci2012]BROJ 【数据分治（暴力+（二分&&容斥））

根据数据范围猜解法，数据分治！！！【x好吧……其实是先想到了容斥的，然而容斥姿势不太好果断GG没写，反正觉得容斥的话p肯定不能太大，然后又yy了循环节啥的各种鬼畜东西233333（虽然最后发现根本没什么卵用然后在考试结束前几分钟被小朋友嘲讽，忽然就想到了怎么写p比较大的，在线性筛的时候，顺手记录每个数的最小质因子，因为p大，所以p的系数应该是很小的，于是直接枚举，如果枚举到的数的最小质因子

2016-11-16 17:17:46 583

原创 BZOJ 3687 简单题【dp，bitset基础应用

因为sum发现出现次数的奇偶性才会影响对答案的贡献，于是存01就好每次新加一个数x，显然有更新： for(int i=x;i既然存01，就用bitset了bitset的左移右移很方便啊2333对了……这题……数据有毒，没给够n个数，顺手读入优化RE了一年2333#include#define MAXN 2000005using namespace std; in

2016-11-16 16:40:14 549

原创 BZOJ 3339 Rmq Problem【离线，值域线段树

区间mex，考虑离线按左端点排序左端点右移时，这个数到它的下一个数之间的位置（作为右端点）的mex值全部与当前数取min#include#define MAXN 200005#define MX 200005#define INF 0x3f3f3f3fusing namespace std; int n,m;inline int read(){ char ch=getchar(

2016-11-15 14:45:05 521

空空如也

空空如也