2018 ACM-ICPC, Syrian Collegiate Programming Contest

字数统计: 4.7k字   |   阅读时长: 23分
训练题解
solved A B C D E F G H I J K L
9 / 12 O O O O · Ø Ø O O · Ø ·
  • O：比赛时通过
  • Ø：赛后通过
  • !：比赛时尝试了未通过
  • ·：比赛时未尝试

比赛链接

A - Hello SCPC 2018!

solved by Tryna. 00:09(+1)

题解： 签到题

AC代码 
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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;
const int N = 2e5 + 10;
int a[100], b[100];
void run () {
	for(int i = 1; i <= 12; i++) {
		scanf("%d", &a[i]);
		b[i] = a[i];
	}
	sort(a + 1, a + 13);
	int flag = 0;
	for(int i = 1; i <= 4; i++) {
		if(a[i] != b[i]) flag = 1;
	}
	if(flag == 1) {
		puts("no");
	}
	else puts("yes");
}

int main () {
	freopen("hello.in", "r", stdin);
	int _ = 1;
	scanf("%d", &_);
	while (_--) run();
}

B - Binary Hamming

solved by lllllan. 00:13(+)

题意 给定两个01字符串，可随意移动每个字符串上01的位置，求重新排列后两个字符串字符不同的最大位数。

AC代码 
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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 110;
const int N = 2e5 + 10;

int n;
char a[maxn];
char b[maxn];

void run () {
	
	scanf("%d", &n);
	
	scanf("%s%s", a + 1, b + 1);
	
	int c1 = 0, c2 = 0;
	int d1 = 0, d2 = 0;
	
	for (int i = 1; i <= n; ++i) {
		if (a[i] == '1') c1++;
		else c2++;
		
		if (b[i] == '1') d1++;
		else d2++;
	}
	
	printf("%d\n", min(c1, d2) + min(c2, d1));
}

int main () {
	freopen("hamming.in", "r", stdin);
	
	int _ = 1;
	scanf("%d", &_);
	while (_--) run();
}

C - Portals

solved by lllllan. 00:55(+)

题意： 一个字符串中

  • ss代表起点
  • ee代表终点
  • #代表不可通过的墙
  • ..代表可通过的路
  • oo代表传送门，可以传送去任意一个传送门的位置。

求最少在可以在多少个..防止墙以隔开，是的起点无法到达终点。

题解： 分类讨论一下，尽量考虑周到一些即可。

  • sese直接相连，那不可能阻断，输出−1-1
  • sese各自直接和一个oo相连，可直接传送到达，也不可能阻断，输出−1-1
  • 剩下的所有情况都是可以阻断的，只是要找到最少的花费罢了
    • 从起点向两边出发：
      • 遇到终点，需要在路上阻断，花费为1。结束探索
      • 遇到传送门，不确定到达其他传送门之后是否可达终点，花费暂且也记为1。结束探索
      • 路径到头或者遇到墙，不可能再往前移动，花费记为0。结束探索
    • 从终点也是同理向两边出发，相同操作
    • 最小花费即为封闭起点两边或封闭终点两边的最小花费
AC代码 
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;
const int N = 2e5 + 10;

int n;
char s[maxn];

void run () {
	
	scanf("%d", &n);
	
	scanf("%s", s + 1);
	
	int flagS = 0;
	int flagE = 0;
	
	int S = 0, E = 0;
	for (int i = 1; i <= n; ++i) {
		if (s[i] == 's') {
			if (i > 1 && s[i - 1] == 'e') return (void)( printf("-1\n") );
			if (i < n && s[i + 1] == 'e') return (void)( printf("-1\n") );
			
			if (i > 1 && s[i - 1] == 'o') flagS = 1;
			if (i < n && s[i + 1] == 'o') flagS = 1;
			for (int j = i + 1; j <= n; ++j) {
				if (s[j] == '#') break;
				if (s[j] == 'e' || s[j] == 'o') {
					S++;
					break;
				} 
			}
			for (int j = i - 1; j; --j) {
				if (s[j] == '#') break;
				if (s[j] == 'e' || s[j] == 'o') {
					S++;
					break;
				} 
			}
		}
		
		if (s[i] == 'e') {
			if (i > 1 && s[i - 1] == 'o') flagE = 1;
			if (i < n && s[i + 1] == 'o') flagE = 1;
			for (int j = i + 1; j <= n; ++j) {
				if (s[j] == '#') break;
				if (s[j] == 's' || s[j] == 'o') {
					E++;
					break;
				} 
			}
			for (int j = i - 1; j; --j) {
				if (s[j] == '#') break;
				if (s[j] == 's' || s[j] == 'o') {
					E++;
					break;
				} 
			}
		}
	}
	
	if (flagS && flagE) return (void)( printf("-1\n") );
	
	if (!flagS && !flagE) return (void)( printf("%d\n", min(S, E)) );
	
	printf("%d\n", flagS ? E : S);
}

