Codeforces Round #647 (Div. 2)。

D. Johnny and Contribution

        可以预见的是，如果两个点相邻，但是它们的权值是相同的，这样必然是无解的，因为无论先选哪一个，都没有办法使得另一个可以选。
        我们应该从小到大来进行选点，若某一个点的值为$v$，它周围相邻点必须包含全部的，权值为$1$到$v-1$的点（否则无解），并且这些点必须先选。根据选点的顺序关系，我们建立一个有向图，从这些权值较小的点，连向较大的相邻点，建出的图明显是一个$DAG$，这样只需要跑一个拓扑排序就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
const int N = 500000 + 5;
typedef long long ll;
struct Edge
{
    int next, to;
};
struct Graph
{
    Edge edge[N << 1];
    int head[N], cnt = 1;
    inline void add(int x, int y)
    {
        edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
    }
} g1, g2;
int n, m, v[N], in[N];
queue<int> que;
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, a, b; i <= m; i++) scanf("%d%d", &a, &b), g1.add(a, b), g1.add(b, a);
    for (int i = 1; i <= n; i++) scanf("%d", v + i);
    for (int i = 1; i <= n; i++) {
        set<int> ssp;
        for (int j = g1.head[i]; j; j = g1.edge[j].next) {
            if (v[g1.edge[j].to] == v[i]) {
                printf("-1");
                return 0;
            }
            if (v[g1.edge[j].to] < v[i]) g2.add(g1.edge[j].to, i), ++in[i], ssp.insert(v[g1.edge[j].to]);
        }
        if (int(ssp.size()) != v[i] - 1) {
            printf("-1");
            return 0;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (in[i] == 0) que.push(i);
    }
    while (!que.empty()) {
        int f = que.front();
        printf("%d ", f);
        que.pop();
        for (int i = g2.head[f]; i; i = g2.edge[i].next) {
            --in[g2.edge[i].to];
            if (in[g2.edge[i].to] == 0) que.push(g2.edge[i].to);
        }
    }
    return 0;
}

E. Johnny and Grandmaster

        这题出得很不错。
        我们首先对$k$从大到小排一个序，如果我们选出最大的$p^{k}$，剩下的数之和不大于它，这样答案必然就是两者之差。如果后者大于前者，则有这样一个断言：从后者中必然可以找出一些数，使其和为$p_{k}$。
        这个结论可以推广为下面的形式：

给出一个可重数集$S=\{p^i|0\leq i\leq k\}$，若该集合的和大于$p^k$，则必然可以从$S$中选出一些数，使其和恰好为$p^k$。

        用数学归纳法不难证明上面的结论。并且，根据归纳的过程，我们还可以知道必然是$S$中前若干个数的和等于$p^k$。
        这样我们就有了一个优雅的贪心思路：起初两个数集都是空，我们记录两者的差（一开始当然是$0$），从大到小枚举数，若这个差为$0$，我们将其加入第一个数集，否则加入第二个数集，更新这个差。
        根据上面证明的结论，也容易理解算法的正确性。
        差可能是一个很大的数，我们需要模一个大质数，但是这个差也可能被大质数整除，从而出错，于是我们需要模两个大质数来保证正确性。实测本题卡常用质数，比如同时用$1e9+7$和$998244353$会$WA$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;
const int mod1 = 1e9 + 7, mod2 = 1004535809, N = 1000005;
typedef long long ll;
int n, p, k[N];
inline int qpow(int x, int y, int mod)
{
    int ans = 1, sta = x;
    while (y) {
        if (y & 1) ans = 1ll * ans * sta % mod;
        sta = 1ll * sta * sta % mod, y >>= 1;
    }
    return ans;
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &p);
        for (int i = 1; i <= n; i++) scanf("%d", k + i);
        sort(k + 1, k + n + 1, greater<int>());
        int n1 = 0, n2 = 0;
        for (int i = 1; i <= n; i++) {
            if (n1 == 0 && n2 == 0) {
                n1 = (n1 + qpow(p, k[i], mod1)) % mod1;
                n2 = (n2 + qpow(p, k[i], mod2)) % mod2;
            } else {
                n1 = ((n1 - qpow(p, k[i], mod1)) % mod1 + mod1) % mod1;
                n2 = ((n2 - qpow(p, k[i], mod2)) % mod2 + mod2) % mod2;
            }
        }
        printf("%d\n", n1);
    }
    return 0;
}

F. Johnny and Megan’s Necklace

        看到答案域很小，直接从大到小枚举答案$k$，然后判断其正确性。
        容易发现，只有两个数它们满足$a\&(2^k-1)==b\&(2^k-1)$才能保证$a$与$b$的异或和能被$2^k$整除，然后下面就有了一个抽象建图的方法。
        将给的$n$个数对$(a,b)$看成边，取它们二进制表示的末尾$k$位，将这些可能的末尾$k$位（从$0$到$2^k-1$）看成点，建无向图。问题转化为求一个回路使得可以遍历所有的边，即求欧拉回路。
        欧拉回路不同于哈密顿回路，欧拉回路可以在$O(n+m)$复杂度下求出。在求欧拉回路之前，需要先判断欧拉回路的存在性：连通图，并且各个点度数都是偶数。
        求欧拉回路可以使用下面这个（参考题解得到的）$DFS$方法。注意在使用这种方法时，需要动态删边（走过的边需要删掉，否则不能保证复杂度），最好用vector而不是链式前向星存图。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;
const int N = 2000000 + 5;
const int nn = 5e6 + 5;
typedef long long ll;
int head[N], cnt = 1, n, p1[nn], p2[nn], Mask, vis[nn], deg[N], fa[N];
vector<pair<int, int>> vec[N];
int dep = 0;
void DFS(int x)
{
    while (!vec[x].empty()) {
        int to = vec[x].back().first, tag = vec[x].back().second;
        vec[x].pop_back();
        if (vis[(tag + 1) >> 1]) continue;
        vis[(tag + 1) >> 1] = 1, DFS(to);
        printf("%d %d ", tag, ((tag - 1) ^ 1) + 1);
    }
}
int ff(int x)
{
    return fa[x] == x ? x : fa[x] = ff(fa[x]);
}
inline int check(int x)
{
    Mask = (1 << x) - 1;
    for (int i = 0; i <= Mask; i++) vec[i].clear(), deg[i] = 0, fa[i] = i;
    for (int i = 1; i <= n; i++) vis[i] = 0;
    for (int i = 1; i <= n; i++) {
        vec[p1[i] & Mask].push_back({p2[i] & Mask, i << 1});
        vec[p2[i] & Mask].push_back({p1[i] & Mask, (i << 1) - 1});
        ++deg[p1[i] & Mask], ++deg[p2[i] & Mask];
        fa[ff(p1[i] & Mask)] = ff(p2[i] & Mask);
    }
    int rt = -1;
    for (int i = 0; i <= Mask; i++) {
        if (deg[i] & 1) return 0;
        if (deg[i]) {
            if (rt == -1) rt = ff(i);
            if (ff(i) != rt) return 0;
        }
    }
    printf("%d\n", x);
    for (int i = 0; i <= Mask; i++) {
        if (deg[i]) {
            DFS(i);
            break;
        }
    }
    return 1;
}
int main()
{
    scanf("%d", &n);
    // n = 500000;
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", p1 + i, p2 + i);
        // p1[i] = (i << 1) - 1, p2[i] = i << 1;
    }
    for (int i = 20; i >= 0; i--) {
        if (check(i)) break;
    }
    return 0;
}