Visits: 724

JOISC 2020

Day1

ビルの飾りつけ 4 (Building 4)

先考虑 $n \le 2 \times 10^3$ 怎么做。

设 $f_{i,j,0/1}$ 表示考虑前 $i$ 个数，在 $a$ 中选了 $j$ 个数，第 $i$ 个数选的是 $a/b$ 是否可行。

那么 $\mathcal O(n^2)$ dp 即可，如果有方案，从后往前构造。

注意到对于 $f_{i,j,0/1}$，如果 $i,0/1$ 固定，$j$ 可行的方案为一个区间。

因此只用 $\mathcal O(n)$ dp 出对于每个 $i,0/1$，$f_{i,j,0/1}$ 中 $j$ 的可行区间。

const int N = 5e5 + 7, inf = 1e9;
int n, a[N<<1], b[N<<1];
pi f[N<<1][2];

inline void upd(pi &a, pi b, bool c) {
    a.fi = min(a.fi, b.fi + c), a.se = max(a.se, b.se + c);
}

inline bool pd(pi a, int x) {
    return a.fi <= x && a.se >= x;
}

int main() {
    rd(n), rda(a, n << 1), rda(b, n << 1);
    f[1][0] = mp(1, 1), f[1][1] = mp(0, 0);
    for (int i = 2; i <= (n << 1); i++)
        for (int j = 0; j < 2; j++)
            f[i][j] = mp(inf, -inf);
    for (int i = 1; i < (n << 1); i++)
        for (int j = 0; j < 2; j++)
            if (f[i][j] != mp(inf, -inf)) {
                if (j == 0 && a[i+1] >= a[i])
                    upd(f[i+1][0], f[i][j], 1);
                if (j == 1 && a[i+1] >= b[i])
                    upd(f[i+1][0], f[i][j], 1);
                if (j == 0 && b[i+1] >= a[i])
                    upd(f[i+1][1], f[i][j], 0);
                if (j == 1 && b[i+1] >= b[i])
                    upd(f[i+1][1], f[i][j], 0);
            }
    if (!pd(f[n<<1][0], n) && !pd(f[n<<1][1], n)) return print(-1), 0;
    int p = n, q = 0;
    string s;
    a[n<<1|1] = b[n<<1|1] = inf;
    for (int i = n << 1; i; i--)
        if (pd(f[i][0], p) && a[i] <= (q ? b[i+1] : a[i+1]))
            s += 'A', --p, q = 0;
        else s += 'B', q = 1;
    reverse(s.begin(), s.end());
    prints(s);
    return 0;
}

美味しい美味しいハンバーグ (Hamburg Steak)

ouuan 的做法，不知道为啥能过。（upd：现在似乎已经被卡掉了）

首先随机 $k$ 个矩形，然后依次将剩下的矩形与 $k$ 个矩形求交，哪个剩下的面积与原来的面积之比最大就选择哪个。

多次随机直到找到解，可以通过本题全部数据。

const int N = 2e5 + 7;
const ld eps = 1e-10L;
int n, k;
struct P {
    int l, d, r, u;
    inline P() {}
    inline P(int l, int d, int r, int u) : l(l), d(d), r(r), u(u) {}
    inline void in() { rd(l), rd(d), rd(r), rd(u); }
    inline ll s() {
        return (l > r || d > u) ? 0ll : 1ll * (r - l + 1) * (u - d + 1);
    }
} p[N];
vector<P> a;

inline ll calc(P a, P b) {
    a.l = max(a.l, b.l);
    a.d = max(a.d, b.d);
    a.r = min(a.r, b.r);
    a.u = min(a.u, b.u);
    return a.s();
}

inline void upd(P &a, P b) {
    a.l = max(a.l, b.l);
    a.d = max(a.d, b.d);
    a.r = min(a.r, b.r);
    a.u = min(a.u, b.u);
}

