20191022测试总结

虽然今天做的是NOI模拟题,但是做的太自闭了,因此总结的是CSP-S模拟题



T1:WOJ4759

零点分段一下即可,注意一下a为0的情况即可(我才不会告诉你我因为这个WA了几次)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
long long sum[2];
long double ans = 10000000000.0;
struct node
{
int a;
int b;
long double x;
} a[300005];
bool cmp(node aa, node bb)
{
return aa.x < bb.x;
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &a[i].a, &a[i].b);
if (a[i].a != 0)
a[i].x = a[i].b * -1.0 / a[i].a;
if (a[i].a != 0)
{
if (a[i].a > 0)
{
sum[0] -= a[i].a;
sum[1] -= a[i].b;
}
else
{
sum[0] += a[i].a;
sum[1] += a[i].b;
}
}
else
{
if (a[i].b > 0)
sum[1] += a[i].b;
else
sum[1] -= a[i].b;
}
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; ++i)
if (a[i].a != 0)
{
ans = min(ans, a[i].x * sum[0] + sum[1]);
if (a[i].a != 0)
if (a[i].a > 0)
{
sum[0] += a[i].a * 2;
sum[1] += a[i].b * 2;
}
else
{
sum[0] -= a[i].a * 2;
sum[1] -= a[i].b * 2;
}
}
else
ans = min(ans, a[i - 1].x * sum[0] + sum[1]);
printf("%.6Lf", ans);
return 0;
}

T2:WOJ4760

根据高度来维护一棵线段树/树状数组记录一下到了一个高度之后岛屿个数的变化即可。
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, ans, h[500005], c[500005];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int val)
{
while (x <= 500000)
{
c[x] += val;
x += lowbit(x);
}
return;
}
int query(int x)
{
int ans = 0;
while (x >= 1)
{
ans += c[x];
x -= lowbit(x);
}
return ans;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &h[i]);
if (h[i] > h[i - 1])
{
add(h[i - 1] + 1, 1);
add(h[i] + 1, -1);
}
}
for (int i = 1; i <= m; ++i)
{
char type;
scanf(" %c", &type);
if (type == 'Q')
{
int c;
scanf("%d", &c);
c = c ^ ans;
printf("%d\n", ans = query(c));
}
else
{
int a, b;
scanf("%d%d", &a, &b);
a = a ^ ans;
b = b ^ ans;
if (h[a] > h[a - 1])
{
add(h[a - 1] + 1, -1);
add(h[a] + 1, 1);
}
if (h[a + 1] > h[a])
{
add(h[a] + 1, -1);
add(h[a + 1] + 1, 1);
}
h[a] = b;
if (h[a] > h[a - 1])
{
add(h[a - 1] + 1, 1);
add(h[a] + 1, -1);
}
if (h[a + 1] > h[a])
{
add(h[a] + 1, 1);
add(h[a + 1] + 1, -1);
}
}
}
return 0;
}

T3:WOJ4761

这道题太毒瘤了。。。

我们可以根据题目条件建图,然后这道题就转换成了给你n个点,m条边,要求你确定这些边的方向使每个点的入度与出度之差最大为2。

由于每个点都是奇数,因此我们可以发现每个点一定存在边权为1的边。

若图中存在边权相同的边(a, b)和(b, c),那么显然这条边可以用(a, c)来代替。我们每加一条边就执行一次这个操作。那么到最后,这个图显然会成为一个完美匹配。

对于所有边权为1的边,我们可以根据这个操作求出整个图的完美匹配。然后,对于边权为2的边,我们也可以进行同样的操作,操作完成后对于所有有边权为2的边的图也显然是个完美匹配。这个时候,我们可以发现只剩下三种情况:

  1. 两点间边权为1、2的边相重合

  2. 边权为1、2的边交替组合为一条链

  3. 边权为1、2的边交替组合为一个环


然后,我们再跑一边bfs/dfs按照顺序确定一下方向(正确性显然)就可以了。

当然,这当中还有一些需要注意的点:

对于每条边,我们先对他钦定一个方向。然后当缩边时,我们如果发现它的方向反了,那么就对他标记一个rev,表示缩成这条边的所有边都需要取反。剩下的就是一些细节问题了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, m, tot, fa[2000005], rev[2000005], ans[2000005], vis[2000005];
struct node
{
int id;
int v;
int next;
} a[2][2000005];
void ins(int id, int u, int v, int pan)
{
node *b;
if (pan == 0)
b = a[0];
else
b = a[1];
if (b[u].id && b[u].v == v)
{
fa[b[u].id] = 0;
fa[id] = 0;
ans[id] = 1;
ans[b[u].id] = b[v].next;
b[u].id = 0;
b[v].id = 0;
return;
}
bool p = true;
if (b[u].id)
{
p = false;
fa[b[u].id] = tot;
rev[b[u].id] = b[u].next;
b[u].id = 0;
u = b[u].v;
}
if (b[v].id)
{
p = false;
fa[b[v].id] = tot;
rev[b[v].id] = b[v].next ^ 1;
b[v].id = 0;
v = b[v].v;
}
b[u].v = v;
b[v].v = u;
b[u].next = 1;
b[v].next = 0;
if (p)
{
b[u].id = id;
b[v].id = id;
}
else
{
fa[id] = tot;
b[u].id = tot;
b[v].id = tot;
++tot;
}
return;
}
void dfs(int k)
{
int x = k, t = 0;
vis[x] = 1;
while (a[t][x].id)
{
ans[a[t][x].id] = a[t][x].next;
if (vis[a[t][x].v])
return;
vis[a[t][x].v] = 1;
x = a[t][x].v;
t ^= 1;
}
x = k;
t = 1;
while (a[t][x].id)
{
ans[a[t][x].id] = a[t][x].next ^ 1;
if (vis[a[t][x].v])
return;
vis[a[t][x].v] = 1;
x = a[t][x].v;
t ^= 1;
}
return;
}
int main()
{
scanf("%d%d", &n, &m);
tot = m + 1;
for (int i = 1; i <= m; i++)
{
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
ins(i, u, v, w - 1);
}
for (int i = 0; i < n; ++i)
if (!vis[i])
dfs(i);
for (int i = tot; i >= 1; --i)
if (fa[i])
ans[i] = ans[fa[i]] ^ rev[i];
for (int i = 1; i <= m; i++)
printf("%d", ans[i]);
return 0;
}

 

评论

此博客中的热门博文