3 Lazer2001

尚未进行身份认证

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

等级
TA的排名 1w+

UOJ#1 A+B Problem

最后一题???打好读入优化8#include<cctype>#include<cstdio>classInputStream{public:template<classT>inlineInputStream&operator>>(T&...

2018-04-08 17:07:09

SCOI2018 被电子神大送退役记

说实话我不知道出了这个题的人良心不会痛吗。D1T1卡空间,写了正解拍过了,怎么都卡不下空间交都不敢交。最后交的数据分治???D1T2不可做的模板题,划出了二次剩余的式子都不会…暴力…D1T3我不会写了记忆化搜索每分自己亲手放掉60分呵呵D2T1维护分段函数被卡到30,我校还不止我一个…还有数据卡abs把我校一个强选手卡成0分。D2T2暴力不会写,被一个选手随机化得了50?...

2018-04-08 16:29:08

BZOJ4802 欧拉函数 Millar_Rabin &&Pollard_Rho

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

2018-03-22 19:52:17

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

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

2018-03-14 15:42:31

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

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

2018-03-10 15:17:31

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

大家都很强,可与之共勉。因为pbds库里的平衡树相当于set而不是multiset,所以我们需要让它兹磁重复元素嘿嘿嘿。实测rb_tree_tag404ms,splay_tree_tag544ms。学到老活到老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\leqx,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模板

之前的被卡常数了……classNetwork{private:structedge{intto,w,nxt;edge(){}edge(intto,intw,intnxt):to(to),w(w),nxt(nxt){}}

2017-12-18 09:19:15

UOJ35 后缀排序 后缀数组

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

2017-12-12 11:21:15

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

泥萌都太强啦!!!题意:  求一个串中本质不同的子串个数。题解:  后缀数组论文题#include<bits/stdc++.h>#defineN20010classSuffix_Array{private:intn,a[N],b[N],c[N],sa[N],height[N],rank[N];public:voidbu

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\leq60,m\leq100。题解:补集转化,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\toN走多少次(路径不相同)?(每走一次都会消耗路径长的能量)。  很明显是找出每一次都走还能走得最短路,这个贪心策略一定是正确的。所以我们用A∗A^*算法。  手写堆的话一定要开够数组……  BZOJ把空间改小了mmp,/*************************************

2017-12-08 21:07:38

查看更多

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