Noip 模拟练习4

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;
}
上一篇:SQL通用处理工具


下一篇:特殊关键字