回归梦想

分类

dfs(2) leetcode(3) PTA(5) python(1) 一起开心(1) 后缀数组(2) 图论(4) 多校(4) 天梯赛(8) 字符串(8) 数据结构(1) 未归档(539) 模板(4) 每日一题(56) 点分治(2) 牛客题霸(117) 知识(4) 算法(76) 经验分享(2) 网络流24(11) 莫比乌斯反演(2) 队列(2) 题解(271)

/ 注册

TA的专栏 41篇文章 0人订阅

16篇文章 978人学习

牛客每日一题

6篇文章 776人学习

0篇文章 0人学习

0篇文章 0人学习

0篇文章 0人学习

3篇文章 685人学习

ACwing寒假每日一题（提高组）

3篇文章 780人学习

13篇文章 912人学习

全部文章（共20篇）

NC20099 [HNOI2012]矿场搭建来自专栏

NC20099 [HNOI2012]矿场搭建题目： • 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。• 于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。•...

**** tarjan 割点

2021-01-14

0 742

NC20603 [ZJOI2007]最大半连通子图

NC20603 [ZJOI2007]最大半连通子图题目： • 一个有向图G=(V,E)称为半连通的(Semi-Connected)，如果满足：u,v∈V，满足u→v或v→u，即对于图中任意两点u，v,存在一条u到v的有向路径或者从v到u的有向路径。• 若G'=(V',E')满足V'∈V，E'是E...

拓扑排序 **** tarjan 缩点

2021-01-14

0 717

Tree Requests

题意：一棵树，每个节点是一个字母跟节点深度为1问对于x的子树，深度为y的节点能否组成回文串？题解：这个题处处都是细节组成回文串的话，要求至多只有一个字母出现奇数次我们先用dfs序给树标上号，同时开vector按照顺序存下每一层的节点以及每一层in[x]对于每一层，我们已经知道有什么节点，然后把...

dfs序 **** 思维二进制

2020-11-28

2 615

CodeForces - 507E Breaking Good

题意： n个城市m条道路，任务是在城市1和城市n之间选择一个最短路径，当有多个最短路径的时候选择影响值最小的（被摧毁的和修好的路的数目总数最少），道路分已修复和未修复两种状态，在选择好最短路径后，要修复好最短路径上未工作的路，并破坏其他路径上工作的路径。题解：修复 = 最短路的长度 - 最短...

**** 最短路思维

2020-11-26

2 0

P2672 推销员

题目描述阿明是一名推销员，他奉命到螺丝街推销他们公司的产品。螺丝街是一条死胡同，出口与入口是同一个，街道的一侧是围墙，另一侧是住户。螺丝街一共有N家住户，第i家住户到入口的距离为Si米。由于同一栋房子里可以有多家住户，所以可能有多家住户与入口的距离相等。阿明会从入口进入，依次向螺丝街的X家住户推销...

线段树 ****

2020-11-25

2 548

H 数据只搬样例

题意：一个树，对其有两个操作，操作1是将节点a的权值增加x操作2是查询节点a到根节点R的简单路径上所有节点的权值的平方的和答案对2^取模题解：如果ull类型的整数溢出了，就相当于取模2^64了。因为ull的范围是[0,2^64-1]，所以直接开unsigned long long就行有两个方法...

**** 树链剖分 dfs序线段树

2020-11-23

1 533

CF505E Mr. Kitayuta vs. Bamboos

题目 Valera is a little boy. Yesterday he got a huge Math hometask at school, so Valera didn't have enough time to properly learn the English alphabet f...

二分 **** 思维

2020-11-22

4 645

Sequence

H Sequence 题意： n个数，有两个操作，操作1是将第x位换成y操作2是问包含第x位的序列中，x为最小数的序列有多少个题解：一开始想用树状数组来做，但是感觉树状数组太弱了，貌似不够用赶紧换成线段树，（不想打线段树）如何统计序列有多少个，比如指定第x位，在第x位之前有a个数比他大，有...

线段树 **** 二分

2020-11-19

6 526

CodeForces - 518D Ilya and Escalator

题意：有n个人在电梯外等待，每隔一秒会有p的概率有一人进入电梯，问t秒后电梯中人数的期望题解：概率dp但是接触概率的题很少，对于求期望自己一无所知dp[i][j]表示i秒后电梯中有j人的概率j=0时，该秒无人进入,dp[i][j]+=dp[i-1][j] * (1-p)0<j<n时...

**** 概率dp

2020-11-17

1 709

Kingdom's Power(2020ccpc qinhuangdao)

题目描述： Alex is a professional computer game player. These days, Alex is playing a war strategy game. The kingdoms in the world form a rooted tree. Alex...

树型dp ****

2020-11-13

2 1340