冷滟泽的个人博客冷滟泽的个人博客

CF1010 总结

感觉这场平均难度比较低。。

A. Fly

明显的二分 + 模拟。EPS 不要设太小。

B. Rocket

先做 ny=1 的询问可以把序列 p 求出来,然后就可以二分答案了。然而我后面居然忘了把次数对 n 取模,想起来真是不应该。

C. Border

很明显将所有 a_ik 取模是对答案没有影响的。这些取模后的面值构成了一些同余类。考虑合并这些同余类,那么最终合并的结果是 gcd(a_1\mod k,a_2\mod k,\cdots,a_n\mod k,k)

D. Mars rover

首先 DP 求出每个节点的答案。考虑修改什么样的叶子会对答案造成影响。这只跟这个叶子到根的路径上的节点有关:如果中间过程中有一个节点无论从该叶子所在子树传上来什么参数这个节点的值都不会变化的话,那么根的答案也不会变。这样的情况只有两种:一种是 and 操作,另一个子树的值为 0;还有一种是 or 操作,另一个子树的值为 1。因为修改操作并不能继承,就可以很方便地 DFS 求出每个点到根的路径上有没有这样的点。

E. Store

把每个 (x_i,y_i,z_i) 视作三维空间里的一个点。在前面给出的 (n+m) 个点中,记 open 的为蓝点,closed 的为红点。那么商店开放的区间就是一个包含所有蓝点、不包含任何红点的长方体。由此可以判断出,矛盾的充要条件是包含所有蓝点的最小长方体(下称“最小矩体”)中包含了红点。

那么,对于一个询问的点,有三种情况:

  • 在最小矩体内,此时答案为OPEN
  • 不在最小矩体内,但包含所有蓝点和该点的最小长方体中包含红点,此时答案为CLOSED
  • 以上两种情况都不满足,此时答案为UNKNOWN

证明可以结合定义。

需要维护查询一个长方体内有没有点,这是经典的三维数点问题,可以用 KDTree(O\left(n^{\frac{2}{3}}\right))或 CDQ 分治(离线,O\left(n\log^2n\right))解决。

下面是 KDTree 实现的代码:

#include <cstdio>
#include <algorithm>
#include <tuple>
using namespace std;
const int MAXN=110000;
const int MAX=1E5+233;
int D;
struct Point
{
    int p[3];
    bool operator < (const Point& rhs) const
    {
        return p[D]<rhs.p[D];
    }
} a[MAXN];
struct KDTree
{
    struct Node
    {
        int ls, rs, d;
        int pla[3], mn[3], mx[3];
    } tr[MAXN];
    int cnt, root;
    void build(int& x, int l, int r, Point* a)
    {
        x=++cnt;
        int rng=-1;
        for (int k=0; k<3; k++)
        {
            tr[x].mn[k]=MAX, tr[x].mx[k]=0;
            for (int i=l; i<=r; i++)
            {
                tr[x].mn[k]=min(tr[x].mn[k], a[i].p[k]);
                tr[x].mx[k]=max(tr[x].mx[k], a[i].p[k]);
            }
            if (tr[x].mx[k]-tr[x].mn[k]>rng)
                rng=tr[x].mx[k]-tr[x].mn[k], tr[x].d=k;
        }
        int mid=l+r>>1; D=tr[x].d;
        nth_element(a+l, a+mid, a+r+1);
        for (int k=0; k<3; k++)
            tr[x].pla[k]=a[mid].p[k];
        if (mid>l) build(tr[x].ls, l, mid-1, a);
        if (mid<r) build(tr[x].rs, mid+1, r, a);
    }
    bool query(int x, Point l, Point r)
    {
        if (!x) return 0;
        bool flag=1;
        for (int k=0; k<3; k++)
        {
            if (tr[x].mn[k]>r.p[k]||tr[x].mx[k]<l.p[k]) return 0;
            if (tr[x].pla[k]>r.p[k]||tr[x].pla[k]<l.p[k]) flag=0;
        }
        if (flag) return 1;
        return query(tr[x].ls, l, r)||query(tr[x].rs, l, r);
    }
} kdt;
int main()
{
//  freopen("E.in", "r", stdin);
//  freopen("E.out", "w", stdout);
    int n, m, q, lx, ly, lz;
    scanf("%d%d%d%d%d%d", &lx, &ly, &lz, &n, &m, &q);
    Point mn, mx;
    for (int k=0; k<3; k++)
        mn.p[k]=MAX, mx.p[k]=0;
    for (int i=1; i<=n; i++)
        for (int k=0; k<3; k++)
        {
            int t; scanf("%d", &t);
            mn.p[k]=min(mn.p[k], t);
            mx.p[k]=max(mx.p[k], t);
        }
    for (int i=1; i<=m; i++)
    {
        bool flag=1;
        for (int k=0; k<3; k++)
        {
            scanf("%d", &a[i].p[k]);
            if (a[i].p[k]<mn.p[k]||a[i].p[k]>mx.p[k]) flag=0;
        }
        if (flag)
        {
            puts("INCORRECT");
            return 0;
        }
    }
    kdt.build(kdt.root, 1, m, a);
    puts("CORRECT");
    while (q--)
    {
        Point t;
        bool flag=1;
        for (int k=0; k<3; k++)
        {
            scanf("%d", &t.p[k]);
            if (t.p[k]<mn.p[k]||t.p[k]>mx.p[k]) flag=0;
        }
        if (flag) puts("OPEN");
        else
        {
            Point l, r;
            for (int k=0; k<3; k++)
            {
                l.p[k]=min(mn.p[k], t.p[k]);
                r.p[k]=max(mx.p[k], t.p[k]);
            }
            if (kdt.query(kdt.root, l, r)) puts("CLOSED");
            else puts("UNKNOWN");
        }
    }
    return 0;
}
未经允许不得转载:冷滟泽的个人博客 » CF1010 总结

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址