搜索结果
查询Tags标签： maxn，共有 417条记录-
P1220 关路灯
感谢所有AC 传送门 经验当遇到动点的$dp$问题时，需要注意动点所在位置对状态转移的影响，如果有影响，可以适当考虑增加一个维度用来表示动点地位置状态。 思路由于老李关掉灯的时间忽略不计，因此老李所过之处一定是所有灯全灭，那么关灯就可以有两种选择，一种是沿着现…
2022/4/23 6:16:22 人评论 次浏览 -
Edge Groups(ICPC)
树上计数 考虑如果一个点的亲儿子是偶数个 两两亲儿子配对就好 如果一个点的亲儿子是奇数个 挑一个出来和连上父亲 其余偶数个两两配对 n个两两配对的方案数为 (C(n,2)C(n-2,2)...C(2,2))/((n/2)!) 化简得 （n!）/（2的n/2次方）（(n/2)!）预处理阶乘就好 #include<bit…
2022/4/21 23:12:37 人评论 次浏览 -
Codeforces Round #782 (Div. 2)
前言 两个 E，两个印度人。 \(\texttt{Rating Change:}\color{grey}{683}\color{black}\to \color{green}{1205}\) \(\Delta={\color{green}{\texttt{522}}}\qquad \texttt{rank:285}\) A 由于题目保证了红色一定大于蓝色，所以直接算在 \(b+1\) 个空隙中把红色均匀插入就…
2022/4/18 23:16:38 人评论 次浏览 -
洛谷P2607 [ZJOI2008] 骑士
在做这道题之前，可以先去看一下: P1453 城市环路： https://www.cnblogs.com/liyishui2003/p/16150985.html 如果说城市环路是没有上司的舞会的基环树版本 那P2607就是城市环路的基环树森林版本 刚开始开开心心把城市环路的代码改了改输出输入就交了，wa，20tps 挠头，想…
2022/4/15 23:13:06 人评论 次浏览 -
CF103D Time to Raid Cowavans 题解
这道题看似可以线段树乱搞，但是真正用线段树就会发现根本没有用。 因此我们考虑根号算法。 难道是分块？错！还有一种根号算法——根号分治。 根号分治的思想就是设定阈值 \(S\) ，大于阈值的暴力计算，小于阈值的快速计算，而取 \(S = \sqrt n\) 时最优（不要问我怎么证…
2022/4/14 23:17:46 人评论 次浏览 -
CF940E Cashback 题解
这道题好像很烦，我第一眼看过去确实没有任何思路。 但是仔细分析题目后，我们会发现：\(c=1\) 时，答案为 0，但是好像没有这个点？ \(c > n\) 时，答案为序列总和。 \(c = n\) 时，答案为序列总和减去最小值。 \(1 < c < n\) 且 \(n < 2 \times c\) 时，此时…
2022/4/14 23:16:36 人评论 次浏览 -
双子序列最大和问题
感谢所有AC 链状 传送门 思路由于两个子序列不重叠，显然的这两个子序列之间一定有一个断点。要求两个子序列之和最大值，可以枚举断点的位置，对比每个断点下左序列和右序列的最大值之和，最大的即为答案。接下来该怎么求解每一个左序列的最大值和右序列的最大值呢？在这…
2022/4/14 6:15:24 人评论 次浏览 -
2022.4.10#树链剖分=链式前向星+dfs序+lca思想+线段树
2022-04-10 树链剖分，理解完只有惊叹。 前置知识： 链式前向星： 需要的变量： cnt 记录边数 edges{ to,w,next}的数组，存储边 head[maxn]存储每个节点的最新的那条边1 //链式前向星，储存图的方式，思想是前向2 //相当于一个邻接表的每一行的链表，向最前端插入3 4 #in…
2022/4/10 23:44:39 人评论 次浏览 -
19. 牛客-学霸大帅哥zyh
题目链接：学霸大帅哥zyh dsu on tree，用线段树维护答案，每次修改的时候只会改变一个数，所以只会变一条链，非常好写。复杂度 \(O(n\log^2 n)\)。题是好题，就是数据太水了，\(O(n^2\log n)\) 的假做法都能过。 #include <bits/stdc++.h> using namespace std; #…
2022/4/9 23:21:16 人评论 次浏览 -
AcWing第8场周赛题解
A. 3770. 最小消耗 题目链接：https://www.acwing.com/problem/content/description/3773/ 题目大意：按照题目要求消灭两种类型怪兽（可以消耗 c 转换）的最小消耗。 解题思路：循环记录 0 和 1 出现的次数，消灭一个 0 的最小消耗为 min(a, b+c)，消灭一个 1 的最小消耗…
2022/4/9 6:20:41 人评论 次浏览 -
DP专题-学习笔记：树形 DP
目录1. 前言2. 详解3. 练习题 1. 前言 树形 DP，是一种 DP （废话），专门用于树上的 DP。 这类 DP 因为其板子好记，标记显眼而十分易懂。 而且树形 DP 长得就不像 DP，更像暴力搜索。 当然 DP 肯定也有很大思维量的，但是像树形 DP 代码确实挺好打。 2. 详解 例题：P135…
2022/4/8 23:22:51 人评论 次浏览 -
CF721C Journey 题解
题目给了我们一张 DAG，对于 DAG 常用的方法就是拓扑排序。 题目要求一条从 1 到 \(n\) 的路径， 点数尽量多但是距离不能超过 \(k\)，那么我们考虑 DP 解决这个问题。 设 \(f_{i,j}\) 表示从 1 开始经过 \(i\) 个点，到达 \(j\) 点的最短路径，那么首先满足最优性。 而拓…
2022/4/7 23:23:03 人评论 次浏览 -
4.6省选练习
省选时间定了,慌是不可能的,这辈子是不可能的 \(T1\) //直接看这一位选什么就好了 #define Eternal_Battle ZXK #include<bits/stdc++.h> #define int long long #define MAXN 1000005 using namespace std; int cnt[35][2]; int n,a[MAXN]; void sol() {int res=0…
2022/4/6 23:22:53 人评论 次浏览 -
最短路问题的一些见解
0x00. 最短路的定义 在一个赋权图 \(G\) 中，点 \(u\) 到点 \(v\) 有若干条通路，定义 \(u\) 到 \(v\) 的最短路为这些通路中边权值和最短的一条在上图中，从 \(1\) 到 \(7\) 的最短路为 \(1 \rightarrow 2 \rightarrow 5 \rightarrow 7\) 或者 \(1 \rightarrow 2 \righta…
2022/4/3 23:24:23 人评论 次浏览 -
P7683 [COCI2008-2009#5] KRUSKA
洛谷上这道题的第一篇题解。上海加油。 题目大意 Aladdin 已经厌倦了宫殿里的生活。他有一份稳定的工作，他的妻子 Jasmine 和孩子们都在路上，生活变得单调。在这一切的驱使下，他决定在安顿下来之前再进行一次冒险。他决定找到 Golden Pear，这是一件极为珍贵的传奇文物…
2022/4/1 23:24:12 人评论 次浏览
