Lazer2001-CSDN博客

原创我的雷打不动的代码风格

大家都很强，可与之共勉。头文件#左边有一个空格，include右边会有一个空格。除了<bits/stdc++.h>之外都用以c为前缀的头文件而不是.h为后缀。不会using namespace std ;一般习惯：花括号不换行，而且左花括号{左边一定会有两个空格。 main函数的返回值是int，且位于整个函数的末尾。(``)的左右两边都必须有空格。[的左边有空格。缩进：缩进一

2017-12-05 10:43:49 523 1

原创数论练习--日常更新

大家都很强，可与之共勉。复习的我会写在知乎专栏啦！！！知乎专栏

2017-11-28 17:31:15 473

原创数据结构练习--日常更新

很久没有写数据结构啦还是要努力共勉!!!11.22SPOJ D-Query题意: 询问区间不同的数的个数有多少个。正解: 主席树或莫队。主席树的做法就是求前缀出现不同数的出现次数。如果这个数已经出现过了，那么直接在当前这棵树上消除之前的下标(不影响之前的结果—-主席树copy节点)，然后添加当前的下标。查询直接在root[r]里面查[l,r]就可以了。莫队比主席树快# include <bits

2017-11-22 12:07:04 554

原创读入输出优化黑科技快过fread&&fwite

