Pts: 235
T1: 100
T2: 100
T3: 35
T1
[NOIP2018 提高组] 铺设道路
贪心
solution
emm……
没啥好说滴= =
若 (a_i > a_{i-1}) , (sum+=a[i]-a[i-1];)
T2
[NOIP2018 提高组] 货币系统
(dp)，数学，贪心，背包
solution
几个性质
-
最坏的情况为 (m = n) 也就是和已知的货币系统一模一样
-
新的货币系统的货币一定都是在原货币系统中出现
-
如果货币系统中小的货币能够凑出某个大的货币来，那么这个大的货币就没有用了
然后直接 (dp) 判断货币系统里面的货币能不能凑出来就好了
(f[i] = 0/1) 表示 (i) 这个面值的货币能不能凑出来
T3
[NOIP2018 提高组] 赛道修建
贪心，二分，最近公共祖先
大意了= =
solution
subtask1 m = 1 20'
树的直径，树形 (dp) 或者两遍 (dfs)
subtask2 (a_i = 1) 20'
菊花图，从大到小，选取 (2*m) 边，贪心的把双指针从两边依次两两匹配
subtask3 (b_i = a_i + 1) 20'
一条链，二分答案，直接二分最小值，判断是否能分成 (m) 段
正解
和链的思路一个样，二分枚举最小的那一条链，考虑整个树，从下到上，先子树内部进行匹配，匹配的方法和菊花图一个样，然后找出剩下的没匹配的最长的一条链继承到它的父亲节点，然后这一层就没有用了（dp没有后效性），然后一直向上 (dp) ，最后判断总共拼成的链是否不小于 (m) 就好了
code
/*
work by:Ariel_
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <algorithm>
#define int long long
using namespace std;
const int N = 50000 + 5;
const int M = 100000 + 5;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, m, ans, fag, o[M], qwq[M], ind[N], flag, l, r, minn = 0x3f3f3f;
struct edge {int v, w, nxt;}e[M];
int head[N], cnt;
void add_edge (int u, int v, int w) {
e[++cnt] = (edge){v, w, head[u]};
head[u] = cnt;
}
bool cmp (edge a, edge b){return a.w < b.w;}
int dis[N];
queue<int> q;
void dfs (int x) {
memset(dis, 0x3f, sizeof dis);
dis[x] = 0, q.push(x);
while(!q.empty()) {
int u = q.front();q.pop();
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if(dis[v] > dis[u] + e[i].w) {
dis[v] = dis[u] + e[i].w;
q.push(v);
}
}
}
}
int all, tot;
void Dfs(int x, int f, int mm) {
for(int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if(v == f) continue;
all += e[i].w;
if(all >= mm) all = 0, tot++;
Dfs(v, x, mm);
}
}
bool check(int x){
int u;
all = 0, tot = 0;
for(int i = 1; i <= n; i++)
if(ind[i] == 1){u = i;break;}
Dfs(u, 0, x);
//cout<<x<<" "<<tot<<" "<< all<<endl;
if(all < x && tot + 1 == m) return false;
if(tot >= m) return true;
if(tot < m) return false;
}
bool Cmp(int a, int b) {return a > b;}
int tail, que[M], res, dp[M], tag[M];
void DFS(int x, int f, int lim) {
for(int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if(v != f) DFS(v, x, lim);
}
tail = 0;
for(int i = head[x]; i; i = e[i].nxt) {
int v = e[i].v;
if(v != f) que[++tail] = dp[v] + e[i].w;//把下面连接的链都继承上来
}
sort(que + 1, que + tail + 1);
for(int i = tail; i >= 1 && que[i] >= lim; i--) {//本来就已经成一个赛道了
tail--, res--;
}
for(int i = 1; i <= tail; i++) {
if(tag[i] != x) {
int l = i + 1, r = tail, pst = tail + 1;
while(l <= r) {
int mid = (l + r) >> 1;
if(que[i] + que[mid] >= lim) pst = mid, r = mid - 1;
else l = mid + 1;
}
while (tag[pst] == x && pst <= tail)
pst++;
if (pst <= tail)
tag[i] = tag[pst] = x, res--;
}
}
dp[x] = 0;
for(int i = tail; i >= 1; i--) {
if(tag[i] != x) {//找个最长的链继承上来
dp[x] = que[i];
break;
}
}
}
signed main(){
n = read(), m = read();
for (int i = 1, u, v, w; i < n; i++) {
u = read(), v = read(), w = read();
add_edge(u, v, w), add_edge(v, u, w);
if(u == 1) fag++;
ind[u]++, ind[v]++;
r += w;
minn = min(w, minn);
}
int root = rand() % n + 1;
int l = 0, r = 0x3f3f3f3f, ans;
while (l <= r){
int mid = ((l + r) >> 1);
res = m;
memset(tag, false, sizeof tag);
DFS(root, 0, mid);
if (res <= 0)
ans = mid, l = mid + 1;
else
r = mid - 1;
}
cout << ans << endl;
return 0;
if (fag == n - 1) {//菊花图
for (int i = head[1]; i; i = e[i].nxt) o[e[i].v - 1] = e[i].w;
sort(o + 1, o + n, Cmp);
//for(int i = 1; i <= tot; i++) cout<<o[i]<<" ";
//cout<<o[tot - 2 * m + 1]<<" "<<o[tot]<< o[tot - m];
int ans = 0x3f3f3f3f;
for (int i = 1; i <= m; i++) ans = min(ans, o[i] + o[2 * m - i + 1]);
printf("%lld", ans);
return 0;
}
if (m == 1) {//树的直径
dfs(1);
int maxx = -0x3f3f3f3f, pos;
for(int i = 2; i <= n; i++)
if (dis[i] > maxx) maxx = dis[i], pos = i;
dfs(pos);
maxx = -0x3f3f3f3f;
for(int i = 1; i <= n; i++) {
if(dis[i] > maxx && i != pos) ans = dis[i], maxx = dis[i];
}
printf("%lld", ans);
return 0;
}
flag = 1;
for (int i = 1; i <= n; i++) if(ind[i] > 2) {flag = false;break;}
if (flag == 1) {//链
l = minn;
while(l <= r) {
int mid = (l + r) >> 1;
if(check(mid)){
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
printf("%lld", ans);
}
puts("");
return 0;
}
/*
直径
6 1
1 2 3
2 3 4
2 4 5
4 6 6
4 5 3
菊花图
7 3
1 2 2
1 3 7
1 4 6
1 7 5
1 5 4
1 6 3
7 3
1 7 50
1 3 100
1 2 20
1 4 30
1 5 40
1 6 100
链
7 3
1 2 10
2 3 4
3 4 5
4 5 6
5 6 7
6 7 8
8 4
1 2 5
2 3 3
3 4 2
4 5 6
5 6 7
6 7 9
7 8 4
*/