Contestant(alt). Rank 993. Rating +168.

A. Insert Digit

题意

给定一个数 \(a\)，以及一个 \([0, 9]\) 的数 \(b\)，将 \(b\) 插入 \(a\)，输出最大的数。

思路

我们从后往前找出最后一个小于 \(b\) 的数，放在这个数前面就可以让结果最大。

当然，如果没有比它小的数，直接放在最后即可。

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

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

void solve() {
    int n;
    char d;
    string w;
    cin >> n >> d >> w;
    int idx = n;
    for(int i=n-1;i>=0;i--){
        if(w[i] < d) {
            idx = i;
        }
    }
    for(int i=0;i<n;i++){
        if(i == idx) cout << d;
        cout << w[i];
        if(i == n - 1 && idx == n) cout << d;
    }
    cout << '\n';
}

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

很简单的贪心捏（我怎么做了这么久

B. Conveyor Belts

题意

给定一个 \(n \times n\) 的矩阵，\(n\) 为偶数。将矩阵从外向里分层为 \(\frac{n}{2}\) 圈，如下图所示：

给定两个点，输出从一个点走到另一个点需要跨越的边界的最少数量。

思路

首先，这个图是对称的，那么我们只需把点全都对阵到左上角即可。

那么，我们规定最外层是第 \(1\) 层，以此类推，我们可以得到：

对于 \((x, y)\)，它位于第 \(\min(x, y)\) 层。

那么，我们取差值的绝对值即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

void solve() {
    int n, x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    if(x1 > n / 2) x1 = n - x1 + 1;
    if(y1 > n / 2) y1 = n - y1 + 1;
    if(x2 > n / 2) x2 = n - x2 + 1;
    if(y2 > n / 2) y2 = n - y2 + 1;
    int i1 = min(x1, y1), i2 = min(x2, y2);
    cout << abs(i1 - i2) << '\n';
}

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

我怎么那么蠢，会卡这么久（

C. Restore the Array

题意

定义对于一个数组 \(a\)，循环遍历 \([1, n-1]\)，将所有 \(\max(a_i, a_{i + 1})\) 提取出来作为新的数组。

现在给定操作后的数组，构建出一个可能的原数组，保证一定能构造出。

思路

记原数组为 \(a\)，新数组为 \(b\)。

那么，我们来考虑 \(\max(\min(b_{i - 1}, b_i), \min(b_i, b_{i + 1}))\)，我们可以经过分类讨论得到最后的答案为 \(b_i\)。

也就是说，\(a_i = \min(b_i, b_{i + 1})\)。

对于边界，\(\max(b_1, \min(b_1, b_2)) = b_1, \max(\min(b_{n - 2}, b_{n - 1})) = b_{n - 1}\)。

也就是说，\(a_1 = b_1, a_n = b_{n - 1}\)。

按照上述结论构造即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n - 1);
    for(int i=0;i<n - 1;i++) cin >> a[i];
    for(int i=0;i<n;i++){
        if(i == 0) cout << a[0] << ' ';
        else if(i == n - 1) cout << a[n - 2] << ' ';
        else cout << min(a[i - 1], a[i]) << ' ';
    }
    cout << '\n';
}

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

有煞笔，我不说是谁

D. Umka and a Long Flight

题意

记 \(F(x)\) 为第 \(x\) 个斐波那契数。给定长为 \(F(n)\)，宽为 \(F(n + 1)\) 的矩阵，矩阵中 \((x, y)\) 被标记。将矩阵分割为 \(n - 1\) 个子矩阵，满足下面的条件：

  1. 被标记的点位于一个长为 \(1\) 或 宽为 \(1\) 的矩阵内

  2. 无长宽均重复的矩阵

  3. 所有矩阵的边长都是斐波那契数

输出是否可以满足条件。

思路

显然，要变为边长为 \(1\) 的矩阵，我们就需要按斐波那契数的计算方式分割。

我们将宽切割为 \(F(n), F(n - 1)\)，判断点落在哪个区域，为方便计算，我们直接改变点的坐标，让点落在较小的区域即可。

切割之后，我们翻转横纵坐标即可。