int main () {
	freopen("portals.in", "r", stdin);
	
	int _ = 1;
	scanf("%d", &_);
	while (_--) run();
}

D - Carnival Slots

solved by lllllan & Sstee1XD. 01:23(+1)

题意： 模拟一个游戏机，上方有c列出口分别释放一定数量的小球，下方r行字符串表示游戏机中的“地图”

  • ‘.’ 表示没有障碍物，小球经过会直线下落
  • ‘\’ 表示一个隔板，经过的小球会向右移动一列然后继续下落
  • ‘/’ 表示一个隔板，经过的小球会向左移动一列然后继续下落
    游戏机的下方会有c列出口分别有不同的得分，小球下落之后进入哪个出口将获得该出口相对应的分数。你可以奖所有的隔板变换成以上三种形态的任意一种，以获得游戏最后的最大得分。

题解： 从游戏机的最下面一层逐步往上模拟，在每个存在隔板的位置，判断它本身和它边上两列的得分情况，取最大值。

比如一到三列的得分分别是1、2、3，假设在第二列上放有一个隔板，我们将这个隔板设置为向右的隔板，使得小球最终向右一列移动以获得更高的得分。直接将第二列的得分修改成3即可

AC代码 
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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 510;
const int N = 2e5 + 10;

int n, m;

ll a[maxn];
ll w[maxn];
ll tem[maxn];

char s[maxn];

vector<int> pos[maxn];

void Max (ll &a, ll b) { if (a < b) a = b; }

void run () {
	
	scanf("%d%d", &n, &m);
	
	for (int i = 1; i <= m; ++i) scanf("%lld", a + i);
	
	for (int i = 1; i <= n; ++i) {
		pos[i].clear();
		scanf("%s", s + 1);
		for (int j = 1; j <= m; ++j) {
			if (s[j] == '\\' || s[j] == '/') pos[i].push_back(j);
		}
	}
	
	for (int i = 1; i <= m; ++i) scanf("%lld", w + i);
		
	for (int i = n; i; --i) {
		for (int j = 1; j <= m; ++j) tem[j] = w[j];
		for (int v : pos[i]) {
			if (v > 1) Max(tem[v], w[v - 1]);
			if (v < m) Max(tem[v], w[v + 1]);
		}
		for (int v : pos[i]) {
			Max(w[v], tem[v]);
		}
	}
	
	ll ans = 0;
	for (int i = 1; i <= m; ++i) ans += a[i] * w[i];
	printf("%lld\n", ans);
	
}

int main () {
	freopen("balls.in", "r", stdin);
	
	int _ = 1;
	scanf("%d", &_);
	while (_--) run();
}

F - Pretests

solved by Tryna, lllllan. (-)

题意： 最多有20组测试样例，以及n次提交。n行字符串表示每次提交的通过情况，1为该测试样例通过，0为不通过。要求重新排列测试样例的顺序，使得所有的提交的测试次数和最小（如果到某个测试样例不通过，则不再进行下一次测试）

题解：

  • 20组测试样例，重新排序以获得更优解，考虑DP（单步贪心不一定能获得最后答案的最优解）
  • 如果DP又要记录通过的提交数量，又要记录几组测试样例的排放顺序，比较棘手。考虑状压，再增设一个pre数组用于记录到达该状态的前一个测试样例是谁以达到记录顺序的目的。
  • 新的问题就又来了，每个状态，新增的哪个测试样例，能通过多少人又或是能判错多少人，又该 如何记录。考虑SOSDP，高维前缀和DP。

重新整理一遍思路。

  • 对某个提交，（因为0表示不通过1表示通过）而我偏偏想要记录不通过的情况，因此对提交的01字符串取反，然后状压记录状态。
  • 对于所有的状态，通过SOSDP记录所有所有状态下涵盖的提交数量（比如说状态111涵盖了两次提交011、101）.
  • 定义DP[i]专门用于表示这个状态下的几个测试样例还没进行，还存在多少没被淘汰的提交记录。
  • 然后就可以进行最后一步了，从小到大枚举所有的状态，题目想要尽可能早地淘汰更过的提交记录，在外面的DP里就是要可能少的留下一下提交记录，然后定义pre[]记录这个状态的前一个测试样例即可
