昵称很长很长真是太好了

每日一题

bfs(5) codeforces(19) kmp(1) python(7) 前缀和(1) 图论(2) 数据结构(18) 未归档(14) 牛客(3) 线段树(4) 记忆优化搜索(1) 逆元(1) 题解(99)

/ 注册

全部文章 / 每日一题（共14篇）

[HAOI2015]树上操作来自专栏

首先先说一下基本概念： 1.重儿子：一个结点的所有儿子中，大小最大的那个（最重的，所以说只有一个，如果有多个儿子的大小相等那就随便取一个）。 2.轻儿子：一个结点的儿子除了重儿子以外的所有儿子都是轻儿子。（根节点为轻儿子） 3.重链：从一个轻儿子开始，一路往重儿子走，连出来的链叫重链。 4.轻链：除...

2021-03-27

1 594

3月9日Tree Decoration 来自专栏

题解：对于叶子节点，我们直接购买要求购买的个数即可然后树上维护几个变量，sz表示该节点的子树已经挂在了多少个礼物了，如果挂载的礼物总数小于要求的总数，那么当前结点是要必须再购买一些礼物的，但是并不一定买在当前结点上，我们可以买在他已经他子树上，找一个最便宜的结点来购买礼物，从而保证价格最低！这个我...

2021-03-11

0 545

区区区间来自专栏

题解：线段树，不过这里线段树区间维护要换一种方法。我们发现这个等差数列的等差为1。对于修改一段区间如果我们知道首项值，那么我们便可以在的时间复杂度计算出这段区间的大小。又可以知道，对于线段树每一个结点，代表一段区间，那么我们我们用lazy数组保存这一段区间的首项，那么我们便可以在O（1）的时间复杂...

2021-03-09

0 508

XOR-pyramid

题解：给n个数，询问q次，每次询问给出l,r. [l,r]区间求异或最大值为多少？所以用dp[l][r]来表示区间l,r的答案先对他进行预处理，预处理后就可以进行dp了。递推公式：f[i][j]=max(f[i][j],max(f[i+1][j],f[i][j-1])); /*Keep on g...

2020-08-31

0 370

蓝魔法师来自专栏

题解：树形dp对于每棵子树，有两种可能1.不删除这条边，两个点相连 2.删除这条边，两个点各自独立定义dp[i][j] 表示 i 结点所在的连通块中节点数为 j 的方案数是多少 /*Keep on going Never give up*/ //#pragma GCC optimize(3,&q...

2020-08-31

0 457

[HEOI2014]南园满地堆轻絮来自专栏

题解：答案就是差距最大的逆序对的一半，因为两个数都减小一半就可以了。时间复杂度O（n） /*Keep on going Never give up*/ //#pragma GCC optimize(3,"Ofast","inline") #include &l...

2020-08-31

1 483

Forsaken喜欢数论来自专栏

题解：欧拉筛和埃氏筛都可以过。在筛素数的过程中，每个非素数都是用他最小的质数筛掉的，所以在筛的时候记录一下就可以了。 /*Keep on going Never give up*/ #pragma GCC optimize(3,"Ofast","inline"...

2020-06-22

0 508

K-th Number 来自专栏

题意：给定一个数列A和一个空的数列B，从数列a中选取大于等于k的连续序列长度的第k大数放进b序列中，再从b序列中找出第m大数。题解：这个题是通过二分答案+尺取法（判断条件）来解决的二分答案：我们通过二分答案来猜测这个第m大的数到底是多少，如果猜大了，那么我们就把他往小区间缩，如果猜小了就把他往大区间...

2020-06-01

0 484

[NC15748]旅游来自专栏

菜鸡第一次接触树形dp这个东西，不过这个东西还是很好理解的（可能是因为模板题吧）个人感觉，相比线性dp，树形dp的状态转移方程更加的直观，难点主要是在“树”的结构上比较麻烦。题解：树的遍历是从根节点往子节点的方向深入，所以用dfs编程会容易一些。这个题根据dp的解题思路，定义状态：dp[i][0]，...

2020-06-01

0 515

[USACO07JAN]Protecting the Flowers S 来自专栏

题意：有n只奶牛正在吃花，农场主要把他们全都抓回去，给出每个奶牛得吃花速度和抓回去得时间（这里时间要乘2，来回），问约翰最少损失多少朵花。题解：贪心这题得贪心还是比较明显得，主要是通过分析前后两个整体来进行交换得，我们要考虑先牵哪一头奶牛才能时吃掉的花朵最小，我们可以讨论牛x和牛y先抓x：2x.ty...

2020-05-31

0 514