回归梦想

分类

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

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 687

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

Jamie and Tree[CF916E]

Jamie and Tree[CF916E] 题意：有一棵n个点的树，每个节点上有一个权值wi，最开始根为1号点．现在有3种类型的操作：• 1 root, 表示将根设为root.• 2 u v x, 设u, v的最近公共祖先为p, 将p的子树中的所有点的权值加上x.• 3 u, 查询u的子树中的所...

线段树 **** 树链剖分

2021-01-23

0 563

[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

餐巾计划问题[网络流24题]

题意： • 一个餐厅在相继的N 天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f 分；或者送到慢洗部，洗一块需n 天(n>m)，其费用为s<f 分。每天结束时，餐厅...

ing **** 网络流思维

2021-01-19

0 606

NC51319 King's Quest

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

****

2021-01-14

0 865