2024年1月编程训练
约 258 个字 68 行代码 预计阅读时间 2 分钟
C. Yuhao and a Parenthesis¶
括号匹配 贪心 2024年1月8日
要使得两个串合起来是合法的,原本两个串都是合法的,合起来自然合法,下面我们讨论两个互补的串来合并的情况。
设前面的串为 S
后面的串为 T
S
的(
数量一定比)
多,T 的(
数量一定比)
多- 两个的数量应该是相等的
S
串保证是左括号始终大于右括号,遇到(
加一,遇到)
减一T
串反着遍历保证右括号始终大于左括号,遇到(
减一,遇到)
加一
代码
void solve()
{
int n;
cin >> n;
vector<string> a(n);
for(auto &it: a) cin >> it;
map<int,int> p,neg;
int res = 0;
for(auto s: a) {
int t = 0;
for(auto c: s) {
if(c == '(') t ++;
else t --;
if(t < 0) break;
}
if(t == 0) res ++;
else if(t > 0) p[t] ++;
}
for(auto s: a) {
int t = 0;
for(int i = s.size() - 1; i >= 0; i --) {
if(s[i] == '(') t --;
else t ++;
if(t < 0) break;
}
// if(t == 0) res ++;
if(t > 0) neg[t] ++;
}
res /= 2;
for(auto s: a) {
int t = 0;
for(auto c: s) {
if(c == '(') t ++;
else t --;
if(t < 0) break;
}
if(t > 0) {
if(neg[t] > 0) {
neg[t] --;
p[t] --;
res ++;
}
}
}
cout << res << "\n";
}
Codeforces Round 919 (Div. 2)¶
比赛链接:点击这里
B. Summation Game¶
答案是从样例中推出来的,而不是猜出来的。
想想答案可能从哪几种方案中选出,靠什么规律想出,为啥另一种不是正确答案,和正确答案的区别在哪?
每个变量有它明确的定义,变量名命名准确。
想清楚再写。
代码
void solve()
{
int n,k,x;
cin >> n >> k >> x;
vector<int> a(n);
ll sum = 0;
for(auto &it: a) cin >> it,sum += it;
sort(a.begin(),a.end(),greater<>());
ll neg = 0;
for(int i = 0; i < x; i ++) neg += a[i];
ll res = sum - 2*neg;
for(int i = 0; i < k; i ++) {
if(i + x < n) neg = neg - a[i] + a[i+x];
else neg = neg - a[i];
sum -= a[i];
res = max(res, sum - 2*neg);
}
cout << res << "\n";
}
¶
Last update:
January 17, 2024
Created: January 9, 2024
Created: January 9, 2024