CF620E New Year Tree 题目地址： https://ac.nowcoder.com/acm/problem/111259 基本思路： 我们发现颜色最多只有种,所以明显我们可以用二进制串来表示每种颜色, 并且因为操作中只有对子树的修改,所以我们直接序+线段树维护一下二进制状态就是了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(...

旅行 题目地址： https://ac.nowcoder.com/acm/problem/19963 基本思路： 数据范围比较小,我们考虑暴力枚举到最小速度,并且在每次最小速度确定情况下的找到对应最小的最大速度。具体的我们只要将边从小到大排序,然后枚举到最小速度对应边后,并查集维护往后连边,直到和联通就行了。得到每次的结果后取最小,注意这里要写个比较函数比较分数。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #def...

Necklace 题目地址： https://ac.nowcoder.com/acm/problem/111227 基本思路： 分情况构造：如果宝石个数中有两个以上的奇数,那么结果一定为,随便输出一个串即可。如果宝石个数中仅有一个奇数,那么结果为所有数的,构造考虑输出个回文串,奇数个数的宝石放在回文串的中间位置。如果宝石个数中没有奇数,那么结果同样为所有数的,由于对称性,只要考虑构造出个回文串。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using nam...

Superhero Battle 题目地址： https://ac.nowcoder.com/acm/problem/113566 基本思路： 比较简单的数学+模拟,我们先考虑一下无限循环下去的情况,很明显只要在一轮循环中不能让HP清零,并且每轮的总和是大于等于零的,那么就会无限循环下去;否则我们实际上只需要枚举最后一轮怪物被杀的位置,然后直接用剩余的血量去计算一下之前循环的轮数就行了。算出每个位置的结果取最小就是答案了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h...

消耗战 题目地址： https://ac.nowcoder.com/acm/problem/212521 基本思路： 先补充一下数据范围: ,, 我们发现如果没有次的查询单单是询问一次,那么设为切断这颗子树下所有点的最小代价,为到号点的路径中最小的边权,我们可以很容易的得到一个树形的转移方程: 但是我们肯定不能对每次的查询暴力跑,我们观察到,似乎可以从这里入手,因此我们引入虚树的概念。虚树,实际上就是对于每次查询的点,我们只针对这些有用的点建树,而忽略那些用不到的点,对于虚树的构建我们可以参考下面的步骤:首先我们要将每次查询的点,根据序进行排序;然后我们维护一个栈,栈底到栈顶的元素...

Military Problem 题目地址： https://ac.nowcoder.com/acm/problem/112932 基本思路： 题目很长,可以概况为给你一棵树,每次查询,你要找到从开始按照遍历顺序,遍历到的第个节点,也就是找到点对应序后第个的节点就是了,然后注意超出子树的范围了要输出。 参考代码： #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false); cin.tie(0) #define ll long long #define...

Propagating tree 题目地址： https://ac.nowcoder.com/acm/problem/110318 基本思路: 我们发现是非常裸的子树修改然后单点查询,所以我们考虑用差分树状数组去维护子树状态,但是我们发现它对于权值的修改是一层加一层减这样的,所以一个树状数组肯定不够了,我们考虑维护两个树状数组,一个维护奇数层的修改,一个维护偶数层的修改,这样每次我们对同奇/偶的层加,对不同奇/偶的层减,就能完成对子树的维护,然后对于每次查询,判断是奇层还是偶层加上贡献就行了。 参考代码: #include <bits/stdc++.h> using n...

Tree Requests 题目地址: https://ac.nowcoder.com/acm/problem/111044 基本思路: 有对每个子树下的查询,但没有修改,考虑，我们先将查询离线,并且预处理出深度,对于每一棵子树我们统计一下每种深度下每个字母的出现次数,由题意我们知道只要在某个深度下出现次数为奇数个的字母数量大于就不能组成回文。这样我们就能得到这棵子树对应的每个深度下的查询结果,然后保留重儿子的结果删除轻儿子的结果就行了。 参考代码: #include <bits/stdc++.h> using namespace std; #define IO std...

选点 题目地址： https://ac.nowcoder.com/acm/problem/22494 基本思路: 我们看到题目给出的条件,要满足这个条件我们可以考虑构造序的访问顺序,我们知道对于一棵子树来说根节点肯定是第一个访问的,那么只要我们先访问右子树再访问左子树,用这样的顺序去构造序列,那么生成的这个序列的就是我们的答案了。 参考代码: #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false); cin.tie(0) #define ll lo...

[ZJOI2006]物流运输 题目地址： https://ac.nowcoder.com/acm/problem/20469 基本思路: 题目信息比较复杂,但是范围较小,所以我们要先整理清楚信息;首先我们可以定义一个二维数组,用来计录在时间范围内线路不变情况下1->m的最短路,由于范围较小,所以这部分我们可以每次暴力用求得,然后我们考虑,设表示在第天的最小成本,那么我们可以得到如下转移方程: 第一个部分表示从开始就用同一个线路,第二个部分表示从之前某天里的其他线路转移过来,这样得到的就是最小成本了。 参考代码： #pragma GCC optimize(2) #pragma...

Garland 题目地址: https://ac.nowcoder.com/acm/problem/111886 基本思路: 首先我们知道只要整棵树的温度总和是确定的,那么这个连通块的温度就也是确定的,考虑树形,令表示以为根的子树的温度总和,只要子树温度和等于,那么我们就将这棵子树断开,消去这部分贡献,然后记录断点。只要符合条件的断点数目大于等于，那么就是符合的。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #def...

筱玛爱线段树 题目地址： https://ac.nowcoder.com/acm/problem/25737 基本思路： 如果只进行操作,很显然可以直接差分,那么我看引入的操作,其实也是一个差分的形式,所以我们考虑将查询离线,倒着维护两个差分,第一个差分我们可以在树状数组上进行,是维护当前的操作的实际次数,然后第二个差分我们再在结果数组上维护差分,这样我们最后一个前缀和就能得到数组每个位置的结果了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using n...

D 数树 题目地址： https://ac.nowcoder.com/acm/contest/7509/D 基本思路： 我们发现既要加边又要删边,显然不好用并查集维护,那么我们关注要求的答案只是有多少个大小不为一的树,因为没有环,其实也就是有几个大小不为一的连通块,那么一个联通块大小为一,就是说明是单个的点,它的度为。那么在每次加边时,如果连着的这两个点的度大于，那么相连后答案显然会减一,而如果两个点的度均为,那么两个连在一起答案会加一,其余情况对答案不会影响。然后考虑删边的时候,如果删除后,两个点的度都变为,那么答案减一,如果删除后两个点的度都大于那么答案加一,同样其余不影响。因为存...

C Mu函数 题目地址： https://ac.nowcoder.com/acm/contest/7509/C 基本思路： 先筛出莫比乌斯函数值,然后我们能发现结果存在循环节,所以找到循环节就好了。 参考代码： #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; #define IO std::ios::sync_with_stdio(false); cin.tie(0) #define int long long #define ul...