Codeforces Round 917 (Div. 2)

发表于 更新于 分类于

A题

A - Least Product

没有0的情况下，更改数字不改变正负性。若是正数，就将其归零；若是负数，则不做处理。注意特判原数有0的情况。

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
//#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;

void work()
{
	cin >> n;
	ll maxn = 0;
	bool rev = 0, suc = 0;
	for (int i = 1, x; i <= n; i++)
	{
		cin >> x;
		if (x < 0)
			rev = !rev;
		else if (x == 0)
		{
			suc = 1;
		}
	}
	if (suc == 1)
	{
		cout << 0 << endl;
		return;
	}
	if (rev)
	{
		cout << 0 << endl;
	}
	else
	{
		cout << "1\n1 0\n";
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B - Erase First or Second Letter

注意到只删第1、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
//#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;

void work()
{
	cin >> n;
	string s;
	cin >> s;
	s = ' ' + s;
	ll sum = 0, lst = 0;
	vector<int> but(26);
	for (int i = 1; i <= n; i++)
	{
		if (!but[s[i] - 'a'])
			lst++;
		sum += lst;
		but[s[i] - 'a']++;
	}
	cout << sum << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C - Watering an Array

显然，对于纯0数列，由于只加前缀，只会创造出一个递减的序列，意味着无论加多少次，答案贡献最多为1。所以，最优操作是每加一次立即清零计算贡献。总贡献即\(\lfloor\frac{总轮数}{2}\rfloor\)。

对于不为0的部分，显然，加的次数不可能超过\(2\times n\)次，直接模拟即可，复杂度\(\Theta(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
//#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;

ll n, m, k, q;
ll d;
int a[N], v[N];
void work()
{
	cin >> n >> k >> d;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= k; i++)
		cin >> v[i];
	ll origin_cnt = 0;
	for (int i = 1; i <= n; i++)
		origin_cnt += a[i] == i;
	ll ans = ((d - 1ll) / 2ll) + origin_cnt;
	for (ll i = 1; i <= min(max(2ll * n, 2ll * k), d - 1); i++)
	{
		int id = (i + k - 1) % k + 1;
		for (int i = 1; i <= v[id]; i++)
			a[i]++;
		ll cnt = 0;
		for (int i = 1; i <= n; i++)
			if (a[i] == i)
				cnt++;
		ans = max(ans, cnt + (d - i - 1ll) / 2ll);
	}
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

E - Construct Matrix

可以分为几种可能进行讨论。

一、\(k\ mod\ 2 = 1\)

显然无解。

二、\(k\ mod\ 4 = 0\)

显然，只需要用\[2\times 2\]的单元块填充整个区域即可。

三、\(k\ mod\ 4 = 2 且6\leq k \leq n \times n -10\)

考虑这样摆放：

1
2
3
4
OO..
O.O.
.OO.
....

O代表填充为1，显然，这样满足题目条件。在剩下的地方填充\(2\times2\)单元块即可。

四、\(k=n\times n-6\)

考虑继续塞满上面那个模型：

1
2
3
4
OO..
O.O.
OOOO
O..O

这样同样满足要求，其他地方填充\(2\times 2\)即可。

五、 特判\(n=2且k=2\)

这种情况下，不符合上述情况，但显然有

1
2
O.
.O

满足需求，特判即可。

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
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 1001;
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[N][N];
int switcher(int n, int k)
{
	if (k != 0 && (n * n < k))
		return 0;
	else if (k % 4 == 0)
		return 3;
	else if (k % 4 == 2 && 6 <= k && k <= n * n - 10)
		return 4;
	else if (k == n * n - 6)
		return 5;
	else if (n == 2 && k == 2)
		return 2;
	else 
		return 0;
}
void work()
{
	cin >> n >> k;
	int condition = switcher(n, k);
	switch (condition)
	{
		case 0:
		{
			cout << "No\n";
			break;
		}
		case 2:
		{
			a[1][1] = a[2][2] = 1;
			a[1][2] = a[2][1] = 0;
			cout << "Yes\n";
			break;
		}
		case 3:
		{
			memset(a, 0, sizeof a);
			cout << "Yes\n";
			for (int i = 1; i <= n && k; i += 2)
				for (int j = 1; j <= n && k; j += 2)
				{
					a[i][j] = a[i + 1][j] = a[i][j + 1] = a[i + 1][j + 1] = 1;
					k -= 4;
				}
			break;
		}
		case 4:
		{
			memset(a, 0, sizeof a);
			k -= 6;
			for (int i = 1; i <= n && k; i += 2)
				for (int j = 1; j <= n && k; j += 2)
				{
					if (i <= 3 && j <= 3)
						continue;
					a[i][j] = a[i + 1][j] = a[i][j + 1] = a[i + 1][j + 1] = 1;
					k -= 4;
				}
			a[1][1] = a[1][2] = a[2][1] = 1;
			a[3][2] = a[2][3] = a[3][3] = 1;
			cout << "Yes\n";
			break;
		}
		case 5:
		{
			memset(a, 0, sizeof a);
			k -= 10;
			for (int i = 1; i <= n && k; i += 2)
				for (int j = 1; j <= n && k; j += 2)
				{
					if (i <= 3 && j <= 3)
						continue;
					a[i][j] = a[i + 1][j] = a[i][j + 1] = a[i + 1][j + 1] = 1;
					k -= 4;
				}
			a[1][1] = a[1][2] = a[2][1] = 1;
			a[3][2] = a[2][3] = a[3][3] = 1;
			a[4][4] = a[3][4] = a[3][1] = a[4][1] = 1;
			cout << "Yes\n";
			break;
		}
	}
	if (!condition)
		return;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			cout << a[i][j] << " \n"[j == n];
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}