DAY3共2題：
-
旅游
-
tokitsukaze and Soldier
?? 作者：Eriktse
?? 簡介：19歲，211計算機在讀，現役ACM銀牌選手??力爭以通俗易懂的方式講解演算法！??歡迎關注我，一起交流C++/Python演算法，（優質好文持續更新中……）??
?? 原文鏈接（閱讀原文獲得更好閱讀體驗）：
旅游
題目傳送門：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原創，創作不易，如果對您有幫助，歡迎小伙伴們點贊??、收藏?、留言??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/548222.html
標籤：其他
下一篇：blender資源庫 【自用】