20191109测试总结

不用女装了）雾

T1、T3两个省选原题，T2一个骗分就可以过的题，真有趣

T1：洛谷P5322

很显然的一个DP。

曾老曰：10min想不出来该挨打

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int s, n, m, a[105][105], f[20005];
int main()
{
    scanf("%d%d%d", &s, &n, &m);
    for (int i = 1; i <= s; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &a[j][i]);
    for (int i = 1; i <= n; ++i)
        sort(a[i] + 1, a[i] + s + 1);
    for (int i = 1; i <= n; ++i)
        for (int j = m; j >= 1; --j)
            for (int k = 1; k <= s; ++k)
            {
                if (j < 2 * a[i][k] + 1)
                    break;
                f[j] = max(f[j], f[j - 2 * a[i][k] - 1] + i * k);
            }
    printf("%d", f[m]);
    return 0;
}

T2：WOJ4806

骗分：

直接判断相邻的数是否有绝对值之差大于k的即可（因为其中一个必定为另一个的祖先，无法通过奇怪的技巧组成可行解）。虽然这个正确性无法保证，但是我们稍微yy一下就可以发现它的正确率是很高的，当然，口说无凭，我们来对拍一下。按照和暴力的对拍，我们可以发现每秒可以拍2-3组数据，平均一刻钟拍出一组hack数据，而且都知错了其中一组数据的结果，因此我们可以发现它的错误率大概为千分之一，这个几率是十分低的。并且，这还是n<=20的情况下得到的条件。我们设想一下当n变大的时候，我们一定会有更多的组合方式，这也就意味的我们可以通过更多的方式来组合出可行解，那么此方法错误的概率会进一步降低。

按照惯例，出题人应该想不到这么奇怪的骗分，而随机生成的数据此算法正确率极高，就算卡也很难卡，稳赚不亏，甚至有打击率直接A掉，所以果断交上去。然而只有90分？？？错的还是第一个点？？？然后一看代码：原来我**是把>2和<n的数和左右两个数进行比较的，但是n=2的时候就会漏掉一次比较，因此就爆了。改了这个交上去：果断A了。

这告诉我们，一个良好的骗分可以在考试中取得出乎意料的结果，我们要学会瞎骗分，通过找刁钻的角度和难以被数据卡掉并且卡掉它的数据很难造的的莫名的做法来过掉一些难道。

