- 博客(23)
- 收藏
- 关注
RSS订阅原创 数列分块入门
数列分块入门 1~9数列分块入门 1区间加法，单点查询完整的块更新标记，不完整的块暴力更新 $ O(q\sqrt{n} ) $数列分块入门 2区间加法，查询区间内比 x 小的数的个数每个块内排序一下，查询二分一下 $ O(q\sqrt{n}\mathrm{log}n) $数列分块入门 3区间加法，查询区间内 x 的前驱每个块内维护一下，查询二分一下 O(qnlogn)O(q...
2018-11-17 13:02:04
213
原创 2018.10.16.2
给定 N,MN, MN,M，对于任意的 1≤k≤N1 \leq k \leq N1≤k≤N，求出叶子数为 kkk，满足每个叶子到根的路径上左向边数量少于 MMM，每个节点都有 000 或 222 个子节点，区分左右的二叉树数量N,M≤5000N, M \leq 5000N,M≤5000一般的DP是 O(n3)O(n^3)O(n3) 的，所以我们要优化一下状态我们考虑像 dfs 遍历整棵树，...
2018-10-16 14:19:08
217
原创 从海带中提取碘
从海带中提取碘原理：2I−+2H++H2O2=I2+2H2O2I−+2H++H2O2=I2+2H2O\mathrm{2I^- + 2H^+ + H_2O_2 = I_2 + 2H_2O} 或： 2I−+Cl2=I2+2Cl−2I−+Cl2=I2+2Cl−\mathrm{2I^- +Cl_2 = I_2 +2Cl^-}若氯水过量，则会将 I2I2\mathrm{I_2} 进一步氧化：...
2018-06-12 20:45:23
4243
原创 atcoder grand contest 024
A - Fairness给定 A,B,CA,B,CA, B, C，进行以下操作 KKK 次：每个数都同时变为其他两个数的和求 KKK 次操作后 A−BA−BA - B 的值，如果答案大于 1018101810^{18}，输出'unfair' A,B,C≤109，K≤1018A,B,C≤109，K≤1018 A, B, C \leq 10^9， K \leq 10^{18}...
2018-05-23 16:28:17
178
原创 atcoder reguler contest 089 E graph xy
构造一个满足下列条件的有向图： 1. 顶点数不超过 300300300，其中有一个源点 SSS 和一个汇点 TTT 2. 没有重边和自环 3. 顶点由 111 至 NNN 编号 4. 每条边的权值 ∈[0,100]∈[0,100]\in [0, 100]，也可以是一个标签 XXX 或 YYY 5. 对于给定的每一对满足 x∈[1,A],y∈[1,B]x∈[1,A],y∈[1,B]x \i...
2018-04-25 20:21:40
291
1
原创 「TJOI / HEOI2016」排序
「TJOI / HEOI2016」排序给定一个111~nnn的排列，进行mmm次以下操作： 0 l r:0 l r:0 \ l \ r:将区间[l,r][l,r][l, r]内的数降序排列 1 l r:1 l r:1 \ l \ r:将区间[l,r][l,r][l, r]内的数升序排列最后，给定一个位置，求...
2018-04-16 14:09:36
229
原创 [九省联考2018] iiidx
给定一颗nnn个点的有根树，和nnn权值d1...dnd1...dnd_1 ... d_n。将每个权值分配个每个节点，要求使父亲的权值小于等于儿子的权值。依次最大化1,2,3...n1,2,3...n1, 2, 3...n号点的权值，输出方案。n≤600000n≤600000n \leq 600000从111号点开始枚举，由于我们要使一个点最大，所以我们每次都要求出当前符合要求的最大的...
2018-04-09 19:29:06
1226
原创 简单的数学题
求 ∑i=1n∑j=1nij gcd(i,j)∑i=1n∑j=1nij gcd(i,j)\sum_{i=1}^n \sum_{j=1}^n ij \ gcd(i, j) n≤1010n≤1010n \leq 10^{10}ans=∑d=1nd∑i=1n∑j=1nij [gcd(i,j)=d]ans=∑d=1nd∑i=1n∑j=1nij [gcd...
2018-04-09 16:05:29
764
原创 最小公倍数计数
51nod 1222求满足a≤lcm(i,j)≤ba≤lcm(i,j)≤b a \leq lcm(i, j) \leq b 的二元组[i,j][i,j][i, j]的个数a,b≤1011a,b≤1011a, b \leq 10^{11}设S(n)=∑i=1n∑j=1i[ijgcd(i,j)≤n]S(n)=∑i=1n∑j=1i[ijgcd(i,j)≤n]S(n) = \sum_{...
2018-04-08 21:01:02
168
转载 杜教筛
杜教筛求积性函数f(x)f(x)f(x)的前缀和S(n)=∑ni=1f(i)S(n)=∑i=1nf(i)S(n) = \sum_{i=1}^n f(i)狄利克雷卷积： (g∗f)(x)=∑d|xg(d)f(xd)(g∗f)(x)=∑d|xg(d)f(xd)(g*f)(x) = \sum_{d|x} g(d) f(\dfrac{x}{d})∑x=1n(g∗f)(x)=∑x=1n∑d|x...
2018-04-08 19:01:13
208
原创 「SDOI2014」数表
「SDOI2014」数表设σ(x)σ(x)\sigma(x)为xxx的约束和，求 ∑i=1n∑j=1m∑k=1ak[σ(gcd(i,j))=k]∑i=1n∑j=1m∑k=1ak[σ(gcd(i,j))=k]\sum_{i=1}^n \sum_{j=1}^m \sum_{k=1}^a k[\sigma(gcd(i, j)) = k] 数据组数<=20000<=20000 n,m...
2018-03-22 16:33:11
185
原创 「SDOI2015」约数个数和
「SDOI2015」约数个数和设d(x)d(x)d(x)为xxx的约数个数，求 ∑i=1n∑j=1md(ij)∑i=1n∑j=1md(ij)\sum_{i=1}^n \sum_{j=1}^m d(ij)n,m<=50000n,m<=50000n, m <=50000<=50000 ——————- 设ijijij唯一分解后为 ∏kqqik+qjkk∏kqkq...
2018-03-21 19:03:25
325
原创 母函数
母函数的一般形式1.普通型： G(x)=1+a1x1+a2x2+...+anxn+...G(x)=1+a1x1+a2x2+...+anxn+... G(x) = 1 + a_1x^1 + a_2x^2 +...+ a_nx^n +... 2.指数型： G(x)=1+x11!+x22!+...+xnn!+...G(x)=1+x11!+x22!+...+xnn!+... G(x) = 1...
2018-03-05 10:26:56
253
原创 [NOI2010] 超级钢琴
luogu2048：https://www.luogu.org/problemnew/show/P2048这道题大概就是求一个序列前 k 大长度在 [ L, R ] 内的连续区间的和。 序列的长度为 5*10^5，枚举每个序列肯定是不现实的。 我们可以想到，可以将多个具有相同性质的区间合并，并维护这一个区间集合的最大的连续区间的值。可以用一个堆来维护，当取到这个值时，将该集合分裂，再加入堆中。
2017-11-29 14:27:47
865
原创 [网络流 24 题] 方格取数问题 骑士共存问题
LOJ6007 https://loj.ac/problem/6007 LOJ6226 https://loj.ac/problem/6226 luogu2774 https://www.luogu.org/problemnew/show/P2774 luogu3355 https://www.luogu.org/problemnew/show/P3355这两道题都差不多，就放在一起写了。两道
2017-11-23 18:00:09
232
1
原创 [网络流 24 题] 最长 k 可重区间集
题目描述给定实直线 L 上 n 个开区间组成的集合 I，和一个正整数 k，试设计一个算法，从开区间集合 I中选取出开区间集合 S⊆I S \subseteq I S⊆I，使得在实直线 L L L 的任何一点 x ，S 中包含点 x 的开区间个数不超过 k 。且 ∑z∈S∣z∣达到最大。这样的集合 S 称为开区间集合 I 的最长 k 可重区间集。∑z∈S∣z∣ 称为最长 k 可重区间集的长度。对于给定
2017-11-22 21:15:57
220
原创 [网络流 24 题] 星际转移问题
LOJ 6015题目描述由于人类对自然资源的消耗，人们意识到大约在 2300 年之后，地球就不能再居住了。于是在月球上建立了新的绿地，以便在需要时移民。令人意想不到的是，2177 年冬由于未知的原因，地球环境发生了连锁崩溃，人类必须在最短的时间内迁往月球。现有 n 个太空站位于地球与月球之间，且有 m 艘公共交通太空船在其间来回穿梭。每个太空站可容纳无限多的人，而每艘太空船 i 只可容纳 Hi 个
2017-11-22 21:04:21
269
原创 [网络流 24 题] 餐巾计划问题
LOJ 6008 luogu1251题目描述一个餐厅在相继的N天里，第i天需要Ri块餐巾(i=l，2，…，N)。餐厅可以从三种途径获得餐巾。(1)购买新的餐巾，每块需p分；(2)把用过的餐巾送到快洗部，洗一块需m天，费用需f分(f#include <bits/stdc++.h>using namespace std;const int MAXN = 5000;const int INF =
2017-11-22 11:44:30
246
原创 Tarjan求割点
模板题：luogu3388题面： 给出一个n个点，m条边的无向图，求图的割点。思路： 对于每一个没有访问过（dfn[n]==0）的顶点，用tarjan算法以此点为根生成一颗dfs树 low记录与该节点连接的dfs序最小的节点的dfs序（时间戳），dfn则记录该节点的dfs序。 当第一个节点回溯到其父节点时，若low[son]>dfn[father]，说明该子节点不与任何在以该子节点为根的
2017-10-31 11:39:55
221
原创 luogu1525 关押罪犯
luogu1525 普及+ / 提高题面： N（N<20000）个点，M（M<100000）条边。每条边有一个权值。将图分成两部分，删除跨越两部分的边，使整个图内权值最大的边最小。思路： 有权并查集 1、将各边按照从大到小的顺序排序（优先队列）struct tEdge(){ ... inline void addEdge(...) {...} bool operat
2017-10-30 11:47:19
133
原创 [SHOI2009] 会场预约
luogu2161 省选 / NOI-题面： 设计一个数据结构，支持两种操作： 1. A i j 添加一个新的预约[i, j]，并删除所有与其冲突的预约。返回此次操作删除的预约的个数。 2. B 返回当前的预约总数。 数据范围：操作数<=200000思路： 线段树+染色 1、颜色。每个预约均用一种颜色代表struct tColor{ int left, right, nu
2017-10-30 07:45:55
522
原创 [SDOI2009]HH的项链
luogu 1972 提高+/ 省选-题面： 输入长度为N（N<50000）的数列，进行M（M<=200000）次询问，每次询问一个区间，输出数列对应区间内出现不同数字的个数。例： 1 2 3 4 3 5 [1, 3] : 3 [2, 5] : 4 [1, 5] : 5思路： 离线查询。 1、读入数列，第一次读入时，将每个数第一次出现的位置启用。int main()
2017-10-27 09:29:21
102
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人