- 博客(167)
- 资源 (2)
- 收藏
- 关注
RSS订阅原创 51nod 2621 树上距离
树上两点之间距离，lca模版题。#include<iostream>#include<stdio.h>#include<algorithm>#include<map>#include<set>#include<queue>#include<vector>#include<cstring>#include<stack>#define mem(ss) memset(ss,0,size
2020-10-15 21:34:06
238
原创 2020牛客暑期多校训练营（第七场) H Dividing 整除分块
稍微推一下，答案是∑i=1k⌊nk⌋+∑i=1k⌊n−1k⌋\sum_{i=1}^k\lfloor \frac{n}{k}\rfloor+\sum_{i=1}^k\lfloor \frac{n-1}{k}\rfloori=1∑k⌊kn⌋+i=1∑k⌊kn−1⌋#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#
2020-10-15 20:44:18
161
转载 最大权闭合子图（RMRC2017 Open-Pit Mining）
闭合图：对于一个有向图G，存在点集合V，任取点u属于V，u的出边的另一个点也属于V，则为闭合图。理解：任取一起点，终点必定是无出度的点。最大权闭合子图：当每个点有一个权值w（有正有负），点权和最大的闭合图为最大权闭合子图。如图：最大权闭合子图为点集{3,4,5}，最大权为7+0-3=4。求解方法：网络流。建立超级源点s，超级汇点t。所有点权为正数的点i，建边 s->i，容量为点权。所有点权为负数的点i，建边i->t，容量为点权绝对值。原图建图后，边容量均为正无穷。最大权闭合图
2020-07-23 17:49:42
198
原创 2020牛客暑期多校训练营（第一场) I 1 or 2
给一个图，要求删一些边，使每个点的度数为给定的di(1≤di≤2)d_i(1\leq d_i\leq2)di(1≤di≤2)。每个点拆成iii和i′i'i′，源点SSS和iii连一条权值为did_idi的边，i′i'i′和汇点TTT连一条权值为did_idi的边；mmm条边，uuu和v′v'v′、u‘u‘u‘和vvv建边。然后只要判断最大流与∑di\sum d_i∑di是否相等即可。#include<iostream>#include<stdio.h>#inclu
2020-07-21 17:43:15
211
原创 2020牛客暑期多校训练营（第四场）H Harder Gcd Problem
给一个数nnn，小于nnn的公因数大于1的两个数可以组合在一起，求最多有多少组数。构造：从小于nnn的最大素数ppp开始，尽量将ppp的倍数组合在一起，如果ppp的倍数的个数为偶数，则将2×p2\times p2×p留下，直到p=2p=2p=2时将这个数用上。#include<iostream>#include<stdio.h>#include<algorithm>#include<map>#include<set>#include&
2020-07-21 16:31:10
133
原创 2020牛客暑期多校训练营（第三场）G Operating on a Graph
q个操作，每次将和oio_ioi相连的点都染成和oio_ioi一样的颜色，求最终每个点所属的集合。(n,q≤2×105)(n,q\leq2\times10^5)(n,q≤2×105)重要观察：只要一个点被归入一个集合，他们之后是一直相连的。用一个链表存储所有与uiu_iui相连的点，每次将所有与e[oi]e[o_i]e[oi]中的点相连的点都染入oio_ioi的集合即可。#include<bits/stdc++.h>#define mem(ss) memset(ss,0,siz
2020-07-21 16:20:10
166
原创 2020牛客暑期多校训练营（第三场）E Two Matchings
E Two Matchings给一个序列aia_iai。要找到两种完全不同的两两匹配，使得所有两两匹配的差的和最小，输出这个和。比赛的时候觉得是一个二分图最小权值环，但是点太多，没法用完全图最小费用流做。（HDU 1853）做出此题需要找到四个特性：1、此题等价于找一些长度为偶数的环使得这些环恰通过每个点一次， 且所有边的总权重最少。2、 2k 个点所构成的环的权重和的最小值为最大的权重减最小的权重。3、先把所有点的按照权重排序，最佳解一定是出现在每个环都是由排序后连续的点构成
2020-07-19 15:09:45
158
原创 51nod 1127 最短的包含字符串
给一串字符串，求最短的包含‘A’-‘Z’字母的子串。尺取。#include<cstring>#include<cstdio>#include<cmath>#include<algorithm>#include<iostream>#define inf 0x3f3f3f3f#define ll long longusing namespace std;string s;int cnt[26];int ans = inf;in
2020-07-14 20:26:21
106
原创 九余数定理（p-1进制规律）
k=∑i=0n(pi−1)∗ai+∑i=0naik=\sum_{i=0}^n(p^i-1)*a_i+\sum_{i=0}^na_ik=i=0∑n(pi−1)∗ai+i=0∑naik≡∑i=0naimod p−1k\equiv \sum_{i=0}^na_i\mod p-1k≡i=0∑naimodp−1p=10时，即为九余数定理：一个数对9取余等于这个数各位之和对9取余。相关题：51nod 1116、hdu 1013...
2020-07-14 19:39:50
935
原创 51nod 1105 第K大的数
两个数组中的每个数两两相乘，求第K大的数。（n≤50000n\leq50000n≤50000)解：二分答案，枚举aaa数组中每个数aia_iai，二分出aia_iai与bjb_jbj乘积中比mid大的数量，然后与k进行比较。#include<cstdio>#include<algorithm>#include<iostream>#define ll long longusing namespace std;const int N = 5e4;int
2020-07-14 17:57:51
124
原创 ICPC North Central NA Contest 2017
C题最后过的，sss条无限长直线将平面画成若干个区域，相邻的类型不一样（可知只需有两个类型就可染色完毕）。ttt个询问，每次询问两个点所在区域是否是同一个类型。思考之后发现，sss条直线中使两个点在其同一侧的直线，并不对答案造成影响；故只需统计使两个点在两侧的直线的数量即可。最后是否是相同的类型只需看上述直线的数量的奇偶性即可。#include<iostream>#include...
2020-02-29 23:46:36
194
原创 51nod 1276 岛屿的数量 (离散化)
给出nnn个岛屿的高度，询问qqq个海平面，每个海平面时存在多少岛屿。对询问和岛屿分别离散化，对于每一个询问，他之前的询问一定把更矮的岛给覆盖了，所以对于一个询问，覆盖当前没覆盖的岛对答案的影响分两种：1、在原序列中这个岛两边的岛都没被覆盖过，那么答案+1；2、在原序列中这个岛两边都被覆盖过了，那么答案被多加了1，所以答案-1。#include<iostream>#include...
2020-01-20 20:46:28
143
原创 2518 和为S
动态维护hash即可#include<iostream>#include<stdio.h>#include<algorithm>#include<map>#include<set>#include<queue>#include<vector>#include<cstring>#incl...
2019-12-08 13:06:47
124
原创 51nod做题笔记
2652 阶乘0的数量 V2因子中2的密度远远大于5的密度，故只需关注因子为5的出现即可，即间隔5，阶乘增加一个零。然后二分答案即可。1094 和为k的连续区间这题有nlognnlognnlogn的做法，求出前缀和后必有sum[r]−sum[l−1]=ksum[r]-sum[l-1]=ksum[r]−sum[l−1]=k，枚举一个sum[r]sum[r]sum[r]，只需要去找sum[l−1...
2019-12-07 17:41:30
142
原创 51nod 1091 线段的重叠
左端点排序，扫一遍，维护右端点的最大值；因为左端点有序，故只需要当前左端点小于最大值即可保证相交。答案即每个相交的长度最大值。#include<iostream>#include<stdio.h>#include<algorithm>#include<map>#include<set>#include<queue>...
2019-12-05 11:26:02
127
1
原创 51nod 1102 面积最大的矩形
单调栈#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<vector>#include<queue>#include<stack>#include&...
2019-11-22 22:09:46
118
原创 51nod 1272最大距离
求max(j−i)，ai<aj\max(j-i)，a_i < a_jmax(j−i)，ai<aj法1⃣️：从前往后维护一个单减栈，每一个新值去栈里二分查。法2⃣️：离散化，然后问题转化为求max(aj−ai)，i<j\max(a_j-a_i)，i < jmax(aj−ai)，i<j.设一个新数组bi=ai−ai−1b_i=a_i-a_{i-1}b...
2019-11-22 22:00:23
117
原创 51nod 2635区间xor
求a⊕(a+1)⊕⋯⊕(b−1)⊕ba \oplus(a+1)\oplus\cdots\oplus(b-1)\oplus ba⊕(a+1)⊕⋯⊕(b−1)⊕b.def f(n): m = n % 4 if m==0: return n elif m==1: return 1 elif m==2: return n+1...
2019-11-22 19:42:40
116
原创 51nod 2602 树的直径
树的直径模板题#include<iostream>#include<stdio.h>#include<algorithm>#include<map>#include<set>#include<queue>#include<vector>#include<cstring>#include...
2019-11-21 19:18:59
182
原创 Codeforces Round #600 (Div. 2)
A 模拟#include<iostream>#include<stdio.h>#include<algorithm>#include<map>#include<set>#include<queue>#include<vector>#include<cstring>#include&l...
2019-11-21 17:28:36
171
原创 51Nod 1086 多重背包+二进制优化
二进制优化裸题#include<iostream>#include<stdio.h>#include<algorithm>#include<map>#include<set>#include<queue>#include<vector>#include<cstring>#include...
2019-11-21 16:36:42
145
原创 2019南昌网络赛B. Fire-Fighting Hero 最短路SPFA
图论：1、看清是否directed；2、板子一定要用对技巧：超级源点把需要跑最短路的点连上序号为0的点，距离设为0.#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>#include<vecto...
2019-09-18 17:41:32
155
原创 2018宁夏邀请赛/2019宁夏网络赛 Fight Against Monsters - 贪心
有关的梗请移步某乎。真·百度之星铜牌题，给nnn个怪，每个怪需要打bib_ibi轮才能打死，在没被打死之前，每轮释放aia_iai的伤害。求释放的最小伤害。考虑两个怪，先打怪兽1：b1∗∑ai+b2∗(∑ai−a1)b_1*\sum a_i +b_2*(\sum a_i -a_1)b1∗∑ai+b2∗(∑ai−a1)先打怪兽2，受到的伤害：b2∗∑ai+b1∗(∑ai−a2)b...
2019-08-31 19:48:25
150
原创 HDU 6695 Welcome Party 贪心
有nnn个学生，每个人有两个值x、yx、yx、y，每人必须且只能选择一个。求选出的xmax−ymaxx_{max}-y_{max}xmax−ymax的最小值。以每个学生的xxx为关键字降序排序，preprepre和sufsufsuf数组分别记录当前学生iii之前和之后的所有yyy值。枚举学生iii，求出以该学生为xmaxx_{max}xmax的结果。显然，我们可以贪心地去找在iii后与x...
2019-08-22 19:10:49
146
原创 HDU 6693 Valentine’s Day 贪心
给nnn个物品，每个物品有一个被选中的概率。任意选kkk个物品，怎么选这kkk个物品才能使从这kkk个物品中选一个物品的的概率最大。设从kkk个物品中选中一个的概率为pkp_kpk，那么Pk=a1(1−a2)...(1−ak)+a2(1−a1)...(1−ak)+...+ak(1−a1)(1−a2)...=a11−a1(1−a1)(1−a2)...(1−ak)+a21−a2(1−a1)(1−a...
2019-08-22 13:48:53
315
原创 2019杭电多校第六场
1003 Valentine’s Day给nnn个物品，每个物品有一个被选中的概率。任意选kkk个物品，求从这kkk个物品中选一个物品的的概率最大。设从kkk个物品中选中一个的概率为pkp_kpk，那么pk=a1(1−a2)...(1−ak)+a2(1−a1)...(1−ak)+...+ak(1−a1)(1−a2)...=a11−a1(1−a1)(1−a2)...(1−ak)+a21−a2(...
2019-08-22 01:03:03
152
原创 2017ICPC北京区域赛 Pangu and Stones 区间dp
给nnn个数和一个上下限LLL和RRR，每次可以将一段连续的kkk个数合并，代价为数值之和，且要满足k∈[L,R]k\in[L,R]k∈[L,R]。求最终合并为1堆的最小代价。与合并石子类似，定义dp[i][j][k]dp[i][j][k]dp[i][j][k]为区间[i,j][i,j][i,j]剩下kkk堆的最小代价，因为只有l≤k≤rl\leq k \leq rl≤k≤r才能合并，所以将k=...
2019-08-20 17:21:03
171
原创 HDU 3449 Consumer有依赖的01背包
有nnn个购物车，每个车可以购买特定的商品，买商品之前必须花费代价购买对应的购物车，求www可以购买的最大的商品价值。在有依赖的背包问题中，购物车称为"主件"，商品为"附件"；#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algo...
2019-08-20 13:38:45
130
原创 HDU6669 Game 2019百度之星初赛
题目给出nnn个区间，起点任意选择，每次可以向左/向右跳一步或两步，求从第一个区间依次跳到第nnn个区间的最少步数。因为是依次跳，所以一定是一个线性的算法：发现每次若需要跳，就近跳即可；关键在于当跳的区间为奇数时最后一步为1步还是2步。只需把两种情况都记录下来，若讨论则会非常复杂。#include<cstdio>#include<cstring>#include&l...
2019-08-18 18:03:46
113
原创 HDU 6662 Acesrc and Travel 换根dp
题意就是给一个无根树，然后每次从一个点出发，两个人轮流决定下一点；对于一个点，Zhang获得a[i]，Liu获得b[i]。每个人都想自己获得的与另一个人的差最大，求Zhang先手的最大差值。Source：2019 Multi-University Training Contest 8一个最大差值，一定是当前的点减去之前的最小值得到的，有状态转移：f(u,v,0)=min{f(p,u,1)}f...
2019-08-17 17:32:26
320
原创 cumtoj 与与与 权值线段树
给定一个长度为nnn序列，一共qqq次询问，每次询问给定区间[l,r][l,r][l,r]和一个数kkk，求lll到rrr区间内所有大于等于kkk的数相与的结果.将aia_iai按照从大到小的顺序插入线段树，插入的时候动态查询区间[l,r][l,r][l,r]的按位与的和即可。//std#include <iostream>#include <cstdio>#i...
2019-08-16 16:48:08
214
原创 cumtoj修建道路 LCA倍增
题目描述nnn个点n−1n-1n−1条边，点之间两两连通，每次询问333个点，求使这333个点连通的最小花费。（1≤n,q≤1051\leq n,q\leq 10^51≤n,q≤105）因为给的是一颗树，最终的答案就是dist(x,y)+dist(y,z)+dist(x,z)2.\frac{dist(x,y)+dist(y,z)+dist(x,z)}{2}.2dist(x,y)+dist(y,...
2019-08-16 16:07:14
119
原创 HDU6667 Roundgod and Milk Tea 二分图 Hall定理
给出nnn个班级，每个班级有aaa个人bbb杯奶茶，每个同学能且只能拿一杯奶茶，并且不能拿自己班的奶茶。求最多喝到奶茶的人数。Source：2019 Multi-University Training Contest 7比赛的时候由于数据太水，大多数人都用贪心过了，但是实际上这道题是一个二分图最大匹配的问题。对于二分图(U+V,E)(U+V,E)(U+V,E)，左边顶点表示学生，右边节点表示...
2019-08-15 15:10:42
326
原创 bzoj2440: [中山市选2011]完全平方数 容斥原理 + 莫比乌斯函数
求第kkk个没有平方因子的数。 对于一个没有平方因子的数，n=p1p2...pk，pin=p_1p_2...p_k，p_in=p1p2...pk，pi为质数。首先二分答案，问题转化为区间[1,x][1,x][1,x]有几个没有平方因子的数。根据容斥原理，对于x\sqrt xx以内的质数:ans=n−由1个质因子组成的平方数的倍数的数量+由2个质因子组成的平方数的倍数的数量−由3个质...
2019-08-10 14:04:01
169
原创 2019杭电多校第六场
Stay Real给一个小根堆，两人每次取一个出度为0的点（没有子节点），求取完后两人的结果。因为小根堆性质是根结点小于叶节点，所以每次取的都是当前所剩下的点中最大的。排序后轮流取即可。TDLHDU 6641 TDL 异或性质定义f(n,m)f(n,m)f(n,m)为比nnn大的第mmm个与nnn互质的数，给出(f(n,m)−n)⊕n(f(n,m)-n)\oplus n(f(n,m)−...
2019-08-08 18:24:44
282
原创 HDU 6641 TDL 异或性质
定义f(n,m)f(n,m)f(n,m)为比nnn大的第mmm个与nnn互质的数，给出(f(n,m)−n)⊕n(f(n,m)-n)\oplus n(f(n,m)−n)⊕n和mmm，求最小的nnn。Source：2019 Multi-University Training Contest 6因为异或满足自反性，不妨另(f(n,m)−n)⊕n=k(f(n,m)-n)\oplus n=k(f(n,m...
2019-08-08 18:23:06
358
原创 HDU 6638 Snowy Smile 线段树+最大子段和
nnn个点，−109≤xi,yi≤109-10^9\leq x_i,y_i\leq 10^9−109≤xi,yi≤109，求最大子矩阵和。（n≤2000n\leq 2000n≤2000）Source：2019 Multi-University Training Contest 6离散化后，枚举矩阵的上下边界，然后将每一列上的数都加入s[y]，则关于该上下边界的最大子矩阵和为sss数组的最大...
2019-08-08 18:18:55
386
原创 SPOJ - GSS1 Can you answer these queries I 线段树最大子段和
线段树求最大子段和。对于一个区间，记录它的前缀最大子段和、后缀最大子段和、区间和、和区间最大子段和，对于每个节点，更新前缀和后缀最大子段和，则当前区间的最大子段和为左区间后缀最大值+右区间前缀最大值和左右区间最大子段和的最大值。查询复杂度O(logn)O(logn)O(logn)#include<set>#include<map>#include<cmath...
2019-08-08 16:00:37
137
原创 51nod 做题记录
51nod 1013计算30+31+...+3n%p3^0+3^1+...+3^n\%p30+31+...+3n%p法1：ans=3n+1−12%pans=\frac{3^{n+1}-1}{2}\%pans=23n+1−1%p=inv(2)∗(3n+1−1)=inv(2)*(3^{n+1}-1)=inv(2)∗(3n+1−1)法2:矩阵快速幂[Sn1]=[3101]∗[Sn−11]\b...
2019-08-05 23:36:04
224
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人