回归梦想

题解

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)

/ 注册

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

Tree Constructer 来自专栏

题目：题意：如果点x和y有连边，当且仅当a[x] or a[y] = 2^60^ - 1 （两者是充分必要）现在给你边的关系，问你每个点的值应该是多少？（给出一种情况即可）题解：构造题，思路非常巧妙2^60^就是（1<<60）,减去1也就是从第一位到第59位都是1（第六十位是0...

构造 01染色 **** 思维 icpc2020济南

2021-01-24

1 825

B-Suffix Array

B-Suffix Array 题意：一个字符串只含有a和b，先给出b数组的构造方式：对于每个位置i来说：如果存在一个位置j，使得j<i,且s[j] == s[i],则b[i]=i-j 否则b[i]=0现在对字符串每个后缀都构造B数组，并按照字典序排序题解：参考博客题目标题就已经透露...

后缀数组 ***** 思维

2021-01-20

2 627

H.Minimum-cost Flow

H.Minimum-cost Flow 题目：其实就是给出每条边的单位费用，q次查询，每次查询改变所有边的容量（所有边容量一样），问最后流出1流量的最小花费是多少？题解：暴力做法肯定是每次询问都改一次容量，但是肯定会超时，想想其他方法对于题目的每次询问，每条增广路的容量为u/v，所需最大流是1...

最小费用最大流 **** 思维

2021-01-20

0 574

Codeforces1437 E. Make It Increasing（LIS）

Codeforces1437 E. Make It Increasing（LIS）题意：你有一个长度为n的数列a和一个含有k个不同整数的集合b，b中的数都在[1,n]内。现在你可以进行一些操作，每次操作中你可以选择两个数i和x，并将x赋值给ai。其中1<=i<=n，但i不能...

LIS 思维

2021-01-19

0 725

CG的通关秘籍

题意： n次顺序填数字，每次填一个[1,m]的数到当前位置，如果这个位置填的数比上一次填的数要大，形成顺序，他的兴奋度会增加1点，如果这个数比上一次填的数要小，形成逆序，他的兴奋度会增加2点，如果两个数相等，那么什么都不会发生。（如果是第一次填数，同样不会发生任何事情）已知n和m求所以填数方案的兴奋...

ing 数论思维

2021-01-16

3 599

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

HDU - 1134 Game of Connections

题意：在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数? 题解：卡特兰数题，卡特兰序列：1,1,2,5,14，42,132,429,1430············· 递推式f（n）=f（n-1）*（4n-2）/ (n+1) , 大数的模板可以做，java也可以队...

大数数论思维

2020-11-26

2 677

D - Take Your Seat

题意：飞机出发时有n个座位，一共n个人，Duha编号为1，每个人都有自己的编号，上飞机按照编号从小到大，Duha会随便选一个位置，后面的人如果发现自己的座位被选也会随机选其他座位，如果自己的座位没被选就会坐到自己的位置，问最后一个人做到自己座位的概率飞机回来时有m个座位，一共m个人，这次不按照顺序...

概率 *** 思维

2020-11-26

2 642

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