AC代码 
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

#define dbg(x...)             \
    do {                      \
        cout << #x << " -> "; \
        err(x);               \
    } while (0)
void err() { cout << endl; }
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
    cout << arg << ' ';
    err(args...);
}

inline int rd() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = (1 << 20) + 101;

char s[22];
int n, m, up;

int a[maxn];
int dp[maxn];
int pre[maxn];

void run() {
    scanf("%d%d", &m, &n);
    up = 1 << m;

    for (int i = 0; i < up; ++i) a[i] = 0;

    int num = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);

        int x = 0;
        for (int j = m; j; --j) {
            x <<= 1;
            if (s[j] == '0') x |= 1;
        }
        // dbg(i, x);
        ++a[x];
        num += (x == 0);
    }

    for (int i = 0; i < m; ++i) {
        for (int mask = 0; mask < up; ++mask) {
            if (mask & (1 << i)) {
                a[mask] += a[mask ^ (1 << i)];
                // dbg(mask, 1 << i, mask ^ 1 << i);
            }
        }
    }
    // for (int i = 0; i < up; ++i) dbg(i, a[i]);

    dp[0] = 0;
    for (int mask = 1; mask < up; ++mask) {
        dp[mask] = inf;
        for (int i = 0; i < m; ++i) {
            if (mask & (1 << i)) {
                int tem = dp[mask ^ (1 << i)] + a[mask ^ (1 << i)];
                if (tem < dp[mask]) dp[mask] = tem, pre[mask] = i;
            }
        }
    }

    printf("%d\n", dp[up - 1] + n - num);
    for (int i = up - 1; i; i ^= 1 << pre[i]) printf("%d ", pre[i] + 1);
    puts("");
}

int main() {
    freopen("tests.in", "r", stdin);

    int _ = 1;
    scanf("%d", &_);

    while (_--) run();

    return 0;
}

G - Is Topo Logical?

solved by lllllan. (-)

题意： 已知有n个点，告诉你这n个点的度数，以及完成拓扑排序之后的度数，要求构造出一个符合度数的图。

题解： 按照拓扑排序的思路去建边。只是建边要分成两个部分，一部分是拓扑排序后的度数，一部分是初始度数减去拓扑后的度数，两部分需要分别建边，注意不能自环和重边。

  • 初始度数为零的才可以进入队列，然后一次对所有度数大于拓扑后度数的点进行建边。然后度数减到零又可以进入队列继续建边
  • 如果队列中零度的点都已经参与过建边，但是仍存在点的初始度数大于拓扑后的度数，则表示不可构造，输出-1.
  • 剩下的是对拓扑之后度数不为零的点进行内部建边，只要没有自环，和前面的前面不重复，随便构造即可。
AC代码 
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;
const int N = 2e5 + 10;

int n;

int pre[maxn];
int deg[maxn];

int st[maxn];
int ed[maxn];

set<pair<int, int> > s;

void run () {
	s.clear();
	
	scanf("%d", &n);
	
	queue<int> Q1, Q2, topo, zero;
	
	for (int i = 1; i <= n; ++i) {
		scanf("%d", pre + i);
		if (pre[i] == 0) zero.push(i);
	}
	
	for (int i = 1; i <= n; ++i) {
		scanf("%d", deg + i);
		if (deg[i]) {
			Q1.push(i);
			Q2.push(i);
		}
		if (pre[i] > deg[i]) topo.push(i);
	}
	
	int cnt = 0;
	while (topo.size()) {
		if (zero.empty())  return (void)( printf("-1\n") );
		int u = zero.front(); zero.pop();
		int sz = topo.size();
		while (sz--) {
			int v = topo.front(); topo.pop();
			cnt++;
			st[cnt] = u, ed[cnt] = v;
			s.insert({u, v});
			pre[v]--;
			if (pre[v] > deg[v]) topo.push(v);
			else if (pre[v] == 0) zero.push(v);
		}
	}
	
	while (Q2.size()) {
		if (Q1.empty()) return (void)( printf("-1\n") );
		int u = Q1.front(); Q1.pop();
		int sz = Q2.size();
		while (sz--) {
			int v = Q2.front(); Q2.pop();
			if (u == v || s.count({u, v})) {
				Q2.push(v);
				continue;
			}
			cnt++;
			st[cnt] = u, ed[cnt] = v;
			deg[v]--, pre[v]--;
			if (deg[v]) Q2.push(v);
		}
	}
	
	
	
	printf("%d\n", cnt);
	for (int i = 1; i <= cnt; ++i) {
		printf("%d %d\n", st[i], ed[i]);
	}
}

