Codeforces Round 948 Div 2

发表于 更新于 分类于

题外话

鸽了好久，忙学校的一堆b课和b考试，打了CF也没写题解。打场div2复健一下。

完成情况

A B C D E
赛时 YES YES YES NO NO
补题 YES NO

A. Little Nikita

直觉法可得能凑成的充要条件是\((n>m) \land (n\equiv m \mod 2)\)。

B. Binary Colouring

考虑对于二进制下一段连续的1，设第一位为\(i\)位，最后一位为\(j\)位，给\(j+1\)设为1，再给\(i\)设为-1。

可以发现两个特殊情况会出现两个连续的非0，一是两段连续的1只有一个0隔开。设低位的连续段位\([i, p]\)，高位的为\([p+2, j]\)。我们要将\(p+1\)位置为1，\(p+2\)位置为-1，那么显然可以替换成将\(p+1\)位置为-1。

二是单独一个1的连续段。这种情况下直接将\(i\)置为1，然后考虑用上面类似的策略和低位的1进行等效替换即可。

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
// Problem: B. Binary Colouring
// Contest: Codeforces - Codeforces Round 948 (Div. 2)
// URL: https://codeforces.com/contest/1977/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
 
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);
 
#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;
 
int n, m, k, q;
int a[40];
void work()
{
	int x;
	cin >> x;
	int n = 0;
	memset(a, 0, sizeof a);
	for (int i = 0; i < 32; i++)
	{
		if (((x >> i) & 1) == 0)
			continue;
		int j = i;
		while ((x >> j) & 1)
			j++;
		if (i + 1 == j)
		{
			if (i != 0 && a[i - 1] != 0)
			{
				a[j] = 1;
				a[i - 1] = -1;
				n = j + 1;
				continue;
			}
			a[i] = 1;
			n = i + 1;
			continue;
		}
		a[j] = 1;
		if (a[i - 1] == 0)
			a[i] = -1;
		else
			a[i - 1] = -1;
		i = j;
		n = j + 1;
	}
	cout << n << '\n';
	for (int i = 0; i < n; i++)
		cout << a[i] << " \n"[i == n - 1];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C. Nikita and LCM

手玩数据可以发现，当序列所有数的\(lcm\)比最大的数还要大时，显然答案一定为n。反之，\(lcm\)就一定等于最大的那个数。同时，\(a\)中所有的数一定都是\(a_n\)的因子，能凑出来的\(lcm\)也一定是\(a_n\)的因子。

排序后，我们暴力枚举\(a_n\)的因子\(d\)，判断它有没有在\(a\)中出现后让它作为最终答案的目标\(lcm\)，然后枚举\(a_i\)看它是不是\(d\)的因子，有就合并\(lcm'\)。然后检查\(lcm'\)是否等于\(d\)，等于的话就直接更新答案。复杂度\(O(n^2)\)。

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
// Problem: C. Nikita and LCM
// Contest: Codeforces - Codeforces Round 948 (Div. 2)
// URL: https://codeforces.com/contest/1977/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
ll a[N];
void work()
{
	cin >> n;
	ll sum = 1;
	map<ll, int> s;
	bool ok = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		s[a[i]]++;
		sum = sum * a[i] / __gcd(sum, a[i]);
		if (sum > (ll)(1e9))
			ok = 1;
	}
	sort(a + 1, a + n + 1);
	if (sum != a[n] || ok)
	{
		cout << n << '\n';
		return;
	}
	vector<ll> vec;
	for (int i = 1; i * i <= sum; i++)
	{
		if (sum % i == 0)
		{
			vec.push_back(i);
			if (i * i != sum)
				vec.push_back(sum / i);
		}
	}
	int ans = 0;
	for (auto maxn : vec)
	{
		if (s[maxn] != 0)
			continue;
		ll s1 = 1;
		int cnt = 0;
		for (int i = 1; i <= n; i++)
		{
			if (__gcd(a[i], maxn) == a[i])
				cnt++, s1 = (ll)s1 * a[i] / __gcd(a[i], s1);
		}
		if (s1 == maxn)
			ans = max(ans, cnt);
	}
	cout << ans << '\n';
	
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

D. XORificator

可以发现一个性质：当我们指定了对于第\(j\)列对答案有贡献，且第\(i\)行的数字为1时，此时的构造方案唯一确定也就是说，最多只有\(n\times m\)种不同的有效方案可以选择。

考虑枚举令\([i,j]\)上的数字为此列唯一的1，\(\text{Hash}\)算出此时的具体方案，然后全部扔进一个map里，最后选取出现次数最多的那个方案。时间复杂度\(\Theta(nmlog_2(nm))\)，用unordered_map能降到\(\Theta(nm)\)​。

注意本题卡单哈希，算方案时记得用双哈希。

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
// Problem: D. XORificator
// Contest: Codeforces - Codeforces Round 948 (Div. 2)
// URL: https://codeforces.com/contest/1977/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// Author: MaxDYF
//
// Powered by CP Editor (https://cpeditor.org)

// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x & -x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
uint64_t pw1[N], pw2[N];
const uint64_t mod1 = 1000000007ULL;
const uint64_t mod2 = 1000000009ULL;
struct myHash
{
    uint64_t hash1, hash2;
    myHash()
    {
        hash1 = hash2 = 0;
    }
};
myHash changePos(myHash hash, int pos, bool originVal, bool newVal)
{
    if (originVal)
    {
        hash.hash1 = (hash.hash1 - pw1[pos] + mod1) % mod1;
        hash.hash2 = (hash.hash2 - pw2[pos] + mod2) % mod2;
    }
    if (newVal)
    {
        hash.hash1 = (hash.hash1 + pw1[pos]) % mod1;
        hash.hash2 = (hash.hash2 + pw2[pos]) % mod2;
    }
    return hash;
}
uint64_t toNormal(myHash hash)
{
    uint64_t h1 = hash.hash1, h2 = hash.hash2;
    return (h1 << 31ULL) | h2;
}

void work()
{
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < m; j++)
            a[i][j] = s[j] - '0';
    }
    unordered_map<uint64_t, int> s;
    int ans = 0;
    string ans_str;
    for (int j = 0; j < m; j++)
    {
        myHash hsh;
        string str;
        for (int i = 0; i < n; i++)
        {
            hsh = changePos(hsh, i, 0, a[i][j]);
            str.push_back(a[i][j] + '0');
        }
        for (int i = 0; i < n; i++)
        {
            if (i != 0)
            {
                hsh = changePos(hsh, i - 1, !a[i - 1][j], a[i - 1][j]);
                str[i - 1] = '0' + (char)(str[i - 1] == '0');
            }
            hsh = changePos(hsh, i, a[i][j], !a[i][j]);
            str[i] = '0' + (char)(str[i] == '0');
            int p = ++s[toNormal(hsh)];
            if (p > ans)
            {
                ans = p;
                ans_str = str;
            }
            // cout << hsh.hash1 << ' ' << hsh.hash2 << '\n';
        }
    }
    cout << ans << '\n' << ans_str << '\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    pw1[0] = pw2[0] = 1;
    for (int i = 1; i < N; i++)
    {
        pw1[i] = (pw1[i - 1] * 2ULL) % mod1;
        pw2[i] = (pw2[i - 1] * 2ULL) % mod2;
    }
    int t;
    cin >> t;
    while (t-- > 0)
    {
        work();
    }
}