关闭
当前搜索:

让Gedit编译你的cpp文件

背景:Linux自带的编译器太辣鸡了 (#ノ`Д´)ノ,怒学Gedit 开始用Gedit都要用gdb编译好麻烦….其实可以给它配置一下,加个”编译+运行”的功能就OK了 主要流程: ①点进工具栏-编辑-首选项 ②在插件栏中,选中”外部工具” ③工具栏-工具-Manage External Tools ④点进去,点左下面的加号,起个名,选个快捷键,设置成下图所示,在上面编辑栏...
阅读(12) 评论(0)

模拟赛-仙人球 Tarjan+树链剖分

题目描述 如果一个无自环无重边无向连通图的任意一个点最多属于一个简单环,我们就称之为仙人球。所谓简单环即不经过重复的结点的环。 现在,小Z有一张仙人球图,他想知道两个点之间不同的非复杂路径的条数。这里复杂路径指的是经过某条边至少两次的路径,两条路径不同当且仅当它们之中的边不同。这个问题太难了,所以小Z想要请教请教你。当然,为了不让你特别尴尬,你只需要求出条数mod 1000000007的值即可...
阅读(13) 评论(0)

Duan2baka的Splay模板!(二叉搜索树)

BZOJ[3224] Tyvj 1728 普通平衡树 题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3224 用Splay搞了一发…. (以下摘自我二逼平衡树那道题) 对于Splay删除操作,我询问了一些dalao的做法,这里选择了一个比较高效的,即将它的前驱Splay到根,他的后继Splay到根的右儿子,直接操掉根右儿子的左儿子...
阅读(29) 评论(0)

BZOJ[1984]月下“毛景树” 树链剖分+线段树

传送门ber~ 边权放到下面的点上,统计/修改时不算他俩的LCA Add时: ①上面已经有覆盖标记——覆盖标记+k ②没有覆盖标记——加标记+k 覆盖时 ①上面已经有加标记——加标记清零,覆盖标记打上 ①上面没有加标记——加标记清零,覆盖标记打上… 代码如下: #include #include #include #define N 100020 using namespac...
阅读(25) 评论(0)

BZOJ[4368][IOI2015]boxes纪念品盒 贪心

传送门ber~ 刘研绎dalao%%% 发现只有三种路线: ①从左面走,从左面回来 ②从右面走,从右面回来 ③直接走一圈 注意到如果进行两次③操作的话,一共发了2k个礼物,根据抽屉原理,一定有哪一边物品数量>=k>=k,即两次③转化为①/②+③,结论就是整个过程中最多只进行一次③ 设左半部分一共有toptop个点,右半部分一共有top1top1个点 枚举路线①送多少个点i,i∈[t...
阅读(27) 评论(0)

BZOJ[1086][SCOI2005]王室联邦 块状树

传送门ber~ 块状数据结构 秒杀一切题目!秒杀一切题目! 代码如下: #include #include #define N 1050 using namespace std; inline int read(){ int x=0,f=1;char c; do c=getchar(),f=c=='-'?-1:f; while(!isdigit(c)); do x=(...
阅读(40) 评论(0)

BZOJ[2038][2009国家集训队]小Z的袜子(hose) 莫队

传送门ber~ 要求区间[l,r][l,r]内选出两个相同颜色的概率,即求 (C2cnt1+C2cnt2+...+C2cntk)/C2r−l+1 (C^{2}_{cnt_1}+C^{2}_{cnt_2}+...+C^{2}_{cnt_k})/C^{2}_{r-l+1} (cnt21−cnt1+cnt22−cnt2+...+cnt2k−cntk)2/(r−l+1)∗(r−l)2 \frac...
阅读(28) 评论(0)

根号类算法讲解——分块,莫队

一、分块 分块算法是比较常见的根号类算法,就是把数分成块换种形式暴力 先放题: 给你一个长度为n(n10510^5)的序列,有m个操作,操作涉及区间加和区间求和 这个东西可以做各种数据结构的裸题,肯定被各种切掉了吧… 考虑最暴力的思想,就是暴力更改统计每个区间 我们也可以将mm个元素分成一块,一共有k=n/mk=n/m块,对于区间的修改,枚举所有区间内包含的整块,将其打上加标记...
阅读(35) 评论(0)

BZOJ[3781]小B的询问 莫队

传送门ber~ 莫队算法直接上 按在同一个块内按右端点排序,不在同一个块按所在块的编号排序将询问按左端点排序 枚举询问,不断移动左右端点,按这种顺序可以保证复杂度为n1.5n^{1.5} 代码如下: #include #include #include #include #define N 50050 using namespace std; inline int read(){...
阅读(25) 评论(0)

BZOJ[2428][HAOI2006]均分数据 模拟退火

传送门ber~ 模拟退火骗分 每次随机一个点,然后把它随机放入另外一个集合里,如果解更优就更新,如果不是更优,则根据当前温度随机判断是否更新,温度越高更新的几率越高,并不断降温,直到小于精度为止 多做几遍即可 代码如下: #include #include #include #include #include #define eps 1e-4 #define INF 2147483647...
阅读(22) 评论(0)

BZOJ[2120]数颜色/BZOJ[2453]维护队列 分块

传送门ber~ber~ 记录preipre_i和前一个第ii位颜色相同的是哪一个,在查询区间ll~rr时只需要在该区间找出prepre小于ll的记录就可以 求出每个点的prepre后将序列分块,每块按prepre从小到大排序,查询时对于完整的块二分查找,对于不完整的块暴力统计就可以 修改时重建,如果这位的prepre不一样了,就重建该块 代码如下: #include #include #...
阅读(23) 评论(0)

BZOJ[2002]弹飞绵羊 分块

传送门ber~ 不会写LCT-。-,分块水过 记录多少次能跳出自己的块,和跳到的点是哪个 修改时更改本块x之前的部分 统计时模拟一遍就可以了 LCT题解可以看这个人 代码如下: #include #include #include #define N 200050 using namespace std; inline int read(){ int x=0,f=1;char...
阅读(76) 评论(0)

BZOJ[3343]教主的魔法 分块+二分

传送门ber~ 分块题 构造:每个块排遍序,块大小为n−−√\sqrt n 加值:给完整的块打标记,不完整的块暴力重构(重新排序) 查询:在每个完整的块中二分查找,不完整的快中暴力判断 代码如下: #include #include #include #include #define N 1000050 using namespace std; inline int read(){...
阅读(34) 评论(0)

BZOJ[2724][Violet 6]蒲公英 分块

题目链接 求区间众数,最暴力的方法就是枚举区间所有的数,枚举时顺便更新 妥妥TLE 可以用分块来优化,先将初始数列离散化,发现区间众数只可能是所有完整的块组成的区间的众数和不完整的块中的数 可以预处理出数组sumi,jsum_{i,j}表示在前jj个块中数字ii出现了多少次,fi,jf_{i,j}表示第ii块到第jj块的众数是多少 统计时枚举不完整的块中的数,初始的出现次数(numnum...
阅读(80) 评论(0)

BZOJ[2733][HNOI2012]永无乡 Splay启发式合并

题目链接题目大意及线段树合并解法在这里每合并两个点,将它俩启发式合并 启发式合并,即把小的暴力往大的那里插 说按前序遍历插复杂度会极其优越??第k大是平衡树基本操作代码如下:#include #include #include #define N 100050 using namespace std; inline int read(){...
阅读(53) 评论(0)

BZOJ[2733][HNOI2012]永无乡 线段树合并+并查集

题目链接 题目大意:给你n个点,每个点有权值k,现有两种操作:将两个点所在联通块合并,查询某个点所在联通块权值第k小是哪个数 Splay启发式合并解法在这里这题输出的是点的编号不是点的值…. 对于每个点,开个权值线段树,合并操作用并查集查找,线段树合并 查询操作是权值线段树基本操作,找第kk小的数时,如果左儿子的数超过k个就在左儿子里,否则去右儿子找第k−ls−>sizk-ls->siz的数...
阅读(59) 评论(0)

BZOJ[3196]Tyvj 1730 二逼平衡树 树套树

题目链接线段树套平衡树 对于opt=1,在每个区间找出所有比k小的数,求和+1即为k的排名 对于opt=2,二分排名为k的值,如果该数存在的话答案就是这个数,不存在答案则为它的前驱 对于opt=3,在平衡树上删除再添加即可 对于opt=4,5,每段区间找一个,求他们的max/min即可一些细节:对于Splay删除操作,我询问了一些dalao的做法,这里选择了一个比较高效的,即将它的前驱Spl...
阅读(49) 评论(0)

BZOJ[2743][HEOI2012]采花 树状数组

题目链接因为一段区间必须需要有两个颜色相同的点才有贡献 换句话说,只有第二个点才会有贡献考虑离线,按询问按左端点从小到大将排序 用nexinex_i表示ii号点下一个相同颜色点的位置,firifir_i表示ii号颜色第一个出现的位置开一个树状数组aa 先将每个nexfir[i]nex_{fir[i]}在树状数组上+1 从左到右移动指针ll,同时处理所有左端点为ii的询问,统计l→rl \to...
阅读(38) 评论(0)

BZOJ[4327]JSOI2012 玄武密码 AC自动机

题目链接将每个字串插入AC自动机中,用主串上去匹配,每个走过的点x都是主串的一个前缀因为一个点的Fail一定是它的后缀,这样沿着x的Fail一直向上爬就可以标记出每一个出现的子串(前缀的后缀,就是原串的一个字串),遇见标记过的就停止,这样保证每个点只被走一次插入子串时,记录每个子串的结束位置,统计时沿着每个字串的结束点一直向上爬,找到第一个被标记的点就是最长的前缀 注意这里的向上爬的意思是向上爬树...
阅读(42) 评论(0)

BZOJ[1823][JSOI2010]满汉全席 2-SAT

题目链接http://www.lydsy.com/JudgeOnline/problem.php?id=1823满式和汉式不能同时选 对于每一个要求x,y,不做x就要做y,不做y就要做x,连边 Tarjan判断是否有一种食材既要做满式,又要做汉式(在一个强连通分量中),如果有,则为BAD 其他情况都是GOOD代码如下:#include #include...
阅读(37) 评论(0)
93条 共5页1 2 3 4 5 ... 下一页 尾页