回归梦想

题解

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)

/ 注册

全部文章 / 题解（共18篇）

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 0

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