回归梦想

分类

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人学习

全部文章（共1124篇）

Stone Game 来自专栏

题意：有n堆石头，每堆石头最多只有三个石头（最少1个），每两堆石头（这两堆各含石头x个和y个）合一起的费用为(x mod 3) * (y mod 3)，现在把所有堆合成一堆，问最小费用题目第一行给出三个数，第i个数表示有i个石头的堆有多少个题解：费用是(x mod 3) * (y mod 3)...

** 思维题 icpc2020济南

2021-01-24

0 978

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

[HAOI2006]均分数据来自专栏

[HAOI2006]均分数据题解：题目稍微解释一下：把n个数以分为m组，计算每一组的和，求得到的这m个数的方差。由于分法是任意的，我们要求这些方差中的最小值我们先用STL中的函数random_shuffle()用来对一个元素序列进行重新排序（随机的）众所周知：如果每个组数的大小都相近的话，方差就...

** 随机数模拟退火

2021-01-23

3 714

质数与合数

质数与合数题意： FFF和GGG正在玩一个质数与合数的游戏一开始有N个石头FFF和GGG轮流对这堆石头进行操作，FFF每次选择1到K之间的一个数x，并拿走x个石头，拿走之后剩下的石头数量必须是质数接着GGG进行同样的操作，但是要求拿走之后剩下的石头数量必须是合数假设双方都足够聪明，第一个不能操作的...

模拟博弈论 ***

2021-01-23

0 749

P3803 【模板】多项式乘法（FFT）

P3803 【模板】多项式乘法（FFT）题目描述给定一个 n 次多项式 F(x)，和一个 m 次多项式 G(x)。请求出 F(x)和 G(x)的卷积。从低到高输出F(x)*G(x)的系数另一种问法：如果有两个无限序列a和b，那么它们卷积的结果是：求出yn值题解：模板题建议背过模板讲的非常不错...

模板题 FFT 数论

2021-01-23

0 722

[AH2017/HNOI2017]礼物

题意：两个数列，每个数列都可以顺序旋转，也可以对所有数同时增加一个非负整数，现在问的最小值题解：在求卷积前要将A数组倍长，B数组翻转B数组翻转好理解，为什么A数组倍长，因为题目的数列是可以移动的，而我们不知道哪一部分和B卷积是最佳答案，所以讲A数组倍增，然后每次取A中连续长度为n的区间与B倍增...

FFT 数论思维

2021-01-23

0 613

P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包

P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包题目：给定一些点，问围住所有点所用的围栏的长度题解：凸包模板题凸包详细代码： #include<iostream> #include<algorithm> #include&l...

** 凸包计算几何

2021-01-23

0 863

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

（神奇的）虚树（初步了解）

参考文献：博文1博文2博文3 引入在一类树上动态规划问题中,题目给出的询问往往包含树上的很多各节点,并保证总的点数规模小于某个值. 如果我们直接在整颗树上进行dp的话,时间复杂度与询问的次数有关,这显然是不可接受的,如果我们可以找到一种动态规划的方法,使其时间复杂度与询问中点的实际规模相关就好了...

虚树 ***

2021-01-21

0 551