- 博客(305)
- 收藏
- 关注
RSS订阅原创 2019 ICPC Asia Nanchang Regional （dsu on tree+treap平衡树）
题意:给你一棵树，每个点有一个val让你找树上有多少有序对(x,y)满足以下条件：1.x!=y2.x不是y的祖先；y不是x的祖先3.x与y的最短路径长度<=k4.x与y的最小公共祖先的值vz,满足2vz=vx+vy解析:就是启发式合并，同时建n棵权值treap树，来维护该权值下，有多少深度的点插入进来。在遍历轻孩子找答案时，每一次，已经确定根和一个点...
2019-12-13 13:50:53
299
原创 2019CCPC 哈尔滨 E - Exchanging Gifts (离散化+fastIO+bfs)
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <queue> #include <iostream> ...
2019-12-01 21:04:35
404
原创 2019 ICPC Asia Nanjing Regional J Spy (KM，最大权匹配)
题意：A队有n个队，每个队赏金是p[i],能力值是a[i]B队有2n个人现在要组成n个小队，每一个队从b[]（长度为n）中取一个人，c[]（长度为n）中取一个人，组成小队，组成的队伍的能力值是两个能力值之和。现在B队中的每个小队，随机遇到A队中的一个小队进行比拼，如果B小队的能力值大于A小队，就获胜并获得赏金，两个小队比拼之后就都out,不能再进行比拼。问你期望得到的赏金n是多少？解...
2019-12-01 21:02:34
430
原创 q = x*w + b 后向传递梯度求导(求dx,dw,db)
x:N∗Dx: N*Dx:N∗Dw:D∗Mw: D*Mw:D∗Mb:Mb: Mb:M后向传递得到：αfαq=dout\frac{\alpha f}{\alpha q} = doutαqαf=doutdout:N∗Mdout:N*Mdout:N∗M求解dxdxdxαqi,kαxi,j=wj,kαfαqi,j∗αqi,kαxi,j=douti,k∗wj,k∵q and ...
2019-10-30 16:15:51
669
2
原创 Codeforces Round #426 (Div. 1) B. The Bakery(区间内不同数个数+dp)
题目链接:http://codeforces.com/problemset/problem/833/B题意：给你一个长度为n的数组a,让你把它分成连续的k段(数组里数的顺序不能改变)使得权值之和最大。每一段的权值就是该段内不同数的个数解析：拼多多笔试的时候做到，所以赛后找了道一样的题目补一下。一开始看到这题，以为是用斜率dp来做，后来写出公式之后发现不能很好地用斜率表示。这里的dp...
2019-10-24 16:48:39
236
原创 ICPC China Nanchang National Invitational A. PERFECT NUMBER PROBLEM(筛法打表)
题目链接题意:让你输出前5个完美数完美数:一个数，除了他本身外，它的因子和=他本身，那么这个数是完美数解析:比赛的时候，第5个数一直打不出来,.,然后就网上搜了一下...看了大佬的打表方法，记录一下#include <cstdio>#include <cstdlib>#include <cmath>#include &l...
2019-04-21 15:55:50
121
原创 HDU 6521 Party(思维+STL/吉司机线段树)
题目链接题意:有n个人，m场派对，n个人一开始互相不认识。每一场派对，你需要输出有多少对人，是第一次互相见面解析:这道题大佬的思路维护a[i],表示[1..i]之内i最远认识到谁，即[a[i]...i)的人，i都已经认识了。那么对于询问[l,r],我们需要更新i∈[l,r] a[i]=min(a[i],l)同时计算贡献是ans+=a[i]-l算这个有两种做...
2019-04-21 15:49:17
240
原创 2017-2018 ACM-ICPC German Contest (GCPC 2017) E Perpetuum Mobile (level 3)(spfa判环+log转换小数乘法)
题目链接题意:题面70%的都是废话，还有很多影响读题的条件...其实就是给你一个有向图，问你这个有向图里面存不存在环，使得组成环的边的权值的总乘积>1有输出"inadmissiable",否则输出"admissiable"解析:这道题其实就是一道spfa判负权环的题目，找最长路。但是这里的小数很难处理，因为有4位小数，并且还有5000条边，乘积的话数据的数值和精度...
2019-04-21 15:08:31
322
原创 Codeforces Round #551 (Div. 2) C. Serval and Parenthesis Sequence(括号匹配)(level 1)
题目链接题意:给你一个包含'(',')','?'的字符串。然后定义严格前缀，s[1...x] 1<=x<|s|让你用 '(' 或 ')' 替换 '?',使得s串的严格前缀都不是正确的圆括号，但是s是正确的圆括号圆括号的定义就是串中所有'('都能正确匹配一个')' '()()' '(())'解析:括号匹配的题目是真的做不来...想了一天...然后想出思路...
2019-04-15 21:11:09
118
原创 ZOJ 4097 Rescue the Princess(tarjan判桥+LCA)(level 3)
题目链接题意:给你一个无向图,n个点,m条边，图中可能存在重边，自环然后有q个询问(n<=1e5,m<=2e5,q<=1e5)每一次询问u,v,w，问你能不能找到两条路径v->u,w->u使得两条路径中没有公共的边有->Yes,无->No解析:其实这道题tarjan判桥的特征挺明显的——无向图，重边，自环然后你画一下样例...
2019-04-15 13:45:03
172
原创 2018-2019 ACM-ICPC Southeastern European Regional (SEERC 2018) G - Matrix Queries (level 3)(线段树)
题目链接题意:给你一个(2^n)*(2^n)的矩阵，矩阵元素只有0，1两种颜色。定义一个元素的价值是1.如果一个矩阵都是一种颜色，那么他的价值为12.如果一个矩阵不纯色，那么他的价值是把他分成4个(2^(k-1))*(2^(k-1))(假设原来的大小是(2^k)*(2^k))的矩阵的价值之和+1然后有q个操作，一开始矩阵都是0颜色，每一次操作，你需要把t=0,把第x...
2019-04-12 19:22:10
601
原创 P2495 [SDOI2011]消耗战 (level 3)(虚树)
题目链接题意:给你一棵n个点的树，树上的边有权值>0然后给你m个询问，每一次询问给你k个点(不包含1(根节点))让你在树上删除几条边，使得从1出发，无法到达这k个点，并使得删掉的边的权值尽可能小，输出权值Σki<=500000解析:这道题我是先看了虚树，然后再做这道题。用虚树做的题目有一个很明显的特征就是询问的点的总和(也就是上面的Σki<=500...
2019-04-09 16:47:28
235
原创 2018-2019 ACM-ICPC Southeastern European Regional (SEERC 2018) C Tree(level 2)(树的直径)(4种解法)
题目链接题意:给你一棵n个点的树(n<=100),每一个点有白/黑色，让你选m个黑色的点，使得你选的这m个点的集合里最远的两个点的距离最小解析:这道题我训练的时候是用st的LCA求两点距离+二分+最大团验证来做的，代码有167行比赛的时候...估计得写将近1个小时，然后还被自己LCA模板上的一个数组大小卡了半个小时...这道题赛后看了大佬们的代码，大多都是和树的直...
2019-04-08 13:38:31
416
原创 树的直径
求法:1.先任意选一个点，找到离这个点距离最远的点q2.然后以q为根，找距离q最远的点p,那么pq就是这棵树的直径了证明:假定st是直径，我们需要证明的其实就是一个性质树上任意一个点x，距离x最远的点=直径的一个端点?那么我们假定的条件就是距离x最远的点y!=直径的一个端点，同时还要保证st是直径的性质，看这样的条件下，能否成立情况1: x在直径上sx=...
2019-04-08 11:38:19
406
原创 牛客练习赛43 B Tachibana Kanade Loves Probability(输出分数的第k1~k2位小数)(快速幂)(level 1)
题目链接题意:如上题，给你一个分数m/n,让你输出该分数的第k1~k2位小数解析:除法得到分数的过程是m=m%n第一位小数: m=m*10 m/n-> m=m%n第二位小数: m=m*10 m/n-> ...
2019-04-06 16:00:18
184
原创 Comet OJ - Contest #0 A 解方程(积性函数)(level 2)
题目链接题意:你只需要给出解的数量和所有解的 xyz 之和对 (109+7) 取模的值即可若方程有无穷多组自然数解，则在这一行输出 “infty”（不含引号），否则在这一行输出两个整数，其中第一个整数表示方程的解数，第二个整数表示所有解的 xyz之和对 (109+7)取模的值，这两个整数之间用恰好一个空格隔开，行末不要有多余的空格。解析：是有理数的时候，只需要输出infty...
2019-04-06 14:02:16
214
原创 Comet OJ - Contest #0 D 项链与计数(level 4)(树上并环)(Kruskal+按秩合并并查集)
题目链接题意:定义简单环:一个点数和边数相等的回路，并且这条回路上没有出现重复的点或边。定义项链:定义 “项链” 是由一些简单环组成的子图，不妨设项链包括 k个简单环 C1C1, C2, ……, Ck (x`)，那么项链需要满足：当且仅当 ∣i−j∣≤1 时，简单环 Ci和 Cj 共用顶点； 简单环 Ci 和 Ci+1 恰好共用一个顶点； 任意两个不同的简单环 ...
2019-04-06 10:50:52
351
原创 Comet OJ - Contest #0 B 旅途(level 3)(概率dp)
题目链接题意:有一个n个点的环，编号为1...n第一天你在节点1，每一天你会在这个点游玩然后下一天，你有3种选择1.p%的概率顺时针走一步，到下一个城市游玩2.q%的概率逆时针走一步，到上一个城市游玩3.(100-p-q)%的概率待在原地再玩一天设f[i]=在第m天后，你游玩了i个城市的概率请你计算对1e9+7取模的结果解析:这道题看到的时候，就感觉用概...
2019-04-02 19:40:30
435
原创 ICPC Nanning L. Twice Equation (打表找规律)(level 1)
题目链接题意:2*m(m+1) = n*(n+1)然后给你一个L，让你输出一个最小的n>=L,(所有数都是整数)解析:这道题虽然只有level 1,比赛的时候也很多人做出来，但是这种题我是完全做不出来....m:0tot:0n:0.0m:2tot:12n:3.0m:14tot:420n:20.0m:84tot:14...
2019-03-30 17:10:31
427
原创 ICPC Nanning J. Rearrangement (level 1)(思维)
题目链接题意:有一个2*n的矩阵，里面有数字，让你重新安排数字，使得相邻两个数字之和不能被3整除可以的话输出YES,否则输出NO解析:这道题很简单，就是把0都交替排列 0 0 ...0 0 0 ...这样然后1从左边开始排到右边，2从右边开始排到左边我们总可以调整中间0的位置来使得1，2不相邻...
2019-03-29 09:43:50
227
原创 2018 ACM-ICPC 上海大都会 H A Simple Problem with Integers(level 4)(线段树+floyd判环+暴力)
题目链接题意:给你长度为n的数组，然后有q个操作，2种类型(n,q<=5e4)1. C a b means performing Ai = (Ai2 mod 2018) for all Ai such that a ≤ i ≤ b.2. Q a b means query the sum of Aa, Aa+1, ..., Ab. Note that the sum is not...
2019-03-27 19:00:01
430
原创 EOJ Monthly 2019.3 (based on March Selection)(level 3) C. 线段树(爆搜+可行性剪枝)
题目链接题意:function build(l, r, x): init node x if l < r then: mid = floor((l + r) / 2) build(l, mid, x * 2) build(mid + 1, r, x * 2 + 1)这是建立线段树的代码，现在给你一个区间[l,r...
2019-03-26 09:15:53
174
原创 Asia Hong Kong Regional Contest 2016 J Taboo(level 3)(ac自动机+dfs/dp)
题目链接题意:给你n个串，让你找出最长的串s,使得这n个串都不是s的子串。串只由0，1组成如果串可以是无穷长，输出-1解析:一开始看的时候没有怎么深入想，后来赛后看了题解。发现是ac自动机，后来看自己以前做的ac自动机的题目，发现有做到过类似的....都是给你n个串，让你构造不包含这个n个串的一个串。这道题构造出ac自动机，你在ac自动机上跑就可以了。一开始还没搞清...
2019-03-21 12:15:48
1971
原创 HDU 6223 Infinite Fraction Path(level 3)(bfs+剪枝/倍增)
题目链接题意:给你一串长度为n的数字,对于里面的每一个位置，第i个位置与第(i*i+1)%n个位置有一条单向的路径你可以从任意位置出发，走n次，得到n个字符组成的数字让你输出你能得到的最大的数字解析:这道题做的时候真的想爆了..什么反向建边变成一棵树，再用树上倍增..还有tarjan缩点...什么想法都想了..但是后来看题解发现这是暴力直接做......要说线索可以打一...
2019-03-17 21:24:00
155
原创 2018 ACM-ICPC 上海大都会赛 A Fruit Ninja(level 3)(几何随机)
题目链接题意:给你n个点，问你有没有一条直线，经过这n个点里的m个点，使得m/n>=x，解析:从1...n里面随机(rand()%n+1)取两个点，那么直线就确定了，然后再扫一遍n个点，计算这条直线的贡献，如果满足条件则输出Yes这个过程好像只要随机250次就能在1e4个点中找到答案，好像有些随机1000次的也能在5s之内过#include <bits/s...
2019-03-14 12:16:36
161
原创 牛客挑战赛30 C 小G砍树(level 3)(换根DP)
题目链接题意:给你一颗n个点的树，每一次你只能删除度数为1的点，问你有多少种方案可以把整棵树删到只剩一个点，两个方案不同，当且仅当有一个点删除的顺序不同。答案MOD998244353解析换根dp：对于一颗无根树，先确定一个根后，求出答案的公式然后再从确定的根出发，按照dfs顺序，分别将根转移到所有节点，同时更新答案公式中的变量，求一遍答案这道题也是一样。先确定一个根，然后...
2019-03-12 11:08:59
343
原创 Codeforces Round #541 (Div. 2) D. Gourmet choice(level 1)（拓扑排序）
题目链接题意:有两个数组a[],b[]，分别由n个和m个然后给你一个n*m的矩阵mp[i,j]='>' 表示a[i]>b[j]mp[i,j]='=' 表示a[i]=b[j]mp[i,j]='<' 表示a[i]<b[j]让你输出满足条件的答案，并且这组答案要是所有元素最大值最小的那组解析:这道题....又脑子挂了..一直在比较同一组...
2019-03-10 19:48:47
111
原创 牛客练习赛39 E 车站(level 4)(线段树+倍增+LCA(ST表))
题目链接题意:给你一颗树n个点，n-1条边，然后有m条铁路，从1-m标号，第i条铁路是ui-vi的简单路径一个点可以作为区间[L,R]铁路的车站满足以下条件： 1、编号为[L,R]的铁路都经过这个车站。 2、编号为[L,R]的铁路经过的所有城市中，离车站最远的城市，与它的距离最小。如果有多个，那么选择编号较小的。然后有两种操作操作1：1,l,r，表示询问[...
2019-03-06 20:54:12
226
原创 zoj 3864 Quiz for EXO-L(level 1)（bfs)
题目链接题意:给你一种转换方法，你要把转换的结果还原成一个n*n的矩阵然后识别这个n*n的矩阵里面的图案是上述哪一个图案，输出那个人的名字。矩阵只有0（黑色），1（白色）组成解析:这个跟之前百度之星的识别0，1的做法一样，还百度之星那个难一点。因为这道题保证图案不会碰到边界那么就找白的联通块个数和黑的连通块个数。但是样例给的那两个图案，黑白连通块的个数是一样的.......
2019-03-05 15:29:14
151
原创 ZOJ 3861 Valid Pattern Lock(level 1)(全排列暴力)
题目Valid Pattern LockTime Limit: 2 Seconds Memory Limit: 65536 KBPattern lock security is generally used in Android handsets instead of a password. The pattern lock can be set by joining p...
2019-03-05 10:13:54
141
原创 牛客练习赛39 D动态连通块(level 1)(bitset)
题目链接题意:白连通块：图中一个点集V，若满足所有点都是白点，并且V中任意两点都可以只经过V中的点互相到达，则称V中的点构成了一个白连通块。 黑连通块：类似白连通块的定义。给你n个点，每一个点有白(0)/黑(1)。然后有m个操作。操作1：在u,v之间连一条边操作2:输出颜色为白(0)/黑(1)连通块的个数操作3:x,y两个点，保证是同色。假定是白色，那么如果...
2019-03-03 16:37:47
108
原创 1145 Hashing - Average Search Time （25 分）(level 1)(二次方探测再散列)
题目链接题意:给你一个hash表的大小msize，如果这个大小是一个合数，那么你要自己把它变成第一个大于它的素数再试你要插入的n个数，如果给你的这n个数中无法插入到hash表，那么你要输出X cannot be inserted.最后给你m个数，让你查询，输出查询的平均时间(一个数的查询次数就是他在hash表里比较的次数)H(key)=key%size解决冲突的方法用正增量...
2019-03-01 20:22:03
341
原创 PAT 1029 Median （25 分）(level 1)(STL优先队列)
题目链接题意:给你两个数组，数组里面的元素都已经按上升序拍好了，让你把这两个数组合并成上升序，并输出中位数解析:这道题开(2e5+10)*2的数组会内存超限..所以看题解是用优先队列，维护前(n+m+1)/2个小的数，然后不断push和pop就可以了，然后最后输出堆顶的元素然后这里虽然说数据范围是long int,但是你开long int好像会爆(题解说的)，这道题数据其实...
2019-02-28 14:17:50
89
原创 PAT 1010 Radix (level 1)(二分)
题目链接题意:给你两个正整数n1,n2,然后是tag，radixtag==1，表示n1是radix进制数,tag==2，表示n2是radix进制数问你，如果要使n1=n2,另外一个数要是多少进制数？，不可能输出impossible解析:写这道题不是这道题有多难，而是这道题有多坑.....这道题radix答案取值范围可以达到long long的水平，但是它又能保证你求答案...
2019-02-25 14:15:49
124
原创 PAT 1003 Emergency （25 分）（level 2）(Dijstra求单源最短路径条数)
题目链接题意:给你n个点，和每一个点救援队的数量，然后m条无向边再给你起点c1和终点c2问你从c1->c2的最短路径的条数，以及这些不同的最短路径中，沿途能经过的救援队的数量的最大值。(即每经过一个点，就把那个点的救援队全部叫上，问你在这些最短路径中，哪一条能叫上最多的救援队，输出这个最大值) 解析:这道题一开始想用Floyd做，但是发现，记录最短路径条数时会有重...
2019-02-24 11:44:58
175
原创 牛客寒假算法基础集训营2 F 处女座与宝藏(level 4)(2-sat)
题目链接题意：有n个宝藏(1...n)，然后n个数表示宝藏的初始状态,0表示开启，1表示关闭有m个开关，每一个开关控制k个宝藏，当你按下一个开关后，这个控制的k个宝藏的状态都会发生改变(开启->关闭，关闭->开启)只有当某一刻，所有宝藏都处于开启状态时，你才能获得所有的宝藏，问你能否获得所有宝藏 解析:2-sat讲解2-sat模板下面是我对算...
2019-02-23 11:42:50
203
原创 Educational Codeforces Round 2 E. Lomsat gelral(level 3)(dsu on tree)
题目链接题意:给你一颗树，每一个节点有一个颜色，在节点v的子树中，颜色x出现的次数最多，则称x支配v的子树，注意一颗子树可能被多个颜色支配，让你输出对于每一个节点，支配他的子树的颜色的编号和 解析:code force上大佬的讲解——dsu on tree树上启发式合并的模板题总结一下，对于在做节点x的子树问题时，答案是通过x的重孩子继承过来，然后在遍历x的每一个轻孩子...
2019-02-17 20:36:31
256
原创 牛客练习赛38 F 出题人的无向图(level 3)(启发式合并优化+离线+线段树/堆维护最大值)
题目链接题意:给你一个n个点，m条边的无向图，每一个点有两个属性ai,bi<=INT_MAX有q个询问，每一个询问，一个边界v,和k个点c1..ck对于每一次询问，进行操作(此操作只作用于本次询问)先将ai>v的点全部删除，包括连接这些点的边在把剩下的图中编号为c1..ck这些点各自对应的连通块删除再对最后剩下的图中的连通块定义其权值:一个连通块的权值是...
2019-02-08 17:16:45
428
原创 牛客练习赛38 E 出题人的数组(level 3)(思维乱搞)
题目链接出题人有两个数组,A,B，请你把两个数组归并起来使得cost=∑i∗ci最小归并要求原数组的数的顺序在新数组中不改变n,m<=100000ai,bi<=100000 解析:这道题的思维量还是有一点大的(对于像我这种蒟蒻来说....)这里就转一个博主的题解，讲的还是非常清楚的其中算平均数这个就是最难想的，也是本题思维量最大的地方转载链接...
2019-01-31 21:36:40
230
原创 Codeforces Round #533 (Div. 2) C Ayoub and Lost Array (level 1)(dp)
C. Ayoub and Lost Array time limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputAyoub had an array aa of integers of size nn and this a...
2019-01-22 09:50:10
263
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人