inline bool work() {
    a.clear();
    map<int, bool> v;
    for (int i = 0; i < k; i++) {
        int x = rdm(1, n);
        while (v[x]) x = rdm(1, n);
        v[x] = 1, a.pb(p[x]);
    }
    for (int i = 1; i <= n; i++)
        if (v.find(i) == v.end()) {
            ld x = 0.0L;
            int o = -1;
            for (int j = 0; j < k; j++) {
                ld y = 1.0L * calc(a[j], p[i]) / a[j].s();
                if (y > x + eps) x = y, o = j;
            }
            if (!~o) return 0;
            upd(a[o], p[i]);
        }
    return 1;
}

int main() {
    srand(time(0));
    rd(n), rd(k);
    for (int i = 1; i <= n; i++) p[i].in();
    while (!work());
    for (int i = 0; i < k; i++) print(a[i].l, ' '), print(a[i].d);
    return 0;
}

掃除 (Sweeping)

写一个可能过不了的做法。。。

先考虑没有操作 $4$，即没有加入新点的情况。

首先有一个显然的结论：对于至少被移动过一次的点 $i,j$，一定不会出现 $x_i < x_j$ 且 $y_i < y_j$ 的情况。

因此，如果我们对至少被移动过一次的点，以横坐标从小到大为第一关键字，纵坐标从大到小为第二关键字排序，则每次移动的一定是一个区间，且移动前后排序关系不变。

考虑移动的本质为，将某一个区间里的点的横坐标或纵坐标对一个定值取 $\max$。

于是我们可以用一个支持区间修改，单点查询的数据结构维护，比如线段树。

那对于没有被移动过的点怎么办呢？

我们可以找到每个点第一次移动的时间，然后在那个时间插入到线段树中……

插入到线段树？这件事显然做不到，因此我们还要将线段树换成平衡树。

如何找到每个点第一次移动的时间呢？

由于移动涉及到的点都在一个矩形内，因此可以用可持久化线段树维护对于每个纵坐标，任意时刻受到影响的最大横坐标。然后对于每个点，在主席树上二分即可。

查询时，直接找到一个点在平衡树中的点，然后从这个点找到根再回溯，过程中下传区间修改时的标记即可。

设 $m,q$ 同阶，时间复杂度 $\mathcal O(m \log^2 m)$。

如果有加入新点的操作，考虑二进制分组维护这个过程。

即，假设当前有 $k$ 个点，按照 $k$ 的二进制位下 $1$ 的位置进行分组。比如如果 $k = 21$，则分成 $16+4+1$ 三组。显然，组的个数是 $\mathcal O(\log k)$ 的。

对于每组内部维护没有加入新点时的情况。当加入一个新点时，分成的组会从后往前合并，合并的同时暴力重构这一组即可。

由于每个节点至多被重构 $\mathcal O(\log m)$ 次，总时间复杂度为 $\mathcal O(m \log^3 m)$。

代码不写了。。。

Day2

カメレオンの恋 (Chameleon’s Love)

对于两个点 $x,y$，如果我们按照如下方式建图：

• 若 $x,y$ 颜色相同，则 $x,y$ 之间连一条无向边，记为 $x \leftrightarrow y$。
• 若 $x$ 喜欢 $y$，则连一条 $x \to y$ 的有向边。

先不考虑询问的限制次数。

如果我们询问所有的点对 $(x,y)$，返回的结果要么为 $1$，要么为 $2$。

如果为 $1$，则只有以下三种情况：

1. $x,y$ 颜色相同。
2. $x$ 喜欢 $y$，但 $y$ 不喜欢 $x$。
3. $y$ 喜欢 $x$，但 $x$ 不喜欢 $y$。

容易发现，当答案为 $1$ 时，$x,y$ 之间一定有边；答案为 $2$ 时，$x,y$ 之间一定无边，除了 $x \to y$ 且 $y \to x$ 的情况。

进一步可以发现，每个点的度数都是 $3$，但是询问出来的度数可能为 $1$。

若询问出来 $x$ 的度数为 $1$，则说明存在一个度数同样为 $1$ 的点 $y$，符合 $x \to y$ 且 $y \to x$ 的情况，而询问出来的那条边，则是一条无向边 $x \leftrightarrow z$，这意味着 $x,z$ 的颜色相同。

