Educational Codeforces Round 168 (Rated for Div.2) • santisify Site

A Strong Password ↗#

题目描述#

给定字符串，现在让我们添加一个字符，使得字符串的价值最大，对于价值是这样看的

第一个字符的价值为2，

后面的字符若与前面的字符相同，则价值为1，否则价值为2。让我们输出价值最大的一种情况

解题思路#

我们可以遍历每一个位置，然后找出在哪个位置插入的价值最大，毕竟 n 的取值较小，最后再将其替换为与前后位置不相等的字符即可。

参考代码#

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve () {
	std::string s, t;
	std::cin >> s;

	if(s.size() == 1) {
		std::cout << (s[0] == 'z' ? 'a' : 'z') << s[0] << endl;
		return;
	}
	int ma = 0;
	for(int i = 0; i < s.size(); i++) {
		auto w = s;
		w.insert(w.begin() + i, '.');
		int res = 2;
		for(int j = 1; j < w.size(); j++) {
			if (w[j] == w[j - 1]) {
				res++;
			} else res += 2;
		}
		if (ma <= res) {
			ma = res;
			t = w;
		}
	}

	int pos = t.find('.');
	int t1 = pos - 1, t2 = pos + 1;
	for(auto i = 'a'; i <= 'z'; i++) {
		if (i != t[t1] && i != t[t2]) {
			t[pos] = i;
			break;
		}
	}
	std::cout << t << endl;
}

signed main () {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	int Lazy_boy_ = 1;
	std::cin >> Lazy_boy_;
	while (Lazy_boy_--) solve();
	return 0;
}

cpp

B Make Three Regions ↗#

题目描述#

给定一个 $2 * n$ 的一个字符矩阵，其中 . 是开放的，而 X 是阻塞的，现在让我们判断有几个点可以将这个字符矩阵分为三个联通的区域。

解题思路#

刚开始的时候，以为是有几个联通的区域，写完 dfs 后，什么WA1，我连 dfs 都能写错，结果自己是小丑（小插曲）可以通过给出的图例看出一列只可能有一个点能成为分割点，那么能成为分割点就需要满足四个条件，

$s[0][i] ='.' \&\& s[1][i] ='.'$

$s[0][i - 1] \neq s[1][i - 1]$

$s[0][i+1] \neq s[1][i+1]$

$s[0][i-1] = s[0][i + 1]$ 既然这样，那就简单了

参考代码#

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

void solve () {
	int n = 2, m;
	std::cin >> m;
	std::vector<std::string> s(n);
	for(int i = 0; i < n; i++) std::cin >> s[i];

	int ans = 0;
	for(int i = 1; i < m - 1; i++) {
		bool k = true;
		k &= (s[0][i] == '.' && s[1][i] == '.');
		k &= (s[0][i - 1] != s[1][i - 1]);
		k &= (s[0][i + 1] != s[1][i + 1]);
		k &= (s[0][i - 1] == s[0][i + 1]);
		ans += k ? 1 : 0;
	}
	std::cout << ans << endl;
}

signed main () {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr), std::cout.tie(nullptr);
	int Lazy_boy_ = 1;
	std::cin >> Lazy_boy_;
	while (Lazy_boy_--) solve();
	return 0;
}

cpp

C Even Positions ↗#

题目描述#

给定字符串，让我们输出字符串匹配的()的最短距离，距离是 $pos('()') - pos('(')$

解题思路#

手指玩玩就行了

参考代码#

#include<bits/stdc++.h>

#define int long long
#define endl '\n'
#define pii std::pair<int ,int>
#define fix(x) std::fixed << std::setprecision(x)
const int inf = 1e17 + 50, MAX_N = 1e5 + 50, mod = 1e9 + 7;

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

    std::string s;
    std::cin >> s;

    int pre = 0, ans = 0;
    for(int i = 0; i < n; i += 2) {
       if (pre > 0) {
          pre--;
       } else {
          pre++;
       }       ans += pre;
       pre += (s[i + 1] == '(' ? 1 : -1);
       ans += pre;
    }
    std::cout << ans << endl;
}

signed main () {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int Lazy_boy_ = 1;
    std::cin >> Lazy_boy_;
    while (Lazy_boy_--) solve();
    return 0;
}

cpp