Contestant_. Rank 245. Rating +76 (+326 -250).

A. Gift Carpet

题意

给定一个 \(n \times m\) 的字符矩阵，判断是否能找出四列，满足这四列按顺序分别包含 "v,i,k,a"。

思路

既然要按顺序，那么我们直接从左向右遍历，从 上一次找到的列 之后 开始 找下一个字符第一次出现的列 即可。

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

对应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, m;
    cin >> n >> m;
    vector<string> s(n);
    for(int i=0;i<n;i++){
        cin >> s[i];
    }
    int ind = 0;
    bool ok = false;
    string fd = "vika";
    for(int i=0;i<m;i++){
        bool f = false;
        for(int j=0;j<n;j++){
            if(s[j][i] == fd[ind]){
                f = true;
                break;
            }
        }
        if(f){
            ind ++;
        }
        if(ind == 4) {
            ok = true;
            break;
        }
    }
    cout << (ok ? "YES\n" : "NO\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();
}

一定要有序

B. Sequence Game

题意

对于长为 \(p\) 的序列 \(a\)，定义序列 \(b\) 的构造方式如下：

1. 将 \(a_1\) 放入序列 \(b\)；

2. 枚举 \(i \in [2, p]\)，如果 \(a_{i - 1} \leq a_i\)，那么将 \(a_i\) 放入序列 \(b\)。

现在，给定序列 \(b\)，构造出任意符合条件的序列 \(a\)，且满足 \(a\) 的长度不超过 \(b\) 长度的两倍。

思路

既然要满足 \(a_{i - 1} \leq a_i\)，那么如果我们遍历的时候发现 \(b_{i - 1} > b_i\)，我们直接在 \(b_i\) 前面多放一个 \(b_i\) 即可。

否则，我们就只需按顺序放入 \(b_i\)。

时间复杂度：\(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() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    vector<int> ans;
    ans.pb(a[1]);
    for(int i=2;i<=n;i++) {
        if (a[i] >= a[i - 1])ans.pb(a[i]);
        else {
            ans.pb(a[i]);
            ans.pb(a[i]);
        }
    }
    cout << ans.size() << '\n';
    for(auto e : ans) cout << e << ' ';
    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();
}

放 \(1\) 应该也是可以的

C. Flower City Fence

题意

给定不递增序列 \(a\)，\(a_i\) 代表从左往右第 \(i\) 列方块的高度。

判断整个图形是否与过左下角的对角线对称，如下图：

思路

显然，如果某一列的高度为 \(a_i\)，那么将其横着放后，\([1, a_i]\) 区域内的高度都会 \(+1\)。

因而，我们考虑差分，最后比较高度即可。

注意特判，防止数组越界。