若询问出来 $x$ 的度数为 $3$，设这 $3$ 个点为 $y,z,w$。考虑到如果我们询问 $(x,y,z),(x,y,w),(x,z,w)$，其中有且仅有一组的答案为 $1$，其它两组的答案都为 $2$。

不妨设为 $1$ 的询问为 $(x,y,z)$，则只可能是 $x \leftrightarrow y$ 且 $z \to x$，或者 $x \leftrightarrow z$ 且 $y \to x$。

尽管我们无法得知是哪种，但是我们可以以此确定 $x \to w$ 这条边。

通过这种方法，我们可以确定所有的有向边，那么剩下的边就是无向边，即颜色相同的点。

这个做法的询问次数为 $\mathcal O(n^2)$ 的，瓶颈在询问两两点对上。

考虑优化这个过程。

我们可以通过 $\mathcal O(n)$ 次询问求出一个极大独立集。

方法为，从 $1 \sim 2n$ 依次尝试加入当前的极大独立集 $S$，如果询问 $(S,x)$ 的答案为 $|S| + 1$，则说明可以加入，否则说明有边。

找到极大独立集之后，对于独立集之外的点，在独立集中二分找到所有边。

此时还剩下独立集之外的点中的边没有找到，那么重复上述过程，直到所有剩下的点都是一个独立集。

由于每个点的度数最多为 $3$，因此每次独立集的大小 $\ge$ 总点数的 $\frac 14$。这意味着每次我们可以将点的规模缩小到原来的 $\frac 34$，那么一共只需要最多重复 $\mathcal O(\log n)$ 次就能找到所有边，因此求最大独立集部分的询问次数为 $\mathcal O(n \log n)$。

又由于每找到一条边需要一次二分，而边数是 $\mathcal O(n)$ 的，所以二分部分也只有 $\mathcal O(n \log n)$ 次询问。

这样我们就可以用 $\mathcal O(n \log n)$ 次询问找到所有边，为了减小常数防止被卡，可以先对点进行 random_shuffle。

inline int get(int x, vi p) {
    int l = 0, r = p.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        vi q(1, x);
        for (int i = l; i <= mid; i++) q.pb(p[i]);
        if (Query(q) != (int)q.size()) r = mid;
        else l = mid + 1;
    }
    return p[l];
}

inline int ask(int x, int y, int z) {
    vi p(3);
    p[0] = x, p[1] = y, p[2] = z;
    return Query(p);
}

void Solve(int n) {
    srand(time(0));
    vi A, B;
    for (int i = 1; i <= (n << 1); i++) B.pb(i);
    random_shuffle(B.begin(), B.end());
    vector<vi> e(n << 1 | 1);
    while (B.size()) {
        vi S = B, v(n << 1 | 1);
        A.clear(), B.clear();
        for (int x : S) {
            A.pb(x);
            if (Query(A) != (int)A.size()) A.pop_back(), B.pb(x);
            else v[x] = 1;
        }
        for (int i : B) {
            vi p = A;
            p.pb(i);
            do {
                p.pop_back();
                int k = get(i, p);
                e[k].pb(i), e[i].pb(k);
                for (int &x : p)
                    if (x == k) swap(x, p.back());
                p.pop_back();
                p.pb(i);
            } while (Query(p) != (int)p.size());
        }
    }
    vi v(n << 1 | 1);
    vector<map<int, bool>> f(n << 1 | 1);
    for (int x = 1; x <= (n << 1); x++)
        if (e[x].size() == 3u) {
            int y = e[x][0], z = e[x][1], w = e[x][2];
            if (ask(x, y, w) == 1) swap(z, w);
            else if (ask(x, z, w) == 1) swap(y, w);
            f[x][w] = f[w][x] = 1;
        }
    for (int x = 1; x <= (n << 1); x++)
        if (!v[x])
            for (int y : e[x])
                if (!f[x][y]) v[x] = v[y] = 1, Answer(x, y);
}

ジョイッターで友だちをつくろう (Making Friends on Joitter is Fun)

并查集维护每个极大团即可。

如果某一次加边后，存在两个团之间可以互相到达，则需要合并这两个团。

