litmxs-CSDN博客

原创 C++学习笔记

C++学习笔记C++里面比较重要、或比较难记住、或比较复杂的一些知识点一些太简单的就没写在这里了页码来自C++ Primer Plus（第6版）中文版 C学习笔记函数模版格式显式实例化 p288具体化 p288完全具体化部分具体化非类型模版参数匹配 p289强制选择 p293关键字 decltypec11 p295后置返回类型c11 p297存储说明符regist

2017-04-03 13:58:07 1558 2

原创上下界网络流

来自： https://blog.csdn.net/linkfqy/article/details/74779656无源汇上下界可行流构建虚拟源点SS，虚拟汇点TT 若i点原来入>出，则SS向i连一条容量为其差值的边若i点原来出>入，则i向TT连一条容量为其差值的边因为一条边最终流量等于下界+新图对应流量，原来流量不平衡的点需要用虚拟源汇来补偿流量因为...

2018-09-15 18:19:38 223

原创线性素数筛模板

const int MAXN = 1e8+1000;int prime[MAXN/10];bool is_prime[MAXN+1] = {0};int getprime(int n){ int tot = 1; prime[0] = 2; is_prime[2] = true; for(int i=3; i<=n; i+=2) is_prime[i...

2018-09-15 18:14:24 233

原创 ACM-ICPC 2018 焦作赛区网络预赛 E. Jiu Yuan Wants to Eat 树链剖分线段树

题目链接:Jiu Yuan Wants to Eat题目大意一颗树，n各节点(n≤105n≤105n \leq 10^5)每个节点上有一个值aiaia_i(ai≤264)ai≤264)a_i \leq 2^{64}) 有四种操作 1. 将u到v路径上所有节点值乘以x(x≤264)x≤264)x \leq 2^{64}) 2. 将u到v路径上所有节点值加上x(x≤264)x≤264...

2018-09-15 18:07:36 282

原创 [HDU 6430] 2018 Multi-University Training Contest 10 Problem E. TeaTree 暴力 bitset

题目链接:Problem E. TeaTree题目大意一颗树, 每个节点上有一个小于等于1e5的数字, 然后每个节点的值等于所有以它为LCA 的节点对(i, j)中gcd(v[i], v[j])的最大值, 要求输出所有节点的值思路一开始想到用bitset记录每个节点的所有因数, 但TLE了, 没想到G++的bitset有一个函数叫做_Find_first()能快速找到为1的最低位,...

2018-08-22 18:35:16 284

原创 Treap kth rank 模版

#include &lt;bits/stdc++.h&gt;using namespace std;const int maxn = 1e5 + 100;struct Node{ Node * ch[2]; int r, v, s; Node (int v = 0): v(v) { ch[0] = ch[1] = nullptr; ...

2018-08-20 11:29:35 206

原创差分标记

次数 a1a1a_1 a2a2a_2 a3a3a_3 a4a4a_4 a5a5a_5 通项一次 1 1 1 1 1 an=1an=1a_n = 1 二次 1 2 3 4 5 an=nan=na_n = n 三次 1 3 6 10 15 an=n(n+1)2an=...

2018-08-05 12:28:47 320

原创牛客网暑期ACM多校训练营（第五场）F take 线段树概率

题目链接: F take题目大意有n个箱子, 每个箱子里面有p[i]/100的概率有一个大小为d[i]的钻石一开始你手上的钻石大小为0, 你从第一个箱子开始, 依次打开每一个箱子, 如果箱子里面的钻石大小比你手上的大, 那就拿起箱子里的钻石替换自己的, 求最后替换次数的期望思路考虑第i次开箱子, 箱子里钻石比你手上的大的概率为, 当前钻石比d[i]小的概率*开箱子开出钻石的...

2018-08-02 19:03:39 204

原创牛客网暑期ACM多校训练营（第五场）E room 费用流

题目链接: E room题目大意4n个学生, 每四个人一个寝室, 告诉你原先每个人在那个寝室, 然后告诉你n个小组, 每组四个人, 要让每个小组的人在同一个寝室, 求怎么换寝室使得最少的人需要换寝室 n<=100思路很容易看出来是网络流, 接下来就是如何建图了把4n个学生每个学生当作一个结点, 再拿n个结点当做小组(小组内4个人要在一个宿舍), 将四个小组成员向小组连边...

