牛客小白月赛87(非常菜的小白)->(两题)

youhualiuh / 2024-02-17 / 原文

这场被B坑了很长时间,导致没有看下面的题哈哈哈,还得练,赛后1分钟写出C,狠狠的加训。

A.小苯的石子游戏

思路:

Alice 和 Bob 玩石子游戏,这里的石头谁多谁赢, 不存在平局。由于本身就是升序, 所以从后往前取即可。

解法:

由于升序,为了方便变成降序,最优解法就是最大的一个个轮流过去拿即可。

Code:

#include <bits/stdc++.h>
    
using namespace std;
    
int n, arr[105];

void solve() {
    int n; cin >> n;
    for (int i = n; i >= 1; i--) {cin >> arr[i];}
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (i & 1) ans += arr[i];
        else ans -= arr[i];
    }
    if (ans > 0) cout << "Alice\n";
    else cout << "Bob\n";
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B.小苯的排序疑惑

思路:

选择一段数组长度小于n的长度进行排序, 问能操作一次使得成立,最优的情况就是n - 1的情况, 因此我们有两种情况

解法:

1- a(1) ~ a(n - 1) 我们要让这些数都要小于等于a(n)

2- a(2) ~ a(n) 我们使得这些数都大于等于a(1) -> 进行排序即可

只要满足输出YES, 否则输出NO

Code:

#include <bits/stdc++.h>
    
using namespace std;

int a[200005];

void solve() {
    int minn = INT_MAX, maxx = INT_MIN;
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        minn = min(a[i], minn), maxx = max(a[i], maxx);
    }
    if (minn == a[1] || maxx == a[n]) {
        cout << "YES\n";
    } 
    else {
        cout << "NO\n";
    }
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C.小苯的IDE括号问题（easy）

思路:

输入一串字符串 I 代表光标
backspace 删除前面括号
    (I) 则I
    ()I 则删除(I
    I() 则I()
delete 删除后面
    I() 则I)

解法:

解法很多这里使用双指针的方法和字符串的方法按照题意来即可

Code:

#include <bits/stdc++.h>
    
using namespace std;
    
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    string s; cin >> s;
    int idex = s.find('I');//查找I的位置
    int left = idex - 1, right = idex + 1;
    // left 记录左边 right 记录右边

    while (k--) {
        string x; cin >> x;
        if (x == "backspace") {
            if (left >= 0) {
                if (s[left] == '(' && s[right] == ')' && right < n) right ++;
                left --;
            }
        }
        else {//delete
            if (right < n) {right++;}
        }
    }

    for (int i = 0; i <= left; i++) {cout << s[i];}
    cout << 'I';
    for (int i = right; i < n; i++) {cout << s[i];} 
    cout << '\n';
    return 0;
}

#include <bits/stdc++.h>
    
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
    
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    string s; cin >> s;
    int idex = s.find('I');

    while (k--) {
        string x; cin >> x;
        if (x == "backspace") {
            if (idex > 0 && idex < n - 1 && s[idex - 1] == '(' && s[idex + 1] == ')') {
                s.erase(idex - 1, 1);
                s.erase(idex, 1);
                idex--;
            }
            else {
                if (idex > 0) {
                    s.erase(idex - 1, 1);
                    idex--;
                }
            }
        }
        else {
            if (idex < n - 1) {
                s.erase(idex + 1, 1);
            }
        }
    }
    cout << s << '\n';
    return 0;
}

D.小苯的IDE括号问题（hard）

思路:

和上面一样,只是多了两个<- and ->使用栈或者其他方法也可,这里只举例栈, ~i 这里相当于 i >= 0

Code:

#include <bits/stdc++.h>
    
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
    
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    string s; cin >> s;
    int idex = s.find('I');
    vector<char> a, b;
    for (int i = 0; i < idex; i++) {a.emplace_back(s[i]);}
    for (int i = idex + 1; i < n; i++) {b.emplace_back(s[i]);}

    reverse(b.begin(), b.end());
    while (k--) {
        string x; cin >> x;
        if (x == "backspace") {
            if (a.size()) {
                if (a.back() == '(' && b.size() && b.back() == ')') {
                    b.pop_back();
                }
                a.pop_back();
            } 
        }
        else if (x == "delete") {
            if (b.size()) {
                b.pop_back();
            }
        }
        else if (x == "<-") {
            if (a.size()) {
                b.emplace_back(a.back());
                a.pop_back();
            }
        }
        else {//"->"
            if (b.size()) {
                a.emplace_back(b.back());
                b.pop_back();
            }
        }
    }
    for (int i = 0; i < a.size(); i++) {cout << a[i];}
    cout << 'I';
    for (int i = b.size() - 1; ~i; i--) {cout << b[i];}
    cout << '\n';
    return 0;
}