JOISC2020 自闭记

以下是考试时以及考试后我想出来的所有算法，因此很多题都不是正解

T1

11 pts 算法：考虑\(DP\)。

设\(f_{i, j, k}\)表示前\(i\)个数，选了\(j\)个\(B\)数组的数，且第\(i\)个数选的是\(A/B\)时，是否存在所要求的单调不降的数列。

直接\(DP\)，可以获得一个\(O(n^2)\)的做法。

100 pts 算法：

我们通过猜结论/打表发现一个规律。如果固定了\(i, k\)的话，那么使得\(f_{i, j, k} = 1\)的\(j\)的集合是一段连续的区间。

因此，我们可以缩减状态。

记录\(i, k\)固定的时候使得\(f_{i, j, k} = 1\)的\(j\)的最小和最大值。

这样转移变成取\(max/min\)。

考虑如何还原方案。

倒着填，通过\(DP\)结果判断是否能填A或者B。能填\(A\)则填\(A\)，否则填\(B\)。

时间复杂度\(O(n)\)，可以获得\(100\)分。

大概证明：对\(i\)归纳证明固定\(i, k \in \{0, 1 \}\)时,\(j\)的取值是一段区间，且固定\(i\),\(k\)为\(0,1\)之间的任意值时\(j\)的取值是一段区间。

T2

本人考场上只拿了\(3\)分。

\(2\)分做法：

\(k = 1\)时，这个点在\(n\)个长方形的交集内。

每个长方形的横坐标取值为\([L_i, R_i]\)，纵坐标取值为\([D_i, U_i]\)。

我们只需要求\(L\)的最大值，\(R\)的最小值，\(D\)的最大值，\(U\)的最小值。

然后在这上面任意放一个点即可。

\(3\)分做法：

\(k = 2, n \leq 2000\)时。

我们考虑求出\(R\)的最小值\(r\)。我们可以发现可以通过调整使得存在一个点的横坐标为\(r\)。枚举它的纵坐标(在这\(2n\)个D数组和U数组的值中枚举)，然后把它能覆盖的长方形删掉。再对剩下的长方形套用\(k = 1\)的算法。

时间复杂度\(O(n^2)\)，可以通过\(3\)分。

\(6\)分做法：

\(k = 2, n \leq 200000\)时，我们考虑从小到大对\(r\)做扫描线，在扫描线的过程中动态维护剩下的长方形中\(L, D\)的最大值和\(R, U\)的最小值。

实现时可以用\(4\)个堆来维护。

时间复杂度\(O(n \log n)\)，可以通过\(6\)分。

\(k = 3\)的做法：

实际上\(k \leq 3\)的时候可以\(O(n)\)。

我们求出\(L\)的最大值\(Lmax\)，\(R\)的最小值\(Rmin\),\(D\)的最大值\(Dmax\)，\(U\)的最小值\(Umin\)。

如果\(Lmax \leq Rmin\)，转换为\(1\)维问题，用区间覆盖算法。

否则形成的矩形的\(4\)条顶点中总有一个点要被选。

枚举这个点被不被选，递归下去求解即可。

时间复杂度\(O(n)\)。

\(k = 4, n \leq 2000\)的做法：

这时候我们需要考虑\(4\)条边中每条边恰好选\(1\)个点的情况。

枚举一条边上的一个点（通过离散化，它可以只有\(O(n)\)种取值），再套用\(k \leq 3\)的算法，可以获得一个\(O(n^2)\)的算法。

通过这些分析，我们可以获得\(21\)分。

正确性没有保证的做法：

随机\(k\)个矩形，将剩余的矩形随机排列。我们按照这个排列的顺序把每个矩形分为\(k\)类中的一类。假设排在它前面的矩形已经分划完毕，我们算出如果把这个矩形加入第\(i\)个集合，那么计算出这个集合的新的矩形交的面积大小/原来的面积大小。我们找其中最大者，加入那个集合。

我们多随机几次，直到划分出来的\(k\)组矩形都交集非空为止。

T3

简要题意：一开始你有\(m\)个二维平面上的点\((x_i, y_i)\)。\(x_i + y_i \leq n\)

然后有\(4\)种操作，

1.询问标号为\(P\)的点的横纵坐标

2.对于所有\(y_i \leq L\)的点，\(x_i \leftarrow \max (x_i, n - L)\)。

3.对于所有\(x_i \leq L\)的点，\(y_i \leftarrow max(y_i, n - L)\)

4.增加一个点\((X, Y)\)，它的标号是之前所有出现的点的个数 \(+ 1\)。

时限:\(11 s\)

数据范围:\(m \leq 500000, q \leq 10^6\)。

考场上这题写了\(22\)分。

\(1\)分算法：

对于\(m \leq 2000, q \leq 5000\)的测试点，我们直接暴力\(O(mq + q^2)\)的求解。

只有\(1,2,4\)操作时：

考虑把问题转换为求一段时间区间里面的\(l \ge x\)的所有\(l\)的最小值。我们可以用可持久化线段树来实现。

只有\(1,2, 3\)且\(x\)非严格递增，\(y\)非严格递减时：

考虑操作过程中永远满足\(x\)非严格递增，\(y\)非严格递减。

所以每次操作影响的标号是一段区间，且影响为\(y\)坐标赋为某个值，或者\(x\)坐标赋为某个值。可以在线段树上维护

\(x\)的最小值，\(x\)的最大值，\(y\)的最小值,\(y\)的最大值，\(x\)的赋值标记,\(y\)的赋值标记这六个变量来实现线段树上二分找区间以及线段树上修改的操作。

我们终于获得了\(22\)分。

JOISC Round2 自闭记

T1

\(O(n^2)\)算法：

