Codeforces Round 954 (Div. 3)

🚀欢迎来到本文🚀
🍉个人简介：陈童学哦，彩笔ACMer一枚。
🏀所属专栏：Codeforces
本文用于记录回顾本彩笔的解题思路便于加深理解。

A. X Axis

You are given three points with integer coordinates $x_1$, $x_2$, and $x_3$ on the $X$ axis ($1\le x_i\le 10$). You can choose any point with an integer coordinate $a$ on the $X$ axis. Note that the point $a$ may coincide with $x_1$, $x_2$, or $x_3$. Let $f(a)$ be the total distance from the given points to the point $a$. Find the smallest value of $f(a)$.

The distance between points $a$ and $b$ is equal to $|a-b|$. For example, the distance between points $a=5$ and $b=2$ is $3$.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^3$) — the number of test cases. Then follows their descriptions.

The single line of each test case contains three integers $x_1$, $x_2$, and $x_3$ ($1\le x_i\le 10$) — the coordinates of the points.

Output

For each test case, output the smallest value of $f(a)$.

解题思路：

可以通过暴力枚举出来最佳的那个点，然后计算答案，但是这里我们其实可以发现f(a)的最小值其实就是a为x1、x2、x3三个点中从小到大排序中间的那个点。

AC代码：

#include
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a,a + 3);
	cout << a[1] - a[0] + a[2] - a[1] << "\n";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t = 1;
	cin >> t;
	
	while(t --){
		solve();
	}
	
	return 0;
} 

B. Matrix Stabilization

You are given a matrix of size $n\times m$, where the rows are numbered from $1$ to $n$ from top to bottom, and the columns are numbered from $1$ to $m$ from left to right. The element at the intersection of the $i$-th row and the $j$-th column is denoted by $a_{ij}$.

Consider the algorithm for stabilizing matrix $a$:

1. Find the cell $(i,j)$ such that its value is strictly greater than the values of all its neighboring cells. If there is no such cell, terminate the algorithm. If there are multiple such cells, choose the cell with the smallest value of $i$, and if there are still multiple cells, choose the one with the smallest value of $j$.
2. Set $a_{ij}=a_{ij}-1$.
3. Go to step $1$.

In this problem, cells $(a,b)$ and $(c,d)$ are considered neighbors if they share a common side, i.e., $|a-c|+|b-d|=1$.

Your task is to output the matrix $a$ after the stabilization algorithm has been executed. It can be shown that this algorithm cannot run for an infinite number of iterations.

Input

Each test consists of multiple sets of input data. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of sets of input data. This is followed by their description.

The first line of each set of input data contains two integers $n$ and $m$ (KaTeX parse error: Expected 'EOF', got '&' at position 33: …100, n \cdot m &̲gt; 1) — the number of rows and columns of matrix $a$.

The next $n$ lines describe the corresponding rows of the matrix. The $i$-th line contains $m$ integers $a_{i1},a_{i2},\dots ,a_{im}$ ($1\le a_{ij}\le 10^9$).

It is guaranteed that the sum of $n\cdot m$ over all sets of input data does not exceed $2\cdot 10^5$.

Output

For each set of input data, output $n$ lines with $m$ numbers in each line — the values of the cells of matrix $a$ after the stabilization algorithm.

解题思路：

从上往下从左往右依次遍历，如果当前数满足条件（严格大于它上、下、左、右的四个数）时，就将当前数设置为它上、下、左、右的四个数中的最大值。

AC代码：

