Contestant. Rank 1719. Rating -8.

被诈骗咯

A. Forbidden Integer

题意

给定三个整数 \(n, k, x\)，在 \([1, k]\) 中任选除了 \(x\) 之外的其他数字，使所选数字的总和为 \(n\)。

思路

我们进行分讨。

首先，如果 \(k = 1\)，那么一定无解。

其次，如果 \(k = 2\)，那么我们分讨一下 \(x = 1, 2\) 的时候的情况，此时如果 \(n\) 为奇数，而 \(x = 1\)，那么无解。

最后，如果 \(k > 2\)，那么我们分讨一下：

\(x = 1\)，那么我们放 \(\frac{n}{2} - 1\) 个 \(2\)，然后再放上剩下的数即可等于 \(n\)；
否则，输出 \(n\) 个 \(1\)。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

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

void solve() {
    int n, k, x;
    cin >> n >> k >> x;
    if(k == 1) {
        cout << "NO\n";
        return;
    }
    if(k == 2){
        if(x == 1 && n % 2 == 1){
            cout << "NO\n";
            return;
        }
        if(x == 1){
            cout << "YES\n";
            cout << n / 2 << '\n';
            for(int i=0;i<n/2;i++) cout << 2 << ' ';
            cout << '\n';
        }else{
            cout << "YES\n";
            cout << n << '\n';
            for(int i=0;i<n;i++) cout << 1 << ' ';
            cout << '\n';
        }
    }else{
        if(x == 1){
            cout << "YES\n";
            cout << n / 2 << '\n';
            for(int i=0;i<n/2-1;i++) cout << 2 << ' ';
            if(n % 2 == 1) cout << 3 << '\n';
            else cout << 2 << '\n';
        }else {
            cout << "YES\n";
            cout << n << '\n';
            for(int i=0;i<n;i++) cout << 1 << ' ';
            cout << '\n';
        }
    }
}

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

为什么有这么复杂的分讨捏，为什么捏，为什么有人想写 \(dp\) 捏

B. Come Together

题意

给定 \(A, B, C\) 三个点的坐标，输出 \(A \rightarrow B, A \rightarrow C\) 的最短路中，重叠的格子最多可以有多少。

思路

我们对 \(x, y\) 坐标分别分讨。

对于 \(x\) 坐标：

如果 \(X_a \geq X_b \geq X_c\) 或 \(X_c \geq X_b \geq X_a\)，那么本坐标下需要移动 \(abs(X_b - X_a)\)；
如果 \(X_b \geq X_c \geq X_a\) 或 \(X_a \geq X_c \geq X_b\)，那么本坐标下需要移动 \(abs(X_c - X_a)\)；
否则，不需要移动

\(y\) 坐标同理。

最后因为算上起点和重点，所以再 \(+1\)。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

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

void solve() {
    int xa, ya, xb, yb, xc, yc;
    cin >> xa >> ya >> xb >> yb >> xc >> yc;
    int ans = 0;
    if((yc >= yb && yb >= ya) || (ya >= yb && yb >= yc)) ans += abs(yb - ya);
    else if((yb >= yc && yc >= ya) || (ya >= yc && yc >= yb)) ans += abs(yc - ya);
    if((xc >= xb && xb >= xa) || (xa >= xb && xb >= xc)) ans += abs(xb - xa);
    else if((xb >= xc && xc >= xa) || (xa >= xc && xc >= xb)) ans += abs(xc - xa);
    cout << ans + 1 << '\n';
}

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

无聊分讨，不过肯定可以归纳为一个式子

C. Strong Password

题意

给定一个字符串 \(s\)，以及两个长度均为 \(n\) 的字符串 \(l, r\)。

上述字符串均为 \([0, 9]\) 内数字组成的字符串。

构造一个字符串 \(t\)，满足下面的条件：

长度为 \(n\)；
不是 \(s\) 的子串；
\(t[i]\) 代表的数字在 \(l[i]\) 和 \(r[i]\) 之间。

思路

首先，我不拦着你写 \(dfs\)，你只要写得好，应该也许大概可以过。

我们考虑贪心。

首先，我们需要遍历字符串 \(s\)，因此我们用 \(p\) 变量记录我们下一次开始遍历的下标。

那么，我们遍历 \(t\) 的每一位。

对于每一位的所有可能数字，我们从 \(p\) 开始，找到所有数字第一次出现的下标。

最后，如果所有数字都出现了，我们就取下标的最大值，更新 \(p = mx + 1\)，否则我们就可以构造出一个不是子序列的字符串。

下面给出不太严谨的说明：

因为我们只需构造出一个满足条件的就可，那么我们不妨极端一点，对于每一位都尽可能向右取，这样如果还无法构造，就显然是 \(NO\) 了。

同样，这也方便了我们的构造。因为只要有一位找不出对应的字符，他就不是子序列。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

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

void solve() {
    string s;
    cin >> s;
    int n;
    cin >> n;
    string l, r;
    cin >> l >> r;
    int p = 0;
    vector<int> st(10);
    for(int i=0;i<n;i++){
        st.assign(10, inf);
        for(int j=p;j<s.size();j++){
            if(s[j] >= l[i] && s[j] <= r[i]) st[s[j] - '0'] = min(st[s[j] - '0'], j);
        }
        int mx = 0;
        for(int j=l[i] - '0';j<=r[i] - '0';j++){
            if(st[j] == inf){
                cout << "YES\n";
                return;
            }
            mx = max(mx, st[j]);
        }
        p = mx + 1;
    }
    cout << "NO\n";
}

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

为什么捏，为什么有人想写 \(dp\) 捏，为什么这个蠢比是我捏

D. Rating System

题意

给定一个非 \(0\) 序列，从左到右依次累加，达到 \(k\) 后，如果某一位累加得到的值小于 \(k\)，那么将当前累加之和改为 \(k\)。输出任意一个 \(k\)，使最后累加的和最大。

思路

首先，既然当达到 \(k\) 后，无论怎样减小都不会低于 \(k\)，那么就等效于两个等于 \(k\) 的前缀和之间的所有数都是可以无视的。

这可以等价于后缀和，因为后缀和表征了跳过部分数后的和，并且后缀和为负数时就不满足上面的条件。

那么，更具体地说，(前 \(k\) 个数的前缀和) 以及 (后 \(k\) 个数的后缀和的最大值) 之和的最大值就是答案。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define psi pair<string, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

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

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), pre(n + 1), suf(n + 2);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        pre[i] = pre[i - 1] + a[i];
    }
    for (int i = n; i >= 0; i--) suf[i] = suf[i + 1] + a[i];
    for (int i = n; i >= 0; i--) suf[i] = max(suf[i], suf[i + 1]);
    int mx = 0, ans = 0;
    for (int i = 0; i <= n; i++) {
        int res = pre[i] + suf[i + 1];
        if (res > mx) mx = res, ans = pre[i];
    }
    cout << ans << '\n';
}

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

有点抽象