CS academy Round 66

Chong Wang Lv6
  2018-02-21 17:09:25 2018-02-21 17:09:25 Created   2026-10-09 08:58:53 2026-10-09 08:58:53 Updated

Second set for the holidays. . .

Question link, A, B, and C are all bad.

D Flipping Matrix

The meaning of the question is to give a 01 grid of $N*N$, in which any two rows and any two columns can be exchanged. Ask whether it is possible to form a rectangle with all diagonals equal to 1. and provide an exchange plan.

Just consider swapping any two rows here. There was a problem on Zhihu before that was to determine whether there are $N$ $1$ such that they are in different rows and different columns of the matrix. Question link

If val[i][j]=1, build an edge from i to j. Finally, run bipartite graph matching. Record the final match.

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
int n;
int vis[maxn];
bool mat[maxn][maxn];
int left_match[maxn],right_match[maxn];

int findmatch(int x)
{
    if(vis[x])
    {
        return false;
    }
    vis[x] = true;
    for(int i=1;i<=n;i++)
    {
        if(mat[x][i] && left_match[i] == 0)
        {
            right_match[x] = i;
            left_match[i] = x;
            return true;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(mat[x][i] && findmatch(left_match[i]))
        {
            right_match[x] = i;
            left_match[i] = x;
            return true;
        }
    }
    return false;
}
map<pair<int,int>,int>hax;
void solve()
{
    sa(n);
    repp(i,1,n)
    {
        repp(j,1,n)
        {
            sa(mat[i][j]);
        }
    }
    memset(left_match,0,sizeof(left_match));
    memset(right_match,0,sizeof(right_match));

    bool flag = true;
    do{
        flag = false;
        for(int i=1;i<=n;i++)
        {
            vis[i] = 0;
        }
        for(int i=1;i<=n;i++)
        {
            if(right_match[i]==0 && findmatch(i))
            {
                flag = true;
            }
        }
    }while(flag);
    int k = 0;
    repp(i,1,n)
    {
        k += right_match[i] != 0;
    }
    if(k != n)
    {
        puts("-1");
        return;
    }
    repp(i,1,n)
    {
        vis[i] = i;
    }
    repp(i,1,n)
    {
        if(right_match[i]==vis[i])continue;
        int j = 1;
        for(;j<=n;j++)
        {
            if(vis[j]==right_match[i])
            {
                break;
            }
        }
        cout<< "R "<<vis[j]<<" "<<vis[i]<<endl;
        int t = vis[j];
        vis[j] = vis[i];
        vis[i] = t;
    }
}

E Domino Train

The meaning of the question is that $N$ dominoes are given, which is the logarithm of $N$. Then you have to perform N-1 steps of operation, each operation handles the front and back positions of the two dominoes, and ultimately makes the adjacent dominoes have the same number at most.

I have been thinking about this topic for a long time. . . In fact, just run the Euler circuit. . .

For each domino $(A_i,B_i)$, establish an edge from A_i to B_i, and then process each connected block as a unit. For multiple points with odd degrees, connect an edge, and then run the Euler loop from the point with odd degrees as the starting point. . .

Record the final position of each point, use it and find the solution to be processed.

It seems that everything is not difficult starting from the answer, but how to get it done is really difficult. . .

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
int n;
map<int, int>edge[maxn];

struct f
{
	int fa[maxn];
	int getfa(int x)
	{
		if (x == fa[x])return x;
		else
		{
			fa[x] = getfa(fa[x]);
			return fa[x];
		}
	}
}A, L, R;

int deg[maxn];
int flag[maxn], ans[maxn], pos[maxn];
vector<int>nums[maxn];
vector<int>path;

void dfs(int x)
{
	while (edge[x].size())
	{
		int id = edge[x].begin()->first;
		int to = edge[x].begin()->second;
		edge[x].erase(id);
		edge[to].erase(-id);
		dfs(to);
		path.push_back(id);
	}
}

void solve()
{
	sa(n);
	repp(i, 1, n)
	{
		A.fa[i] = i;
	}
	repp(i, 1, n)
	{
		int x, y;
		sa(x), sa(y);
		edge[x][i] = y;
		edge[y][-i] = x;
		deg[x] ++;
		deg[y] ++;
		A.fa[A.getfa(x)] = A.getfa(y);
	}
	repp(i, 1, n)
	{
		nums[A.getfa(i)].push_back(i);
	}
	int cnt = 0;
	int m = n;
	repp(i, 1, n)
	{
		if (nums[i].size() == 0)continue;
		vector<int>odd;
		rep(k, 0, nums[i].size()) {
			if (deg[nums[i][k]] % 2) {
				odd.push_back(nums[i][k]);
			}
		}
		while (odd.size()>2)
		{
			int k1 = odd.back(); odd.pop_back();
			int k2 = odd.back(); odd.pop_back();
			m++;
			edge[k1][m] = k2;
			edge[k2][-m] = k1;
		}
		int start = i;
		if (odd.size())start = odd[0];
		dfs(start);
		while (path.size() != 0)
		{
			int id = path.back();
			path.pop_back();
			if (abs(id) <= n)
			{
				if (id<0)
				{
					flag[abs(id)] = 1;
				}
				ans[++cnt] = abs(id);
			}
		}
	}
	repp(i, 1, n)
	{
		L.fa[i] = i;
		R.fa[i] = i;
		pos[ans[i]] = i;
	}
	repp(i, 1, n - 1)
	{
		int x;
		sa(x);
		x = pos[x];
		x = L.getfa(x);
		if (x == 1)
		{
			int y = R.getfa(x) + 1;
			printf("%d %d\n", ans[x], ans[y]);
			R.fa[R.getfa(x)] = y;
			L.fa[L.getfa(y)] = x;
		}
		else
		{
			int y = L.getfa(x - 1);
			printf("%d %d\n", ans[y], ans[x]);
			R.fa[R.getfa(y)] = x;
			L.fa[L.getfa(x)] = y;
		}
	}
	repp(i, 1, n)
	{
		if (i>1)printf(" ");
		printf("%d", flag[i]);
	}
}

On this page
CS academy Round 66
  1. D Flipping Matrix
  2. E Domino Train