这样操作的话，我们可以发现，\(y \in (F(n) - F(n - 1), F(n - 1)]\) 时， 也就是卡在中间的情况，这时最后构造出的分隔方法无法满足条件 \(2\)。

如上，循环判断即可。

斐波那契数可以预先初始化。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

int f[50];

void init(){
    f[1] = f[2] = 1;
    for(int i=3;i<=49;i++) f[i] = f[i - 1] + f[i - 2];
}

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    int t = n + 1;
    while(t > 1){
        if(y <= f[t] && y > f[t + 1] - f[t]){
            cout << "NO\n";
            return;
        }
        if(y >= f[t]) y -= f[t];
        t --;
        swap(x, y);
    }
    if(t == 1) cout << "YES\n";
}

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

复杂但是很形象之

E. Living Sequence

题意

去掉所有包含 \(4\) 的数字，从大到小排序后，对于所有询问，输出第 \(x\) 个数。

思路

等价于去掉 \(9\)，也就是说，在 \(8\) 的时候就进一了，不难发现就是 \(9\) 进制。

转 \(9\) 进制后，将所有大于等于 \(4\) 的数字加一即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e5 + 10, inf = 0x3f3f3f3f3f3f3f3f, mod = 1e9 + 7;

void init(){}

void solve() {
    int n;
    cin >> n;
    vector<int> ans;
    while(n > 0){
        ans.emplace_back(n % 9);
        n /= 9;
    }
    for(int i=ans.size()-1;i>=0;i--){
        if(ans[i] >= 4) cout << ans[i] + 1;
        else cout << ans[i];
    }
    cout << '\n';
}

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

为什么这题比 A 还简单（x

F. Is It Flower?

题意

定义 \(k\) 环如下：

  1. 中心为一个 \(k\) 个点组成的环；

  2. 中心环上每一个点都作为另一个单独的 \(k\) 个点组成的环的顶点

\(3\) 环如下图：

现在，给定一个图，判断是否是 \(k\) 环图。

思路

首先我们可以进行特判，\(k\) 环图的点的数量为 \(k ^ 2\)，边的个数为 \(k + k ^ 2\)，且中间环上所有点的度数都是 \(4\)，其余点的度数都是 \(2\)。

后两个条件不好判断，但我们可以先判断是否存在度数不是 \(2, 4\) 的点。

特判结束后，我们考虑找出中间环，然后删掉这个环上的边（保留顶点），最后就会剩下 \(k\) 个点数为 \(k\) 的环。

因而，我们需要做的就是：

  1. 判断是否只存在一个连通块；

  2. 删去中间的环上的边，保留顶点；

  3. 枚举所有剩下的环，判断长度

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