2018-08-02 18:31:40 271

原创组合数模板

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e5 + 100, mod = 1e9 + 7;ll inv[maxn], fac[maxn], finv[maxn];//逆元，阶乘，阶乘逆元void init(){ inv[1] = 1; ...

2018-08-02 10:09:08 129

原创 HDU 6333 2018 Multi-University Training Contest 4 1002 Problem B. Harvest of Apples 组合数学莫队算法

题目链接:HDU 6333 Harvest of Apples题目大意Ｔ组询问（T≤105T≤105T \leq 10^5)，每次询问求Ｓ(n,m)=∑mi=0C(n,m)mod(109+7)Ｓ(n,m)=∑i=0mC(n,m)mod(109+7)Ｓ(n, m) = \sum_{i=0}^{m} C(n, m) mod (10^9+7)思路可以得出： S(n, m) = ...

2018-08-02 10:07:27 156

原创牛客网暑期ACM多校训练营（第四场）J Hash Function 拓扑排序线段树

题目链接: J Hash Function题目大意一张hash表，长度为n，哈希函数为hash(x) = x mod n，如果有冲突，则位置向后移一位（n-1的下一位是0）现在给你一张hash表，要求出字典序最小插入顺序思路如果a[i]%n != i，说明在a[i]插入前，a[i]%n到i-1所在的位置已经被占用了，也就是说区间[a[i]%n, i-1]中的数字必须在a...

2018-07-30 09:58:29 237

原创 ext/rope和ext/pb_ds库

官方文档堆#include&lt;ext/pb_ds/priority_queue.hpp&gt;using namespace __gnu_pbds;__gnu_pbds::priority_queue&lt;node,less&lt;node&gt;,pairing_heap_tag&gt; pq;//如果using了std, 必须显示表面名称空间__gnu_pbdsjoin...

2018-07-27 16:37:25 1258

原创 2018 Multi-University Training Contest 2 1003 Cover 图论欧拉通路

题目链接: 1003 Cover题目大意一张无向图，n个节点，m条边，没有重边和自环，不一定连通，求最少多少条路径能覆盖这张图所有边，每条边只能被一条路径覆盖思路将图中每个联通块的奇点（度数为奇数的点）找出来，如果有两个或两个以下的奇点，则为欧拉图，可以一笔画，否则将从第三个奇点开始，将奇点们两两连接起来，让这张图变成欧拉图，求其欧拉通路，将后来新增的奇点连边删除后，得到的路径...

2018-07-26 09:55:44 142

原创 2018 Multi-University Training Contest 2 1007 Naive Operations 线段树区间更新区间查询

题目链接:1007 Naive Operations题目大意两个数组a和b，长度为n，a一开始全都是0，b里面是1-n的排列有两两种操作 add l, r : 将a数组[l, r]内所有元素+1 query l, r : 求∑ri=l⌊aibi⌋∑i=lr⌊aibi⌋\sum_{i = l}^{r} \lfloor \frac{a_i}{b_i} \rfloor思路线...

2018-07-25 17:33:20 125

转载小球和盒子

from: https://blog.csdn.net/jaihk662/article/details/79572685 问题列举：把n个不同的小球放在m不同的个盒子里，有空盒把n个不同的小球放在m不同的个盒子里，无空盒把n个不同的小球放在m相同的个盒子里，有空盒把n个不同的小球放在m相同的个盒子里，无空盒把n个相同的小球放在m不同的个盒子里，有空盒把n个相同的小球放在m不同的个...

2018-07-25 09:44:18 482

原创 2018 Multi-University Training Contest 1 1008 RMQ Similar Sequence 笛卡尔树概率

题目链接:1008 RMQ Similar Sequence题目大意rmq(a, l, r)表示a[l-r]中最大值的下标，如果有相同的数字，取下标小的定义rmq相似，如果两个数组a, b长度相同，对于所有[l, r]，都有rmq(a, l, r) == rmq(b, l, r)则abrmq相似现在给你一个数组a，有一个数组b长度与a相同，且每一个元素都是从[0, 1]之间独...

