Codeforces Round 919 Div 2

发表于 更新于 分类于

A - Satisfying Constraints

每次动态更新上下界，最后二分判断一下界内的被删除数字即可。

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
//#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 l = 0, r = 1e10, x;
	vector<int> vec;
	for (int i = 1, op; i <= n; i++)
	{
		cin >> op >> x;
		switch (op)
		{
			case 1:
			{
				l = max(x, l);
				break;
			}
			case 2:
			{
				r = min(x, r);
				break;
			}
			case 3:
			{
				vec.push_back(x);
				break;
			}
		}
	}
	if (l > r)
	{
		cout << 0 << endl;
		return;
	}
	sort(vec.begin(), vec.end());
	unique(vec.begin(), vec.end());
	auto it1 = lower_bound(vec.begin(), vec.end(), l);
	auto it2 = --upper_bound(vec.begin(), vec.end(), r);
	if (it2 - it1 < 0 || (*it1) < l || (*it2) > r)
	{
		cout << r - l + 1 << endl;
	}
	else
	{
		cout << r - l + 1ll - (ll)(it2 - it1 + 1) << endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B - Summation Game

对后手而言，显然把最大的\(x\)个数取反了是最优的。所以作为先手，我们枚举去掉最大的\(1\dots k\)个数，最终结果是多少，排序+前缀和即可，注意判断边界。

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
//#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 a[N];
void work()
{
	int n, k, x;
	cin >> n >> k >> x;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1);
	ll val = -1e10;
	for (int i = 2; i <= n; i++)
		a[i] += a[i - 1];
	if (n == k)
		val = 0;
	for (int i = 0; i <= k; i++)
	{
		if (n - i < 0)
			break;
		val = max(val, 2ll * a[max(0, n - i - x)] - a[n - i]);
	}
	cout << val << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

C - Partitioning the Array

题意可知，对于每个整除n的\(k\)，每一个下标组 \[ \begin{gather} \{1,1+k,1+2k\dots 1+(\frac n k -1)k\}, \\\\ \{2,2+k,2+2k\dots 2+(\frac n k -1)k\}, \\\\ \dots \\\\ \{k,2k\dots n\} \end{gather} \] 组内的元素对某个数\(m\)同余。

观察题目可以发现，我们实际上并不关心\(m\)是多少，只需知道存不存在这样的\(m\)。

对于这样一个式子: \[ \begin{align} a \equiv b\pmod M \\\\ b \equiv c\pmod M \\\\ \end{align} \] 移项得： \[ \begin{align} a-b \equiv 0\pmod M \\\\ b-c \equiv 0\pmod M \\\\ \end{align} \] 等效于： \[ gcd(a -b,b-c) \not= 1 \]

可知，若一组数存在这样一个\(M\)，那么其相邻数的差的\(gcd\)一定不为1。

枚举每个\(k\)，然后将每组下标提取出来，判断即可。

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
//#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];
void work()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	auto calc = [&](int k)
	{
		int val = 0; // __gcd(0, val) = val
		for (int i = 1; i <= k; i++)
		{
			vector<int> b;
			for (int pos = i; pos <= n; pos += k)
				b.push_back(a[pos]);
			sort(b.begin(), b.end());
			for (int i = 1; i < b.size(); i++)
				val = __gcd(val, b[i] - b[i - 1]);
		}
		return val != 1;
	};
	int ans = 0;
	for (int k = 1; k * k <= n; k++)
		if (n % k == 0)
			ans += calc(k);
	for (int k = n; (n / k) * (n / k) < n; k--)
		if (n % k == 0)
			ans += calc(k);
	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

D - Array Repetition

查询的下标很大(1e18)，不可能构造出实际数列，考虑其他做法。

每次1操作只会在末尾加上一个新数字，说明有效数字较少，长度的增加主要来自于2操作的增倍。

先模拟生成数列的过程，记录下操作到当前步骤时的数列长度以及增加数字（操作1）或复制次数（操作2），按照数列长度排序。

若现在要查询下标\(pos\)，二分找到比\(pos\)大的最小长度对应的操作。

若是操作1，则增加的数字显然就是\(pos\)对应的数值。

若是操作2，设增倍后，长度变为\(X\)倍（题目中是复制\(x\)次，即有\(X=x+1\)），长度为\(L\)，则等效于在查找\((pos+ 1)\bmod X -1\)下标的数字。

容易发现，每经过这样一次取模操作，数据规模都减小至少一半，即单次复杂度小于\(log_{2}^2Q_i\)，总复杂度为\(\Theta(Qlog_2^2{(q_{max})})\)

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
//#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;
typedef pair<__int128, __int128> p128;
struct Node
{
	int opt;
	__int128 pos, x;
	Node(int a, __int128 b, __int128 c) : opt(a), pos(b), x(c) {}
	bool operator < (const Node b)
	{
		return pos < b.pos;
	}
};
int n, m, k, q;
int a[N], cnt;
vector<Node> vec;
map<__int128, int> f;
int search(__int128 pos)
{
	if (f.find(pos) != f.end())
		return f[pos];
	auto it = lower_bound(vec.begin(), vec.end(), Node(0, pos, 0));
	//cout << "TEST :  OPT = " << it->opt << ", POS = " << (ll)(it->pos) << endl; 
	if (it->opt == 1 && it->pos == pos)
		return a[it->x];
	__int128 new_pos = (__int128)((pos - 1) % it->x + 1ll);
	return f[pos] = search(new_pos);
}
void work()
{
	cin >> n >> k;
	__int128 len = 0;
	vec.clear();
	f.clear();
	for (int i = 1, opt; i <= n; i++)
	{
		ll x;
		cin >> opt >> x;
		if (len > (__int128)(1e18))
			continue;
		if (opt == 1)
		{
			len++;
			vec.push_back(Node(opt, len, ++cnt));
			a[cnt] = x;
		}
		else
		{
			__int128 bk = len;
			len *= (x + 1ll);
			vec.push_back(Node(opt, len, bk));
		}
		
		//cout << (ll)(len) << endl;
	}
	ll x;
	for (int i = 1; i <= k; i++)
	{
		cin >> x;
		cout << search(x) << ' ' << flush;
			
	}
	cout << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

E - Counting Binary Strings

考虑dp。

设计状态dp[i][j]表示在有\(i\)个仅含1个1的子串、最后一个1前有\(j\)个0、以1结尾的字符串个数。

状态确定后，大致的转移方程也可以很快写出来： \[ dp[i][j] = \sum{dp[i-cnt][k]} \\ \] 其中，cnt表示从上一个状态转移到下一个状态后，增加了多少个符合要求的子串。

接下来考虑如何计算cnt以及判断边界。

考虑这样的串： \[ \underbrace{0,0\dots 0}_{k个0},1 \] 当在后面加上\(j\)个0、1个1后： \[ \underbrace{0,0 \dots 0}_{k个0},1,\underbrace{0,0 \dots 0}_{j个0},1 \] 增加的满足要求子串分为四部分：

一部分是前面的1到后面的0构成的子串，有\(j\)个；

第二部分是前面的\(k\)个0到后面的\(j\)个0构成的子串，有\(j*k\)个；

第三部分是后面\(j\)个0与后面的1构成的子串，有\(j\)个；

最后一部分是增加的1本身，有1个。

所以， \[ \begin{align} cnt & =j+j+j*k+1 \\\\ & =j*(k+2)+1 \\\\ \end{align} \]

然后考虑边界条件。

最大长度不能超过\(lim\)（即输入中的k），所以有 \[ j+k+1 \leq lim \] 增加的子串数量显然不能超过当前状态的子串数量，有 \[ cnt\leq i \] 这样就完成了主要部分的转移方程。

但是，可以发现，开头部分的转移并没有1在最前面，因此需要特判；结尾部分也要处理结尾不为0的部分，统计答案的时候也要单独处理，详细的可以看代码理解。

时间复杂度不会分析，反正是\(\Theta(能过)\)。

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
//#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, lim;
ll f[2510][2510];
const ll mod = 998244353ll;
void work()
{
	cin >> n >> lim;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			f[i][j] = 0;
	for (int j = 0; j <= n; j++) // j个0在开头
	{
		if (j + 1 > lim)
			break;
		f[j + 1][j] = 1;
	}
	for (int i = 1; i <= n + 1; i++)
	{
		for (int j = 0; j < lim; j++)
		{
			if (j > i)
				break;
			for (int k = 0; k <= i; k++)
			{
				if (j + k + 1 > lim)
					break;
				int cnt = j * k + 2 * j + 1;
				if (i < cnt)
					break;
				f[i][j] =  (f[i][j] + f[i - cnt][k]) % mod;
			}
		}
	}
	bool DEBUG = false;
	if (DEBUG)
	{
		cout << "   ";
		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;
		}		
	}
	ll ans = 0;
	for (int j = 0; j <= n; j++) // 添加j个0在末尾
	{
		for (int k = 0; k <= n; k++)
		{
			int cnt = j * k + j;
			if (j + k + 1 > lim)
				break;
			if (n <= cnt)
				break;
			ans = (ans + f[n - cnt][k]) % mod;
			if (DEBUG && f[n - cnt][k] != 0)
				cout << j << ' ' << k  << ' ' << n - cnt << ' ' << f[n - cnt][k] << endl;
		}
	}

	cout << ans << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

F1 - Smooth Sailing (Easy Version)

要求求路径到火山最小距离的最大值，似乎可以二分？

于是考虑二分到火山距离的最小值\(x\)。然后，我们直接从\((x,y)\)出发，暴力\(\text{BFS}\)把所有离火山距离$ x\(的**四联通**点全部染上，点到火山的距离可以用类似\)\(的做法在\)n2\(的时间内预处理出来。然后，再暴力从火山出发**八联通扩展**，看能否从火山扩展到边界。这样就能够非常暴力地完成这题。时间复杂度\)(qn2log_2n)$，显然能通过此题。

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
// Problem: F1. Smooth Sailing (Easy Version)
// Contest: Codeforces - Codeforces Round 919 (Div. 2)
// URL: https://codeforces.com/contest/1920/problem/F1
// Memory Limit: 1024 MB
// Time Limit: 5000 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 >> q;
	vector< vector<int> > a(n + 2, vector<int>(m + 2));
	char ch;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			cin >> ch;
			switch (ch)
			{
				case '.':
					a[i][j] = 0;
					break;
				case '#':
					a[i][j] = 1;
					break;
				case 'v':
					a[i][j] = 2;
					break;
			}
		}
	vector< vector<int> > f(n + 2, vector<int>(m + 2, inf));
	// 离(i,j)最近的火山距离
	auto process = [&]()
	{
		#define min(x,y,z) min(x, min(y, z))
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (a[i][j] == 2)
					f[i][j] = 0;
				else
					f[i][j] = min(f[i][j], f[i - 1][j] + 1, f[i][j - 1] + 1);
		for (int i = n; i >= 1; i--)
			for (int j = 1; j <= m; j++)
				if (a[i][j] == 2)
					f[i][j] = 0;
				else
					f[i][j] = min(f[i][j], f[i + 1][j] + 1, f[i][j - 1] + 1);
		for (int i = 1; i <= n; i++)
			for (int j = m; j >= 1; j--)
				if (a[i][j] == 2)
					f[i][j] = 0;
				else
					f[i][j] = min(f[i][j], f[i - 1][j] + 1, f[i][j + 1] + 1);
		for (int i = n; i >= 1; i--)
			for (int j = m; j >= 1; j--)
				if (a[i][j] == 2)
					f[i][j] = 0;
				else
					f[i][j] = min(f[i][j], f[i + 1][j] + 1, f[i][j + 1] + 1);	
	};
	process();
	process();
	#define __DEBUG__  false
 
	auto check = [&](int lim, pii pos)
	{
		vector< vector<int> > b(n + 2, vector<int>(m + 2, 0));
		queue<pii> q1;
		q1.push(pos);
		const pii dir[] = {make_pair(-1, 0), make_pair(1, 0), 
						   make_pair(0, -1), make_pair(0, 1)};
						   	
		b[pos.first][pos.second] = 1;
		while (!q1.empty())
		{
			auto [x, y] = q1.front();
			q1.pop();
			for (auto [dx, dy] : dir)
			{
				if (x + dx < 1 || x + dx > n || y + dy < 1 || y + dy > m)
					continue;
				if (f[x + dx][y + dy] >= lim && !b[x + dx][y + dy] && a[x + dx][y + dy] == 0)
				{
					b[x + dx][y + dy] = 1;
					q1.push({x + dx, y + dy});
				}
			}
		}
			
		if (__DEBUG__)
		{
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= m; j++)
					cout << b[i][j] << " \n"[j == m];
			cout << endl;
		}		
			
			
			
		queue<pii> q;
		const pii dirs[] = {make_pair(-1, 0), make_pair(1, 0), 
						   make_pair(0, -1), make_pair(0, 1),
						   make_pair(-1, -1), make_pair(1, 1), 
						   make_pair(1, -1), make_pair(-1, 1)};
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				if (a[i][j] == 1)
					q.push({i, j});
		while (!q.empty())
		{
			auto [x, y] = q.front();
			q.pop();
			if (x == 1 || x == n || y == 1 || y == m)
				return false;
			for (auto [dx, dy] : dirs)
			{
				if (b[x + dx][y + dy] == 0)
				{
					b[x + dx][y + dy] = 2;
					q.push({x + dx, y + dy});
				}
			}
		}
		return true;
	};
	for (int i = 1; i <= q; i++)
	{
		int x, y;
		cin >> x >> y;
		int l = 0, r = f[x][y], mid, ans = 0;
		while (l <= r)
		{
			mid = (l + r) / 2;
			if (check(mid, {x, y}))
			{
				l = mid + 1;
				ans = mid;
			}
			else
				r =  mid - 1;
		}
		cout << ans << endl;
	}
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	while (t --> 0)
	{
		work();
	}
}