4 Lazer2001

尚未进行身份认证

天涯何处无芳草 只是白兔寻不到

等级
TA的排名 1w+

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

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

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

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

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

2018-03-10 15:17:31

冒泡——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

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

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

2018-01-02 19:12:03

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

CDQZ 多校集训Day5 冒个泡

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

2017-12-23 18:48:17

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

BZOJ4872 [SHOI2017]分手是祝愿

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

2017-12-18 14:33:03

网络流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

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

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

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

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

2017-12-11 22:05:10

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

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

2017-12-11 18:53:35

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

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

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

2017-12-08 22:15:26

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

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

2017-12-08 21:24:35

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

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

2017-12-08 21:07:38

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

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

2017-12-08 14:49:56

查看更多

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