2018-07-24 13:06:13 177

原创 2018 Multi-University Training Contest 1 1004 Distinct Values

题目链接:1004 Distinct Values题目大意一个数列, 长度为n, 有m个特征[l, r], 表示区间内所有数字都不重复思路用一个数组pre[i], 表示上一次数字i在数组中出现的位置将所有特征排序, 先按l从小到大排序, 如果l相同, 按r从大到小排序(这样如果区间相互包含的情况只需要处理一次最大的那个区间, 小的区间跳过就好了) 然后遍历所有特征, 对于...

2018-07-23 22:20:05 329

原创 Balanced Sequence HDU 6299 2018 Multi-University Training Contest 1 1002 Balanced Sequence 贪心排序

题目链接:1002 Balanced Sequence题目大意给你n个括号序列, 你可以重新排序这些序列, 然后拼接起来, 求最大的合法括号子序列思路先将每个序列的可以匹配的括号去掉, 最后剩下一个类似”))))(((“的序列, 用一个pair保存’)’和’(‘的数量, 按照’)’的数量乘以’(‘的乘机从大到小排序, 最后从第一个开始, 贪心地拼接序列, 看放到已有序列的左边还...

2018-07-23 19:17:12 181

原创牛客网暑期ACM多校训练营（第一场）E. Removal 动态规划

题目链接: E. Removal题目大意一个数组s，长度为n(n≤105)n≤105)n \leq 10^5)，数组元素s[i]≤10s[i]≤10s[i] \leq 10，要求从中删除m（m≤10)m≤10)m \leq 10)个数字，求能得到多少个不重复的结果, mod 1e9+7思路动态规划，如果不考虑重复，令dp[i][j] := 前i个数字删除j个后有多少种结果...

2018-07-21 09:55:54 397 1

原创牛客网暑期ACM多校训练营（第一场）D. Two Graphs 图论枚举全排列

题目链接:D. Two Graphs题目大意两张图G1和G2, 最多只有8个节点, 两个节点之间最多有一条边, 两张图节点个数都为n, 边数为m1和m2 求由多少种方案, 从G2中选出m1条边, 使得G1和G2重构思路枚举n个节点的全排列, 就是将G2中节点和G1的节点一一对应起来, 一共由n!中对应方案, 判断每一种方案是否可行, 如果可行, 那将方案用一个unsigned l...

2018-07-19 19:09:03 335

原创牛客网暑期ACM多校训练营（第一场）J. Different Integers 莫队算法优化

题目链接: J. Different Integers题目大意一个数组, 长度n&lt;=1e5, q次询问(l, r), 输出区间[1, l], [r, n]中不同数字的个数, q&lt;=1e5思路莫队算法, 裸题, 需要一点优化有一个重大的坑点就是l可能会大于r, 但是看到题面没有说l&lt;r我就觉得有问题了读取(l, r)的时候判断一下l和r的大小关系, ...

2018-07-19 18:57:22 353

原创牛客网暑期ACM多校训练营（第一场）题解

比赛链接:牛客网暑期ACM多校训练营（第一场）A. Monotonic Matrix题解链接:未补B. Symmetric Matrix题解链接:未补C. Fluorescent 2题解链接:未补D. Two Graphs题解链接:未补E. Removal题解链接:未补F. Sum of Maximum题解链接:未补G...

2018-07-19 18:34:55 1344 1

原创 Aragorn's Story HDU - 3966 树链剖分点权区间更新单点查询模板

题目链接：HDU - 3966题目大意一棵树，结点数为n（n&lt;=5e5)，有两种操作，将结点c1和c2路径上所有结点的权值增加或减少k，查询结点c的权值思路树链剖分，用BIT（树状数组）进行更新和查询思路 Result Time(ms) Mem(MB) Length Lang Accepted 967 16.7 244...

2018-07-18 09:36:58 160

原创 Query on a tree SPOJ - QTREE 树链剖分模板

题目链接：Query on a tree题目大意一棵树，有n个节点n<=1e4, 有两种操作：1.求节点a和b之间路径的最大权值的边；2. 将边i的权值改为ti思路树链剖分，边的权值存在儿子节点上，线段树求区间值和修改代码#include <bits/stdc++.h>using namespace std;typedef long lon...