对应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 = 1e6 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

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, m;
    cin >> n >> m;
    vector<vector<int>> e(n + 1);
    for(int i=0;i<m;i++){
        int u, v;
        cin >> u >> v;
        e[u].pb(v), e[v].pb(u);
    }
    if(ex_sqrt(n) * ex_sqrt(n) != n){
        cout << "NO\n";
        return;
    }
    int k = ex_sqrt(n);
    if(k + k * k != m){
        cout << "NO\n";
        return;
    }
    for(int i=1;i<=n;i++){
        if(e[i].size() != 2 && e[i].size() != 4){
            cout << "NO\n";
            return;
        }
    }
    vector<bool> st(n + 1);
    auto sz = [&](auto self, int x) -> int{
        st[x] = true;
        int ans = 1;
        for(auto y : e[x]){
            if(st[y]) continue;
            ans += self(self, y);
        }
        return ans;
    };
    if(sz(sz, 1) != n){
        cout << "NO\n";
        return;
    }
    for(int i=1;i<=n;i++) {
        if (e[i].size() == 2) continue;
        for (int j = 0; j < e[i].size(); j++) {
            int x = e[i][j];
            if (e[x].size() == 2) continue;
            swap(e[i][j], e[i].back());
            e[i].pop_back();
            j --;
            for (auto &y: e[x]) {
                if (y == i) {
                    swap(y, e[x].back());
                    e[x].pop_back();
                    break;
                }
            }
        }
    }
    st = vector<bool>(n + 1);
    for(int i=1;i<=n;i++){
        if(st[i]) continue;
        if(sz(sz, i) != k){
            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();
}

《2100》难度

G1. Vlad and the Nice Paths (easy version)

详见 \(G2\)，区别是本题可以 \(O(n ^ 3)\) 通过

G2. Vlad and the Nice Paths (hard version)

题意

给定一个序列 \(a\)，以及一个整数 \(k\)，从左向右任意取 \(p\) 个数，满足下面的条件：

  1. \(p\) 是 \(k\) 的倍数；

  2. 将取出的数按照 \(k\) 长度为一组分组，满足每一组内所有元素相等

输出最大的 \(p\) 对应的方案数。

思路

首先，如果我们一组一组考虑，可以发现答案是具有递推性的。

递推性不止在方案数上，对于 \(p\) 的大小也是。

我们先来看如何递推 \(p\)，且令 \(p[i]\) 为当前位置 \(p\) 的最大值：

  1. 枚举 \(i\) 作为当前位，并从 \(i - 1\) 开始向前枚举 \(j\) 作为当前组的开头，也就是说当前组为 \([j, i]\)，其中 \(j, i\) 分别为左右端点；

  2. 在枚举 \(j\) 的时候，统计 \(a_{[j ,i]}\) 中有多少元素和 \(a_i\) 相同，我们记数量为 \(cnt\)；

  3. 如果 \(cnt = k\)，那么我们形成了一个独立的组 \([j, i]\)，此时我们直接从 \(p[j - 1]\) 递推答案，\(p[i] = p[j - 1] + 1\)；

  4. 如果 \(cnt \geq k\)，那么此时存在从 \([j ,i]\) 里挑 \(k\) 个相同数的选择，但是我们也可以在 \([j ,i]\) 里挑一个数作为开头，而且理论上后者可能更大，因而如果我们发现递推的时候，上一个状态 \(p[j - 1] + 1 < p[i]\)，我们就可以直接停止再向前枚举 \(j\) 了；

  5. 注意我们一开始的定义，因为 \(p[i]\) 为当前位置 \(p\) 的最大值，所以我们需要和 \(p[i - 1]\) 取最大值，从而递推下来，保证 \(p\) 序列一定是不递减的。

那么对于方案数，我们记前 \(i\) 个数的最大 \(p\) 对应的方案数为 \(dp[i]\)，来看看我们刚才是如何递推的：

  1. 如果 \(p[i] = p[i - 1]\)，那么显然 \(dp[i] += dp[i - 1]\)；

  2. 如果在枚举的时候，\(cnt \geq k\)，那么我们可以以 \(j, i\) 为开头和结尾，中间任选 \(k - 2\) 个，那么方案数可以乘上 \(C_{cnt - 2}^{k - 2}\)

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

对应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 = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

int C[5010][5010];

void init(){
    // 预处理组合数
    for (int i = 0; i <= 5000; i++) {
        C[i][0] = 1;
        C[i][i] = 1;
        for (int j = 1; j < i; j++) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }
    }
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    vector<vector<int>> dp(n + 1, vector<int>(2)); //0为考虑组合的答案，1为记录可以形成最多多少组
    dp[0][0] = 1;
    for(int i=1;i<=n;i++){
        int cnt = 1;
        for(int j=i-1;j>=1;j--){
            if(a[j] == a[i]){
                cnt ++;
                if(cnt == k){ //可以形成新的组合[j,i]
                    dp[i][1] = dp[j - 1][1] + 1;
                }
                if(cnt >= k){
                    if(dp[j - 1][1] < dp[i][1] - 1) break;
                    dp[i][0] += dp[j - 1][0] * C[cnt - 2][k - 2] % mod;
                    dp[i][0] %= mod;
                }
            }
        }
        if(dp[i][1] < dp[i - 1][1]){
            dp[i][0] = 0, dp[i][1] = dp[i - 1][1];
        }
        if(dp[i][1] == dp[i - 1][1]){
            dp[i][0] += dp[i - 1][0];
            dp[i][0] %= mod;
        }
    }
    cout << dp[n][0] << '\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();
}

也是一眼就觉得是 \(dp\)，一眼写半天写不出来