int main () {
	freopen("topo.in", "r", stdin);
	
	int _ = 1;
	scanf("%d", &_);
	while (_--) run();
}

H - Bugged System

solved by lllllan. 02:24(+)

题意： 想象一下高速上的收费机制，从某个站A上高速，你会获得一张卡片记录上高速的地点，再从某个站B下高速，收费将为A到B的距离。但是这样就会有一个机制bug，假设某人要从A到B，有另一个人要从B到A，如果这两个人在高速上交换卡片，最后将以零花费到达各自的目的地。
现在要你协助一个“犯罪团伙”，帮助所有人以零花费到达各自的目的地。

题解； 卡片是一个切入点，要想达到零花费，关键点是要拿到起点为A的卡片并在A点下高速。也就是说每张卡片从哪里来，就应该回那里去。对应到题目里，就应该是有多少人想到达A点，就需要有多少人从A点出发。
因此记录每个点的出度和入度，所有点的出度都与入度相同，才可能完成目标。最后移动的距离仅是各自从起点到达终点的距离和而已。

AC代码 
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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 10;
const int N = 2e5 + 10;

int n, m;

int st, ed;

ll x[maxn];

ll dis (int a, int b) { return abs(x[a] - x[b]); }

int deg[maxn];

void run () {
	
	scanf("%d%d", &n, &m);
	
	for (int i = 1; i <= n; ++i) {
		deg[i] = 0;
		scanf("%lld", x + i);
	}
	
	ll ans = 0;
	for (int i = 1; i <= m; ++i) {
		scanf("%d%d", &st, &ed);
		ans += dis(st, ed);
		deg[st]++, deg[ed]--;
	}
	
	for (int i = 1; i <= n; ++i) {
		if (deg[i]) return (void)( printf("-1\n") );
	}
	printf("%lld\n", ans);
}

int main () {
	freopen("bugged.in", "r", stdin);
	
	int _ = 1;
	scanf("%d", &_);
	while (_--) run();
}

I - Rise of the Robots

solved by Tryna. 02:40(+2)

题意： 有一个圆形机器人，还有一个圆桌，给出机器人运动的轨迹，确定一个起点，使机器人在圆桌上运动不掉落圆桌。

题解： 因为机器人是圆形的，圆桌也是圆形的，我们可以把机器人看作是一个点，将圆桌的半径缩小机器人的半径的长度。然后就是求这个运动轨迹都在圆内了。我们可以假设起点在原点，然后求出这些点的坐标。然后求一个最小的圆覆盖。最后将圆心平移到原点后的起点坐标就是答案了。

AC代码 
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const double eps = 1e-8;
const int maxn = 3e2;
int sgn(double x) {
	if(fabs(x) < eps) return 0;
	else return x < 0 ? -1 : 1;
}
int n;
double R,r;
struct Point{
	double x, y;
	Point(){}
	Point(double x, double y):x(x),y(y){}
	Point operator - (Point B) {
		return Point(x - B.x, y - B.y);
	}
	Point operator + (Point B) {
		return Point(x + B.x, y + B.y);
	}
	Point operator * (double k) {
		return Point(k * x, k * y); 
	}
	Point operator / (double k) {
		return Point(x / k, y / k); 
	}
	bool operator < (const Point &b) const {
		if(x == b.x) return y < b.y;
		return x < b.x;
	}
}P[maxn], ch[maxn];

double Distance(Point a, Point b) {
	return hypot(a.x - b.x, a.y - b.y);
}

Point circle_center(const Point a, const Point b, const Point c) {
	Point center;
	double a1 = b.x - a.x;
	double b1 = b.y - a.y;
	double c1 = (a1 * a1 + b1 * b1) / 2;
	double a2 = c.x - a.x;
	double b2 = c.y - a.y;
	double c2 = (a2 * a2 + b2 * b2) / 2;
	double d = a1 * b2 - a2 * b1;
	center.x = a.x + (c1 * b2 - c2 * b1) / d;
	center.y = a.y + (a1 * c2 - a2 * c1) / d;
	return center;
}