考虑询问任意一对点\((u, v)\)，如果答案为\(1\)的话，得到\(u\)颜色与\(v\)相同或$u \space loves \space v \(或\)v \space loves \space u$。

接下来我们考虑如何区分这三类边。

对一个点\(u\)，如果\((u, v_1), (u, v_2), (u, v_3)\)是我们得到的点，那么我们询问\((u, v_1, v_2), (u, v_1, v_3), (u, v_2, v_3)\)，会得到其中一组的答案是\(1\)。设为\((u, v_1, v_2)\)。我们可以得到\(u \space loves \space v_3\)。如果\(u\)度数为\(1\)，那么和它相邻的点与它颜色相同。

这样我们可以得到所有的有向边，于是剩下的边就是满足端点颜色相同的边。

可以获得\(40\)分。

4分算法

问题变成询问一个点集里面出现不同颜色个数。

我们可以考虑二分，对每个点\(u\)，设剩下的点是\(v_1, ...., v_{2n - 1}\)。

询问\((u, v_1, ..., v_i)\)，再询问\((v_1, ..., v_i)\)。

如果第一个询问的答案比第二个多，说明\(u\)的颜色和\((v_1, .., v_i)\)是不同的。

这样我们可以二分出来和\(u\)的颜色相同的点。

Subtask 4 算法

如果我们知道每只变色龙的性别？

我们考虑对一个雄性的点\(u\)，设雌性的点为\(v_1, ..., v_n\)，那么我们询问:

\((u, v_1, ..., v_i)\)，如果答案是\(i + 1\)，那么就知道\(u\)到\(v_1, ..., v_i\)没有边。

我们可以通过这个事实依次二分出\(3\)条\(O(n^2)\)算法所要知道的边。

再使用\(O(n^2)\)算法的后半部分即可。

通过长途跋涉我们获得了\(64\)分。

某个\(O(n \log n)\)算法：

By zbw

另外一个：

By wyp

首先我们发现如果\(S\)是独立集，且\(u\)不在\(S\)中。

如果Query \(S\)与\(\{ u \}\)的并集，答案为\(\lvert S \rvert + 1\)，那么S与\(\{ u \}\)的并集也是独立集。

我们考虑在所有的点中，随机一个顺序，然后从左往右如果能加进独立集就加，会得到一个比较大的独立集。

(\(\ge 点数/4\))。

把所有不在独立集的点\(u\)去向独立集这个序列二分，会得到所有不在独立集的点连向在独立集的点的边。

然后把这个较大的独立集删掉。不断这样子做，直到最后所有点都访问过位置。

下同\(O(n^2)\)的后半部分。

T2

维护所有双向边构成的连通块。

我们发现要维护的东西有：

1.对每个连通块\(i\)，维护一个\(set\) ，\(from_i\)，所有连向它的点。

2.对每个点\(i\)，维护一个\(set\)，\(to1_i\)，表示它连向的连通块的集合。

3.对每个连通块\(i\)，维护一个\(set\)，\(to2_i\)，表示它连向的连通块。

4.对每个连通块\(i\)，维护一个\(set\)，\(comp_i\)，表示它内部的点数。

维护一个队列，表示可能需要缩的两个连通块。

每次在成功缩连通块后，

1.更新答案。

2.把增加的可能要缩的连通块\(push\)进队列。

连通块合并的过程我们可以用启发式合并来获得更优的复杂度。

关键代码如下：

void merge (int u, int v) {
    int ru = findroot(u), rv = findroot(v);
    if (ru == rv) return ;
    if (!to1[u].count(rv)) {
        to1[u].insert(rv), to2[ru].insert(rv);
        from[rv].insert(u), ans += sz[rv];
    }
    if (!to2[rv].count(ru)) return ;

    ans -= 1ll * sz[ru] * from[ru].size();
    ans -= 1ll * sz[rv] * from[rv].size();
    ans -= 1ll * sz[ru] * (sz[ru] - 1) / 2;
    ans -= 1ll * sz[rv] * (sz[rv] - 1) / 2;
    if (sz[ru] > sz[rv]) swap(ru, rv);

    for (set<int> :: iterator it = comp[ru].begin(); it != comp[ru].end(); it++) {
        int x = *it;
        comp[rv].insert(x), from[rv].erase(x);
        for (set<int> :: iterator i = to1[x].begin(); i != to1[x].end(); i++) q.push(make_pair(x, *i));
    }
    comp[ru].clear();
    
    for (set<int> :: iterator it = from[ru].begin(); it != from[ru].end(); it++) {
        int x = *it, rx = findroot(x);
        to1[x].erase(ru), to2[rv].erase(ru);
        if (rx != rv) {
            to1[x].insert(rv), to2[rx].insert(rv);
            from[rv].insert(x);
            q.push(make_pair(x, rv));
        }
    }
    from[ru].clear();

    for (set<int> :: iterator it = to2[ru].begin(); it != to2[ru].end(); it++) {
        int x = *it;
        if (x != rv) to2[rv].insert(*it);
    }
    to2[ru].clear();

    ans += 1ll * (sz[ru] + sz[rv]) * from[rv].size();
    ans += 1ll * (sz[ru] + sz[rv]) * (sz[ru] + sz[rv] - 1) / 2;
    fa[ru] = rv, sz[rv] += sz[ru];
}

    for (int i = 1; i <= m; i++) {
        int u, v;
        read(u), read(v);
        q.push(make_pair(u, v));
        while (!q.empty()) {
            pair<int, int> pi = q.front();
            q.pop(), merge(pi.first, pi.second);
        }
        write(ans), putchar('\n');
    }

若使用\(hash\)表，复杂度可以做到\(O((n + m) \log n)\)。否则为\(O((n + m) \log^2 n)\)。可以获得\(100\)分。