凡尔赛卷卷

做题笔记

学习笔记(16)

/ 注册

全部文章 / 做题笔记（共85篇）

CF E69 D dp

Educational Codeforces Round 69 (Rated for Div. 2) D 题目链接题目大意：输入一个数组 n m k 求在数组中找一段连续的数求 ∑ai − k * ⌈(r−l+1)/m⌉ 的最大值显然 r - l + 1 是找的连续的数的长度；这个题m...

2020-09-15

0 477

牛客练习赛56 E 图

牛客练习赛 56 E 题目链接这道题其实并不难，为什么要写他呢？因为被他坑了题目：给一个图，自己加上一条边后，问随机删去一条边后让图不连通的最小概率。很明显缩点建图然后跑个树的直径设直径为 d 缩点图上共 m 条边原先图*** s 条边答案就是 (m-d)/(s+1) 但...

2020-09-15

0 406

牛客最长树链图

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

2020-09-15

0 365

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 577

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

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

2020-09-15

0 552

cf 1189d1 图

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

2020-09-15

0 361

acwing249 蒲公英分块

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

2020-09-15

0 379

牛客 Shortest Path 图

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

2020-09-15

0 401

vj Innumerable Ancestors 图

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

2020-09-15

0 353

cf 566 D. Complete Mirror 图

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

2020-09-15

0 451