2024年1月编程训练

约 258 个字 68 行代码 预计阅读时间 2 分钟

C. Yuhao and a Parenthesis

括号匹配 贪心 2024年1月8日

要使得两个串合起来是合法的，原本两个串都是合法的，合起来自然合法，下面我们讨论两个互补的串来合并的情况。

设前面的串为 S 后面的串为 T

1. S 的 ( 数量一定比 ） 多，T 的 ( 数量一定比 ） 多
2. 两个的数量应该是相等的
3. S 串保证是左括号始终大于右括号，遇到 （ 加一，遇到 ） 减一
4. 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

Comments