20191029测试总结

继续没睡醒状态)雾

T1:WOJ4774

一个拓欧的题目,用拓欧解出来之后注意一下最优解是最靠近0的两个数之一就行。

#include <iostream>
#include <cstdio>
#include <cmath>
#define int long long
using namespace std;
int n, a, b, c, d, x, y, ans;
int exgcd(int aa, int bb)
{
    if (bb == 0)
    {
        x = 1;
        y = 0;
        return aa;
    }
    int tem = exgcd(bb, aa % bb);
    int tmp = x;
    x = y;
    y = tmp - aa / bb * y;
    return tem;
}
signed main()
{
    scanf("%lld%lld%lld", &n, &a, &b);
    if (a > b)
        swap(a, b);
    c = exgcd(a, b);
    a /= c;
    b /= c;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lld", &d);
        if (d % c != 0)
        {
            printf("-1");
            return 0;
        }
        d /= c;
        int xx = d * x, yy = d * y;
        int t = xx / b;
        xx -= t * b;
        yy += t * a;
        if (xx > 0)
            ans += min(abs(xx) + abs(yy), abs(xx - b) + abs(yy + a));
        else
            ans += min(abs(xx) + abs(yy), abs(xx + b) + abs(yy - a));
    }
    printf("%lld", ans);
    return 0;
}

T2:WOJ4775

通过推到可以发现当ai+bi<=aj+bj时情况一定是最优的,因此排序一次之后线段树优化DP一下就好。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lch id << 1
#define rch id << 1 | 1
#define int long long
using namespace std;
int n, b[200005];
struct node
{
    int a;
    int b;
    int w;
} a[100005];
struct tree
{
    int l;
    int r;
    int sum;
    int lazy;
} tr[800005];
bool cmp(node aa, node bb)
{
    return aa.a + aa.b < bb.a + bb.b;
}
void build(int id, int l, int r)
{
    tr[id].l = l;
    tr[id].r = r;
    if (l == r)
        return;
    int mid = (l + r) >> 1;
    build(lch, l, mid);
    build(rch, mid + 1, r);
    return;
}
void pushdown(int id)
{
    if (tr[id].l != tr[id].r)
    {
        int lazy = tr[id].lazy;
        tr[id].lazy = 0;
        tr[lch].sum += lazy;
        tr[rch].sum += lazy;
        tr[lch].lazy += lazy;
        tr[rch].lazy += lazy;
    }
    return;
}
void change(int id, int w, int val)
{
    pushdown(id);
    if (tr[id].l == tr[id].r)
    {
        tr[id].sum = max(tr[id].sum, val);
        return;
    }
    int mid = (tr[id].l + tr[id].r) >> 1;
    if (w <= mid)
        change(lch, w, val);
    else
        change(rch, w, val);
    tr[id].sum = max(tr[lch].sum, tr[rch].sum);
    return;
}
void add(int id, int l, int r, int val)
{
    pushdown(id);
    if (tr[id].l == l && tr[id].r == r)
    {
        tr[id].sum += val;
        tr[id].lazy += val;
        return;
    }
    int mid = (tr[id].l + tr[id].r) >> 1;
    if (r <= mid)
        add(lch, l, r, val);
    if (l >= mid + 1)
        add(rch, l, r, val);
    if (l <= mid && r >= mid + 1)
    {
        add(lch, l, mid, val);
        add(rch, mid + 1, r, val);
    }
    tr[id].sum = max(tr[lch].sum, tr[rch].sum);
    return;
}
int query(int id, int l, int r)
{
    pushdown(id);
    if (tr[id].l == l && tr[id].r == r)
        return tr[id].sum;
    int mid = (tr[id].l + tr[id].r) >> 1;
    if (r <= mid)
        return query(lch, l, r);
    if (l >= mid + 1)
        return query(rch, l, r);
    if (l <= mid && r >= mid + 1)
        return max(query(lch, l, mid), query(rch, mid + 1, r));
}
signed main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lld%lld%lld", &a[i].a, &a[i].b, &a[i].w);
        b[2 * i - 1] = a[i].a;
        b[2 * i] = a[i].b;
    }
    sort(b + 1, b + 2 * n + 1);
    int len = unique(b + 1, b + 2 * n + 1) - b - 1;
    for (int i = 1; i <= n; ++i)
    {
        a[i].a = lower_bound(b + 1, b + len + 1, a[i].a) - b;
        a[i].b = lower_bound(b + 1, b + len + 1, a[i].b) - b;
    }
    sort(a + 1, a + n + 1, cmp);
    build(1, 1, len);
    for (int i = 1; i <= n; ++i)
    {
        change(1, a[i].a, query(1, 1, min(a[i].a, a[i].b)) + a[i].w);
        if (a[i].b > a[i].a)
            add(1, a[i].a + 1, a[i].b, a[i].w);
    }
    printf("%lld", query(1, 1, len));
    return 0;
}

