五月第四次周赛题解

乒乓球

思路

把输入中的所有 W / L 按顺序读入，遇到 E 立刻停止。

然后分别模拟：

• 11 分制
• 21 分制

对于当前局维护两个人的分数 a, b：

• W 则 a++
• L 则 b++
• 当 max(a,b) >= limit 且 abs(a-b) >= 2 时，这一局结束，输出并清零

最后别忘了输出当前未结束那一局的比分。

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)，其中 n 是读入的总字符数

参考代码

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

vector<string> work(const string &s, int lim) {
    int a = 0, b = 0;
    vector<string> ans;
    for (char ch : s) {
        if (ch == 'W') ++a;
        else ++b;
        if (max(a, b) >= lim && abs(a - b) >= 2) {
            ans.push_back(to_string(a) + ":" + to_string(b));
            a = b = 0;
        }
    }
    ans.push_back(to_string(a) + ":" + to_string(b));
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    char ch;
    while (cin >> ch) {
        if (ch == 'E') break;
        s += ch;
    }

    auto a = work(s, 11);
    auto b = work(s, 21);

    for (auto &x : a) cout << x << '\n';
    cout << '\n';
    for (auto &x : b) cout << x << '\n';
    return 0;
}

---

搞快点搞快点

思路

设 dp[k][x] 表示：

• 当前还剩 k 层蛋仔塔
• 塔底端位于位置 x
• 此时让最上方蛋仔 D 继续到终点的最小已花费时间

初始状态是 dp[4][0] = 0。

转移分两种：

1. 普通前进
   从 x 到 x+1，代价是第 x+1 段路的耗时。

2. 超级弹射
   若当前有 k >= 2 层，那么最下方蛋仔消失，其余 k-1 层被弹到 min(l, x+d)，耗时 0。

因为所有移动都只会让位置变大，所以每一层的普通前进直接从左到右扫一遍即可。

顺序是：

• 先处理 4 层的前进，再从 4 层弹到 3 层
• 再处理 3 层的前进，再弹到 2 层
• 再处理 2 层的前进，再弹到 1 层
• 最后处理 1 层前进到终点

答案是 dp[1..4][l] 的最小值。

复杂度

• 时间复杂度：O(l)
• 空间复杂度：O(l)

参考代码

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

using ll = long long;
const ll INF = (ll)4e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int l, d;
    cin >> l >> d;
    ll t0, t1, t2;
    cin >> t0 >> t1 >> t2;
    string s;
    cin >> s;

    vector<ll> cost(l + 1);
    for (int i = 1; i <= l; ++i) {
        if (s[i - 1] == '0') cost[i] = t0;
        else if (s[i - 1] == '1') cost[i] = t1;
        else cost[i] = t2;
    }

    vector<vector<ll>> dp(5, vector<ll>(l + 1, INF));
    dp[4][0] = 0;

    for (int k = 4; k >= 2; --k) {
        for (int x = 0; x < l; ++x) {
            if (dp[k][x] == INF) continue;
            dp[k][x + 1] = min(dp[k][x + 1], dp[k][x] + cost[x + 1]);
        }
        for (int x = 0; x <= l; ++x) {
            if (dp[k][x] == INF) continue;
            int to = min(l, x + d);
            dp[k - 1][to] = min(dp[k - 1][to], dp[k][x]);
        }
    }

    for (int x = 0; x < l; ++x) {
        if (dp[1][x] == INF) continue;
        dp[1][x + 1] = min(dp[1][x + 1], dp[1][x] + cost[x + 1]);
    }

    ll ans = min({dp[1][l], dp[2][l], dp[3][l], dp[4][l]});
    cout << ans << '\n';
    return 0;
}

---

来打uno吗

思路

目标状态要求：

1. 颜色顺序是 R < Y < G < B
2. 同色内部点数非递减

允许交换的条件是：相邻两张牌同色，或者同点数。

关键观察：

• 同色的两张牌，最终内部顺序可以调整
• 同点数的两张牌，也可以互相跨过去
• 但是如果两张牌 颜色不同且点数不同，那么它们之间永远不可能直接交换

因此：

如果在当前序列中，存在一张更靠前的牌 A 和一张更靠后的牌 B，满足：

• A 的颜色应该排在 B 后面
• 并且 A 与 B 点数不同

那么这对相对顺序无法修复，答案一定是 NO。

我们从左到右扫描每张牌 (x, c)，统计前面已经出现过多少张更高颜色的牌； 但如果那些牌与当前牌点数相同，则它们是可以通过“同点数交换”跨过去的，不算坏对。

于是只要检查：

前面更高颜色的牌数 - 前面更高颜色且同点数的牌数

是否大于 0 即可。

复杂度

• 时间复杂度：O(4n)
• 空间复杂度：O(4n)

参考代码

#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
typedef vector<vector<int>> mat;
using pii = pair<int, int>;
using pdd = pair<double,double>;
constexpr int N = 2e5 + 10;
void solve()
{
    int n;cin>>n;
    vector<int> a(n*4+10);
    vector<char> b(n*4+10);
    map<char,int> mp;
    mp['R']=1;mp['Y']=2;mp['G']=3;mp['B']=4;
    for(int i=1;i<=n*4;i++)  cin>>a[i]>>b[i];
    for(int i=1;i<=n*4;i++)
        for(int j=i;j<=n*4;j++)
        {
            if(mp[b[i]]>mp[b[j]]&& a[i]!=a[j]) 
            {
                cout<<"NO\n";
                return;
            }
        }
        cout<<"YES\n";
        return;
}
signed main()
{
    IOS;
    int _= 1;
    cin >> _;
    while(_--)
    {
        solve();
    }
    return 0;
}

---

马拉松的困难

思路

题目要求判断 N 是否能整除 M，也就是判断：

M % N == 0

成立则输出 1，否则输出 0。

复杂度

• 时间复杂度：O(T)
• 空间复杂度：O(1)

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int M, N;
        cin >> M >> N;
        cout << (M % N == 0 ? 1 : 0) << '\n';
    }
    return 0;
}