用 set 维护每个团内的节点，点团之间的边，和团团之间的边，合并时启发式合并。

时间复杂度 $\mathcal O(n \log^2 n)$。

const int N = 1e5 + 7;
int n, m, f[N];
set<int> s[N], e[N], g[N], fe[N], fg[N];
deque<int> X, Y;
ll ans;

int get(int x) {
    return x == f[x] ? x : (f[x] = get(f[x]));
}

inline void work(int x, int y) {
    int fx = get(x), fy = get(y);
    if (fx == fy) return;
    if (fe[fy].find(fx) == fe[fy].end()) {
        if (g[fy].find(x) == g[fy].end())
            ans += s[fy].size(),
            e[x].insert(fy), g[fy].insert(x),
            fe[fx].insert(fy), fg[fy].insert(fx);
        return;
    }
    ans -= 1ll * s[fx].size() * (s[fx].size() - 1);
    ans -= 1ll * s[fy].size() * (s[fy].size() - 1);
    fe[fy].erase(fx), fg[fx].erase(fy);
    if (s[fx].size() < s[fy].size()) swap(fx, fy);
    for (int i : s[fy]) {
        for (int j : e[i])
            ans -= s[j].size(),
            g[j].erase(i),
            X.pb(i), Y.pb(j);
        e[i].clear();
    }
    for (int i : g[fy])
        ans -= s[fy].size(),
        e[i].erase(fy),
        X.pb(i), Y.pb(fx);
    g[fy].clear();
    for (int i : fe[fy]) fg[i].erase(fy);
    for (int i : fg[fy]) fe[i].erase(fy);
    for (int i : s[fy]) s[fx].insert(i);
    f[fy] = fx;
    ans += 1ll * s[fx].size() * (s[fx].size() - 1);
    ans += 1ll * g[fx].size() * s[fy].size();
    s[fy].clear();
}

int main() {
    rd(n), rd(m);
    for (int i = 1; i <= n; i++) f[i] = i, s[i].insert(i);
    for (int i = 1, x, y; i <= m; i++) {
        rd(x), rd(y), X.pb(x), Y.pb(y);
        while (X.size()) work(X[0], Y[0]), X.pop_front(), Y.pop_front();
        print(ans);
    }
    return 0;
}

最古の遺跡 3 (Ruins 3)

题目太神仙了，先咕咕咕着。

Day3

星座 3 (Constellation 3)

考虑从上往下选，则如果选择了一个星星，那下面就由一些星星不能选了。

建出笛卡尔树之后可以发现，笛卡尔树上面的每个节点都对应着一个极大矩形，而一棵星星所在的极大矩形，在笛卡尔树上正好是一条，从某个节点到其子树内某个叶子的路径。

因此对于一个笛卡尔树上的节点，其对应区间的上面最多只会有一颗星星。考虑树形 dp，设 $f_{i,j}$ 表示在横坐标为 $i$ 的节点对应区间的上面，星星的纵坐标为 $j$ 时的最大权值和。

直接 dp 状态数有 $\mathcal O(n^2)$ 个，但有效的状态只和星星数有关。

因此用 map 记录有效状态，转移时启发式合并即可，时间复杂度 $\mathcal O(n \log^2 n)$。

const int N = 2e5 + 7;
int n, m, a[N], s[N], t, l[N], r[N], rt;
map<int, ll> f[N];
ll g[N], z[N], ans, sum;

inline void work(int x, int y) {
    while (f[x].size() && f[x].begin() -> fi <= y)
        g[x] = max(g[x], f[x].begin() -> se + z[x]), f[x].erase(f[x].begin());
}

inline int merge(int x, int y) {
    if (f[x].size() < f[y].size()) swap(x, y);
    z[x] += g[y], z[y] += g[x], g[x] += g[y];
    for (auto o : f[y]) f[x][o.fi] = max(f[x][o.fi], o.se + z[y] - z[x]);
    return x;
}

