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;
}

 

发表评论

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