链接：https://codeforces.com/contest/2136

A. In the Dream

算法：

    找规律，模拟。

思路：

    可以发现要想让结果成立，某个人不能同时赢三场，控制 \(1：2\) ，所以 \(max / min\) < 3 即可。

关键代码：

void solve()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    c -= a, d -= b;

    if (c < 0 || d < 0)
    {
        cout << "NO" << endl;
        return;
    }

    if (a < b)
        swap(a, b);
    if (c < d)
        swap(c, d);

    if ((a + b) / (b + 1) >= 3 || (c + d) / (d + 1) >= 3)
        cout << "NO" << endl;
    else
        cout << "YES" << endl;
}

B. Like the Bitset

算法：

    构造、贪心。

思路：

    只要不出现连续的 \(k\) 个 \(1\) 就存在答案，直接在 \(1\) 上面放最小的几个数字即可。

关键代码：

void solve()
{
    int n, k;
    string s;
    cin >> n >> k >> s;

    s = ' ' + s;

    ll cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (s[i] == '1')
            ++cnt;
        else
            cnt = 0;

        if (cnt >= k)
        {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;

    ll num = 1;
    vector<int> p(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        if (s[i] == '1')
            p[i] = num++;

    for (int i = 1; i <= n; ++i)
        if (s[i] == '0')
            p[i] = num++;

    for (int i = 1; i <= n; ++i)
        cout << p[i] << ' ';

    cout << endl;
}

C. Against the Difference

算法：

    \(dp\)。

思路：

    定义 \(dp[i]\): 使用前 \(i\) 个元素构造整洁子序列的最大长度。

    使用 \(p\) 数组记录每个元素出现的位置，在当前 \(i\) 如果 \(p[a[i]]\) 的大小大于 \(a[i]\)，就可以状态转移：

\(dp[i] = max(dp[i], x + dp[p[x][p[x].size() – x] – 1]);\)

关键代码：

void solve()
{
    int n;
    cin >> n;

    vector<vector<int>> p(n + 1);
    vector<ll> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i)
    {
        ll x;
        cin >> x;

        p[x].push_back(i);
        dp[i] = dp[i - 1];

        if (p[x].size() >= x)
            dp[i] = max(dp[i], x + dp[p[x][p[x].size() - x] - 1]);
    }

    cout << dp[n] << endl;
}

D. For the Champion

    交互题就先不补了。