• avatar 一只橘橘猫 2019-05-01 11:11:00

    multiset的应用

    multiset 和set差不多 ,但是可以存储多个一样的元素

    来自 一只橘橘猫
    0 0
  • avatar 复杂的哈皮狗 2019-02-18 09:42:00

    bzoj1741 [Usaco2005 nov]Asteroids 穿越小行星群 最小点覆盖

    链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1741 思路 消除所有的小行星 每个点(x,y)只有选择x或者y才能被覆盖 二分图最小点覆盖=最大流 首先,最小顶点覆盖一定>=最大匹配,因为假设最大匹配为n,那么我们就得到

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-16 18:54:00

    SP10707 COT2 - Count on a tree II 莫队

    链接 https://vjudge.net/problem/SPOJ-COT2 https://www.luogu.org/problemnew/show/SP10707 思路 dfs欧拉序转化为普通莫队(并不算树上莫队,不过也可做) 好神仙啊,原来欧拉序是可以求任意两点的点,不过要加lca。

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-14 11:14:00

    GCD与莫比乌斯反演的勾当

    目录 机房最后一个学懵逼钨丝的人 题目一 题目 bzoj1101 机房最后一个学懵逼钨丝的人 题目一 链接 题目没找到 求\(\sum_{1}^{n}\sum_{1}^{m}gcd(i,j)\)

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-13 10:05:00

    2870: 最长道路tree

    链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2870 思路 先把树转化为二叉树 再链分治 %%yyb 代码 #include <iostream> #include <algorithm> #include

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-12 14:40:00

    bzoj2152: 聪聪可可 点分治

    链接 https://www.lydsy.com/JudgeOnline/problem.php?id=2152 luogu爆搜都能过,总时间超过100ms就是写错了 思路 直接mod上面跑点分治就行了,又是模板 代码 #include <cstdio> #include &l

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-12 09:14:00

    bzoj2599: [IOI2011]Race

    链接&&题面 https://www.lydsy.com/JudgeOnline/problem.php?id=2599 思路 没啥思路,就是模板题 只不过顺便维护桶的时候维护一个最小边数 不过最气人的是 我用手写栈会RE,会WR,会运行错误 我用stl的queue会wro

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-11 06:29:00

    点分治

    1 点分治好难写呀 写的变量好多,太乱了,一点也不优美 代码 #include <bits/stdc++.h> using namespace std; const int N=1e5+7; int read() { int x=0,f=1;char s=getchar()

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-10 16:50:00

    bzoj3262: 陌上花开 树套树

    链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3262 思路 CDQ版本稍后再说 二维偏序排序用树状数组求就可以 而三维之后就不可以了,但我们可以在BIT上维护一个功能强大的treap 维护多出来的一维c BIT套treap a

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-10 15:29:00

    bzoj 1251: 序列终结者 平衡树,fhqtreap

    链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1251 思路 好简单的模板题 不过还是wrong了好几发 叶子节点要注意下,不能使用 遇到就不管 写的fhq-treap,OI中常数最大的平衡树,中间还T了一发 代码 #include

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-09 21:57:00

    [SDOI2016]游戏 树剖+李超树

    目录 链接 思路 update 代码 链接 https://www.luogu.org/problemnew/show/P4069 思路 树剖+超哥线段树 我已经自毙了,自闭了!!!! update 上次抄了没认真看,这次考

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-08 22:05:00

    牛客竞赛&amp;&amp;mjt的毒瘤赛

    题目链接 https://ac.nowcoder.com/acm/contest/368/F 思路 询问可以离线。 然后每个节点上建32个权值线段树(权值不大,其实只要20颗) 记录每一位权值为x(如果是根节点的话)的01和 然后从根节点向上合并。 访问到需要访问的就查询。 大体这样,不过细节

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-08 21:50:00

    P4097 [HEOI2013]Segment(李超树)

    链接 https://www.luogu.org/problemnew/show/P4097 https://www.lydsy.com/JudgeOnline/problem.php?id=3165 思路 还是模板超哥线段树 注意没有斜率的时候 还有貌似卡精度了,long doule不行,需

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-07 16:53:00

    二次剩余&amp;&amp;Cipolla

    目录 二次剩余 勒让德符号(legendre symbol) Cipolla's Algorithm. 代码 end 二次剩余 给定y和奇质数p,求x,使得\(x^2≡y(mod p)\) 勒让德符号(legendre s

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-07 09:36:00

    Pollard Rho大质数分解学习笔记

    目录 问题 流程 代码 生日悖论 end 问题 给定n,要求对n质因数分解 普通的试除法已经不能应用于大整数了,我们需要更快的算法 流程 大概就是找出\(n=c*d\) 如果\(c\)是素数,结束,不是继续递归处理。 具

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-04 21:03:00

    Miller_Rabin整理笔记

    目录 问题 别的 正事 代码 问题 一个数到底是不是素数 别的 首先列一下我们可以求素数的东西 根号暴力求 \(O(nloglogn)\)的埃氏筛 \(O(n)\)的欧拉筛 还有我们要学习的Miller_Rabin算法 对了,还

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-15 19:57:00

    SDOI2017相关分析 线段树

    题目 https://loj.ac/problem/2005 思路 \[ \sum_{L}^{R}{(x_i-x)^{2}} \] \[ \sum_{L}^{R}{(x_i^2-2*x_i*x+x^{2})} \] \[ \sum_{L}^{R}{x_i^2}-2*x*\sum_{L}^{

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-02-12 14:35:00

    3545: [ONTAK2010]Peaks 平衡树,最小生成树

    链接 https://www.lydsy.com/JudgeOnline/problem.php?id=3545 离线询问,按照权值排个序 就是在克鲁斯卡尔时候维护个treap,到时候挨个查询一下就好了 nb的gzy说要要在线才是呢,nb 代码 /********************

    来自 复杂的哈皮狗
    0 0
  • avatar 一只橘橘猫 2019-02-26 22:55:00

    母函数详解

    在数学中,某个序列的母函数(Generating function,又称生成函数)是一种形式幂级数,其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。 母函数———把组合问题的加法法则和幂级数的的乘幂的相加对应起来 我们从经典的砝码的例子讲起 题目:有1g 2g

    来自 一只橘橘猫
    0 0
  • avatar 复杂的哈皮狗 2019-02-10 16:59:00

    P1552 [APIO2012]派遣

    链接 https://www.luogu.org/problemnew/show/P1552 思路 忍者数量肯定越多越好 那就从下到上的合并它的孩子 左偏树的话 顺便维护一个tot,大头堆,如果tot大于了m,把大的删掉 如果左偏树忘干净了或者没学的话 线段树合并也是个不错的选择 直接权值线段

    来自 复杂的哈皮狗
    0 0
  • avatar 一只橘橘猫 2019-02-26 13:12:00

    HDU-2602 Bone Collector——01背包

    首先输入一个数字代表有n个样例  接下来的三行 第一行输入n  和  v,代表n块骨头,背包体积容量为v。 第二行输入n块骨头的价值 第三行输入n块骨头的体积 问可获得最大的价值为多少 核心:关键在于dp【j】=max(dp[j],dp[j-w[i]]+v[i]) 的状态转移!! 背包

    来自 一只橘橘猫
    0 0
  • avatar 一只橘橘猫 2019-02-25 19:40:00

    ZOJ - 3747 Attack on Titans

    题意就是输入三个数字 n m k,  给n个士兵排队 每个士兵三种G,R,P可选,求至少有m个连续的G士兵和最多有k个连续的R士兵的排列总和   分析题意:在n个士兵中至少有m个连续的G士兵和最多有k个连续的R士兵的排列总和 就等于 (在n个士兵中最多有k个连续的R士兵和最多有n个连续的G士

    来自 一只橘橘猫
    0 0
  • avatar 复杂的哈皮狗 2019-02-08 15:22:00

    bzoj1568 [JSOI2008]Blue Mary开公司

    题目链接 https://www.lydsy.com/JudgeOnline/problem.php?id=1568 https://www.luogu.org/problemnew/show/P4254 思路 超哥线段树模板题 若当前线段完全高于标记线段,则将当前线段进行标记 若当前线段完全

    来自 复杂的哈皮狗
    0 0
  • avatar 一只橘橘猫 2019-02-18 11:30:00

    CF 429B B.Working out 四个角递推

    B. Working outtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputSummer is coming! It's time for Ia

    来自 一只橘橘猫
    0 0
  • avatar 复杂的哈皮狗 2019-02-04 21:02:00

    bsgs整理

    目录 bsgs问题 或 poj2417: 概述 代码 exbsgs 鸣谢 \(gzy gzy gzy\) bsgs问题 或 poj2417: 给定质数\(p\),给定\(a\),\(b\),\((a,p)=1\) 求出最小的

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-01-13 18:57:00

    bzoj4709 柠檬 单调栈,DP,斜率优化

    目录 思路 错误 代码 /* 思路 s是值等于a[i]的前缀和 转移方程$f[i]=max(f[i],f[j-1]+a[i]*(s[i]-s[j]+1)*(s[i]-s[j]+1))$ 不难写出暴力方程(by wxyww) //@baol

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-01-12 10:20:00

    bzoj 3437 小p的农场

    bzoj 3437 小p的农场 思路 \(f[i]=min(f[j]+\sum\limits_{k=j+1}^{i}{b[k]*(i-k)}+a[i])\) \(f[i]=min(f[j]+\sum\limits_{k=j+1}^{i}{(b[k]*i-b[k]*k)}+a[i])\) 再来前缀

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2019-01-04 22:01:00

    luoguP4072 [SDOI2016]征途

    [SDOI2016]征途 大体 大概就是推推公式,发现很***的\(n^3\)DP get60 进一步我们发现状态不能入手,考虑优化转移 套个斜率优化板子 每一层转移来一次斜率优化 思路 先便便式子 \[s^2=m^{2}*\frac{\sum_{1}^{m}(a_{i}-\overline

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-28 09:40:00

    P2761 软件补丁问题

    P2761 软件补丁问题 思路 貌似不用网络流,直接状态压缩 用spfa跑最短路,直接判断是否能过 位运算太渣了,WA了好几发 代码 #include <bits/stdc++.h> using namespace std; const int N = 21, M = 101,

    来自 复杂的哈皮狗
    0 0
  • avatar 一只橘橘猫 2019-02-25 21:07:00

    java 大数详细讲解

    介绍 java中用于操作大叔的类主要有俩种 第一个是BigInteger,代表大整数。第二个是BigDecimal,代表大浮点数。两种类的操作方法类似,所以我们只讲解BigInterger的用法 基本用法 Scanner input = new Scanner(System.in); Big

    来自 一只橘橘猫
    0 0
  • avatar 复杂的哈皮狗 2018-12-28 08:24:00

    12.27 cf div3 解题报告

    12.27 cf div3 解题报告 wxy.wxy,带上分拉,全场做了个无脑小白 比赛场地 A: T1,跟着模拟就好了 B: sort一遍之后 去除的数一定是a[1]或者a[n] 比较去除谁小就输出谁 C: 他的二进制有多少个1 如果>k说明无解 他的二进制位都放优先队列里

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-27 12:14:00

    网络流24题 P2754 [CTSC1999]家园

    思路 如图,建立分层图跑dinic 每次在残余网络里加边继续跑 跑到ans>=k时候的i就是答案 诶呀啊,忘记弄箭头了,最后一列是向上的箭头,不过聪明的你们应该没啥影响 代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(i

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-26 20:18:00

    P2147 [SDOI2008]洞穴勘测

    P2147 [SDOI2008]洞穴勘测 思路 没办法,我就是喜欢板子都想发的人 都是基础操作,不多说了 代码 #include <bits/stdc++.h> #define ls ch[x][0] #define rs ch[x][1] #define FOR(i,a,b)

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-26 20:15:00

    P3203 [HNOI2010]弹飞绵羊

    P3203 [HNOI2010]弹飞绵羊 思路 每个点都往后面连边 所以肯定没有环 超过n的算连向n+1 n+1个点,n条边,没有环,一定联通 那就差不多是个树了 然后就LCT模拟他的操作就行 有比较简单的LCT做法,不过我还是喜欢无脑一点的 错误 cut操作x写错i 代码 #inclu

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-26 20:09:00

    P4172 [WC2006]水管局长

    P4172 [WC2006]水管局长 前言 luogu数据太小 去bzoj,他的数据大一些 思路 正着删不好维护 那就倒着加,没了 LCT维护他的最小生成树MST 树上加一条边肯定会有一个环 看看环上最大值和加边的大小 然后选择加不加,改不改 错误 哇,恶心撒 怼着题解都写不出来 最后乱

    来自 复杂的哈皮狗
    0 0
  • avatar 一只橘橘猫 2019-01-25 17:06:00

    now code寒假练习赛2——处女座的砝码(找规律题+高精度题)

    #include <bits/stdc++.h> #define ll long long using namespace std; int main() { long double n ; cin>>n; long double sum=1,coun

    来自 一只橘橘猫
    0 0
  • avatar 一只橘橘猫 2019-01-22 21:21:00

    now code——小a和黄金街道(欧拉函数和快速幂模板)

    小a和小b来到了一条布满了黄金的街道上。它们想要带几块黄金回去,然而这里的城管担心他们拿走的太多,于是要求小a和小b通过做一个游戏来决定最后得到的黄金的数量。游戏规则是这样的:假设道路长度为米(左端点为,右端点为),同时给出一个数(下面会提到的用法)设小a初始时的黄金数量为,小b初始时的黄金数量为小

    来自 一只橘橘猫
    0 0
  • avatar 一只橘橘猫 2019-01-25 17:25:00

    高精度题目(10的1000次方的数)

    1.用java import java.math.BigInteger public class Main{   public static void main(){       Scanner input = new Scanner(System.in);      BigI

    来自 一只橘橘猫
    0 0
  • avatar 复杂的哈皮狗 2019-01-13 20:13:00

    一个数的(勾股数)组

    大概 一开始还以为是勾股 的数组呢、、 题目-->codeforces 求一个数所在的任意勾股数组 算了,不胡扯扯了,还是看原博客吧 应该是中国人写的,翻译友好 #include <iostream> #define ll long long using namespace s

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-26 20:28:00

    P3690 【模板】Link Cut Tree (动态树)

    P3690 【模板】Link Cut Tree (动态树) 思路 candy 不是太掌握 也落落不太清楚 自己学习吧 lmc讲的时候睡着了 #include<bits/stdc++.h> #define ls c[x][0] #define rs c[x][1] const int

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-26 20:05:00

    P3979 遥远的国度

    P3979 遥远的国度 思路 一开始我用这个函数得到左端点 int get_l(int x,int y) { if(top[x]==top[y]) return son[x]; int last=top[x]; while(top[x]!=top[y]) {

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-26 19:59:00

    P3128 [USACO15DEC]最大流Max Flow

    思路 这个题哪里有那么费脑筋 我们可以树链剖分嘛LCT昨天学的时候睡着了,不是太会 两遍dfs+一个5行的BIT 其实树链剖分学好了对倍增和LCT理解上都有好处 一条路径上的修改 由于一条剖出来的链是连续的,我们要选择数据结构维护 不过这里不用维护太多东西,只是区间+1 我们可以选择常数小,好写的

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-26 19:56:00

    P3178 [HAOI2015]树上操作

    P3178 [HAOI2015]树上操作 思路 板子嘛,其实我感觉树剖没啥脑子 就是debug 代码 #include <bits/stdc++.h> #define int long long #define ll long long #define ls rt<<

    来自 复杂的哈皮狗
    0 0
  • avatar 哦咧 2019-07-18 18:38:27

    2019牛客暑期多校(一)题解

    传送门:https://ac.nowcoder.com/acm/contest/881#question A.Equivalent Prefixes 单调栈求每个i所能影响的最左端(思考下为什么不用考虑右端)。 #include<iostream> #include&

    来自 哦咧
    2 0
  • avatar Free-Fly 2019-07-18 18:39:46

    sublime text3 搭建c++/c环境

    sublime搭建的c++/c使用很方便,实用性很强,自己阅览了无数的博客,csdn,博客园的都看了,最后还是自己摸索着搭建成功了,如果觉得还不错请给个评论谢谢。(提前声明本人专利不允许转载!!!!) 转载备注地址:https://www.cnblogs.com/luhongkai/p/981

    来自 Free-Fly
    0 0
  • avatar 复杂的哈皮狗 2018-12-26 17:35:00

    SP6779 GSS7

    GSS7解题报告 前言 唔,有点恶心哪,废了两个多小时debug 思路 很容易看出傻子都知道,这个是树链剖分+线段树的裸题,只不过是恶心了点,这里重点讲一下细节问题 线段树 做过GSS系列的都应该很熟悉了 线段树维护的前缀最大子段和,后缀最大子段和,和区间最大子段和 那么我们就可以很容易

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-25 21:49:00

    luogu P2486 [SDOI2011]染色

    树剖做法: 就是两个dfs+一个线段树 难度的取决基本==线段树的维护难度 所以对有点线段树基础的,树剖也不难做吧 这里操作有二 一:两点间路径染***r> 线段树的区间赋值操作 二:查询路径段的个数 考虑线段树如何做 我们发现两端区间的合并取决于他们相连接的那两个颜***r> 比如这张

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-24 09:51:00

    CF 1087解题报告

    cf解题报告 记录一下吧 做出:T1 rating :-97 想起几个月前做不出T1还是有点小搞笑呀2333 T1 双指针+特判 T2 发现k特别小,枚举剩余系 还要判断是否是能被n整除 移项发现可以算出整除是多少 然后\(整除*k+剩余数=n\)算出答案,复杂度\(O(k)\) T3

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-21 11:12:00

    后缀自动机

    https://oj.zrt.io/problem/44 比较容易懂得文档 新浪

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-21 08:17:00

    poj2774

    思路 求出height之后 只要相邻两个子串是本串不同的来更新就好 因为这样一定是最优啊、、取min显然越长越不好 (这里'%'当成‘{’吧) abc%bca height i sa belong 0 1 a 7 2 1 2 abc

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-20 14:35:00

    poj1743

    思路 不得不说,罗穗骞太厉害了 他写的论文比哪一篇博客都好 去看吧,也别看我的了 里面有这题目详解 论文 代码 // 不得不说,罗穗骞nb哇,%%%%%%%%% /* 0 0 1 1 2 2 3 3 4 10 1 2 3 4 5 1 2 3 4 5 差分 1 1 1 1 0 1 1 1 1

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-18 20:07:00

    luogu P4051 [JSOI2007]字符加密

    前言 其实就是个后缀数组模板题 可还是有几个的地方不太明白 思路 先将子串复制一遍,组成长度为2*n的子串 给出的子串一定会在前n个后缀 而且后面的优先级不会影响前面的相对大小 然后求得sa输出就好 输出的时候把没有必要输出的忽略掉就好 代码 #include <bits/stdc+

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-18 17:11:00

    后缀数组学习笔记

    目录 前置 重点及其目标 分析目标&&正题 代码 前置 纯属博主虎的的 罗穗骞2009NOI集训队论文 还是原版的最明白啊 先了解基数排序和倍增求sa思想 并且有一定的看别人博客的基础(对,没错,就是这么不要脸) 基

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-18 11:43:00

    ## 基数排序--------无人问津的优秀算法

    基数排序--------无人问津的优秀算法 在这个被stl的sort独霸的c++世界(毕竟stl的sort太过好用) 似乎所有普通排序算法都被挤到了一边,但毕竟各有各的优点 这个排序算法还是不错的 但最近学习后缀数组的时候遇到了这个算法,就简单学习一下吧 介绍 多关键字排序中有两种方法:最高位

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-17 10:34:00

    luogu P5105 不强制在线的动态快速排序

    前言 考试的时候居然想错了区间贡献,mdzz 思路 题目看着很方啊,难道要树套树? 但数据范围提醒我们,是nlogn的复杂度 Sort(S)的定义是不是很鬼畜 但我们不动脑子的打表容易发现 连续区间[1,n]内\(a_i^2-a_{i-1}^2\)为连续的奇数 (其实这里直接用初中的完全平方公

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-26 19:52:00

    [SDOI2014]旅行

    P3313 [SDOI2014]旅行 思路 有点恶心咯 每个信仰开一颗线段树记录 修改或者查询的时候去那一颗信仰线段树中查询就好 必须动态开点线段树 没有区间修改还算好写 错误 查询跳链写错了 #include <bits/stdc++.h> #define FOR(i,a,b

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-26 19:48:00

    [HEOI2016/TJOI2016]树

    [HEOI2016/TJOI2016]树 思路 做的时候也是糊里糊涂的 就是求最大值的线段树 错误 线段树写错了 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;++i) using namespa

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-14 20:23:00

    luogu1975 [国家集训队]排队

    思路 序列中 |i | 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| |----|--|--|--|--|--|--|--|--|--|--| |a[i]| a| b| c| L| d| e| f| R| g| h| 现逆序对为ans,要交换L,R 则\([1,3],[9,10]\

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-13 10:37:00

    luogu P2713 罗马游戏

    思路 模拟就好 左偏树合并 并查集寻找 代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;++i) using namespace std; const int maxn=1000005; int

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-12 16:27:00

    luogu P3168 [CQOI2015]任务查询系统

    思路 又是强制在线--主席树 每一次操作建一棵树 但实际用的的rt只有n个 所以实际内存是n230 我见到只开n*30的,不会, 错误 debug 以为每一秒建立一颗树 第一次 query没有递归 第二、三次 权值线段树的查询处理,就是到叶子节点的处理 代码 // luogu-judger

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-12 10:41:00

    luogu P2633 Count on a tree

    思路 强制在线--主席树 以1为root建主席树 (就是在树上建树,差不多) rt[i]就是1到i的路径上的一棵树的root 其实我感觉,主席树之间的运算差不多于加减 类似lca的运算 root(1到x)+root(1到y)-root(lca)-root(fa[lca]) 查询他们的第k小就OK

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-11 21:58:00

    luogu P2617 Dynamic Rankings

    前置知识: 普通主席树,树状数组 大概 待修主席树 和静态的一样 只不过还要加一颗树 来维护你修改的值 这棵树就是是树状数组,每个节点上再维护一颗动态开点线段树 (就是所说的树套树,不过没啥可怕的,就是麻烦一丢丢) 查询的时候老样子 不过要多加上树状数组中的值罢了 代码还算好些,如果 主席树,

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-11 12:28:00

    P3380 【模板】二逼平衡树(树套树)

    思路 若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名 若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数 若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k 若opt=4 则为操作4,之后有三个数l

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-10 21:53:00

    P4556 [Vani有约会]雨天的尾巴

    目录 思路 优化 过程中的问题/疑问 错误 代码 思路 每个节点维护一课线段树(当然是动态开点) 线段树的作用是统计这个节点有多少种粮食型号,以及最多的粮食型号 然后树上差分,u和v点 +1,lca(u,v)和f[lca(u

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-10 16:33:00

    luogu P3605 [USACO17JAN]Promotion Counting晋升者计数

    题目链接 luogu 思路 可以说是线段树合并的练手题目吧 也没啥说的,就是dfs,然后合并、、、 看代码吧 错误 和写主席树错的差不多 都是变量写错、、、、 代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-10 14:20:00

    线段树合并学习笔记

    顾名思义 就是两颗线段树合成一个线段树 那合成的线段树是适合所有线段树吗 当然不是,是动态开点线段树 建树 这里建n个节点的时候,每个节点建一棵树 而且要按照一定的形态建立一条链 就是说如果最终形态是有n个数字的树, 那你初始化的那一条链子一定是这颗树上扣下来的 这样才方便合并 merge操

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-10 10:19:00

    luogu1110[ZJOI2007]报表统计

    思路 这里的初始化就不讲了,看完操作讲解就应该明白了,再不行就去看代码 对于操作1 由于操作2的需要,vector[n]存下数 对于操作2的维护 查询相邻两个元素的之间差值(绝对值)的最小值 先把所有答案存入一个小头堆里 比如 a,c之间你要插入b 那么,你就要删除|c-a|,然后加入|a

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-09 21:40:00

    P3224 [HNOI2012]永无乡

    思路 并查集+fhqtreap 合并的时候由于是大小不一,所以不能直接合并 所以我们就暴力合并喽 对,就是那种很暴力的把小的往大的身上靠 他们说是启发式合并 抄一波博客 启发式合并 启发式合并核心思想就一句话:把小集合的合并到大的里。 启发式合并思想可以放到很多数据结构里,链表、线段树、甚至平衡

    来自 复杂的哈皮狗
    0 0
  • avatar 复杂的哈皮狗 2018-12-20 21:24:00

    4698: Sdoi2008 Sandy的卡片

    前言 总之这个东西说起来很麻烦就是了, 思路 差分合并+后缀数组+二分(dddl) 类似于那个bzoj1031的复制子串和那个poj1743的差分 来看个例子 3 5 1 2 3 4 5 4 1 1 1 2 4 1 2 3 4 变成了这个(最后一个INF最好删掉吧,应该不影响的吧)

    来自 复杂的哈皮狗
    0 0