void min_cover_circle(Point *p, int n, Point &c, double &rr) {
	random_shuffle(p, p + n);
	c = p[0];
	rr = 0;
	for(int i = 1; i < n; i++) {
		if(sgn(Distance(p[i], c) - rr) > 0) {
			c = p[i]; rr = 0;
			for(int j = 0; j < i; j++) {
				if(sgn(Distance(p[j], c) - rr) > 0) {
					c.x = (p[i].x + p[j].x) / 2;
					c.y = (p[i].y + p[j].y) / 2;
					rr = Distance(p[j], c);
					for(int k = 0; k < j; k++) {
						if(sgn(Distance(p[k], c) - rr) > 0) {
							c = circle_center(p[i], p[j], p[k]);
							rr = Distance(p[i], c);
						}
					}
				}
			}
		}
	}
}

void run () {
	Point c;
	double rr;
	scanf("%d %lf %lf", &n, &R, &r);
	P[0] = Point(0, 0);
	for(int i = 1; i <= n; i++) {
		double x, y;
		scanf("%lf %lf", &x, &y);
		P[i].x = P[i - 1].x + x;
		P[i].y = P[i - 1].y + y;
	}
	n++;
	min_cover_circle(P, n, c, rr);
	c.x = -c.x;
	c.y = -c.y;
	if(sgn(c.x) == 0) c.x = 0;
	if(sgn(c.y) == 0) c.y = 0;
	printf("%.10f %.10f\n", c.x, c.y);
}

int main () {
	freopen("robots.in", "r", stdin);
	
	int _ = 1;
	scanf("%d", &_);
	while (_--) run();
}

K - Tourists’ Tour

solved by lllllan. (-)

题意： 有n个高度互不相同的塔，要求给所有的塔进行染色，使得某座塔，和他左边第一个比他高的塔，和他右边第一个比他高的塔，颜色都不相同。

题解：

  • 单调栈建边：因为只要和左右两边第一个比他高的塔颜色不同，考虑单调栈来咱窜前面的塔，然后对中间的塔，向两边第一个比他高的塔建有向边。
  • 拓扑排序，依次染色。给某座塔染色col，则对他链接的两座塔，都标记颜色col不可用即可。
AC代码 
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 10;

int n;

int h[maxn];
int sta[maxn];
int deg[maxn];
int col[maxn][4];
int ans[maxn];

int cnt, head[maxn];
struct edge { int v, next; } e[maxn << 1];
void add (int u, int v) { e[++cnt] = {v, head[u]}; head[u] = cnt; }

void init () {
	cnt = sta[0] = 0;
	for (int i = 1; i <= n; ++i) {
		deg[i] = head[i] = 0;
		for (int j = 1; j < 4; ++j) col[i][j] = 0;
	}
}

void run () {
		
	scanf("%d", &n);
	init();
	
	for (int i = 1; i <= n; ++i) scanf("%d", h + i);
	
	for (int i = 1; i <= n; ++i) {
		while (sta[0]) {
			int top = sta[ sta[0] ] ;
			if (h[i] < h[ top ]) {
				deg[i]++;
				add(top, i);
				sta[ ++sta[0] ] = i;
				break;
			} else {
				deg[ top ]++;
				add(i, sta[ sta[0]-- ]);
			}
		}
		if (sta[0] == 0) sta[ ++sta[0] ] = i;
	}
	
	queue<int> Q;
	for (int i = 1; i <= n; ++i) {
		if (deg[i] == 0) Q.push(i);
	}
	
	int maxx = 1;
	while (Q.size()) {
		int u = Q.front(); Q.pop();
		for (int i = 1; i < 4; ++i) {
			if (col[u][i] == 0) {
				ans[u] = i;
				if (i > maxx) maxx = i;
				break;
			}
		}
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			col[v][ ans[u] ] = 1;
			if (--deg[v] == 0) Q.push(v);
		}
	}
	
	printf("%d\n", maxx);
	for (int i = 1; i <= n; ++i) {
		printf("%d%c", ans[i], " \n"[i == n]);
	}
}

int main ()  {
	
	freopen("tour.in", "r", stdin);

	int _ = 1;
	scanf("%d", &_);
	
	while (_--) run();
	
	return 0;
}
文章目录
  1. A - Hello SCPC 2018!
  2. B - Binary Hamming
  3. C - Portals
  4. D - Carnival Slots
  5. F - Pretests
  6. G - Is Topo Logical?
  7. H - Bugged System
  8. I - Rise of the Robots
  9. K - Tourists’ Tour
|