题目描述
给定字符串，现在让我们添加一个字符，使得字符串的价值最大，对于价值是这样看的
- 第一个字符的价值为
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;
}
|
题目描述
给定一个 $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;
}
|
题目描述
给定字符串，让我们输出字符串匹配的()的最短距离，距离是$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;
}
|
