DeNeRATe

分类

题解(55)

/ 注册

全部文章（共10篇）

[SCOI2015]国旗计划

题意给你一个环，有个区间,区间之间互相不覆盖。求当任意一个区间必须选择时，最少需要多少个区间能够覆盖整个环。思路对于一个战士，如果选了他，那么下一个战士一定是所有左端点小于等于的右端点的战士中最大的一个战士，因为这样子才是是最优的。所以我们只需要预处理加二分找到下一个战士就好了...

喹啉

2020-11-26

6 865

A and B and Lecture Rooms

题意题目的意思就是每次询问点x，y，要你求其中离它们距离一样的点有多少个。分析我们可以先找到这两个点的，然后路径的中点肯定是一个解（没有就无解咯）。然后从这个点不经过这条路径任意一点能到达的点，就是其他解。求法的话，比较两个询问节点的深度深度相同：深度不同：代码 #inclu...

喹啉

2020-11-25

2 771

疫情控制

题意给你一棵有个节点的树，要求在所有叶子节点到根节点的路径上有一个节点是特殊的（军队）。问如果要封死这棵树，移动距离最大的点移动的最小距离是多少？分析这题挺恼火的，一步一步慢慢来首先：树上倍增先预处理用存储节点的第个祖先的节点编号，存储节点到它的第个祖先的路径长度。在...

喹啉

2020-11-25

9 998

[AHOI2008]MEET 紧急集合

题意 PS:（最近好多题题意都好难懂啊QAQ）给你一棵个节点的树，有次询问，每个询问给你三个节点，求树上一个节点使得这三个点到的距离之和最小。每次询问输出这个节点的编号以及路径之和。分析考虑每两个节点之间的最短距离就是求这两个点的，那么三个点我们可以先两两一组找到。我们可以发现...

喹啉

2020-11-25

8 1039

对称二叉树

题意给你一棵树，你需要找到它的一颗子树满足以下条件1.是一棵二叉树2.这棵树的所有节点的左右儿子交换位置，交换后新树和原树的结构及每个位置的点权没变。分析先预处理出每棵子树的大小，然后枚举以任意节点为子树的根。递归处理这棵树的正确性。当这个节点没有儿子直接返回。当有两个儿子且两个儿子的权相同时...

喹啉

2020-10-16

6 765

[ZJOI2006]物流运输

做法 SPFA+DP 思路贪心显然不可取，考虑用动归。令表示第天的最小花费，最后输出的答案显然就是。DP方程的转移显然：哦，对了数组存的是第天到第天都走同一条最短路的花费。对于数组的初始化，很简单，对于每一个，先把到天之间封闭的码头全部设为不可走，跑一遍最短路即可，初值为无穷。代码 #inclu...

喹啉

2020-10-14

3 602

筱玛爱线段树

题意给你一个初始值为的序列。你现在有两种操作，一是给的区间加；二是再执行一遍第次到第次的操作。思路两次差分。第一次为处理第二种操作，我们定义为第次操作要执行的次数，用差分实现。第二次是处理区间加，也可以用差分。所以，差分就对啦！代码 #include<bits/stdc++.h>...

喹啉

2020-10-12

6 778

[SCOI2009]最长距离

题意给你一的网格图，表示通路，为障碍。你有次机会使得障碍变为道路（变为）。求这张图上的最大欧几里得距离。思路先预处理表示一个点到任意点之间的障碍个数，如果小于则视为通路。再求这一点和全图的最大欧几里得距离。最后枚举全图每一个点作为起点的情况，再用记录最大值就可以了。代码 #include&...

喹啉

2020-09-25

3 840

最后的晚餐

一眼看上去就是一个经典题啊直接考虑不是很容易那就容斥全部方案为：一对相邻：,此情况有种两对相邻：,此情况有种……所以：最后预处理一下就可以了。 #include<bits/stdc++.h> #define ll long long const ll N=30000010,INF...

喹啉

2020-09-23

3 738

The XOR-longest Path

首先说一下题意。这题就是给你一棵树，求树上所有路径中异或和最大的。一个前置小芝士：01trie树不会的童鞋自行百度一下（雾）好了，分析一下本题我们对于每一个数到根节点的异或和进行建01trie树。我们知道一个数，如果它两次异或同一个数，那么它是不会变的。所以i-j的路径上的异或和，就可以表示...

喹啉

2020-09-16

3 744