Codeforces Round 954 (Div. 3)

A. X Axis

题意：给3个x轴上的点xi，我们要放置一个点到x轴上，到这3个点的距离最短。(1 <= xi <= 10)

思路：直接暴力破解即可

int a, b, c;
inline int cal(int x){
	return abs(x - a) + abs(x - b) + abs(x - c);
}

void solve() {
	cin >> a >> b >> c;

	int ans = (int)1e9;
	for (int i = min({a, b, c}); i <= max({a, b, c}); ++i){
		ans = min(ans, cal(i));
	}
	cout << ans << '\n';
}

B. Matrix Stabilization

题意：给个n*m平面，可以进行无限次操作，对平面满足条件的点的数值进行修改。条件：与当前的格子共享了边的格子中，如果所有的格子的数值都比他小，则改变它为其他格子中的最大值。输出修改后的grid。

思路：修改没有后继性，一次遍历即可。

void solve() { 
	int n, m;
	cin >> n >> m;

	vector<vector<int>> mat(n + 1, vector<int> (m + 1));
	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j){
			cin >> mat[i][j];
		}
	}

	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j){
			int maxn = 0;
			for (int k = 0; k < 4; ++k){
				int pi = dx[k] + i;
				int pj = dy[k] + j;
				if (min(pi, pj) >= 1 && pi <= n && pj <= m){
					maxn = max(maxn, mat[pi][pj]);
				}
			}
			if (mat[i][j] > maxn){
				mat[i][j] = maxn;
			}
		}
	}

	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j){
			cout << mat[i][j] << " \n"[j == m];
		}
	}
}

C. Update Queries

题意：给定长度为n的字符串s和长度为m的操作顺序ind和长度为m的字符串c。每次操作将s[idx[j]] = c[j]。但是现在可以对ind和（或）c进行重排序，目标是修改后的s字典序最小。输出s。

思路：贪心+sort。对操作去重并升序排序，对c升序排序，直接修改即可。

总结：一开始读错题了，以为对于相同的操作下标，可以更改其操作的顺序，使用的map，跑tc发现理解错题了，浪费几分钟。

void solve() { 
	int n, m;
	cin >> n >> m;

	string s;
	cin >> s;

	vector<int> order(m);
	for (int i = 0; i < m; ++i){
		cin >> order[i];
		order[i] --;
	}
	string c;
	cin >> c;

	sort(order.begin(), order.end());
	order.erase(unique(order.begin(), order.end()), order.end());

	sort(c.begin(), c.end());
	for (int i = 0; i < (int)order.size(); ++i){
		s[order[i]] = c[i];
	}

	cout << s << '\n';
}

后面开始，坐牢两个多小时...

D. Mathematical Problem

题意：给定长度为n的字符串，字符串包含0~9的数字。现在要为字符串加上exactly n - 2个运算符，运算符包括+和*。问加了运算符的表达式输出最少是多少。 (2 <= n <= 20)

思路：考虑n = 2的情况，不能加运算符，如果第一个字符为0，则输出第二个字符，否则输出s。
考虑n = 3且有0，0 在中间的情况，答案为第一个和第三个字符乘积或者相加中较小的一个。
其他长度的情况：如果有0，则将所有运算符置为乘，最后结果就是0。如果没有0，则将s中所有不为1的数统计求和。此时的求和有n - 1个运算符，其中涉及到1的运算符全为*，不涉及1的运算符全为+。此时需要去掉一个运算符，再次遍历s，依此考虑将s中任意两个相邻的字符组合成一个二位数字，看哪个组合最后得到的结果最小。

总结：一开始一眼dp（脑子抽了），然后就dp了一个多小时。。最后发现乘法的状态没办法转移，因为乘法会改变运算符顺序，还需要记录上一次加法的位置。。。太年轻了，居然想用dp，哎。
还有就是没看测试样例，其实看看测试样例就知道，要贪心的分情况讨论，看字符串中0和1，以及长度的情况。。
最后补题的时候，发现处理最后一种情况的写法很巧妙，先不将1加到贡献中，但是在缩减符号数量的时候，又必须考虑所有的1。 这种操作直觉上会让人想到在求sum的时候把x > 1的条件去掉，然后在求和的时候直接sum - s[i]，但是这种会导致错误。为什么呢？因为有一些1最终不需要记录到答案中，而是作为乘法来消耗符号数量。

