20191017测试总结

这套题的区分度可谓十分之高，让大家分数没啥差距。

T1：WOJ4756

送分题，记得开long long）雾

#include <iostream>
#include <cstdio>
using namespace std;
int n, m, s, t, a, w, d[200005];
long long ans;
int read()
{
    int x = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
int main()
{
    n = read();
    m = read();
    for (int i = 2; i <= m; ++i)
    {
        a = read();
        d[i] = d[i - 1] + a;
    }
    for (int i = 1; i <= n; ++i)
    {
        s = read();
        t = read();
        w = read();
        ans += (d[t] - d[s]) * w;
    }
    printf("%lld", ans);
    return 0;
}

T2：WOJ4757

挺有意思的一道DP，不过推出来了转移状态之后就不知道该干什么了。

原来DP的转移可以通过转换为下标来优化复杂度，以后数据范围小的题如果想不出来都应该想想这个方法。

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, num, s = 1, c[100005], f[100005];
struct node
{
    int id;
    int a;
} a[100005];
inline int read()
{
    int x = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
bool cmp(node aa, node bb)
{
    return aa.a < bb.a;
}
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int val)
{
    while (x <= n)
    {
        c[x] = max(c[x], val);
        x += lowbit(x);
    }
    return;
}
int query(int x)
{
    int ans = 0;
    while (x >= 1)
    {
        ans = max(ans, c[x]);
        x -= lowbit(x);
    }
    return ans;
}
int main()
{
    n = read();
    for (register int i = 1; i <= n; ++i)
    {
        a[i].id = i;
        a[i].a = read();
    }
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++i)
    {
        if (a[i].id >= a[i].a)
            f[i] = query(a[i].id - a[i].a + 1) + 1;
        if (a[i].a != a[i + 1].a)
        {
            for (int j = s; j <= i; ++j)
                if (a[j].id >= a[j].a)
                    add(a[j].id - a[j].a + 1, f[j]);
            s = i + 1;
        }
        num = max(num, f[i]);
    }
    printf("%d", num);
    return 0;
}

T3：WOJ4758

又是一道成功想出来了离正解差一点点的方法的题目。。。

通过x，y坐标分别排序之后就可以从前到后连边来解决问题了，极大的减少了边的数量。

看来我还需要多练习一下图论的建图题啊。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int n, sum, vis[200005], d[200005], head[200005];
struct node
{
    int v;
    int w;
    int next;
} a[800005];
struct bili
{
    int id;
    int x;
    int y;
} b[200005];
struct point
{
    int id;
    int d;
    point(int aa, int bb)
    {
        id = aa;
        d = bb;
    }
    bool operator<(point bb) const
    {
        return d > bb.d;
    }
};
priority_queue<point> q;
inline int read()
{
    int x = 0;
    char c = getchar();
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
    {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x;
}
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;
}
bool cmp1(bili aa, bili bb)
{
    return aa.x < bb.x;
}
bool cmp2(bili aa, bili bb)
{
    return aa.y < bb.y;
}
void dijkstra()
{
    memset(d, 0x7f, sizeof(d));
    d[1] = 0;
    q.push(point(1, 0));
    while (!q.empty())
    {
        point k = q.top();
        q.pop();
        if (vis[k.id])
            continue;
        vis[k.id] = 1;
        if (k.id == n)
            break;
        int dd = head[k.id];
        while (dd)
        {
            if (!vis[a[dd].v] && d[a[dd].v] > d[k.id] + a[dd].w)
            {
                d[a[dd].v] = d[k.id] + a[dd].w;
                q.push(point(a[dd].v, d[a[dd].v]));
            }
            dd = a[dd].next;
        }
    }
    return;
}
int main()
{
    n = read();
    for (int i = 1; i <= n; ++i)
    {
        b[i].id = i;
        b[i].x = read();
        b[i].y = read();
    }
    sort(b + 1, b + n + 1, cmp1);
    for (int i = 1; i < n; ++i)
    {
        ins(b[i].id, b[i + 1].id, b[i + 1].x - b[i].x);
        ins(b[i + 1].id, b[i].id, b[i + 1].x - b[i].x);
    }
    sort(b + 1, b + n + 1, cmp2);
    for (int i = 1; i < n; ++i)
    {
        ins(b[i].id, b[i + 1].id, b[i + 1].y - b[i].y);
        ins(b[i + 1].id, b[i].id, b[i + 1].y - b[i].y);
    }
    dijkstra();
    printf("%d", d[n]);
    return 0;
}