D1T1 铺设道路
分析
这题就是NOIP2013 积木大赛原题=。=，贪心地想，如果 ai>ai−1， ans+=ai−ai−1，因为搞 ai−1 的时候，能尽量搞 ai 就搞 ai。
代码如下
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100001], max1, s;
int main(){
int i, j, n, m;
scanf("%d", &n);
for(i=1;i<=n;i++) scanf("%d", &a[i]);
for(i=1;i<=n;i++){
if(a[i]>a[i-1]) s += a[i]-a[i-1];
}
printf("%d",s);
return 0;
}
D1T2 货币系统
分析
由于 b 与 a 等价且 b 要尽量小， b 肯定是 a 的子集，其中对于 x∈a,x∈/b， x 能用 b 中的元素表示。
于是我们将 a 排个序跑个背包就可以了。
代码如下
#include <bits/stdc++.h>
using namespace std;
int f[25005], a[105], ans;
int main(){
int i, j, n, m, T;
scanf("%d", &T);
while(T--){
ans = 0;
memset(f, 0, sizeof(f));
scanf("%d", &n);
for(i = 1; i <= n; i++) scanf("%d", &a[i]);
sort(a + 1, a + i);
f[0] = 1;
for(i = 1; i <= n; i++){
if(f[a[i]]) continue;
ans++;
for(j = a[i]; j <= 25000; j++) f[j] += f[j - a[i]];
}
printf("%d\n", ans);
}
return 0;
}
D1T3 赛道修建
分析
要求最小的最大，于是我们二分。
那怎么 check 呢？
首先，如果是一条链的情况，明显就是长度到了 t 就 tot+1。
于是我们从下往上每到一个分叉点，一定汇聚了多条长度小于 t 的链，如图。
红色的是 3 条未到 t 的链，显然只有 1 条可以继续往上延伸，其他链都要在这里进行合并。于是我们就对每个节点维护一个 multiset，放置这些链。然后每次从这些链中贪心地合并，最后剩的最大那条链向上传递。这样我们就保证了长度大于 t 的链总数尽量大。
总结就是这道题用了几个贪心：
第一个是单链上要贪心，第二个是合并的时候要贪心，第三个是传递的时候要贪心，这些贪心保证了解的最优性。
代码如下
#include <bits/stdc++.h>
#define N 50005
#define inf 2147483647
using namespace std;
struct node{
int a, b, c, n;
}d[N * 2];
int h[N], cnt, n, m, t, f[N], tot;
int read(){
int x, f = 1;
char ch;
while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
x = ch - 48;
while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
return x * f;
}
void cr(int a, int b, int c){
d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].n = h[a]; h[a] = cnt;
}
void dfs(int a, int p){
int i, j, b, c, ret = 0;
multiset<int> s;
set<int>::iterator it;
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
c = d[i].c;
if(b == p) continue;
dfs(b, a);
if(f[b] + c >= t) tot++;
else s.insert(f[b] + c);
}
while(!s.empty()){
if(s.size() == 1){
f[a] = max(f[a], *s.begin());
break;
}
it = s.lower_bound(t - *s.begin());
if(it == s.begin() && s.count(*it) == 1) it++;
if(it == s.end()){
f[a] = max(f[a], *s.begin());
s.erase(s.begin());
}
else{
tot++;
//printf("%d %d\n", *it, *s.begin());
s.erase(it);
s.erase(s.begin());
}
}
}
int ok(int t){
dfs(1, 1);
if(tot >= m) return 1;
return 0;
}
int main(){
int i, j, a, b, c, l = inf, r = 0;
scanf("%d%d", &n, &m);
for(i = 1; i < n; i++){
a = read(); b = read(); c = read();
cr(a, b, c);
cr(b, a, c);
r += c;
l = min(l, c);
}
r /= m;
while(l < r){
for(i = 1; i <= n; i++) f[i] = 0;
tot = 0;
t = l + r + 1 >> 1;
if(ok(t)) l = t;
else r = t - 1;
}
printf("%d", l);
return 0;
}
D2T1 旅行
分析
这道题考的应该是边排序，首先对 m=n 的情况，我们枚举断掉的边，那么问题就变成了 m=n−1 的情况。我们考虑在 O(n) 复杂度下解决 m=n−1的情况。
应该不难发现，题目中所得到的序列就是树的 dfs 序，我们要让字典序尽量小，只要让每个节点访问的点按从小到大排序就可以了。如何实现这个排序呢？
我的做法是先让所有边的出点按从小到大排序，然后单独对每个点再来加边（emmm我突然发现有点难说，大家看代码吧
代码如下
#include <bits/stdc++.h>
#define N 10005
using namespace std;
struct node{
int a, b, c, n;
bool operator < (const node & A) const{
return b < A.b;
}
}d[N], e[N], re[N];
int h[N], p[N], v[N], vis[N], n, cnt, ret, tot, ans[N];
int mp[5005][5005];
void cr(int a, int b){
d[++cnt].a = a; d[cnt].b = b; d[cnt].n = h[a]; h[a] = cnt;
}
void crr(int a, int b){
e[++ret].a = a; e[ret].b = b; e[ret].n = p[a]; p[a] = ret;
}
void dfs(int a){
int i, b;
v[a] = 1;
printf("%d ", a);
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
if(!v[b]) dfs(b);
}
}
void dfs1(int a){
int i, b;
v[a] = 1;
vis[++tot] = a;
for(i = h[a]; i; i = d[i].n){
b = d[i].b;
if(mp[a][b]) continue;
if(!v[b]) dfs1(b);
}
}
void cmp(){
int i, j;
for(i = 1; i <= n; i++){
if(vis[i] < ans[i]){
for(j = 1; j <= n; j++) ans[j] = vis[j];
return;
}
if(vis[i] > ans[i]) return;
}
}
int main(){
int i, j, m, a, b;
scanf("%d%d", &n, &m);
for(i = 1; i <= m; i++){
scanf("%d%d", &a, &b);
re[i].a = a; re[i].b = b;
e[++tot].a = a; e[tot].b = b;
e[++tot].a = b; e[tot].b = a;
}
sort(e + 1, e + tot + 1);
for(i = 1; i <= tot; i++){
a = e[i].a; b = e[i].b;
crr(a, b);
}
for(a = 1; a <= n; a++){
for(i = p[a]; i; i = e[i].n){
b = e[i].b;
cr(a, b);
}
}
if(m == n - 1) dfs(1);
else{
for(i = 1; i <= n; i++) ans[i] = n;
for(i = 1; i <= m; i++){
tot = 0;
memset(v, 0, sizeof(v));
a = re[i].a; b = re[i].b;
mp[a][b] = mp[b][a] = 1;
dfs1(1);
if(tot == n) cmp();
//printf("=====%d %d %d\n", tot, a, b);
//for(j = 1; j <= n; j++) printf("%d ", vis[j]);
//printf("\n");
mp[a][b] = mp[b][a] = 0;
}
for(i = 1; i <= n; i++) printf("%d ", ans[i]);
}
return 0;
}
京公网安备 11010502036488号