#include
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
int g[110][110];
void solve(){
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cin >> g[i][j];
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			if(g[i][j] > g[i - 1][j] && g[i][j] > g[i + 1][j] && g[i][j] > g[i][j + 1] && g[i][j] > g[i][j - 1]){
				g[i][j] = max({g[i - 1][j],g[i + 1][j],g[i][j - 1],g[i][j + 1]});
				
			}
		}
	}
	for(int i = 1;i <= n;i ++){
		for(int j = 1;j <= m;j ++){
			cout << g[i][j] << " ";
		}
		cout << "\n";
	}
	for(int i = 0;i < 110;i ++){
		for(int j = 0;j < 110;j ++){
			g[i][j] = 0;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t = 1;
	cin >> t;
	
	while(t --){
		solve();
	}
	
	return 0;
} 

C. Update Queries

Let’s consider the following simple problem. You are given a string $s$ of length $n$, consisting of lowercase Latin letters, as well as an array of indices $ind$ of length $m$ ($1\le in{d}_i\le n$) and a string $c$ of length $m$, consisting of lowercase Latin letters. Then, in order, you perform the update operations, namely, during the $i$-th operation, you set $s_{in{d}_i}=c_i$. Note that you perform all $m$ operations from the first to the last.

Of course, if you change the order of indices in the array $ind$ and/or the order of letters in the string $c$, you can get different results. Find the lexicographically smallest string $s$ that can be obtained after $m$ update operations, if you can rearrange the indices in the array $ind$ and the letters in the string $c$ as you like.

A string $a$ is lexicographically less than a string $b$ if and only if one of the following conditions is met:

• $a$ is a prefix of $b$, but $a\ne b$;
• in the first position where $a$ and $b$ differ, the symbol in string $a$ is earlier in the alphabet than the corresponding symbol in string $b$.

Input

Each test consists of several sets of input data. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains two integers $n$ and $m$ ($1\le n,m\le 10^5$) — the length of the string $s$ and the number of updates.

The second line of each set of input data contains a string $s$ of length $n$, consisting of lowercase Latin letters.

The third line of each set of input data contains $m$ integers $in{d}_1,in{d}_2,\dots ,in{d}_m$ ($1\le in{d}_i\le n$) — the array of indices $ind$.

The fourth line of each set of input data contains a string $c$ of length $m$, consisting of lowercase Latin letters.

It is guaranteed that the sum of $n$ over all sets of input data does not exceed $2\cdot 10^5$. Similarly, the sum of $m$ over all sets of input data does not exceed $2\cdot 10^5$.\

Output

For each set of input data, output the lexicographically smallest string $s$ that can be obtained by rearranging the indices in the array $ind$ and the letters in the string $c$ as you like.

解题思路：

我们想得到字典序最小的字符串，首先的话我们肯定是尽量想让字符串c中字典序小的字母尽可能的去替换原字符串索引位置靠前的字母，这样才能保证字典序最小，但是我们需要考虑到问题就是题目所给的索引数组ind中的数可能是相等的，也就意味着如果出现两个相同索引连续出现两次以上的话，当我们先去用字符串c中字典序更小的字母去替换的时候下次再次替换时会导致这个地方的字典序不是最小的。那么考虑如何解决这个弊端呢，这里可以考虑使用双指针，当出现两个相同以上的索引时，我们可以先从字符串c的尾指针先开始替换，这样就能保证下次替换的时候是字典序更小的字母替换更大的，而不是字典序小的被字典序大的替换掉。

AC代码：

#include
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){
	int n,m;
	cin >> n >> m;
	string s1,s2;
	cin >> s1;
	int n1 = s1.size();
	s1 = '?' + s1;
//	look(s1);
	vector<int> a(m + 1);
	for(int i = 1;i <= m;i ++){
		cin >> a[i];
	}
	cin >> s2;
	int n2 = s2.size();
	sort(s2.begin(),s2.end());
//	look(s2);
	s2 = '?' + s2;
//	look(s2);
	sort(a.begin() + 1,a.end());
	int l = 1,r = n2;
//	look(a[1]);
//	look(a[2]);
	for(int i = 1;i <= m;i ++){
		if(i != m && a[i] == a[i + 1]){
//			look(s1);
			s1[a[i]] = s2[r];
			r --;
		}		
		if(i == m){
			s1[a[i]] = s2[l];
			break;
		}
		if(a[i] != a[i + 1]){
//			look(i);
//			look(s1);
			s1[a[i]] = s2[l];
			l ++;
		}
	}
//	look(s1);
	cout << s1.substr(1,n1) << "\n";
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t = 1;
	cin >> t;
	
	while(t --){
		solve();
	}
	
	return 0;
} 

D. Mathematical Problem

You are given a string $s$ of length KaTeX parse error: Expected 'EOF', got '&' at position 3: n &̲gt; 1, consisting of digits from $0$ to $9$. You must insert exactly $n-2$ symbols $+$ (addition) or $\times$ (multiplication) into this string to form a valid arithmetic expression.

In this problem, the symbols cannot be placed before the first or after the last character of the string $s$, and two symbols cannot be written consecutively. Also, note that the order of the digits in the string cannot be changed. Let’s consider $s=987009$:

• From this string, the following arithmetic expressions can be obtained: $9\times 8+70\times 0+9=81$, $98\times 7\times 0+0\times 9=0$, $9+8+7+0+09=9+8+7+0+9=33$. Note that the number $09$ is considered valid and is simply transformed into $9$.
• From this string, the following arithmetic expressions cannot be obtained: $+9\times 8\times 70+09$ (symbols should only be placed between digits), $98\times 70+0+9$ (since there are $6$ digits, there must be exactly $4$ symbols).

The result of the arithmetic expression is calculated according to the rules of mathematics — first all multiplication operations are performed, then addition. You need to find the minimum result that can be obtained by inserting exactly $n-2$ addition or multiplication symbols into the given string $s$.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. Then follows their description.

The first line of each test case contains a single integer $n$ ($2\le n\le 20$) — the length of the string $s$.

The second line of each test case contains a string $s$ of length $n$, consisting of digits from $0$ to $9$.

Output

For each test case, output the minimum result of the arithmetic expression that can be obtained by inserting exactly $n-2$ addition or multiplication symbols into the given string.

解题思路：

长度为n的字符串插入n-2个符号，首先n为2是就是当前字符串转换为十进制数的结果，否则的话就是n-1个数字与n-2个符号之间的运算，n个字符组成n-1个数，显然必有一个数为两位数其余都为一位数，那么当n > 2时我们可以从左往右依次枚举相邻两位组成一个两位数时的与其他数进行加、乘运算的最小值，如果有0出现那么最小值必然为0，其次有1出现的话相乘能让结果不变，其余数均相加即可让值最小，最后在枚举的所有情况中取最小值即位答案。

