DAY3共2题：
- 游览
- tokitsukaze and Soldier
🎈 作者：Eriktse
🎈 简介：19岁，211计算机在读，现役ACM银牌选手🏆力争以通俗易懂的形式解说算法！❤️欢送关注我，一起交换C++/Python算法。（优质好文继续更新中……）🚀
🎈 原文链接（浏览原文取得更好浏览体验）：https://www.eriktse.com/algorithm/1093.html
游览
题目传送门：https://ac.nowcoder.com/acm/problem/15748
该题次要考查对树的了解，以及简略的树上dp和贪婪算法。
咱们将会住的节点标记为1，其余不住的节点标记为0。
咱们能够发现，根节点（s）是肯定会标记为1的，那么剩下的节点该怎么调配能够使得标记为1的节点数最多呢？
当咱们在某个点x标记时，咱们能够发现它的父亲、儿子们都不能再被标记了。然而点x的兄弟却不受影响，接下来考虑一下哪些节点的兄弟多呢？应该是叶子节点。
所以咱们能够想到首先将根节点和叶子结点全副都标记为1，而后遍历整棵树，如果某个点的父亲和儿子们都没被标记，那么他也能够被标记为1。
留神思考非凡状况，比方只有一个点的树，只有两个点的树….
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 9, inf = 8e18;
bitset<maxn> sel;
vector<int> g[maxn];
int n, s;
void dfs(int x, int pre)
{
//如果到了叶子节点，就间接标记并返回
//这里sel[x] = !sel[pre]是思考到叶子的深度可能为2（即叶子的父亲就是根）
//此时根肯定被标记，那么叶子就不能被标记
//如果是个别状况，那么父亲必定不会被标记（因为父亲的标记须要儿子解决实现之后再决定）
//本人就打上标记
if(g[x].size() == 1 and x != s)return sel[x] = !sel[pre], void();
bool tag = true;//tag == true示意以后点能够被标记
if(x == s)sel[x] = true;//根肯定被标记
else if(sel[pre])tag = false;//如果父亲被标记了，那么以后点肯定不能被标记
//看看儿子们是否被标记
for(auto &y : g[x])
{
if(y == pre)continue;
dfs(y, x);
if(sel[y])tag = false;
}
sel[x] = tag;
}
signed main()
{
scanf("%lld %lld", &n, &s);
for(int i = 1;i < n; ++ i)
{
int x, y;scanf("%lld %lld", &x, &y);
g[x].push_back(y), g[y].push_back(x);
}
dfs(s, 0);
int ans = 0;
for(int i = 1;i <= n; ++ i)
if(sel[i])ans ++;//统计标记的点的个数
printf("%lld\n", ans);
return 0;
}做完这道题，咱们能够总结一点点对于树上dp这一类题的教训技巧：
1.将非凡点作为根，建设一棵树，建树个别用双向边，边的条数严格等于点的个数-1。
2.优先思考树中非凡的点，比方根、叶子。
3.不要遗记思考非凡状况，比方一条链状的树（此时留神根是否会被断定为叶子、留神复杂度是否会爆）、仅有1个点的树（可能须要特判）。
tokitsukaze and Soldier
题目传送门：https://ac.nowcoder.com/acm/problem/50439
这题次要考查贪婪+优先队列保护区间k个最值。
咱们察看题目能够发现，当咱们枚举到一个士兵的要求是”队伍人数不能超过s[i] = k“时，那么此时军队的战斗力最大值应该是所有s >= k的军人中的最大的k个军人的战斗力之和。
咱们能够思考用一个优先队列保护最大的k个值之和(小根堆，每次弹出最小值，即可保护最大值之和），而后通过限度“遍历形式”使得当遍历到第i集体(s[i] = k)时，优先队列里的所有值对应的s都是>= k的，这样就只需要求出优先队列里最大的k个数字之和即可，这个遍历形式就是依照s[i]降序排列，而后从前往后遍历。
咱们能够保护一个大小始终等于s[i]的优先队列，因为s[i]为降序，所以这个优先队列的元素个数的最大值是始终在减小的，减小的时候只须要弹出最小的元素即可，用一个变量sum保护优先队列里的所有元素之和（push时加上，pop时减去）。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
struct Node
{
int v, s;
}a[maxn];
signed main()
{
int n;scanf("%lld", &n);
for(int i = 1;i <= n; ++ i)scanf("%lld %lld", &a[i].v, &a[i].s);
sort(a + 1,a + 1 + n, [](const Node &u, const Node &v)
{
return u.s > v.s;
});
priority_queue<int, vector<int>, greater<int> > pq;
int ans = 0, sum = 0;
for(int i = 1;i <= n; ++ i)
{
sum += a[i].v, pq.push(a[i].v);
while(pq.size() > a[i].s)sum -= pq.top(), pq.pop();
ans = max(ans, sum);
}
printf("%lld\n", ans);
return 0;
}经验总结：
1.用某种遍历形式来限度某个条件，比方本题用”降序”来限度在以后点之前的所有点的s[i]都比以后的大或相等。
2.优先队列能够保护区间的k个最值之和，只实用于间断的查问且k只能变小或不变，因为变大的话，不晓得要将哪一个放进去。
最初
感激大家的浏览，欢送大家跟我一起刷题呀！
🎈 本文由eriktse原创，创作不易，如果对您有帮忙，欢送小伙伴们点赞👍、珍藏⭐、留言💬
发表回复