2018-07-17 16:35:50 146

原创 Codeforces Round #484 (Div. 2) D. Shark

题目链接:D. Shark题目大意一个数组a[i], 长度为n，选一个数字k，将所有大于等于k的数字去掉，让剩下的每一段子段长度相等（且字段长度不能为0），求让子段数量最多的最小的k思路利用单调栈求出l[i]:=a[i]往左第一个大于a[i]的元素的下标，如果不存在则为0，r[i]:=a[i]往右第一个大于a[i]的元素的下标，如果不存在则为n+1 很容易看出k一定是某个a[...

2018-07-14 12:54:54 171

原创树的重心模板

删除重心后，子树的最大权值最小 dfs遍历每个点，node的所有子树除了它的儿子们还有它往父亲那个方向的一颗子树（权值=总权值-所有子树权值和-1）下面的代码权值为边权#include <bits/stdc++.h>using namespace std;const int maxn = 1e5 + 100, inf = 0x3f3f3f3f;int n, k;str...

2018-07-12 13:33:39 562

原创 Codeforces Round #378 (Div. 2) F. Drivers Dissatisfaction图论树链剖分最小生成树+最近公共祖先+倍增法或树链剖分模板

题目链接:F. Drivers Dissatisfaction题目大意无向图有n个节点，m条边，每条边有wiwiw_i（边的权值），cicic_i（让wiwiw_i减少1需要花费ci)ci)c_i)两个属性现在有预算S，可以用这些钱让一些边的权值减小（边的权值可以减少到0甚至负数）设计一个方案，减小某些边的权值，使得这张图的最小生成树的权重和最小输出最小生成树的权值和，以及最小...

2018-07-12 13:03:39 227

原创 Codeforces Round #489 (Div. 2) D. Nastya and a Game

题目链接: D. Nastya and a Game题目大意一个数组a，有n个元素，1≤n≤2⋅1051≤n≤2⋅1051 \leq n \leq 2 \cdot 10^5, 1≤a[i]≤10181≤a[i]≤10181 \leq a[i] \leq 10^{18} , 求有多少区间[l,r][l,r][l, r]满足ps=k,p=∏ri=la[i],s=∑ri=la[i],k为给定常...

2018-07-11 10:01:18 110

原创 Educational Codeforces Round 46 (Rated for Div. 2) E. We Need More Bosses 图论桥

题目链接: E. We Need More Bosses题目大意：一个无向图， n个节点， m条边，选择两个节点s和t，使得从s到t所有路径中都出现的边的数量最大（从s到t无论怎么走都必须要经过这些边）思路无向图中，在两点间所有路径出现的边为无向图的桥，将所有非桥边的权值设为0，桥的权值设为1（即将边双联通分量缩成一个点），求得出的无向图最长路径，即为答案桥与割点定...

2018-07-09 13:46:11 258

原创 Java学习笔记

Java学习笔记tags: note java writing 学习笔记Java学习笔记基本语法 (P32)基本类型Unicode (P34)运算符 (P38)String字符串 (P45)String常用方法StringBuilder常用方法 (P54)输入输出 (P55)输入输出格式化 (P58)文件输入输出 (P61)流程控制 (P63)带标签的...

2018-05-31 20:45:02 175

原创 Codeforces Round #460 (Div. 2) D. Substring

题目链接：D. Substring题目大意一张有向图，每个结点上有一个字母，定义一条路径的权值为路径中出现次数最多的字母的出现次数，求图中权值最大的路径的权值，如果权值可以无限大，输出-1思路26次DFS，，每次只统计一个字母的权值，cnt[i]记录从i点开始的路径当前字母出现的最大次数 26次DFS中所有cnt[i]的最大值就是答案如果图中有环，则权值可以无限大，可

2018-01-31 23:25:58 289

原创 Codeforces Round #459 (Div. 2) C. The Monster

