Codeforces Round #647 (Div. 2)

        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;
}

0%