Contestant~ Rank 1115. Rating +1.

又是一个疯狂叉人场

A. Not a Substring

题意

给定一个长为 \(n\) 的 不一定合法的 括号字符串 \(S\)，构造一个长为 \(2n\) 的 合法 括号字符串 \(T\)，满足 \(S\) 不是 \(T\) 的子串。

思路

可以发现，只要 \(S\) 中存在连续的 \(((\) 或者 \())\)，我们就只需构造 \(()()()\ldots\)。

如果 \(S\) 不满足上述的条件，那么我们就构造存在连续 \(((\) 或者 \())\) 的 \(T\)，即 \((((\ldots)))\ldots\)。

显然，只有 \(()\) 无法构造。

上述操作也可以更改为：

1. 特判 \(()\)；

2. 构造 \((((\ldots)))\ldots\)；

3. 判断是否为子串；

4. 是则输出，否则改为 \(()()()\ldots\)。

至于判断子串，直接判断 \(S\) 是否是由连续的 \((((\ldots\) 和连续的 \()))\ldots\) 拼接而成即可。

当然，也可以直接无脑 \(\mathtt{KMP}\)，复杂度可行。

时间复杂度：\(O(n)\)

对应AC代码

#define chatgpt "bits/stdc++.h"

#include chatgpt

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    string s;
    cin >> s;
    int n;
    n = s.size();
    if(s == "()"){
        cout << "NO\n";
    }else{
        cout << "YES\n";
        bool f = false;
        int ind = 0;
        for(;ind<n;ind++){
            if(s[ind] == ')'){
                break;
            }
        }
        for(;ind<n;ind++){
            if(s[ind] == '('){
                f = true;
                break;
            }
        }
        if(f){
            for(int i=0;i<n;i++) cout << "(";
            for(int i=0;i<n;i++) cout << ")";
            cout << '\n';
        }else{
            for(int i=0;i<n;i++) cout << "()";
            cout << '\n';
        }
    }
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

能让人想到 \(\mathtt{KMP}\) 还是很逆天的

B. Fancy Coins

题意

给定总额 \(m\) 元，购买下面所属的硬币，使 花哨硬币 花费数量尽可能少，并满足最后没有钱剩余：

1. 花费 \(1\) 元的硬币：\(a_1\) 个常规硬币，无限多个花哨硬币；
2. 花费 \(k\) 元的硬币：\(a_k\) 个常规硬币，无限多个花哨硬币

输出最少的数量。

思路

首先，既然要尽量不使用花哨硬币，我们自然会尽可能多使用 \(k\) 元的硬币。

因此，我们可以先算出全都使用 \(k\) 后的代价，然后将部分硬币换为用使用 \(1\)，从而得到答案。

显然我们不可以暴力搜索，但上述可以进行分类讨论推出式子。

1. \(a_0 + k \times a_k \geq m\)，此时我们可以发现，花费 \(k\) 元的常规硬币一定是够用的，而因为需要最后没有钱剩余，我们就需要比较我们还需多少个 \(1\) 元花哨硬币，而不是输出 \(0\)；

2. \(a_0 + k \times a_k < m\)，此时我们可以发现，我们还需使用 \(d = m - (a_0 + k \times a_k)\) 个硬币，那么我们尽可能多使用 \(k\)，剩余的用 \(1\)，然后和情况 \(1\) 一样，判断一下即可

这题也可以用三分搜索

时间复杂度：\(O(1)\)

对应AC代码

#define chatgpt "bits/stdc++.h"

#include chatgpt

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int m, k, a0, ak;
    cin >> m >> k >> a0 >> ak;
    int sum = a0 + k * ak;
    if (m <= sum) {
        cout << max(0ll, max(m - k * ak, m % k) - a0) << '\n';
        return;
    }
    int d = m - sum, w = d / k + d % k;
    int t = d % k == 0 ? 0 : k - d % k;
    if (a0 >= t) w = min(w, d / k + 1);
    cout << w << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

分讨分讨

C. Game on Permutation

题意

给定一个排列 \(p\) 以及一个标签，定义 \(A, B\) 之间的游戏为：

1. 当前标签位于 \(i\)；

2. 选定一个下标 \(j\)，满足 \(j < i, p_j < p_i\)；