题目链接:C. The Monster题目大意给你一个括号序列，包括()?三个字符，其中?可以代替()中的任意一个，求有多少区间[L, R]，使得[L, R]是合法的括号序列。思路判断一个括号序列是否合法，必须保证(和)的数量相等，并且从左往右的过程中，)的数量一定一直小于等于(的数量，否则多余的)之后永远无法匹配。从左往右判断一遍，如果)的数量大于(和?的数量，说明之

2018-01-30 13:38:20 197

原创 Codeforces Round #445 (Div. 2) D - Restoration of string 思维图论

题目链接: D - Restoration of string题目大意给你一个字符串集合, 集合中每个字符串都是原字符串中作为子串出现次数最多的子串, 求出原字符串(如果有多个输出字典序最小的)思路因为集合中的所有字符串都是出现次数最多的子串, 所以它们在原串中出现的次数应该都是一样的, 而且因为要字典序最小, 所以出现的次数肯定都为1, 所以最后的字符串中肯定不能有其他子串出现超过一次建一张有

2017-11-14 21:30:27 216

原创 Codeforces Round #439 (Div. 2) E. The Untended Antiquity hash+二维树状数组或二维线段树

题目链接: E. The Untended Antiquity题目大意一个n*m的网格, 有三种操作, 一是将包含(x1, y1)(x2, y2)两点的最小矩形套上障碍, 二是将某个障碍取消, 三是查询点(x1, x2)(y1, y2)之间是否能直接到达(之间没有障碍)思路题解的思路非常6 利用二维线段树, 对于每个障碍对应一个随机的hash值, 然后操作一则让所有矩形内所有点都加上这个值, 操作

2017-11-12 21:53:51 191

原创 Codeforces Round #439 (Div. 2) 869 C. The Intriguing Obsession

题目链接:C. The Intriguing Obsession题目大意三种颜色的点, 数量分别为a, b, c, 建边, 如果点i和点j有一条边直接相连, 那么ij的距离是1, 要求同种颜色的点距离必须大于等于3 求建边的方案总数(modulo 998 244 353)思路因为要求同色点距离大于等于3, 所以同色点之间不能建边考虑ab两种颜色的点, 如果a色点连b色点, 这个b色点再连一个a

2017-11-12 18:20:02 265

原创 Mosaic HDU - 4819 二维线段树模板

题目链接:Mosaic HDU - 4819题目大意一个n*n的矩阵, 让你求其中一个矩形区域中的最大值和最小值, 并更新其中的一个位置的值思路二维线段树代码#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <set>#include <queue>#include <ve

2017-11-12 17:56:07 297

原创 Codeforces Round #442 (Div. 2) 877 F - Ann and Books 莫队算法离散化

题目链接: F - Ann and Books题目大意n本书的序列, 第i本书有a[i]若干道数学或者经济学题目, q个询问[li, ri], 要求输出[li, ri]中, 满足”数学题总数比经济学题总数多k道”的子区间数量数据范围: 1≤n≤105,0≤a[i]≤109,−109≤k≤109,1≤q≤1051 \leq n \leq 10^5, 0 \leq a[i] \leq 10^9, -

2017-10-28 17:59:25 319

原创 BZOJ - 2038: 小Z的袜子(hose) 莫队算法模板

题目链接: 2038: [2009国家集训队]小Z的袜子(hose)题目大意一个长度为n的序列, 每个点有一个颜色, 用col[i]表示, q次询问, 每次求出[L, R]区间中随机选两个点的颜色相同的概率对于[L, R], 设区间内各种颜色的数量为a,b,c⋅⋅⋅a, b, c \cdot \cdot \cdot, 则答案为:a(a−1)2+b(b−1)2+c(c−1)2⋅⋅⋅(R−L+1)(R−

2017-10-26 19:27:46 231

原创 Codeforces Round #442 (Div. 2) 877 E. Danil and a Part-time Job DFS序线段树

题目链接: E. Danil and a Part-time Job题目大意一棵有根树, 每个节点可以是1或者0, 两种操作: 1. pow v: 将v节点的子树中所有节点的值反置(1变0, 0变1, 相当于异或1) 2. get v: 输出v节点的字数中1的个数节点个数: 1≤n≤2⋅1051 \leq n \leq 2 \cdot 10^5, 操作次数: 1≤q≤2⋅1051 \leq

2017-10-26 00:10:18 230

空空如也

空空如也