T3:WOJ4776

跑一段多源最短路,对于每个节点记录它是由哪个源点拓展来的。跑完之后遍历一遍所有边,如果一条边的两个顶点是由两个不同的源点拓展来的,那么我们就可以以此更新两个源点之间的距离,正确性显然。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int n, m, p, sum = 1, head[200005], x[200005], vis[200005], fa[200005];
long long ans[200005], d[200005];
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
inline int read()
{
    int x = 0, f = 1;
    char c = gc();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = gc();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 3) + (x << 1) + (c & 15);
        c = gc();
    }
    return x * f;
}
char bbuf[1 << 21];
int pp1 = -1;
const int pp2 = (1 << 21) - 1;
inline void flush()
{
    fwrite(bbuf, 1, pp1 + 1, stdout);
    pp1 = -1;
    return;
}
inline void pc(char x)
{
    if (pp1 == pp2)
        flush();
    bbuf[++pp1] = x;
    return;
}
inline void write(long long x)
{
    char buffer[10];
    int len = -1;
    if (x >= 0)
    {
        do
        {
            buffer[++len] = (x % 10) | 48;
            x /= 10;
        } while (x);
    }
    else
    {
        pc('-');
        do
        {
            buffer[++len] = -(x % 10) | 48;
            x /= 10;
        } while (x);
    }
    while (len >= 0)
        pc(buffer[len--]);
    return;
}
struct node
{
    int v;
    int w;
    int next;
} a[400005];
struct point
{
    int id;
    int d;
    point(int aa, int bb)
    {
        id = aa;
        d = bb;
    }
    inline bool operator<(const point &bb) const
    {
        return d > bb.d;
    }
};
priority_queue<point> q;
inline void ins(int u, int v, int w)
{
    ++sum;
    a[sum].v = v;
    a[sum].w = w;
    a[sum].next = head[u];
    head[u] = sum;
    return;
}
int main()
{
  	n = read();
  	m = read();
  	p = read();
    for (register int i = 1; i <= p; ++i)
    {
        x[i] = read();
    	ans[x[i]] = 0x7f7f7f7f7f7f7f7f;
    }
    for (register int i = 1; i <= m; ++i)
    {
        int u, v, w;
      	u = read();
      	v = read();
      	w = read();
        ins(u, v, w);
        ins(v, u, w);
    }
    memset(d, 0x7f, sizeof(d));
    for (register int i = 1; i <= p; ++i)
    {
        fa[x[i]] = x[i];
        d[x[i]] = 0;
        q.push(point(x[i], 0));
    }
    while (!q.empty())
    {
        point kk = q.top();
        q.pop();
        int id = kk.id;
        if (vis[id])
            continue;
        vis[id] = 1;
        int dd = head[id];
        while (dd)
        {
            if (d[a[dd].v] > d[id] + a[dd].w)
            {
                d[a[dd].v] = d[id] + a[dd].w;
                fa[a[dd].v] = fa[id];
                q.push(point(a[dd].v, d[a[dd].v]));
            }
            dd = a[dd].next;
        }
    }
    for (register int i = 2; i <= 2 * m; i += 2)
        if (fa[a[i].v] != fa[a[i ^ 1].v])
        {
            if (ans[fa[a[i].v]] > d[a[i].v] + d[a[i ^ 1].v] + a[i].w)
                ans[fa[a[i].v]] = d[a[i].v] + d[a[i ^ 1].v] + a[i].w;
            if (ans[fa[a[i ^ 1].v]] > d[a[i].v] + d[a[i ^ 1].v] + a[i].w)
                ans[fa[a[i ^ 1].v]] = d[a[i].v] + d[a[i ^ 1].v] + a[i].w;
        }
    for (register int i = 1; i <= p; ++i)
    {
        write(ans[x[i]]);
  		pc(' ');
    }
  	flush();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注