20191029测试总结
继续没睡醒状态）雾
T1：WOJ4774
一个拓欧的题目，用拓欧解出来之后注意一下最优解是最靠近0的两个数之一就行。
T2：WOJ4775
通过推到可以发现当ai+bi<=aj+bj时情况一定是最优的，因此排序一次之后线段树优化DP一下就好。
T3：WOJ4776
跑一段多源最短路，对于每个节点记录它是由哪个源点拓展来的。跑完之后遍历一遍所有边，如果一条边的两个顶点是由两个不同的源点拓展来的，那么我们就可以以此更新两个源点之间的距离，正确性显然。
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;
}
评论
发表评论