void solve() { 
	int n;
	cin >> n;

	string s;
	cin >> s;

	if (n == 2){
		cout << (s[0] == '0' ? string(1, s[1]) : s) << '\n';
	}
	else if (n == 3 && s[1] == '0'){
		cout << min(s[0] + s[2] - '0' * 2 , (s[0] - '0') * (s[2] - '0')) << '\n';
	}
	else if (s.find('0') != std::string::npos){
		cout << "0\n";
	}
	else{
		int sum = 0;
		for (const auto& x : s){
			if (x > '1') {
				sum += x - '0';
			}
		}
		int ans = INT_INF;
		for (int i = 0; i < n - 1; ++i){
			int num = stoi(s.substr(i, 2));
			ans = min(ans, sum - (s[i] == '1' ? 0 : s[i] - '0') - (s[i + 1] == '1' ? 0 : s[i + 1] - '0') + num);
		}
		cout << ans << '\n';
	}
}

E. Beautiful Array
题意：给定长度为n的数组a，现在可以将a shuffle，然后将a中的元素 + k（给的定值），最后a变成了一个回文数组，就是beautiful。 求最少的+k次数，或者输出-1（不可能完成）。

思路：首先map将a中的出现偶数次的元素去掉，然后如果一个数能通过另一个数相加若干个k得到，则这两个数%k的余数是相等的。然后将剩下的元素%k存到map<int, vector>中，最后遍历这个新的map，对vector排序，如果vector的元素数量是偶数，那么可以将相邻的两个vector作为一组进行+k变换。如果vector中的元素数量是奇数，那么这样的vector不能超过1个（奇数长度回文中心只有自己跟自己相等），然后维护一个前缀和后缀和来讨论vector中哪个元素作为回文中心，不参与到这种配对的计算中（自然是一个代价非常大的数，这里用前后缀和来维护非常巧妙，之前从来没有过这种想法）

总结：赛时在讨论vector为奇数时，实在是想不出来用什么方法来讨论出一个作为中心的元素，就这样耗到比赛结束，后面的题也没看。今天补提，发现使用前缀和后缀和，并将他们的求和的点放到同一个下标上，然后就可以奇妙的进行遍历，并且讨论了每个元素不参与计算的情况。

void solve() { 
	int n, k;
	cin >> n >> k;

	map<int, int> mapp;
	for (int i = 0; i < n; ++i){
		int t;
		cin >> t;
		mapp[t] ++;
	}

	vector<int> a;
	for (const auto&[x, y] : mapp){
		if (y & 1){
			a.push_back(x);
		}
	}

	if ((int)a.size() <= 1){
		cout << "0\n";
		return;
	}

	map<int, vector<int>> rec;
	for (int i = 0; i < (int)a.size(); ++i){
		int t = a[i];
		rec[t % k].push_back(t);
	}

	int cnt = 0;
	long long ans = 0;
	for (auto& [x, cur] : rec){
		bool ok = true;
		if (cur.size() & 1){
			cnt ++;
			ok = false;
			if (cnt > 1){
				cout << "-1\n";
				return;
			}
		}
		sort(cur.begin(), cur.end());
		if (ok){
			for (int i = 1; i < (int)cur.size(); i += 2){
				ans += (cur[i] - cur[i - 1]) / k;
			}
		}
		else if (cur.size() > 1){
			int m = (int)cur.size();
			vector<long long> pref(m);
			vector<long long> suff(m);
			pref[1] = cur[1] - cur[0];
			for (int i = 3; i < m; i += 2){
				pref[i] = pref[i - 2] + cur[i] - cur[i - 1];
			}
			suff[m - 2] = cur[m - 1] - cur[m - 2];
			for (int i = m - 4; i >= 0; i -= 2){
				suff[i] = suff[i + 2] + cur[i + 1] - cur[i];
			}
			long long minn = min(pref[m - 2], suff[1]);
			for (int i = 2; i < m - 2; i += 2){
				minn = min(minn, pref[i - 1] + suff[i + 1]);
			}
			ans += minn / k;
		}
	}

	cout << ans << '\n';

}

需要多思考，思维方面有点弱

有模板写题就是好用，只要维护固定的几个函数即可。
模板放在了下面的仓库，如果使用，请点进去点个star。
https://github.com/yxc-s/programming-template/tree/master
该仓库是一个新仓库，旨在打造一个通用的C++算法编程竞赛模板，包含数据结构，数论等各种实用的算法编程模板。如果您使用的语言不是C++，也可以将对应的代码实现翻译成其他语言来使用。