AC代码：

#include
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){
	int n;
	cin >> n;
	string s;
	cin >> s;
	if(n == 2){
		cout << stoi(s) << "\n";
		return;
	}
	int ans = 1e9;
	map<int,int> mp;
	for(int i = 0;i < n - 1;i ++){
		int x = stoi(s.substr(i,2));
		int sum = 0;
		sum += x;
		mp[i] = 1;
		mp[i + 1] = 1;
		for(int i = 0;i < n;i ++){
			if(!mp[i]){
				int y = (s[i] - '0');
				if(y == 0){
					cout << "0\n";
					return;
				}

				if(sum == 1){
					sum *= y;
					continue;
				}				
				if(y != 1){
					sum += y;
				}
			}
		}
		ans = min(ans,sum);
		mp.clear();
	}
	
	cout << ans << "\n";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t = 1;
	cin >> t;
	
	while(t --){
		solve();
	}
	
	return 0;
} 

E. Beautiful Array

You are given an array of integers $a_1,a_2,\dots ,a_n$ and an integer $k$. You need to make it beautiful with the least amount of operations.

Before applying operations, you can shuffle the array elements as you like. For one operation, you can do the following:

• Choose an index $1\le i\le n$,
• Make $a_i=a_i+k$.

The array $b_1,b_2,\dots ,b_n$ is beautiful if $b_i=b_{n-i+1}$ for all $1\le i\le n$.

Find the minimum number of operations needed to make the array beautiful, or report that it is impossible.

Input

Each test consists of several sets of input data. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains two integers $n$ and $k$ ($1\le n\le 10^5$, $1\le k\le 10^9$) — the size of the array $a$ and the number $k$ from the problem statement.

The second line of each set of input data contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all sets of input data does not exceed $2\cdot 10^5$.

Output

For each set of input data, output the minimum number of operations needed to make the array beautiful, or $-1$ if it is impossible.

解题思路：

要构造漂亮数组，首先如果一个数出现的次数如果为偶数的话，我们就不需要进行操作，否则的话我们需要使用一个map里套vector的map的结构来将ai%k相等的数存在同一个vector中，因为只有余数相等的两个数才能通过相加或相减若干倍的k才能得到。然后我们遍历map这个结构，如果有两个以上的vector的大小为奇数的话那么我们必然无法构造漂亮数组，因为我们最多将一个数放在整个数组的中间来让这个数成为回文中心而不用依靠两两配对完成，而出现两个以上的奇数大小的vector时，两个vector各自中多出来的那个数必然无法通过加减k来完成配对，所以此时必然无法完成构造。而如果上述条件满足的话，当vector的大小为偶数时，我们只需要从小到大依次取两个数使得两个数的差值尽可能的小，这样我们的操作数也会尽可能的小，但是当vector的大小为奇数时我们处理结果时会有些麻烦，因为我们不知道vector中的哪个数作为中心数能够使得结果最佳，如果我们暴力枚举vector中的每个数字作为中心数的话复杂度必然会爆炸，所以这里我们考虑使用前缀、后缀记录值的巧妙方法来降低复杂度。

AC代码：

#include
#define look(x) cout << #x << " == " << x << "\n"
using namespace std;
using i64 = long long;
using ld = long double;
const int N = 2e5 + 10;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;
void solve(){
	int n,k;
	cin >> n >> k;
	vector<int> a(n + 1);
	map<int,int> mp;
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
		mp[a[i]] ++;
	}
	map<int,vector<int>> mv;
	for(auto [x,y] : mp){
		if(y & 1){
			mv[x % k].push_back(x);
		}
	}
	i64 ans = 0;
	int res = 0;
	for(auto [x,y] : mv){
		if(y.size() & 1){
			res ++;
			if(res > 1){
				cout << "-1\n";
				return;
			}
		}
		sort(y.begin(),y.end());
		if(y.size() % 2 == 0){
			for(int i = 1;i < y.size();i += 2){
				int x = y[i] - y[i - 1];
				ans += x / k;
			}
		}else if(y.size() > 1){
			int m = (int)y.size();
			vector<i64> sum1(m);
			vector<i64> sum2(m);
			sum1[1] = y[1] - y[0];
			for(int i = 3;i < m;i += 2){
				sum1[i] = sum1[i - 2] + y[i] - y[i - 1];
			}
			sum2[m - 2] = y[m - 1] - y[m - 2];
			for(int i = m - 4;i >= 0;i -= 2){
				sum2[i] = sum2[i + 2] + y[i + 1] - y[i];
			}
			i64 tmp = min(sum1[m - 2],sum2[1]);
			for(int i = 2;i < m - 2;i += 2){
				tmp = min(tmp,sum1[i - 1] + sum2[i + 1]);
			}
			ans += tmp / k;
		}
	}
	cout << ans << "\n";
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int t = 1;
	cin >> t;
	
	while(t --){
		solve();
	}
	
	return 0;
}