Codeforces Round 920 Div 3

发表于 更新于 分类于

A - Square

直接记录最左最右、最上最下即可。

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
// Problem: A. Square
// Contest: Codeforces - Codeforces Round 920 (Div. 3)
// URL: https://codeforces.com/contest/1921/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: MaxDYF
// 
// 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;

void work()
{
	ll x, y;
	ll now1 = llinf, now2 = llinf, len1, len2;
	for (int i = 1; i <= 4; i++)
	{
		cin >> x >> y;
		if (now1 == llinf)
			now1 = x;
		else if (now1 != x)
			len1 = abs(now1 - x);
		if (now2 == llinf)
			now2 = y;
		else if (now2 != y)
			len2 = abs(now2 - y);	
	}
	cout << len1 * len2 <<endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B - Arranging Cats

先算需要转换多少个0/1使得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
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
// Problem: B. Arranging Cats
// Contest: Codeforces - Codeforces Round 920 (Div. 3)
// URL: https://codeforces.com/contest/1921/problem/B
// Memory Limit: 512 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 = 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[N], b[N];
void work()
{
	cin >> n;
	char ch;
	int cnt1 = 0, cnt2 = 0;
	for (int i = 1; i <= n; i++)
	{
		cin >> ch;
		a[i] = ch - '0';
		cnt1 += a[i];
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> ch;
		b[i] = ch - '0';
		cnt2 += b[i];
	}
	int dif1 = 0, dif2 = 0;
	for (int i = 1; i <= n; i++)
	{
		if (a[i] == 0 && b[i] == 1)
			dif1++;
		else if (a[i] == 1 && b[i] == 0)
			dif2++;
	}
	if (cnt1 < cnt2)
		dif1 = max(0, dif1 - (cnt2 - cnt1));
	else
		dif2 = max(0, dif2 - (cnt1 - cnt2));
	cout << (dif1 + dif2) / 2 + (abs(cnt1 - cnt2)) << endl;
	
			
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C - Sending Messages

简单dp。

设dp[i]表示发出第i条信息后的最小耗电量。容易发现，转移到下一个状态，只有两个状态：

  1. 发完上一条马上关机，下一次再开机；
  2. 发完上一条不关机。

即得方程： \[ dp[i] = dp[i - 1] + min(b, (t[i] - t[i - 1]) * a); \]

注意在0时手机就已经开机，初始代价为a而不是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
// Problem: C. Sending Messages
// Contest: Codeforces - Codeforces Round 920 (Div. 3)
// URL: https://codeforces.com/contest/1921/problem/C
// 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 = 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, f, a, b;
ll t[N];
ll dp[N];
void work()
{
	cin >> n >> f >> a >> b;
	for (int i = 1; i <= n; i++)
		cin >> t[i];
	sort(t + 1, t + n + 1);
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		dp[i] = dp[i - 1] + min(b, (t[i] - t[i - 1]) * a);
	}
	//cout <<  min(dp[n][0], dp[n][1]) << endl;
	cout << (f >= dp[n] ? "YES\n" : "NO\n");
}
int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

D - Very Different Array

本题没有严格证明（全靠乱搞

凭直觉可以发现，最优解的序列应当是令\(a\)升序，选中的\(b\)降序，二者构成\(X\)型或八字型的趋势。

又可以发现，对于这种趋势的数列对来说，中间的部分贡献较少，两边的贡献较大，因此可以得出一个一点都不严谨的结论：在选择b序列中的数时，我们总是选择较大的那一批和较小的那一批，舍弃掉中间的部分。

根据这个结论，可以搞出一个乱搞方法：

  1. 将a按从小到大排序，b按从大到小排序；
  2. 将b前n个数与a对应位置的差处理出前缀和s1；
  3. 将b后n个数与a末尾对应位置的差处理出前缀和s2；
  4. 然后直接计算s1[i]+s2[n-i+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
// Problem: D. Very Different Array
// Contest: Codeforces - Codeforces Round 920 (Div. 3)
// URL: https://codeforces.com/contest/1921/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 = 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 >> m;
	vector<ll> a(n + 1), b(m + 1);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= m; i++)
		cin >> b[i];
	auto calc = [&]()
	{
		vector<ll> s1(n + 1), s2(n + 1);
		for (int i = 1; i <= n; i++)
			s1[i] = s1[i - 1] + abs(a[i] - b[i]);
		for (int i = 1; i <= n; i++)
			s2[i] = s2[i - 1] + abs(a[n - i + 1] - b[m - i + 1]);
		ll ans = 0;
		for (int i = 0; i <= n; i++)
			ans = max(ans, abs(s1[i] + s2[n - i]));
		return ans;
	};
	sort(a.begin() + 1, a.end());
	sort(b.begin() + 1, b.end(), greater<int>());
	ll ans = calc();
	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 - Eat the Chip

可以发现，无论如何，每进行一步，两人的x坐标相对距离就-1。所以，只要判断x相对距离的奇偶性就能确定谁必定赢不了。

然后是确定不输的那方能否必胜。

先不讨论边界，若确定自己赢不了，这一方要做的显然是“逃离”另一方，不让它碰到自己。

而后手不输的情况下，两人行走步数相同，所以只有两人y坐标相等时才能必胜。

先手不输的情况下，先手比后手多走一步，所以两人y坐标相差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: E. Eat the Chip
// Contest: Codeforces - Codeforces Round 920 (Div. 3)
// URL: https://codeforces.com/contest/1921/problem/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Author: MaxDYF
// 
// 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;

void work()
{
	int n, m, x1, y1, x2, y2;
	cin >> n >> m >> x1 >> y1 >> x2 >> y2;
	int round = x2 - x1;
	if (round <= 0)
	{
		cout << "Draw\n";
		return;
	}
	int width = y1 - y2;
	if (round % 2 == 0) // Bob or Draw
	{
		if (width == 0)
			cout << "Bob\n";
		else
		{
			if (width > 0 && abs(width) <= round / 2 - (m - y1))
				cout << "Bob\n";
			else if (width < 0 && abs(width) <= round / 2 - (y1 - 1))
				cout << "Bob\n";
			else
				cout << "Draw\n";
		}
	}
	else // Alice or Draw
	{
		if (abs(width) <= 1)
			cout << "Alice\n";
		else
		{
			if (width < 0 && abs(width) <= round / 2 - (m - y2) + 1)
				cout << "Alice\n";
			else if (width > 0 && abs(width) <= round / 2 - (y2 - 1) + 1)
				cout << "Alice\n";
			else
				cout << "Draw\n";
		}
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

F - Sum of Progression

看数据范围\(n \leq 1e5\)，可以发现是经典的分块范围（大雾

将每个询问分为两种：

一种是步长d大于\(\sqrt n\)的，显然最多跳不超过\(\sqrt n\)次，直接暴力计算即可。

另一种是小于\(\sqrt n\)的，我们暴力预处理出来几个数组sum[i][step],f[i][step],stp[i][step]。

sum[i][step]:以i为结尾、最开头是st、step为步长的数列的前缀和，即a[st] + a[st + d] + ... + a[i]。

f[i][step]：以i为结尾、最开头是st、step为步长的数列，每个数乘上对应系数的和，即1 * a[st] + 2 * a[st + d] + ... + k * a[i]。

stp[i][step]：以i为结尾、最开头是st、step为步长的数列，a[i]对应的系数。

这些数组可以很容易的在\(\Theta(n\sqrt n)\)的时间内预处理完成。

然后，用这些数组，就可以在询问时用\(\Theta(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
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
// Problem: F. Sum of Progression
// Contest: Codeforces - Codeforces Round 920 (Div. 3)
// URL: https://codeforces.com/contest/1921/problem/F
// Memory Limit: 1024 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 = 1e5 + 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], f[N][400], sum[N][400], stp[N][400];

void work()
{
	cin >> n >> q;
	int lim = sqrt(n);
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= lim; j++)
		{
			if (i - j < 1)
			{
				stp[i][j] = 1;
				sum[i][j] = f[i][j] = a[i];
				continue;
			}
			sum[i][j] = sum[i - j][j] + a[i];
			stp[i][j] = stp[i - j][j] + 1;
			f[i][j] = f[i - j][j] + stp[i][j] * a[i];
		}
	}
	int s, d, k;
	for (int i = 1; i <= q; i++)
	{
		cin >> s >> d >> k;
		if (d > lim)
		{
			ll ans = 0;
			for (ll p = s, j = 1; j <= k; j++, p += d)
				ans += j * a[p];
			cout << ans << ' ';
		} 
		else
		{
			int st = s, ed = s + d * (k - 1);
			ll part1 = (f[ed][d] - (st > d ? f[st - d][d] : 0ll));
			ll part2 = (sum[ed][d] - (st > d ? sum[st - d][d] : 0ll)) * (stp[st][d] - 1ll);
			cout << part1 - part2 << ' ';
		}
	}
	bool DEBUG = false;
	if (DEBUG)
	{
		cout << "f  ";
		for (int i = 0; i <= n; i++)
			cout << i << ' ';
		cout << endl;
		for (int i = 0; i <= n; i++)
		{
			cout << i << "| ";
			for (int j = 0; j <= n; j++)
				cout << f[i][j] << ' ';
			cout << endl;
		}		
		cout << "stp";
		for (int i = 0; i <= n; i++)
			cout << i << ' ';
		cout << endl;
		for (int i = 0; i <= n; i++)
		{
			cout << i << "| ";
			for (int j = 0; j <= n; j++)
				cout << stp[i][j] << ' ';
			cout << endl;
		}		
	}
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

G - Mischievous Shooter

可以发现，本题相当于求一个特定图形内的1的个数的最大值，因此考虑前缀和维护。

四种不同的图形可以通过旋转矩阵合并为一种讨论，在这里以原点在左上角讨论。

我们维护4个前缀和：

  1. sum_col[i][j]：列前缀和，a[1][j] + a[2][j] + ... + a[i][j]。
  2. sum_row[i][j]：行前缀和
  3. sum_diag[i][j]：副对角前缀和，即a[i][j] + a[i-1][j+1] + a[i-2][j+2]...
  4. sum_f[i][j]：以左上角为原点的霰弹图形内的个数。

通过纸上模拟可以很容易得出从[i-1][j]和从[i][j-1]的两种递推公式。然后可以暴力求解sum_f[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
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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
// Problem: G. Mischievous Shooter
// Contest: Codeforces - Codeforces Round 920 (Div. 3)
// URL: https://codeforces.com/contest/1921/problem/G
// 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 = 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;
template <typename T>
class Matrix {
public:
    Matrix(size_t rows, size_t cols, const T& initial_value = T())
        : rows_(rows), cols_(cols), data_(rows, std::vector<T>(cols, initial_value)) {}


    // 重载()运算符用于访问行列列
    T& operator()(size_t row, size_t col) {
        if (row < 0 || row >= rows_ || col < 0 || col >= cols_) {
            //std::cerr << "Error: Index out of bounds\n";
            // 返回一个默认值
            static T default_value = 0;
            return default_value;
        }
        return data_[row][col];
    }

    // 用于获取行数和列数的函数
    size_t rows() const {
        return rows_;
    }

    size_t cols() const {
        return cols_;
    }

private:
    size_t rows_;
    size_t cols_;
    std::vector<std::vector<T>> data_;
};
void work()
{
	cin >> n >> m >> k;
	Matrix<int> a(n + 1, m + 1, 0);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			char ch;
			cin >> ch;
			if (ch == '#')
				a(i, j) = 1;
		}
	#define __DEBUG__ false
	auto autodbg = [&](Matrix<int> a, string msg)
	{
		if (__DEBUG__)
		{
			cout << msg << endl;
			for (int i = 1; i < (int)a.rows(); i++)
				for (int j = 1; j < (int)a.cols(); j++)
					cout << a(i, j) << (j == m ? "\n" : " ");
			cout << endl;
		}		
	};

	auto calc = [&]()
	{
		Matrix<int> sum_diag(n + 1, m + 1, 0),
				    sum_row(n + 1, m + 1, 0),
				    sum_col(n + 1, m + 1, 0), 
				    sum_f(n + 1, m + 1, 0);
		// Process sum
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				sum_row(i, j) = sum_row(i - 1, j) + a(i, j);
				sum_col(i, j) = sum_col(i, j - 1) + a(i, j);
			}
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				sum_diag(i, j) = sum_diag(i - 1, j + 1) + a(i, j);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
			{
				if ((i - 1) + (j - 1) <= k)
					sum_f(1, 1) += a(i, j);
				else
					break;
			}
		for (int i = 2; i <= n; i++)
		{
			int x = i + k, y = 1;
			if (x > n)
			{
				y += x - n;
				x = n;
			}
			sum_f(i, 1) = sum_f(i - 1, 1) - 
						  sum_col(i - 1, min(m, k + 1)) + 
						  (sum_diag(x, y) - sum_diag(i - 1, k + 2));
			
		}
		for (int i = 1; i <= n; i++)
			for (int j = 2; j <= m; j++)
			{
				int x = i + k, y = j;
				if (x > n)
				{
					y += x - n;
					x = n;
				}
				sum_f(i, j) = sum_f(i, j - 1) - 
							  (sum_row(min(n, i + k), j - 1) - sum_row(i - 1, j - 1)) +
							  (sum_diag(x, y) - sum_diag(i - 1, j + k + 1));
				
			}
		int ans = 0;
		for (int i = 1; i <= n; i++) 
			for (int j = 1; j <= m; j++)
				ans = max(ans, sum_f(i, j));
		autodbg(a, "This is A");
		autodbg(sum_f, "This is SUM_F");
		autodbg(sum_row, "This is SUM_ROW");
		autodbg(sum_col, "This is SUM_COL");
		autodbg(sum_diag, "This is SUM_DIAG");
		return ans;
				
				
	};
	auto turn = [&]()
	{
		Matrix<int> b(m + 1, n + 1, 0);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				b(j, i) = a(i, m - j + 1);
		swap(n, m);
		swap(a, b);
	};
	int ans = 0;
	for (int i = 1; i <= 4; i++)
	{
		ans = max(ans, calc());
		turn();
	}
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}