lifehappy

分类

未归档(1) 每日一题(2) 题解(78)

/ 注册

全部文章（共81篇）

Military Problem

Military Problem DFS序模板题了，l[rt]标记rt节点第一次进入，r[rt]表示rt节点退出，然后只要判断l[rt] + k - 1 是否小于等于r[rt]即可。 /* Author : lifehappy */ #include <bits/stdc++.h> ...

2020-11-06

4 803

金字塔（区间dp）

金字塔利用dfs序的通性，如果[l, r]是一颗完整的子树，一定有str[l] = str[r]，接下来就是考虑如何划分子树了。考虑对[l, r]的子树进行划分，枚举中间划分值mid，那么因为dfs序一定有str[l] = str[mid] = str[r]。我们定义dp[l][r]，为区间[l...

2020-11-05

4 624

Legacy（线段树优化建边跑Dijkstra）

Legacy 线段树优化建边，开两颗线段树：对于线段树1，自顶向下连边。对于线段树2，自底向上连边。然后对于op1我们直接连边即可。对于op2（u -> [l, r] cost = w），这个操作在线段树1上完成即可。对于op3（[l, r] -> v cost = w），这个操作在线段...

2020-11-05

5 758

Xor-MST

思路异或最小生成树，这里采用了一种分治的方法来贪心求解最值：首先我们对所有的点权值从小到大排个序，从高位开始在中间找到一个这个位置上的分界点分成两个集合，然后再通过递归的去求解两个集合。在递归的时候，对两个分开的集合，我们通过树去贪心的在两个集合连上一条边，把这条边加入我们的答案。为什么...

2020-10-26

5 665

Perfect Security

Perfect Security 思路只要把P数组加入树就好了，然后通过这颗树对A中的每一个数，去查找一个与之异或最小的值即可，同时还要支持删除操作，直接加入一个数组，记录当前是否还有数字经过这条边即可。注意在查询的过程中要不断的减小数组的标记。代码 /* Author : lifeha...

2020-10-26

4 698

Vitya and Strange Lesson

Vitya and Strange Lesson 思路树专题，所以一定是用树来写了，我们考虑，对原始数组，如何通过树来查找最小值。显然我们可以把，不在数组中的所有数字加入树，然后通过查找与0异或最小的数即为答案。这题显然我们也可以同样利用这一性质，先把不在数组中的所有数加入树，然后再通过查找与所有...

2020-10-26

4 650

奶牛异或

奶牛异或思路利用前缀异或和，不断遍历加入树就行，接下来的操作就跟查找异或最大值一模一样了，无非就是在结束点标记上当前访问的是第几个数就行了。代码 /* Author : lifehappy */ #include <bits/stdc++.h> using namespa...

2020-10-26

5 758

The XOR Largest Pair

The XOR Largest Pair 思路树板子题，直利用异或的性质，在树上遍历就行了。代码 /* Author : lifehappy */ #include <bits/stdc++.h> using namespace std; const int N = 5e6 ...

2020-10-26

3 543

对称二叉树

对称二叉树思路递归就好了，确实，递归就好了一个递归去dfs，另一个去递归check，check注意要对称进行左右子树的访问，然后整体复杂度因该是的。代码 /* Author : lifehappy */ #include <bits/stdc++.h> using name...

2020-10-18

3 633

[CQOI2013]新NIM游戏

[CQOI2013]新NIM游戏思路 NIM游戏，先手获胜的条件就是，所以值异或后不为0，也就是在进行完第二轮后，场面不为0即可获胜。也就是让第二***作的人不能从这若个个数得到0，这个判断就可以用线性基来完成了，同时我们又要保证第一轮拿的值最小，所以我们考虑贪心，优先把较大的放入线性基这样我们就...

2020-10-15

5 486