Codeforces Round #629 (Div. 3)

D. Carousel

题目：https://codeforces.com/contest/1328/problem/D

题解

仔细思考一下，会发现至多可能用到3种颜色（oooorz）
分类讨论

1. \(n\)个数相同，只用一种颜色
2. \(n\)是偶数，只用两种颜色：1， 2， 1， 2，，，
3. \(n\)是奇数
   • 如果存在\(a[i] = a[i \% n + 1]\)，那么将\(a[i]\)和\(a[i \% n + 1]\)染上同一种颜色，就成了第二种情况
   • 不存在的话，就用三种颜色，前\(n - 1\)个数的染色为：1，2，1，2，，，。最后一个数染色为 3。

我的\(idea\) ：当\(n\)是奇数，则前\(n - 1\)个数按第二类染色就行。讨论\(a[n]\)和\(a[1]\)的关系：①\(a[n] = a[1]\)，②\(a[n]\) != \(a[1]\)。①显然只要两种颜色，②需要三种颜色，既\(a[n]\)染色为3。对于②，考虑这样的样例: 1 2 2，很明显只需要用到两种颜色，而不是三种颜色。这时候，很自然的会想到判断\(a[n - 1]\)和\(a[n]\)的关系。emmmm，再进一步，考虑样例：2 1 1，发现只判断\(a[n - 1]\)和\(a[n]\)的关系是不够的。所以将思路打开，判断\(a[i] == a[i \% n + 1]\)，相同，就合并染同一种颜色。

void Solve() {

    cin >> n;

    vector<int> a(n);
    myfor(i, 0, n) cin >> a[i];

    if (count(a.begin(), a.end(), a[0]) == n) {
        cout << 1 << endl;
        myfor(i, 0, n) cout << 1 << " ";
        cout << endl;
        return;
    }
    if (n % 2 == 0 || a[0] == a[n]) {
        cout << 2 << endl;
        myfor(i, 0, n) cout << i % 2 + 1 << " ";
        cout << endl;
        return;
    }

    int pos = -1, k = 0;
    myfor(i, 0, n) if (a[i] == a[(i + 1) % n]) {
        pos = i;
        break;
    }

    if (pos == -1) {
        cout << 3 << endl;
        myfor(i, 0, n - 1) cout << i % 2 + 1 << " ";
        cout << 3 << endl;
    }
    else {
        cout << 2 << endl;
        myfor(i, 0, n) {
            cout << (i + k) % 2 + 1 << " ";
            if (i == pos) k = 1;
        }
        cout << endl;
    }
    return;
}

E. Tree Queries

\(n\)个点组成了一棵以1为根的树，有\(m\)次询问，每次询问给出一个点集\(S\)，然后问：是否存在一条从\(root\)到节点\(u\)的路径，使得\(S\)中的点要么在这条路径上，要么离这条路径的距离为1 ？

题解：

其实仔细体会一下：\(S\)中的点离这条路径小于等于1 \(\Longrightarrow\) \(S\)中的点的父亲节点都在这条路径上，也就是判断它们的父亲节点是不是在一条链上。这儿要用到一个叫 \(dfs\) \(order\) 的东西，假如$ u = pa[v]\(，\)timein_u < timein_v$ \(\&\&\) \(timeout_u > timeout_v\)。因为在一条链上，所以这种关系是层层嵌套的。

void DFS(int u, int p) {
    pa[u] = p;
    st[u] = cnt++;
    for (int i = head[u]; i != -1; i = e[i].next) {
        int v = e[i].to;
        if (v == p) continue;
        DFS(v, u);
    }
    ed[u] = cnt;
}

void Solve() {

     DFS(1, 1);

     int k;
     while(m--) {
        cin >> k;

        int mx = -1, mi = INF, x;
        myfor(i, 0, k) {
            cin >> x;
            x = pa[x];
            mi = min(mi, ed[x]);
            mx = max(mx, st[x]);
        }

        puts(mx < mi ? "YES" : "NO");
    }
    
    return;
}

int main() {
    Inite();

    cin >> n >> m;
    myfor(i, 1, n) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    Solve();
    return 0;
}

我的\(idea\)：考虑\(u\)的选择，首先有一个假设，如果存在这样一条路径，那么：\(u \in S\)一定能够成立，所以\(u\)的深度在\(S\)中一定最大。找到\(u\)以后，怎么判断\(S\)中的点到这条路径的距离小于等于1呢？很简单，举例：\(v \in S\)，\(p = LCA(v, u)\)，判断\(dep[v] - dep[p] <= 1\)是否成立即可。

void DFS(int u, int p, int deep) {
    dp[u] = deep;
    pa[0][u] = p;
    for (int i = head[u]; i != -1; i = e[i].next) {
        int v = e[i].to;
        if (v == p) continue;
        DFS(v, u, deep + 1);
    }
}

void Inite_Pa() {
    DFS(1, -1, 0);
    for (int k = 0; k + 1 < 17; k++) {
        for (int v = 1; v <= n; v++) {
            if (pa[k][v] < 0) pa[k + 1][v] = -1;
            else  pa[k + 1][v] = pa[k][pa[k][v]];
        }
    }
}

int LCA(int u, int v) {
    if (dp[u] > dp[v]) swap(u, v);
    myfor(k, 0, 17) if ((dp[v] - dp[u]) >> k & 1) v = pa[k][v];
    if (v == u) return v;
    for (int k = 15; k >= 0; k--) if (pa[k][v] != pa[k][u]) {
        v = pa[k][v];
        u = pa[k][u];
    }
    return pa[0][v];
}

void Solve() {
     Inite_Pa();


     int k;
     while(m--) {
        cin >> k;
        vector<int> a(k);

        int mx = -1, u = -1;
        myfor(i, 0, k) {
            cin >> a[i];
            if (dp[a[i]] > mx) {
                mx = dp[a[i]];
                u = a[i];
            }
        }
        bool flag = true;
        myfor(i, 0, k) {
            int p = LCA(u, a[i]);

            if (dp[a[i]] - dp[p] > 1) {
                flag = false;
                break;
            }
        }
        puts(flag ? "YES" : "NO");
     }

}

Codeforces Round #629 (Div. 3)

原文：https://www.cnblogs.com/zgglj-com/p/12593387.html