#include <iostream>
#include <cstdio>
#include <cmath> 
using namespace std;
int t, n, k, a[200005];
int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch))
    {
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(isdigit(ch))
    {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int main()
{
    scanf("%d", &t);
    for(int tt = 1; tt <= t; ++tt)
    {
        n = read();
        k = read();
        for(int i = 1; i <= n; ++i)
            a[i] = read();
        bool p = true;
        for(int i = 2; i <= n; ++i)
            if(abs(a[i] - a[i - 1]) > k)
            {
                p = false;
                break;
            }
        if(p)
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

正解：

分治、扫描线和贪心都行，不过后两种方法比较奇怪，这里只说第一种。

我们可以发现，任意一个区间[l,r]都存在一个节点$latex i \in [l, r]$使得对于任意$latex j \in [l, r]$满足$latex |a_i - a_j| \leq k$是此题成立的充分必要条件。

因此，我们对于每个区间[l,r]找到符合条件的i就可以说明跨过i的区间一定都合法，然后再分治查找区间[l,i-1]和[i+1,r]即可。

当然，这样的话复杂度还是n^2的，只有60。因此我们还需要将找i从顺序枚举改成从首尾同时枚举（启发式合并的思想），这样就可以将复杂度降到O(nlogn)了。

#include <iostream>
#include <cstdio>
#include <cmath>
#define lch id << 1
#define rch id << 1 | 1
using namespace std;
int t, n, k, a[200005];
struct node
{
    int l;
    int r;
    int mi;
    int ma;
} tr[800005];
void build(int id, int l, int r)
{
    tr[id].l = l;
    tr[id].r = r;
    if (l == r)
    {
        tr[id].ma = a[l];
        tr[id].mi = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(lch, l, mid);
    build(rch, mid + 1, r);
    tr[id].ma = max(tr[lch].ma, tr[rch].ma);
    tr[id].mi = min(tr[lch].mi, tr[rch].mi);
    return;
}
int query_ma(int id, int l, int r)
{
    if (tr[id].l == l && tr[id].r == r)
        return tr[id].ma;
    int mid = (tr[id].l + tr[id].r) >> 1;
    if (r <= mid)
        return query_ma(lch, l, r);
    if (l >= mid + 1)
        return query_ma(rch, l, r);
    if (l <= mid && r >= mid + 1)
        return max(query_ma(lch, l, mid), query_ma(rch, mid + 1, r));
}
int query_mi(int id, int l, int r)
{
    if (tr[id].l == l && tr[id].r == r)
        return tr[id].mi;
    int mid = (tr[id].l + tr[id].r) >> 1;
    if (r <= mid)
        return query_mi(lch, l, r);
    if (l >= mid + 1)
        return query_mi(rch, l, r);
    if (l <= mid && r >= mid + 1)
        return min(query_mi(lch, l, mid), query_mi(rch, mid + 1, r));
}
bool dfs(int l, int r)
{
    if (l >= r)
        return true;
    int maxn = query_ma(1, l, r), minn = query_mi(1, l, r);
    int head = l, tail = r, pos = -1;
    while (head <= tail)
    {
        if (abs(a[head] - maxn) <= k && abs(a[head] - minn) <= k)
        {
            pos = head;
            break;
        }
        if (abs(a[tail] - maxn) <= k && abs(a[tail] - minn) <= k)
        {
            pos = tail;
            break;
        }
        ++head;
        --tail;
    }
    if (pos == -1)
        return false;
    if (dfs(l, pos - 1) && dfs(pos + 1, r))
        return true;
    return false;
}
int main()
{
    scanf("%d", &t);
    for (int tt = 1; tt <= t; ++tt)
    {
        scanf("%d%d", &n, &k);
        for (int i = 1; i <= n; ++i)
            scanf("%d", &a[i]);
        build(1, 1, n);
        if (dfs(1, n))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

T3：洛谷P5302

CSP模拟居然出现了省选T3。。。

显然a，b的算法和c的算法是完全独立的。

首先，我们可以发现交点个数等于逆序对个数。

对于a，b，最大值和最小值显然一种是一直对向交换，而对于另一种情况，我们设将到达的位置i与其要交换到的位置j连边，最后找到所有简单环，设环长为len，那么对向交换次数就是$latex \sum (len-1)$，剩下的就可以擦肩而过了。

对于c，将菱形转换成正方形，然后维护矩形并，判断交点是否在举行内部。

复杂度O((m+k)logm)。

代码来自std。

#include <set>
#include <cstdio>
#include <algorithm>

typedef long long ll;
const int maxN = 100005, maxM = 500005;
const double eps = 1e-6;

int N, A, B, C, Xst, Xed, K, Ys[maxN], Ye[maxN];
double Disc[maxM];
int discCnt;

struct line_t
{
    double x;
    int l, r, f;
    line_t() {}
    line_t(double _x, int _l, int _r, int _f) : x(_x), l(_l), r(_r), f(_f) {}
    inline bool operator<(const line_t &other) const
    {
        return x < other.x;
    }
} L[maxN * 2 + 1];
int Lcnt;

struct point_t
{
    double x, y;
    point_t() {}
    point_t(double _x, double _y) : x(_x), y(_y) {}
    inline bool operator<(const point_t &other) const
    {
        return x < other.x;
    }
} P[maxM];
int M;

int BIT[maxM];

void modify(int i, int v)
{
    for (; i <= M; i += i & -i)
        BIT[i] += v;
}
int query(int i)
{
    int res = 0;
    for (; i; i &= i - 1)
        res += BIT[i];
    return res;
}

int main()
{
    //freopen("trick.in", "r", stdin);
    //freopen("trick.out", "w", stdout);

    scanf("%d%d%d%d%d%d", &N, &A, &B, &C, &Xst, &Xed);
    for (int i = 1; i <= N; ++i)
        scanf("%d", Ys + i);
    for (int i = 1; i <= N; ++i)
        scanf("%d", Ye + i);
    scanf("%d", &K);
    for (int i = 1, p, q, x, y, r; i <= K; ++i)
    {
        scanf("%d%d%d", &p, &q, &r);
        x = p + q, y = p - q;
        L[++Lcnt] = line_t(x - r, y - r, y + r, 1);
        L[++Lcnt] = line_t(x + r + eps, y - r, y + r, -1);
    }
    
    static int perm[maxN];

    for (int i = 1; i <= N; ++i)
        perm[i] = i;
    
    for (int i = 1; i <= N; ++i)
    {
        int j;
        for (j = i - 1; j && Ye[perm[j]] > Ye[i]; --j)
        {
            perm[j + 1] = perm[j];
            int ds = Ys[i] - Ys[perm[j]], de = Ye[perm[j]] - Ye[i];
            double x = Xst + (double)(Xed - Xst) / (ds + de) * ds;
            double y = Ys[perm[j]] + (double)(Ye[perm[j]] - Ys[perm[j]]) / (ds + de) * ds;
            P[++M] = point_t(x + y, x - y);
            Disc[++discCnt] = x - y;
        }
        perm[j + 1] = i;
    }

    std::sort(Disc + 1, Disc + 1 + discCnt);
    discCnt = std::unique(Disc + 1, Disc + 1 + discCnt) - Disc - 1;

    ll ans1 = (ll)A * M;
    int cnt = N;

    static bool vis[maxN];

    for (int i = 1; i <= N; ++i)
        if (!vis[i])
        {
            --cnt;
            vis[i] = true;
            for (int j = perm[i]; j != i; j = perm[j])
                vis[j] = true;
        }
    
    ll ans2 = (ll)A * cnt + (ll)B * (M - cnt);

    cnt = 0;
    std::sort(L + 1, L + 1 + Lcnt);
    std::sort(P + 1, P + 1 + M);

    for (int i = 1, j = 1; i <= M; ++i)
    {
        while (j <= Lcnt && L[j].x <= P[i].x)
        {
            int l = std::lower_bound(Disc + 1, Disc + 1 + discCnt, (double)L[j].l) - Disc;
            int r = std::upper_bound(Disc + 1, Disc + 1 + discCnt, (double)L[j].r) - Disc - 1;
            if (l <= r)
                modify(l, L[j].f), modify(r + 1, -L[j].f);
            ++j;
        }
        int x = std::lower_bound(Disc + 1, Disc + 1 + discCnt, P[i].y) - Disc;
        if (query(x))
            ++cnt;
    }

    ans1 += (ll)cnt * C;
    ans2 += (ll)cnt * C;

    if (ans1 > ans2)
        std::swap(ans1, ans2);
    
    printf("%lld %lld\n", ans1, ans2);

    return 0;
}