int dfs(int x) {
    int y = x;
    if (l[x]) l[x] = dfs(l[x]), work(l[x], a[x]), y = merge(y, l[x]);
    if (r[x]) r[x] = dfs(r[x]), work(r[x], a[x]), y = merge(y, r[x]);
    return y;
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) {
        rd(a[i]);
        int k = t;
        while (k && a[s[k]] < a[i]) --k;
        if (k) r[s[k]] = i;
        if (k < t) l[i] = s[k+1];
        s[++k] = i, t = k;
    }
    rt = s[1];
    rd(m);
    for (int i = 1, x, y, z; i <= m; i++)
        rd(x), rd(y), rd(z), f[x][y] = z, sum += z;
    rt = dfs(rt), ans = g[rt];
    for (auto o : f[rt]) ans = max(ans, o.se + z[rt]);
    print(sum - ans);
    return 0;
}

収穫 (Harvest)

题目太神仙了，先咕咕咕着。

迷い猫 (Stray Cat)

通信题，扔了。

Day4

首都 (Capital City)

答案相当于要找到一个包含颜色最少的连通块，满足连通块内的颜色和连通块外的颜色两两不同，我们称这样的连通块为合法连通块。

考虑点分治，对于每一次点分出来的重心和连通块，我们在连通块中找到最小的包含重心的合法连通块，用这个连通块的答案去更新答案。

这样，最优解一定会被更新到，时间复杂度 $\mathcal O(n \log n)$。

const int N = 2e5 + 7;
int n, m, a[N], c[N], ans, f[N], s[N], rt, mn;
vi e[N], b[N], p;
bool u[N], v[N], w[N];

void getrt(int x, int S) {
    v[x] = 1, s[x] = 1;
    if (!b[a[x]].size()) p.pb(a[x]);
    b[a[x]].pb(x); 
    int o = 0;
    for (int y : e[x])
        if (!v[y] && !w[y]) getrt(y, S), s[x] += s[y], o = max(o, s[y]);
    o = max(o, S - s[x]);
    if (o < mn) rt = x, mn = o;
    v[x] = 0;
}

void dfs(int x) {
    v[x] = 1, s[x] = 1;
    for (int y : e[x])
        if (!v[y] && !w[y]) f[y] = x, dfs(y), s[x] += s[y];
    v[x] = 0;
}

void solve(int x, int S) {
    rt = x, mn = S, f[x] = 0, getrt(x, S), dfs(rt);
    queue<int> q;
    q.push(a[rt]), u[a[rt]] = 1, v[rt] = 1;
    int cnt = 0;
    bool ok = (int)b[a[rt]].size() == c[a[rt]];
    while (ok && q.size()) {
        int x = q.front();
        q.pop();
        for (int y : b[x])
            while (!v[y]) {
                v[y] = 1;
                if (!u[a[y]]) {
                    if ((int)b[a[y]].size() != c[a[y]]) ok = 0;
                    q.push(a[y]), u[a[y]] = 1, ++cnt;
                }
                y = f[y];
            }
    }
    if (ok) ans = min(ans, cnt);
    for (int x : p) {
        for (int y : b[x]) v[y] = 0;
        b[x].clear(), u[x] = 0;
    }
    p.clear();
    w[rt] = 1;
    int now = rt;
    for (int nxt : e[now])
        if (!w[nxt]) solve(nxt, s[nxt]);
}

int main() {
    rd(n), rd(m), ans = m;
    for (int i = 1, x, y; i < n; i++)
        rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    for (int i = 1; i <= n; i++) rd(a[i]), ++c[a[i]];
    solve(1, n), print(ans);
    return 0;
}

伝説の団子職人 (Legendary Dango Maker)（1,2,3,4,5,6）

提答题，扔了。

治療計画 (Treatment Project)

我们以横坐标为时间轴，纵坐标为位置轴构建平面直角坐标系。

考虑一个治疗方案 $(T_i,L_i,R_i)$ 单独在这样一个坐标系中的覆盖区域，可以发现其覆盖的区域为以 $(T_i,L_i),(T_i,R_i)$ 为两个 $45^\circ$ 角向右的一个等腰直角三角形。

特别地，对于 $L_i = 1$ 的方案，它还能多覆盖一点三角形下方的区域；对于 $R_i = n$ 的方案，它还能多覆盖一点三角形上方的区域。具体可以自己手画一下。

