fuzhiji

题解

/ 注册

全部文章 / 题解（共19篇）

kingdom------(dp)

我们先根据题意一步一步分析，由于只是给出树的节点个数，树可以由我们任意构造，我们假设n个节点取得答案最大的时候树长这样根节点root，连接着k个子树，k个子树大小分别为sum1,sum2.....sumk，有我们令ans[n]为n个节点的树所得的最优解root的“心腹”其实就是root的重儿子，我们...

dp

2020-07-10

10 1306

Color-------二分图的最大匹配

根据题意，一个点延伸的所有边，一定是颜色不一样的，求最小颜色数和方案。由于是二分图，最小颜色很显然是全部点的最大度数，关键就在于如何求解方案？我们这样思考，由于存在最小颜色数是最大度数这一结论，所以，我们每次使用一个颜色后，所有度数最大的点的度数肯定会减一，不然就会得出一个错误的构造方案（与结论相反...

二分图最大匹配

2020-07-08

0 1000

最短路------LCA+bfs

题意简洁明了，数据级别，直接排除了多源最短路的算法，值得一提的是，十分奇特，一棵树的边是，我们可以将这个图看成一棵树加上100条以内的边的图。先考虑一棵树，如何求两点距离？我们需要前置知识点：LCA（最近公共祖先）红色框框的两个节点u,v，求他们的距离，看他们的深度:depth[u]=4，de...

lca bfs

2020-07-07

5 1395

平衡二叉树------递推

根据题意，找出左右子树最大差值，这个最大值一定是通过这颗树的根节点的左右子树的差值得到的，对于左子树，我们可以令他为满二叉树，这样的节点数最多，假设深度为n，那么左子树为满二叉树的节点数 ,对于右子树，如果差值要越大，那么节点数尽可能小，我们只要求出高度差为不超过d且深度为n-d-1的平衡树的最少节...

递推

2020-07-03

0 2480

毒瘤xor-------前缀和+贪心

对于一个区间[L,R],对于X二进制下的每一位，如果第i位1，那么对总和的贡献就是[L,R]中的元素第i位是0的元素个数，反之，所以对于X的每一位i的取值依赖于[L,R]中所有元素该位中0，1的数量，如果1居多，那我们就设置0，得到的总和就会大一点，否则就设置1，前缀和预处理一下即可。 #inclu...

贪心前缀和

2020-07-02

0 972

借教室-------线段树（区间更新）

以时间为下标，1~n，每个位置的值初始化为当天可以出租的教室数量，按顺序处理订单，对于每个订单d s t，在区间[s,t]减去d，如果出现了区间最小值出现了小于零的情况，说明不符合，直接输出然后return 0，否则处理完全部订单之后输出0即可。 #include <cctype> #i...

线段树区间更新

2020-06-30

0 977

漂亮的公园——虚树+dp+lca

假设节点颜色为 ,对于求颜色在树上距离最大的两点，我们需要先找出树上颜色为的距离最大的两点，找出树上颜色为的距离最大的两点，然后枚举求不同颜色的两点距离，得到的最大值就是的最远距离。所以，我们只需要预处理出所有颜色的最远两点，然后计算的时候用LCA求距离即可。当然，颜色可能很多，多达种...

虚树树的直径 lca dp

2020-06-03

2 894

小C的棋王之路------（ODT）

相信珂学emmm，一眼板子题，直接珂朵莉树，set针对区间覆值进行启发式合并，使用内置二分函数lower_bound分裂区间左右端点，然后暴力模拟，十分简单粗暴，操作1和操作2都是暴力，直接for，为何不会超时，就因为有操作3，每次区间赋值，我们可以将区间合并为一个，直接用结构体表示struce n...

珂朵莉 stl

2020-05-18

1 692

环鸽不会X点------(规律)

，如果k是奇数，那么sum也是奇数，如果k是偶数，那么sum也是偶数，第一步先判断n和k的奇偶性是否一致，第二步，因为正偶数2开始，正奇数1开始，所以最小总和为，判断n是否小于这个最小值，如果小于就，否则 #include <bits/stdc++.h> using namespa...

2020-05-17

1 726

环鸽的CHONG------（乱搞^o^）

由于要求全部子区间都存在唯一元素，所以最初可以判断是否符合，直接暴力for，然后记录只出现一次的元素的下标，存进一个vector里面，我们可以发现，只要包含唯一元素的区间，肯定符合条件，因为在区间唯一，所以其他区间该元素肯定也唯一，就像分治一样，以这些唯一元素为分界点，递归其剩余区间。例如区间 ...

2020-05-17

1 827