洛谷 P5021 [NOIP2018]赛道重建
洛谷 P5021 [NOIP2018]赛道重建
传送门
思路
思路就是常规的思路，所以就不说了……我就是来记录一下我的\(AC\)之路的，真的是太爽了
没错……我也是一个个打的部分分，最后终于AC的，至于为什么中间又会有\(35\)、\(25\)、\(0\)这样的分数……纯粹是因为我犯了zz错误……
代码
1、\(b_i = a_i + 1\) 链的情况
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 50011;
int a[N], n, m, cnt, head[N], sum;
struct node {
int to, nxt, val;
} e[N << 1];
inline void add(int from, int to, int w) {
e[++cnt].to = to;
e[cnt].val = w;
e[cnt].nxt = head[from];
head[from] = cnt;
}
void dfs(int x, int fa) {
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to;
if(y == fa) continue;
dfs(y, x);
a[x] = e[i].val;
}
}
int check(int k) {
int t = 0, now = 1;
for(int i = 1; i < n; i++) {
if(now + a[i] >= k) {
now = 0;
t++;
}
else now += a[i];
}
return t >= m;
}
int main() {
n = read(), m = read();
for(int i = 1; i < n; i++) {
int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, w);
sum += w;
}
dfs(1, 0);
int l = 1, r = sum, mid;
while(l < r) {
mid = (l + r) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
}2、\(m = 1\) 求树的直径
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 50011;
int a[N], n, m, cnt, head[N], sum, ans;
struct node {
int to, nxt, val;
} e[N << 1];
inline void add(int from, int to, int w) {
e[++cnt].to = to;
e[cnt].val = w;
e[cnt].nxt = head[from];
head[from] = cnt;
}
int dfs(int x,int fa) {
int sum1 = 0, sum2 = 0;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if(y == fa) continue;
sum2 = max(sum2, dfs(y, x) + e[i].val);
if(sum2 > sum1) swap(sum1, sum2);
}
ans = max(ans, sum1 + sum2);
return sum1;
}
int main() {
n = read(), m = read();
for(int i = 1; i < n; i++) {
int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, w);
sum += w;
}
dfs(1, 0);
cout << ans << '\n';
}3、\(a_i = 1\) 菊花图
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 50011;
const int inf = 0x3f3f3f3f;
int a[N], n, m, cnt, head[N], sum, ans;
struct node {
int to, nxt, val;
} e[N << 1];
inline void add(int from, int to, int w) {
e[++cnt].to = to;
e[cnt].val = w;
e[cnt].nxt = head[from];
head[from] = cnt;
}
bool cmp(int a, int b) {
return a > b;
}
int main() {
n = read(), m = read();
for(int i = 1; i < n; i++) {
int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, w);
sum += w;
}
for(int i = head[1], y; i; i = e[i].nxt) {
y = e[i].to;
a[y - 1] = e[i].val;
}
sort(a + 1, a + n, cmp);
int ans = inf;
for(int i = 1; i <= m; i++)
ans = min(ans, a[i] + a[2 * m - i + 1]);
cout << ans << '\n';
return 0;
}4、混起来的部分分
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 50011;
const int inf = 0x3f3f3f3f;
int a[N], n, m, cnt, head[N], sum, ans;
struct node {
int to, nxt, val;
} e[N << 1];
inline void add(int from, int to, int w) {
e[++cnt].to = to;
e[cnt].val = w;
e[cnt].nxt = head[from];
head[from] = cnt;
}
namespace subtask1 {
int a[N];
void dfs(int x, int fa) {
for(int i = head[x]; i ; i = e[i].nxt) {
int y = e[i].to;
if(y == fa) continue;
dfs(y, x);
a[x] = e[i].val;
}
}
int check(int k) {
int t = 0, now = 1;
for(int i = 1; i < n; i++) {
if(now + a[i] >= k) {
now = 0;
t++;
} else now += a[i];
}
return t >= m;
}
void solve() {
dfs(1, 0);
int l = 1, r = sum, mid;
while(l < r) {
mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
}
}
namespace subtask2 {
int dfs(int x,int fa) {
int sum1 = 0, sum2 = 0;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if(y == fa) continue;
sum2 = max(sum2, dfs(y, x) + e[i].val);
if(sum2 > sum1) swap(sum1, sum2);
}
ans = max(ans, sum1 + sum2);
return sum1;
}
void solve() {
dfs(1, 0);
cout << ans << '\n';
}
}
namespace subtask3 {
bool cmp(int a, int b) {
return a > b;
}
void solve() {
for(int i = head[1], y; i; i = e[i].nxt) {
y = e[i].to;
a[y - 1] = e[i].val;
}
sort(a + 1, a + n, cmp);
int ans = inf;
for(int i = 1; i <= m; i++)
ans = min(ans, a[i] + a[2 * m - i + 1]);
cout << ans << '\n';
}
}
int main() {
n = read(), m = read();
int flag = 1, f = 1;
for(int i = 1; i < n; i++) {
int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, w);
if(u != 1) flag = 0;
if(v != u + 1) f = 0;
sum += w;
}
if(flag) {
subtask3::solve();
}
else if(f){
subtask1::solve();
}
else {
subtask2::solve();
}
return 0;
}5、正解！！（\(multiset\)）
#include <bits/stdc++.h>
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
return x * f;
}
const int N = 50011;
const int inf = 0x3f3f3f3f;
int a[N], n, m, cnt, head[N], ans, up;
struct node {
int to, nxt, val;
} e[N << 1];
multiset<int> s[N];
multiset<int>::iterator it;
inline void add(int from, int to, int w) {
e[++cnt].to = to;
e[cnt].val = w;
e[cnt].nxt = head[from];
head[from] = cnt;
}
int dfs(int x, int fa, int k) {
s[x].clear();
int w;
for(int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if(y == fa) continue;
w = dfs(y, x, k) + e[i].val;
if(w >= k) ans++;
else s[x].insert(w);
}
int maxn = 0;
while(!s[x].empty()) {
if(s[x].size() == 1) {
return max(maxn, *s[x].begin());
}
it = s[x].lower_bound(k - *s[x].begin());
if(it == s[x].begin() && s[x].count(*it) == 1) it++;
if(it == s[x].end()) {
maxn = max(maxn, *s[x].begin());
s[x].erase(s[x].find(*s[x].begin()));
} else {
ans++;
s[x].erase(s[x].find(*it));
s[x].erase(s[x].find(*s[x].begin()));
}
}
return maxn;
}
int dfs1(int x,int fa) {
int sum1 = 0, sum2 = 0;
for(int i = head[x], y; i; i = e[i].nxt) {
y=e[i].to;
if(y == fa) continue;
sum2 = max(sum2, dfs1(y, x) + e[i].val);
if(sum1 < sum2) swap(sum1, sum2);
}
up = max(up, sum1 + sum2);
return sum1;
}
int check(int k) {
ans = 0;
dfs(1, 0, k);
if(ans >= m) return 1;
return 0;
}
int main() {
n = read(), m = read();
for(int i = 1; i < n; i++) {
int u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, w);
}
dfs1(1, 0);
int l = 1, r = up, mid;
while(l < r) {
mid = (l + r + 1) >> 1;
if(check(mid)) l = mid;
else r = mid - 1;
}
cout << l << '\n';
}
CVTE公司福利 265人发布
查看19道真题和解析