由于最终要求所有人都被治愈，因此一个方案合法当且仅当这些区域可以拼接起来且使某个 $L_i=1$ 的方案与某个 $R_i = n$ 的方案连通。

注意，这里的拼接并不是指有交，对于方案 $i,j$，$i$ 可以与 $j$ 单向地拼接当且仅当 $|T_i-T_j|\le R_i – L_j + 1$，具体也可以自己手画一下。

显然，求解这个问题就是一个最短路。

直接连边边数是 $\mathcal O(m^2)$ 的，显然无法承受，用线段树 + set 优化连边即可。

这个优化连边的 Trick 跟 P5471 [NOI2019]弹跳 很像。具体来说，在点权最短路上，每个点最多只会被松弛一次，即对于每个点，第一次更新到它时的值就是它的最短路（在边权最短路中这显然是不一定的）。于是我们可以在某一个点被更新过就立刻删掉它，这样时间复杂度就与边数无关，为 $\mathcal O(n \log n)$ 了。

这两道题都有一个共同点是，二维平面上从一个点到一个区域连边跑点权最短路，于是我们可以用一棵线段树维护第一维，线段树中每个节点用一个 set 存下在第一维里这个区间内的所有点，这样每个点被复制了 $\mathcal O(\log m)$ 次，总点数为 $\mathcal O(m \log m)$，跑上述所说的点权最短路，总时间复杂度为 $\mathcal O(m \log^2 m)$。

const int N = 1e5 + 7;
const ll inf = 1e18;
int n, m;
struct P {
    int t, l, r, c;
    inline void in() { rd(t), rd(l), rd(r), rd(c); }
    inline bool operator < (const P o) const { return t < o.t; }
} p[N];
struct T {
    int l, r;
    set<pi> s;
} t1[N<<2], t2[N<<2];
ll d[N], ans = inf;
pq<pair<ll, int>> q;
bool v[N], w[N];

void build(T* t, int p, int l, int r) {
    t[p].l = l, t[p].r = r;
    if (l == r) return;
    build(t, ls, l, md), build(t, rs, md + 1, r);
}

void ins(T *t, int p, int x, pi k) {
    t[p].s.insert(k);
    if (t[p].l == t[p].r) return;
    if (x <= md) ins(t, ls, x, k);
    if (x > md) ins(t, rs, x, k);
}

void upd(T *t, int p, int l, int r, int x, ll k) {
    if (l <= t[p].l && r >= t[p].r) {
        while (t[p].s.size() && t[p].s.begin() -> fi <= x) {
            int y = t[p].s.begin() -> se;
            t[p].s.erase(t[p].s.begin());
            if (w[y]) continue;
            d[y] = k + ::p[y].c, q.push(mp(-d[y], y)), w[y] = 1;
        }
        return;
    }
    if (l <= md) upd(t, ls, l, r, x, k);
    if (r > md) upd(t, rs, l, r, x, k);
}

int main() {
    rd(m), rd(n);
    for (int i = 1; i <= n; i++) p[i].in();
    sort(p + 1, p + n + 1);
    build(t1, 1, 1, n), build(t2, 1, 1, n);
    for (int i = 1; i <= n; i++)
        ins(t1, 1, i, mp(p[i].l - p[i].t, i)),
        ins(t2, 1, i, mp(p[i].l + p[i].t, i));
    for (int i = 1; i <= n; i++)
        if (p[i].l != 1) d[i] = inf;
        else d[i] = p[i].c, q.push(mp(-d[i], i)), w[i] = 1;
    while (q.size()) {
        int x = q.top().se;
        q.pop();
        if (v[x]) continue;
        v[x] = 1;
        if (x != 1) upd(t1, 1, 1, x - 1, p[x].r - p[x].t + 1, d[x]);
        if (x != n) upd(t2, 1, x + 1, n, p[x].r + p[x].t + 1, d[x]);
    }
    for (int i = 1; i <= n; i++)
        if (p[i].r == m) ans = min(ans, d[i]);
    print(ans == inf ? -1 : ans);
    return 0;
}