侃YE西

分类

图论(1) 基础算法二分双指针等(4) 数据结构(3) 数论数学(5) 比赛(1) 题解(53)

/ 注册

TA的专栏 29篇文章 0人订阅

29篇文章 869人学习

全部文章（共9篇）

幸运数字II 打表

题意：定义只包含4和7的数字为幸运数字给出区间l,r 求l,r中每个next(i)的值的和 next（i）为第一个大于等于i的幸运数思路：看到数据范围好像很大其实不然在范围内的幸运数字只有几千个按位数来算的话 1~9 那么幸运数字总共有2^1+2^2+...+2^9个所以我们采用bfs打...

2020-04-09

0 888

【每日一题】 Running Median 优先队列来自专栏

题意：动态求中位数思路：建一个大根堆和一个小根堆用大根堆维护较小的部分（中位数左端）用小根堆维护较大的部分（中位数右端）这样大根堆堆顶的就为中位数插入数据时维护两堆堆顶的大小关系即可 #include <bits/stdc++.h> using namespace std; ...

2020-04-08

0 569

【每日一题】黑白树 dfs 来自专栏

思路：树的题目多半和dfs有点关系滑稽.jpg首先对于叶子结点的话是一定要染色的这显而易见关键点在于对于已经被覆盖了的点的操作根据贪心可能会想已经覆盖的点我不再去动它了但这其实是错的很容易就举出反例若其中有一个点覆盖范围巨大这思路就是错的了所以对于其他的结点更新最大染色范围的...

2020-04-08

0 639

【每日一题】树 dp 来自专栏

题意：给出n个结点的树用k种不同的颜色染色当且仅当对于所有相同颜色的点对(x,y)，x到y的路径上的所有点的颜色都要与x和y相同个染色方案才是合法的题意：既然是颗树连通性是一定的题目说的有点绕但其实就是至多给k个联通块染色求染色方案数从一个叶子结点出发考虑用来代表前i个结点染j种颜...

2020-04-07

0 810

Maximize The Beautiful Value 前缀和

题意：给出n个数字和 k 问将一个数字（只要一个）向前移动至少k个单位有变化的向后顺延使得最大思路：先预处理个前缀和和原始数组的答案越往前面越小为了保证答案最大只需要移动k位就好然后从第k+1位开始枚举变化情况因为每次移动在当前位置i 到 i - k区间内的数都会往后顺延1...

2020-04-07

0 653

NC13221 数码枚举暴力优化来自专栏

题意：求区间l,r中的数x 及其 x的约数最高位出现的次数思路：首先利用前缀和的思想将问题转化成求 [1,r] - [1,l-1]题目是说求x的约数首位出现次数自然就想到枚举因子假设当前有因子a 则另一个边界显然就是x/a将他们都假设成 L,R 所以问题变成了在L,R中求最高位为出现的次数而...

2020-04-06

0 627

Shortest Path 来自专栏

题意：将n个点分成n/2个集合问最小代价是多少思路：通过画图可以发现，当某个结点的子树结点个数（包括它本身）个数为偶数的话，他是可以实现内部互联的，反之，如果点为奇数的话，它肯定要和外边的点相连，所该点到父亲结点的一定会有贡献 #include <bits/stdc++.h> us...

2020-04-04

0 562

月月查华华的手机预处理优化+暴力来自专栏

题意：在主串中寻找子序列思路：字符串长度都来到了1e6 暴力肯定超时我们可以先预处理一个next数组来表示主串当前第i个字符到任意26个字母下一个位置是在哪然后模式串根据next数组匹配复杂度为 "图片标题") #include <cstdio> #includ...

2020-04-02

0 605

NC22598 Rinne Loves Edges 来自专栏

题意：给出n个结点m条边的无向联通图备注里说边的数量m恒等于n-1 那么就是一颗树选出一个点s 使得所有度为1的结点都到不了s 度为1的点显然就是叶子结点思路：既然是树形dp 那么就先思考下他们的子问题是什么目标是使得所有叶子结点都到不了s 显然子问题要从子树开始入手处理的方法也就两...

2020-04-01

0 536