大家都很强，可与之共勉。可能还是比不上mmap 但是使用了iostream底层的streambuf，效果极快。namespace In {# define In_Len 2000000 static std :: streambuf *fb ( std :: cin.rdbuf ( ) ) ; static char buf [In_Len], *ss ( 0...

2017-11-06 15:05:04 1486 1

原创我的Vim(Gvim) 配置

大家都很强，可与之共勉。因为暂时用不到Linux，所以先用Gvim凑合一下。之前的有点小问题…Upd(2018.4.01)我的配置source $VIMRUNTIME/vimrc_example.vimsource $VIMRUNTIME/mswin.vimbehave mswinset aiset nuset cinset hlsearchset incsear...

2017-09-25 09:40:53 671

原创计数器

大家都很强，可与之共勉。点这里。欢迎大家来这里开车！#include <cstdio>int cnt;int main () { printf ( "Page view = %d\n", ++cnt ); puts ( "Thank You!" ); return 0;}

2017-05-29 21:51:47 6723 1

原创 UOJ#1 A+B Problem

最后一题？？？打好读入优化8# include <cctype># include <cstdio>class InputStream { public : template < class T > inline InputStream& operator >> ( T&...

2018-04-08 17:07:09 479

原创 BZOJ4802 欧拉函数 Millar_Rabin &&Pollard_Rho

233题意就是求N(N≤1e18)N(N≤1e18)N(N\leq 1e18)的欧拉函数值。不知道为什么自己的随机函数不加一个数会GG就用积性函数算呀…分解质因数就好了…# include <bits/stdc++.h>inline unsigned int Rand ( ) { static unsigned int seed ( 233 ) ; ...

2018-03-22 19:52:17 456

原创 LOJ121 动态图联通性这个线段树分治啊，Excited !!!

大家都太强辣！！！没有题解，因为太弱了… 复习一下奇怪的数据结构姿势# include <bits/stdc++.h>char In_buf [10000000], *ip ( In_buf ), Out_buf [1000000], *iq ( Out_buf ) ;# define readIn(_x_) {\ while ( isspace ( *ip...

2018-03-14 15:42:31 951

原创冒泡水矩阵快速幂和矩阵等比数列求和

一道十分傻(jing)B(dian)的题目：给定一有向图，边长均为111，求长度小于kkk的环个数modmmodm\bmod m 。（点数小于等于100100100）。倒是写了个很全的模板…… 典型的水题…(矩阵套矩阵，分治两种做法都可以……后者常数非常小) 贴一个分治的代码（注意在分治的时候顺便处理出AkAkA^k）：# include <cctype># incl...

2018-03-10 15:17:31 726

原创冒泡——pb_ds库水 BZOJ3224普通平衡树

大家都很强，可与之共勉。因为pbds库里的平衡树相当于set而不是multiset，所以我们需要让它兹磁重复元素嘿嘿嘿。实测rb_tree_tag 404ms，splay_tree_tag 544ms。学到老活到老233333# include <bits/stdc++.h># include <ext/pb_ds/tree_policy.hpp>...

2018-02-27 17:12:33 761

原创我萌的红太阳发现了她自己的博客%%%%%%%%%%%%%%%%

大家都太弱了，需要红太阳的光芒！！！这是红太阳%%%%%%%

2018-01-02 19:12:03 562 2

原创 BZOJ4152 坠短路优化建边我的第一次超级大封装

大家都很强，可与之共勉。题意：您有n(n≤2e5)n(n\leq2e5)个点，以一个pair(x,y)pair(x,y)给出，表示横纵坐标(0≤x,y≤1e9)(0 \leq x,y\leq1e9)。求从11号点到nn号点的坠短路。两点之间的距离定义为min(|x1−x2|,|y1−y2|)min(|x_1-x_2|,|y_1-y_2|)。题解：其实很早之前就做了这道题，大约是在

2017-12-26 21:18:14 425

原创 CDQZ 多校集训Day5 冒个泡

大家都很强，可与之共勉。一天出锅，三天补锅。

2017-12-23 18:48:17 615

原创 Codeforces 662C Binary Table FWT 快速沃尔什变换

大家都很强，可与之共勉。题意：给出一个n(n≤20)n(n≤20)行m(m≤105)m(m≤10^5)列的0101矩阵。每次操作可以将某一行取反或者将某一列取反。要求操作后的矩阵中的11的个数最少，求最小个数。题解：我们会发现行数很小，是一个可以状态压缩的范围（滑稽）。于是我萌就状压行对于每一列，用statestate表示这一列的状态，若第ii位为11，

2017-12-20 21:34:44 440

原创 BZOJ4872 [SHOI2017]分手是祝愿

大家都很强，可与之共勉。题意： B君在玩一个游戏，这个游戏由N个灯和N个开关组成，给定这N个灯的初始状态，下标为从1到N的正整数。每个灯有两个状态亮和灭，我们用1来表示这个灯是亮的，用0表示这个灯是灭的，游戏的目标是使所有灯都灭掉。但是当操作第i个开关时，所有编号为i的约数（包括1和i）的灯的状态都会被改变，即从亮变成灭，或者是从灭变成亮。B 君在玩一个游戏，这个游戏由 N 个灯和 N 个

2017-12-18 14:33:03 481

原创网络流Dinic模板

之前的被卡常数了……class Network {private : struct edge { int to, w, nxt ; edge ( ) { } edge ( int to, int w, int nxt ) : to ( to ), w ( w ), nxt ( nxt ) { } }

2017-12-18 09:19:15 378

原创 UOJ35 后缀排序后缀数组

大家都很强，可与之共勉。清嗓子，之前的后缀数组的板子都有问题…… 特此补一个# include <bits/stdc++.h># define N 100010class Suffix_Array {private : int n, a [N], b [N], c [N], sa [N], height [N], rank [N] ;public : void build

2017-12-12 11:21:15 399

原创 SPOJ694&&SPOJ705 DISUBSTR - Distinct Substrings && SUBST1 - New Distinct Substrings 后缀数组

泥萌都太强啦！！！题意：求一个串中本质不同的子串个数。题解：后缀数组论文题# include <bits/stdc++.h># define N 20010class Suffix_Array {private : int n, a [N], b [N], c [N], sa [N], height [N], rank [N] ;public : void bu

2017-12-12 09:03:31 338

原创 BZOJ2938 POI2000 病毒补全AC自动机 Trie图判环

大家都太强了辣，和我这样的大蒟蒻共勉吼不吼啊？题意：给您一堆0101串，问是否可以构造一个无限长的字符串，使得这些0101串都不是她的子串。题解：补全AC自动机判环（不走以单词结尾的点（不止是它本身）），记得加一个优化，就是搜过了没有答案了就continue;continue; 然后就是简单的DFS判环。/*************************************

2017-12-11 22:05:10 523

原创 BZOJ1174 [Balkan2007] Toponyms 邻接链表优化 TRIE树

大家都吼强，可与之共勉嗯嗯。题意：给您一个字符集合，你从其中找出一些字符串出来。希望你找出来的这些字符串的最长公共前缀×\times字符串的总个数最大化。空格也是嗯，所以我看不懂样例！！！！！！！！题解：傻逼题，哎呀MLE了。怎么办，那就暴力找转移叭！！！我们发现转移go[cur][26]go [cur] [26]并不是2626个都用上了（又不是补全AC自动机），于是我

2017-12-11 18:53:35 576

原创 BZOJ1030 [JSOI2007]文本生成器补全AC自动机+简单DP

大家都吼强，可与之共勉。题意：您现在有nn个单词，您得构造一只长度为mm的文章，使得这个文章里面包含至少一个单词。（所有文本只包含大写字母）问构造方案数，答案对1000710007取模。数据范围n≤60,m≤100n\leq 60, m\leq 100。题解：补集转化，AC自动机上面DP。首先我们构造出这nn个单词的AC自动机，然后考虑到求出能构造出的，我们可以用总方案数减去不

2017-12-11 14:19:36 403

原创 BZOJ3890 [Usaco2015 Jan]Meeting Time K短路 Astar || 拓扑DP

大家都很强，可与之共勉。题意：有A,BA,B两个人她萌要从11走到NN，每个人在每条边走的时间不一样，求她萌同时出发，同时到达的最短时间。题解：正解应该是拓扑图DP，之后补上。我用Astar暴力跑出一个人的前500000条路，然后再另一个人的图里面查，第一个查到的就是答案。如果查不到直接输出IMPOSSIBLEIMPOSSIBLE。讲道理很好卡掉的，数据太水啦！！

2017-12-08 22:15:26 407

原创 BZOJ2260 商店购物 BZOJ4349 最小树形图坠小树形图朱刘算法

大家都很强，可与之共勉。惊了，我以前朱刘算法的模板是错的！！！！题意：您要买nn种商品，每一种商品都有价格和需求量，有mm个优惠条件，以a,b,pa,b,p给出表示您买了aa商品之后bb商品的价格就会变成pp，（p<原来的价格p < 原来的价格）。请问您卖完这些东西最少花费多少？题解：坠小树形图，先跑出坠小树形图。确定每个东西买一个的最小总花费，然后所有东西一定可以以最小单价买到

2017-12-08 21:24:35 494

原创 BZOJ1975 [Sdoi2010]魔法猪学院 K短路 Astar A* 贪心

大家都很强，可与之共勉。题意：给定一张图，一共有kk的能量，求最多可以从1→N1\to N走多少次（路径不相同）？（每走一次都会消耗路径长的能量）。很明显是找出每一次都走还能走得最短路，这个贪心策略一定是正确的。所以我们用A∗A^*算法。手写堆的话一定要开够数组…… BZOJ把空间改小了mmp，/*************************************

2017-12-08 21:07:38 406

原创 LOJ6122 「网络流 24 题 - 18」航空路线问题最长不相交路径坠大费用坠大流

大家都很强，可与之共勉。题意：给定一张航空图，图中顶点代表城市，边代表两个城市间的直通航线。现要求找出一条满足下述限制条件的且途经城市最多的旅行路线。从最西端城市出发，单向从西向东途经若干城市到达最东端城市，然后再单向从东向西飞回起点（可途经若干城市）。除起点城市外，任何城市只能访问一次。对于给定的航空图，试设计一个算法找出一条满足要求的最佳航空旅行路线。题解：网络流要做

2017-12-08 14:49:56 521

原创 LOJ6226 「网络流 24 题 - 22」骑士共存二分图坠大点独立集

大家都很强，可与之共勉。题意：这道题有图呃题解：二分图，然后……同方格取数，只不过把每个点点权看为11，只能是左边的点向右边连边。数组开小了RERERERERERERERERERRERERERERERER# include <bits/stdc++.h># define oo 0x3f3f3f3f# define N 40040class Network {private

2017-12-08 11:26:51 398 3

原创 LOJ6015「网络流 24 题 - 16」星际转移枚举解坠大流判可行解

大家都很强，可与之共勉。题意：由于人类对自然资源的消耗，人们意识到大约在2300 2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，21772177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有nn个太空站位于地球与月球之间，且有 mm 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，

2017-12-08 10:56:57 414

原创 LOJ6014「网络流 24 题 - 15」最长 k 可重区间集坠大权不相交路径坠大费用坠大流

大家都很强，可与之共勉。题意：给定实直线LL上nn个开区间组成的集合II，和一个正整数kk，试设计一个算法，从开区间集合II中选取出开区间集合 S⊆IS \subseteq I，使得在实直线LL的任何一点xx， SS中包含点xx的开区间个数不超过kk。且 ∑z∈S|z|\sum\limits_{z \in S} | z |达到最大。这样的集合SS称为开区间集合II的最长 kk可重区间集。

2017-12-08 09:11:53 415

原创 LOJ6013「网络流 24 题 - 14」负载平衡坠小费用坠大流

大家都很强，可与之共勉。题意： GG公司有nn个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使nn个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。题解：求出平均值，转化为供求问题。这道题相当于把盈余的仓库供给亏损的仓库。于是盈余的在一个集合，亏损的在一个集合。注意到这道题可以再相邻仓库之间连边，也就是所有仓库可以互达，只是单位费用不一样，

2017-12-08 07:27:51 390

原创 LOJ6012「网络流 24 题 - 13」分配问题坠小费用坠大流坠大费用坠大流

大家都很强，可与之共勉。题意：有nn件工作要分配给nn个人做。第ii个人做第jj件工作产生的效益为cijc_{ij} 。试设计一个将nn件工作分配给nn个人做的分配方案，使产生的总效益最大。还是要输出最小效益和最大效益。题解：保证每个工作只分配给一个人用源点到她流量为11限制，一个人只接受一份工作于是用到汇点流量为11限制，对于效益我们视作费用，然后二分图之类的连边。和

2017-12-07 21:21:40 354

原创 LOJ6011「网络流 24 题 - 12」运输问题坠小费用坠大流坠大费用坠大流

大家都很强，可与之共勉。题意： WW公司有mm个仓库和nn个零售商店。第ii个仓库有aia_i个单位的货物；第jj个零售商店需要 bjb_j个单位的货物。货物供需平衡，即 ∑i=1mai=∑j=1nbj\sum\limits_{i = 1} ^ m a_i = \sum\limits_{j = 1} ^ n b_j 。从第 ii个仓库运送每单位货物到第jj个零售商店的费用为cijc

2017-12-07 21:05:24 484

原创 LOJ6010 「网络流 24 题 - 11」数字梯形坠大费用坠大流坠大权不相交路径

大家都很强，可与之共勉。题意：给定一个由 nn行数字组成的数字梯形如下图所示。梯形的第一行有mm个数字。从梯形的顶部的mm个数字开始，在每个数字处可以沿左下或右下方向移动，形成一条从梯形的顶至底的路径。分别遵守以下规则：从梯形的顶至底的mm条路径互不相交；从梯形的顶至底的mm条路径仅在数字结点处相交；从梯形的顶至底的mm条路径允许在数字结点相交或边相交。要求输出三个任务

2017-12-07 20:35:02 322

原创 LOJ6009「网络流 24 题 - 10」软件补丁最小代价转移 SPFA状态压缩

大家都很强，可与之共勉。题意：不好概括啊题解：发现nn很小，于是状态压缩。看是否能够到00这个状态，跑最短路就可以了。 LOJ越来越慢了# include <bits/stdc++.h>template < class T > inline bool chkmin ( T& d, const T& x ) { return d > x ? ( d = x ), 1

2017-12-07 17:40:31 319

原创 LOJ6008 「网络流 24 题 - 9」餐巾计划坠小费用坠大流

大家都很强，可与之共勉。哎呀麻麻我终于会写最小费用最大流了！！！！题意：一个餐厅在相继的 nn天里，每天需用的餐巾数不尽相同。假设第ii天需要rir_i块餐巾。餐厅可以购买新的餐巾，每块餐巾的费用为PP分；或者把旧餐巾送到快洗部，洗一块需MM天，其费用为FF分；或者送到慢洗部，洗一块需NN天，其费用为SS分(S<F)(S<F)。每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多

2017-12-07 17:07:24 293

原创 LOJ6007 「网络流 24 题 - 8」方格取数二分图最大点权独立集

大家都很强，可与之共勉。题意：在一个有 m×nm \times n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意22个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。题解：求一张图的最大点权独立集。关于概念：最大点权独立集：从一张图中找到权值和最大的点集，使得它们之间两两没有边。最小点权覆盖集：从一张图中选取一些点，使这

2017-12-07 12:25:02 377

原创 LOJ6006「网络流 24 题 - 7」试题库坠大流

大家都很强，可与之共勉。题意：有kk种试题，nn道试题，每种道题属于一些种类。你要组一套试卷，其中每一种试题的数量只能是kik_i，求方案。题解：最大流判是否满流，满流就有解。建图方式：虚拟源点SS和汇点TT，其中让种类在左边，试题在右边（因为要输出方案）。对于每一种试题KK，S→KS\to K连一条容量为kik_i的弧，对于属于KK的试题OO，连一条K→O

2017-12-07 11:32:17 262

原创 LOJ6005 「网络流 24 题 - 6」最长递增子序列坠大流

大家都很强，可与之共勉。题意：给定正整数序列 x1x_1~xnx_n ，以下递增子序列均为非严格递增。计算其最长递增子序列的长度ss。计算从给定的序列中最多可取出多少个长度为ss的递增子序列。如果允许在取出的序列中多次使用x1x_1和xnx_n ，则从给定序列中最多可取出多少个长度为ss的递增子序列。题解：我忘了O(nlogn)O(nlogn)的最长不递减子序列怎么写

2017-12-07 10:55:26 302

原创 LOJ6004 「网络流 24 题 - 5」圆桌聚餐最大流

大家都很强，可与之共勉。题意：假设有来自nn个不同单位的代表参加一次国际会议。每个单位的代表数分别为rir_i 。会议餐厅共有mm张餐桌，每张餐桌可容纳cic_i个代表就餐。为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。问是否存在方案，若存在输出一种方案。题解：最大流满流判是否有解。然后输出方案判哪些边被流满流。建边方式：我们虚拟一个原点SS和汇点TT

2017-12-07 09:06:26 358

原创 LOJ6003 「网络流 24 题 - 4」魔术球坠小路径覆盖数二分图坠大匹配

大家都很强，可与之共勉。题意：假设有nn根柱子，现要按下述规则在这nn根柱子中依次放入编号为 1,2,3,4,⋯1,2,3,4,\cdots的球。每次只能在某根柱子的最上面放球。在同一根柱子中，任何22个相邻球的编号之和为完全平方数。试设计一个算法，计算出在nn根柱子上最多能放多少个球。题解：转化为最小路径覆盖，即每一根柱子当成一条路。枚举解（或者二分答案），

2017-12-07 08:32:59 298

CCF WC2017 冬令营 课件集合 （圆方树等）

C++的pb_ds库在OI中的应用集合

CCF2016-2017国家集训队论文

空空如也

CCF WC2017 冬令营课件集合（圆方树等）