Noip 模拟练习4
- 满分300。本人机房老爷机下55pts，洛谷上170pts
- 这次的练习均为历年NOI原题。
道路修建
题目：
题解：
- 这题是NOI！我都不敢相信。不就是一个深搜就解决的事情吗… …
- 搜子树大小，一条边的权就 = 边权 * |它底下那个点(x)的子树大小 - (根子树大小 - x子树大小)|
#include <iostream>
#include <cstdio>
#include <cmath>
#define N 1000005
#define LL long long
using namespace std;
struct E {LL next, to, dis;} e[N * 2];
LL n, num, ans;
LL h[N], size[N];
LL read() {
LL x = 0; char c = getchar();
while (c < '0' || c > '9') c = getchar();
while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return x;
}
void add(LL u, LL v, LL w) {
e[++num].next = h[u];
e[num].to = v;
e[num].dis = w;
h[u] = num;
}
void dfs(LL x, LL fat) {
size[x]++;
for (LL i = h[x]; i != 0; i = e[i].next)
if (e[i].to != fat) {
dfs(e[i].to, x);
size[x] += size[e[i].to];
}
}
void dfss(LL x, LL fat) {
for (LL i = h[x]; i != 0; i = e[i].next)
if (e[i].to != fat) {
LL y = e[i].to;
ans += e[i].dis * abs(size[y] - (size[1] - size[y]));
dfss(e[i].to, x);
}
}
int main() {
cin >> n;
for (LL i = 1; i < n; i++) {
LL u = read(), v = read(), w = read();
add(u, v, w);
add(v, u, w);
}
dfs(1, 0);
dfss(1, 0);
cout << ans;
return 0;
}
郁闷的出纳员
题目：
题解：
开车旅行
题目：
题解：
- 这题我只打了70pts的暴力，毕竟当时GX省拿到了>=70pts的也只有5人。
- 100pts的倍增这个坑以后填
- 70分思路就是先预处理出每个点要开往的城市。然后将A和B拆开，分别搜索。合起来搜索就会比较复杂，这可能就是暴力只有5人得分的原因。
#include <iostream>
#include <cstdio>
#include <cmath>
#define inf 2000000007
#define N 100005
#define M 10005
using namespace std;
struct R {int p1, p2;} r[N];
struct Q {int s, x;} q[M];
int n, x0, m;
int h[N];
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 dfs1(int x, int y) {
if (x == -1) return 0;
if (r[x].p2 == -1) return 0;
if (y < 0) return 0;
int ans = 0;
if (y - abs(h[r[x].p2] - h[x]) >= 0) {
ans += abs(h[r[x].p2] - h[x]);
int yy = y - abs(h[r[x].p2] - h[x]);
int pp = r[x].p2;
if (yy - abs(h[pp] - h[r[pp].p1]) >= 0)
ans += dfs1(r[pp].p1, yy - abs(h[pp] - h[r[pp].p1]));
}
return ans;
}
int dfs2(int x, int y) {
if (x == -1) return 0;
if (r[x].p1 == -1) return 0;
if (y < 0) return 0;
int ans = 0;
if (y - abs(h[r[x].p1] - h[x]) >= 0) {
ans += abs(h[r[x].p1] - h[x]);
int yy = y - abs(h[r[x].p1] - h[x]);
int pp = r[x].p1;
if (yy - abs(h[pp] - h[r[pp].p2]) >= 0)
ans += dfs2(r[pp].p2, yy - abs(h[pp] - h[r[pp].p2]));
}
return ans;
}
int main() {
freopen("drive.in", "r", stdin);
freopen("drive.out", "w", stdout);
cin >> n;
for (int i = 1; i <= n; i++) h[i] = read();
for (int i = 1; i <= n; i++) {
int min1 = inf, min2 = inf;
int pos1 = -1, pos2 = -1;
for (int j = i + 1; j <= n; j++)
if (abs(h[i] - h[j]) < min2) {
min2 = abs(h[i] - h[j]);
pos2 = j;
if (min2 < min1) {
swap(min1, min2);
swap(pos1, pos2);
}
else if (min2 == min1) {
if (h[pos2] < h[pos1]) swap(min1, min2), swap(pos1, pos2);
}
}
else if (abs(h[i] - h[j]) == min2) {
if (h[j] < h[pos2]) min2 = abs(h[i] - h[j]), pos2 = j;
}
r[i].p1 = pos1;
r[i].p2 = pos2;
}
cin >> x0 >> m;
for (int i = 1; i <= m; i++) {
q[i].s = read();
q[i].x = read();
}
double minn = inf + 1, t;
int pos;
for (int i = 1; i <= n; i++) {
int tot1 = dfs1(i, x0);
int tot2 = dfs2(r[i].p2, x0 - abs(h[i] - h[r[i].p2]));
if (!tot2) t = inf;
else t = ((double)tot1 / (double)tot2);
if (t < minn) {
minn = t;
pos = i;
}
else if (t == minn) {
if (h[i] > h[pos]) minn = t, pos = i;
}
}
cout << pos << endl;
for (int i = 1; i <= m; i++) {
printf("%d ", dfs1(q[i].s, q[i].x));
int y = r[q[i].s].p2;
printf("%d\n", dfs2(y, q[i].x - abs(h[q[i].s] - h[y])));
}
return 0;
}