凡尔赛卷卷

分类

做题笔记(85) 学习笔记(16)

/ 注册

全部文章（共101篇）

牛客最长树链图

最长树链题目链接这道题让我明白了运气是实力的一部分暴力出奇迹题目大意：给一棵树让求最长的树链: ***，这不就树的直径吗给每个点权值，找出的链要满足链上的点的权值的 gcd > 1 然后找一个最长的所以怎么做呢？一直想不出来没想到就是暴力，怎么暴呢？就是枚举质数，但...

2020-09-15

0 468

acwing 区间 gcd 线段树

区间gcd 题目链接题目大意：两种操作： Q l r 查询 l~r 的区间gcd C l r x 将l~r 区间的数都加上x 怎么做？我这tm都不会好菜想一下怎么求gcd？辗转相减？ gcd(a,b) == gcd(a,b-a); 所以 gcd(a1,a2,a3,a4,……) ...

2020-09-15

0 698

牛客练习赛56 小魂和他的数列

小魂和他的数列题目链接题目大意给出一个数列，让求长度为k的严格递增子序列有多少个怎么做呢？显然dp 这个是很好想的 for (int i= 1; i <= n; i ++ ) { dp[i][1] =1; } for (int i = 2; i <...

2020-09-15

0 653

分块简单的

分块分块是啥？暴力？以前看分块看了一半，放在那里了，，今天想起来了，就又看了一下分块的思想：把n分成根号n块然后暴力，这也没啥，主要是记录一下大段: 被分成的块一大块假设要维护的区间是 l~r 把在这个区间里的大段区间暴力维护一下，把两旁的不是一整段的小段暴力维护就好。时间复杂度...

2020-09-15

0 367

cf 1189d1 图

cf1189d1 题目链接题目大意有一种操作：选择两个叶子结点，把两个点的最短路径上的权值同时加或减任意一个数给出一棵树，问你是否可以经过操作把这棵树上的权值变成任意数刚开始我的想法：在每一个非叶子节点上必须直接相连一个叶子结点（错的）比如这样：因为我感觉只有这样才可以满足条...

2020-09-15

0 452

acwing249 蒲公英分块

acwing 249 题目链接题目大意题目意思很简单，给出一个长度为n的数组、m个查询；每个查询有 l ~ r 查询的是区间里的众数，如果数量相等输出小的那个。这可怎么做，？刚开始看到这道题、懵了一会、想不到怎么做；线段树没办法维护或者是我不会维护感觉咋咋都不行于是看了看书上的...

2020-09-15

0 492

牛客 Shortest Path 图

Shortest Path 题目链接题意给一棵树、让把树分成两半（不是砍成两半、是节点分成两半）也就是分成n/2 个 A -------- B 然后让他们的总的权值最小保证n是偶数怎么做？权值最小是忽悠人的。。因为只能分成一种情况首先叶子结点肯定跟他的父节点相连。。（因为必须得...

2020-09-15

0 500

vj Innumerable Ancestors 图

Innumerable Ancestors 题目链接题意给出一棵树（1为根）、有m次询问；每次询问给出两个节点集合、从这每个集合中挑出一个节点（可能相同）、让求这两个节点的lca最深是多少。怎么做？ lca很好求，倍增，但是节点怎么挑？这里很巧妙？或许是我见识短求出这棵树的dfs...

2020-09-15

0 445

替罪羊树学习笔记哦

替罪羊树替罪羊树是啥？就是一个平衡树，只不过没有旋转操作那遇到不平衡的咋办呢？重构。怎么重构？先求出不平衡子树的中序遍历（这个中序遍历肯定是有序的递增的）于是就可以分治建树，取中间那个点当根左边的当左子树、右边的当右子树……递归下去于是就把不平衡的子树变成平衡的子树。例题：洛谷模板...

2020-09-15

0 428

cf 566 D. Complete Mirror 图

D. Complete Mirror 题目链接题目大意给出一棵树，让你找一个根节点，使每个到根节点距离相等的点的度数都相等。怎么做呢？想一下答案有几种情况： 1、所有叶子节点。这个应该都可以想到不是叶子结点的情况：又是歪歪又扭扭的图这个图的答案只能是4。所以： 2、树的重心。...

2020-09-15

0 569