3. 将标签移动到 \(j\)；

4. 不能移动 的一方 赢

现在，由 \(A\) 决定标签的初始位置，然后由 \(B\) 先手开始游戏。

如果 \(A\) 决定 \(i\) 为标签的初始位置，并满足它有必胜策略，那么该点 \(i\) 为 幸运点。

输出 幸运点 的个数。

思路

首先，形象地说，对于一个点 \(i\)，必胜的条件就是以 \(i\) 结尾的 最长 不一定连续 递增 子序列 的长度为 \(2\)。

上述条件可以转化为：当前位置 \(i\)，对应的值 \(p_i\) 满足：

1. 大于 \(p_{[1, i - 1]}, n + 1\) 中的最小值；

2. 小于 \(p_{[2, i - 1]}, n\) 中的最小值 \(+ 1\)

3. \(p_i \neq 1\)

可以使用数据结构维护，也可以直接用两个变量记录。

时间复杂度：\(O(n \log n)\)

对应AC代码

#define chatgpt "bits/stdc++.h"

#include chatgpt

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    set<int> st;
    st.emplace(n + 1);
    int ans = 0;
    int mn = n + 1;
    for(int i=1;i<=n;i++){
        if(*st.begin() < a[i]){
            if(mn > a[i] && a[i] != 1) ans ++;
            mn = min(mn, a[i] + 1);
        }
        st.emplace(a[i]);
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

丢两个线段树上去是最抽象的

D. Balanced String

题意

给定一个二进制字符串 \(s\)，定义一次操作为选定 \(i, j, i < j\) 并交换 \(s_i, s_j\)。

输出让字符串中所有长为 \(2\) 的 不一定连续 子序列中 \(01, 10\) 个数相等所需的最小操作数。

思路

首先，如果你想到了类似贪心的思路，请使用下面的强样例验证你的代码：

in: 0011110101001010000000000111100101011110100111001011000101111111010011001000110010110110001101110111
Out: 2

上述样例几乎叉掉了所有的贪心写法。

既然不可以用贪心，我们自然考虑 \(dp\)。

定义 \(dp[i][j][k]\) 为 前 \(i\) 个数中包含 \(j\) 个 \(0\) 和 \(k\) 个 \(01\) 串所需 修改 的最小数量，那么状态很好推：

1. 在 \(i\) 位置放上 \(1\)，那么会多出 \(j\) 个 \(01\) 串，此时 \(dp[i + 1][j][k + j] = dp[i][j][k] + p\)；

2. 在 \(i\) 位置放上 \(0\)，那么会多出 \(1\) 个 \(0\)，此时 \(dp[i + 1][j + 1][k] = dp[i][j][k] + p\)

上述的 \(p\) 取决于放上的数和原来位置的数是否相等，相等为 \(0\)，不等为 \(1\)。

那么，最后 \(dp[n][cnt0][cnt0 \times (n - cnt0)]\) 就是最少修改次数。

至于最后的答案，我们注意一下边界情况的赋值，那么就可以满足修改是成对的，最后答案就只需 \(÷2\)。

时间复杂度：\(O(n ^ 4)\)

对应AC代码

#define chatgpt "bits/stdc++.h"

#include chatgpt

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    s = " " + s;
    vector<vector<vector<int>>> dp(2, vector<vector<int>>(n + 1, vector<int>(n * n * 2 + 1)));
    int cnt0 = 0;
    for(int i=1;i<=n;i++){
        if(s[i] == '0') cnt0 ++;
        for(int j=0;j<i+1;j++){
            for(int p=0;p<=j * (i + 1 - j);p++){
                dp[1][j][p] = n;
            }
        }
        for(int j=0;j<i;j++){
            for(int p=0;p<=j * (i - j);p++){
                dp[1][j + 1][p] = min(dp[1][j + 1][p], dp[0][j][p] + (s[i] == '1'));
                dp[1][j][p + j] = min(dp[1][j][p + j], dp[0][j][p] + (s[i] == '0'));
            }
        }
        swap(dp[0], dp[1]);
    }
    cout << dp[0][cnt0][cnt0 * (n - cnt0) / 2] / 2 << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
//    cin >> t;
    while (t--) solve();
}

叉掉这么多人，直接从 \(-10\) 变成 \(+1\)。