回归梦想

题解

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篇）

P4178 Tree

P4178 Tree 题意：给定一棵 n 个节点的树，每条边有边权，求出树上两点距离小于等于 k 的点对数量。题解：点分治的模板题是求等于K的路径条数本题是求小于等于K的路径条数，我们只需要改变统计答案即可原本统计答案是对一个路劲长度len，判断K-len在之前的子树中出现多少次，用f数组来记...

**** 点分治

2021-02-23

0 681

P4381 [IOI2008]Island

P4381 [IOI2008]Island 题意：给你一棵基环树森林，求出基环树的直径之和. 题解：对于基环树,我们将环看作根,那么直径有两种情况:: 1.不经过环,也就是环上某个点的子树内部,对于这种情况,直接在子树内部处理直径,更新答案即可; 2.经过环,答案就是i的子树内长度+j的子树内长...

ing **** 基环树

2021-02-22

0 665

Strange Definition CodeForces - 1471D 来自专栏

题意：定义数字 x 和 y 是“相邻”的当且仅当 lcm(x,y)/gcd(x,y) 是一个平方数。给定一个长度为 n 的数组 a。每过一秒，数组 a 会发生变化：ai 会变成数组 a 中与其“相邻”的所有数字的乘积。定义 di 为数组 a 中与 ai “相邻” 的数字个数。定义数组 a 的美丽值...

**** 数论思维

2021-01-29

0 628

Matrix Equation 来自专栏

题意：题目给出两个矩阵X,Y,现在有两种操作Z = X × YD = X⊙Y问是否存在一个矩阵C，使得A×C=B⊙C式子成立，问矩阵C能有多少个题解：这个式子在模2意义下的加法就等于异或也就相当于那现在有将BC移到左边然后将Ci,j的系数进行合并得到：aik =Aik A i,i = = B...

**** 数论高斯消元

2021-01-25

4 731

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

[SDOI2011]消耗战

[SDOI2011]消耗战题意：给出n个点的一棵带有边权的树,以及q个询问.每次询问给出k个点,询问这使得这k个点与1点不连通所需切断的边的边权和最小是多少. 题解：树型dp+虚树dp[x]:切断x及其子树上询问点的最小代价预处理出minv[pos]代表从11到pos路径上最小的边权如果pos...

dfs序 **** 虚树

2021-01-21

0 644

H.Minimum-cost Flow

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

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

2021-01-20

0 574

NC51319 King's Quest

NC51319 King's Quest 题目： N个男生和N个女生，告诉你每个男生喜欢的女生编号，然后给出一个初始匹配（这个初始匹配是一个完美匹配），求在保证匹配是完美匹配的基础上，输出每个男生可能会匹配的女生题解：参考题解：让我们首先来考虑建图如果王子u喜欢妹子v那我们可以从u向v连一条有...

****

2021-01-14

0 865

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