时间复杂度：\(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() {
    int n;
    cin >> n;
    vector<int> a(n + 1), d(n + 2);
    for(int i=1;i<=n;i++) cin >> a[i];
    if(a[1] > n){
        cout << "NO\n";
        return;
    }
    for(int i=1;i<=n;i++){
        d[1] ++;
        d[a[i] + 1] --;
    }
    for(int i=1;i<=n;i++){
        d[i] += d[i - 1];
        if(a[i] != d[i]){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\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. Ice Cream Balls

题意

定义 \(<x, y>\) 为无序对，即 \(<2,3>\ =\ <3,2>, <1,1>\ =\ <1,1>\)。

对于一个序列 \(a\)，其不同无序对的个数是确定的。

现在，给定不同的无序对的个数，输出序列 \(a\) 的最短长度。

思路

令序列 \(a\) 中共有 \(x\) 种数字，其中 \(y\) 种数字的数量 \(\geq 2\)，那么 \(cnt = C_x^2 + y\)。

我们可以二分，或者求出接近正解的 \(x\) 的值。

化简式子，我们可以得到 \(x(x-1) = 2 \times (cnt - y)\)。

可得 \(x \geq \sqrt {2 \times cnt}\)。

然后我们暴力求出正解即可。

时间复杂度：\(O(玄学)\)

对应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;

template<class T> T ex_sqrt(T x) { //返回精度更高的sqrt
    T sqrtX = sqrt(x) - 1;
    while (sqrtX + 1 <= x / (sqrtX + 1)) sqrtX++;
    return sqrtX;
}

void solve() {
    int n;
    cin >> n;
    int k = max(0ll, ex_sqrt(2 * n));
    while (k * (k - 1) <= 2 * n) k++;
    k --;
    k += (n - k * (k - 1) / 2);
    cout << k << '\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();
}

糟糕的题面

E. Kolya and Movie Theatre

题意

给定序列 \(a\)，定义可从中最多选 \(m\) 个元素，价值为 \(a_i - d \times t\)，其中 \(d\) 给定，\(t\) 为距上一个选择的元素的下标差。

序列下标从 \(1\) 开始，特别地，在选择之前，"第 \(0\) 个元素默认被选择"。

输出最大价值之和。

思路

题目等价于：选择最多 \(m\) 个元素，总和为 \(sum\)，其中最后一个元素的下标为 \(p\)，最后答案即为 \(sum - d \times p\)。

最后一个元素的下标是可以枚举的，那么我们只需快速算出前 \(p\) 个元素中最大的前 \(m\) 个最大数的和即可。

我们考虑使用 \(\mathtt{multiset}\) 维护即可。

注意长度超过 \(m\) 后的增删操作。

时间复杂度：\(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, m, d;
    cin >> n >> m >> d;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    int ans = 0;
    multiset<int> st;
    int sum = 0;
    for(int i=1;i<=n;i++){
        if(a[i] < 0) continue;
        if(st.size() == m){
            if(*st.begin() > a[i]) continue;
            sum -= *st.begin();
            st.extract(st.begin());
        }
        st.emplace(a[i]);
        sum += a[i];
        ans = max(ans, sum - d * 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();
}

题面还是看了好久才看懂

F. Magic Will Save the World

题意

给定两种法术，每一个时刻，两种法术分别会提高 \(w, f\) 点。

给定 \(n\) 个怪物，消灭第 \(i\) 个怪物需要 \(a_i\) 点法术，且不可以同时使用两种法术。

输出最早在哪个时刻能把所有怪消灭。

思路

题目等价于：输出最小的\(t\)，满足对于容量为 \(w \times t\) 的背包 \(1\) 和容量为 \(f \times t\) 的背包 \(2\)，恰好能分别将所有物品装下。

那么如果 \(t\) 更大，能装下的物品自然就更多，满足单调性。

因而我们考虑二分答案。

在检查答案的时候，我们可以直接用 \(\mathtt{bitset}\) 优化 \(\mathtt{01}\) 背包。

时间复杂度：\(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 w, f, n;
    cin >> w >> f >> n;
    vector<int> a(n + 1);
    int sum = 0;
    bitset<1000010> dp;
    dp.set(0);
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum += a[i];
        dp |= (dp << a[i]);
    }
    auto check = [&](int mid) -> bool{
        for(int i=0;i<=sum;i++){
            if(dp[i]) {
                if((i <= w * mid && sum - i <= f * mid) || (sum - i <= w * mid && i <= f * mid)){
                    return true;
                }
            }
        }
        return false;
    };
    int l = 1, r = 1e9, mid;
    while(l < r){
        mid = (l + r) >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << '\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();
}

其实不用这两个优化好像也行

G. The Great Equalizer

题意

对于一个数组，定义其 值 的计算方式如下：

1. 升序排序并去重；

2. 如果数组长度等于 \(1\)，那么跳出循环，剩下的元素就是 数组的值；

3. 将 \(\{n, n - 1, \ldots , 1\}\) 依次加到数组各个元素上，其中 \(n\) 为数组当前的长度

现在，对于 \(q\) 次 非独立 询问，每次询问给定 \(i, x\)，并将数组的第 \(i\) 个元素修改为 \(x\)，输出修改后 数组的值。

思路

我们不妨打表，可以发现，每一次循环后，数组的最大相邻元素差值 恰好减少了 \(1\)。

那么，循环的次数只和 数组的最大相邻元素差值 有关。

至于最大的元素，从值的角度看，可以发现它始终是最大的，因而最后他被加上了 数组的最大相邻元素差值。

因而，我们可以发现规律：最后的答案为 数组的最大相邻元素差值 \(+\) 数组的最大元素。

至于维护答案，我们可以用两个 \(\mathtt{multiset}\)，其中第一个维护值，第二个维护差值。

我们可以发现，修改一个元素，等价于删掉原来的元素，并加入一个新元素。

那么，以加入元素为例，我们在 \(a, b\) 中间插入一个 \(c\)，那么差值集合就需要删掉 \(b - a\)，并添加 \(b - c, c - a\)。当然我们需要判断插入的位置，因为可能会插在序列的头部或者尾部。

对于元素位置的获取，其实是很方便的，因为 \(\mathtt{insert, emplace}\) 方法都会返回插入后元素的位置。

同样的，对于删除，我们只需执行相反操作即可。

时间复杂度：\(O((n + 2q) \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 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() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    multiset<int> dis{0}, val;
    for(int i=1;i<=n;i++) cin >> a[i];
    //multiset模拟链表
    auto add = [&](int x) -> void{
        auto cur = val.ep(x), nxt = next(cur);
        if(cur != val.begin()){
            dis.ep(x - *prev(cur));
        }
        if(nxt != val.end()){
            dis.ep(*nxt - x);
        }
        if(cur != val.begin() && nxt != val.end()){
            dis.extract(*nxt - *prev(cur));
        }
    };
    auto del = [&](int x) -> void{
        auto cur = val.find(x), nxt = next(cur);
        if(cur != val.begin()){
            dis.extract(x - *prev(cur));
        }
        if(nxt != val.end()){
            dis.extract(*nxt - x);
        }
        if(cur != val.begin() && nxt != val.end()){
            dis.ep(*nxt - *prev(cur));
        }
        val.erase(cur);
    };
    for(int i=1;i<=n;i++) add(a[i]);
    int q;
    cin >> q;
    while(q --){
        int x, y;
        cin >> x >> y;
        del(a[x]);
        a[x] = y;
        add(a[x]);
        cout << *val.rbegin() + *dis.rbegin() << ' ';
    }
    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();
}

其实就像链表一样吧（?