Contestant'. Rank 785. Rating +41.

A. The Good Array

题意

定义满足下面条件的二进制数组 \(a\) 是好的：

枚举 \(i \in [1, n]\)，前 \(i\) 个数至少有 \(\lceil \frac{i}{k} \rceil\) 个为 \(1\)，后 \(i\) 个数至少有 \(\lceil \frac{i}{k} \rceil\) 个为 \(1\)。

给定 \(k\)，输出好数组中 \(1\) 的最少个数。

思路

首先，第一个和最后一个一定是 \(1\)。

那么，对于前 \(n - 1\) 个数，至少有 \(\lceil \frac{n - 1}{k} \rceil\) 个 \(1\)。

因此，答案即为 \(\lceil \frac{n - 1}{k} \rceil + 1\)。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, 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;
    cin >> n >> k;
    cout << (n - 1) / k + ((n - 1) % k == 0 ? 0 : 1) + 1 << '\n';
}

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

抽象

B. Lamps

题意

给定 \(n\) 盏灯，一开始所有灯都是熄灭的。

每盏灯有两个参数 \(a_i, b_i\)，有三个状态：亮、灭、坏。

定义一次操作如下：

  1. 选择一个没坏的熄灭的灯 \(i\)，将其打开，得到 \(b_i\) 个积分；

  2. 记 \(x\) 为上述操作后的没坏的亮的灯的个数，将所有满足 \(a_p \leq x\) 的灯砸坏，无论是否灯打开。

任意次操作后，输出最大积分数。

思路

既然我们会把 \(a_i\) 小的灯砸烂，那么我们不妨直接从 \(a_i\) 小的开始放。

我们从小到大枚举所有 \(a_i\) 的值，然后将 \(a\) 值等于 \(a_i\) 的所有灯按照 \(b_i\) 降序排列。

我们依次取出，不难发现，当我们取出 \(a_i\) 个灯的时候刚好满足条件，此时所有灯都会被砸烂。

因而，我们枚举 \(a_i\) 的值，对前 \(a_i\) 个数的 \(b_i\) 求和即可。

比较省事的方法是用 \(n\) 个优先队列。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, 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<priority_queue<int, vector<int>, less<>>> q(n + 1);
    for(int i=0;i<n;i++){
        int x, y;
        cin >> x >> y;
        q[x].emplace(y);
    }
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(q[i].empty()) break;
            ans += q[i].top();
            q[i].pop();
        }
    }
    cout << ans << '\n';
}

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

写法有点抽象

C. Insert Zero and Invert Prefix

题意

给定一个二进制序列 \(a\)，通过下面的 \(n\) 次操作，将一个空序列 \(b\) 变为 \(a\)：

  1. 选择一个下标 \(i\)；

  2. 将 \([1, i]\) 内所有元素取反；

  3. 在 \(i\) 的后面插入一个 \(0\)

用选择的下标来表征每次操作，输出满足条件的一个方案。

思路

首先，显然我们无法将序列的最后一个数变为 \(1\)，因为我们一定会在取反后插入一个 \(0\)。

其次，举个例子，对于 \(1\ 1\ 0\)，最简单的方法是：

  1. 先在开头执行两次操作，也就是 \(0\ 0\)，此时序列为 \(0\ 0\)；

  2. 在结尾执行一次操作，也就是 \(2\)，此时序列为 \(1\ 1\ 0\)。

更复杂地，对于任意 \([\, \overbrace{1, 1, \ldots, 1}^{k}, 0 \,]\)，我们都可以先放入 \(k\) 个 \(0\)，最后在 \(k\) 位置执行一次操作，将前面放入的 \(0\) 全部变为 \(1\)，最后放入一个 \(0\)。

有趣的是，我们的操作对后面的元素是无影响的，也就是说，我们只需将 \(a\) 拆分成若干个上述形式的段，然后从右向左执行操作即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, 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);
    for(int i=1;i<=n;i++) cin >> a[i];
    if(a[n] == 1){
        cout << "NO\n";
        return;
    }
    cout << "YES\n";
    int cnt = 0;
    for(int i=n-1;i>=0;i--){
        if(a[i] == 0){
            cout << cnt << ' ';
            cnt = 0;
        }else {
            cnt ++;
            cout << 0 << ' ';
        }
    }
    cout << '\n';
}

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

比前面的题好想多了（

D. Ball Sorting

题意

给定一个 \(n\) 的排列 \(a\)，对于整数 \(k\)，按照下面的操作进行排序：

  1. 在排列中任意添加 \(k\) 个 \(0\)；

  2. 在一次操作中，可选择一个和 \(0\) 相邻的元素，并将其移动到任何位置。

对于 \(k \in [1, n]\)，输出第二种操作最少需要几次，才能让排列升序。

思路

首先，既然需要最少操作，不妨找到最长递增子序列，因而我们会发现，我们只需用该序列的元素将排列分段，每一段放上一个 \(0\)，即可让需要的 \(0\) 个数最少。如果个数不够，那怎么去掉呢？如何优先选择呢？

上面的思路很显然，但存在一种情况：有多个最长递增子序列。因而，这种 "暴力" 的方法不可行。

既然上面的操作需要 \(dp\) 了，我们不妨想想如何用 \(dp\) 直接解决。

上面，我们提到了分段的概念，那么我们可以将其应用到单个元素的状态区分上。

对于一个元素，他有下面三种状态：

  1. 和它相邻的元素比他小，那么它可以作为前面那个元素所在递增段的一部分；

  2. 和他前面不相邻的元素比他小，那么它可以成为新的一个递增段；

  3. 前面没有一个元素比他小，那么它注定会被移动

因而，我们定义 \(dp[i][j]\) 为前 \(i\) 个位置分了 \(j\) 段，可得出下面的状态转移方程：

  1. 如果 \(a[i - 1] < a[i]\)，那么 \(dp[i][j] = dp[i - 1][j]\)；

  2. 对于 \(p \in [0, i - 1]\)，如果 \(a[k] < a[i]\)，那么 \(dp[i][j] = \min(dp[i][j], dp[k][j - 1] + i - k - 1)\)，其中 \(i - k - 1\) 为 \(i, k\) 之间元素的数量。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define pci pair<char, 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 + 2);
    a[n + 1] = inf;
    vector<vector<int>> dp(n + 2, vector<int>(n + 1, inf));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        dp[0][i] = 0;
    }
    for(int i = 1; i <= n + 1; i ++){ //遍历到哪个元素
        for(int j = 0; j <= n; j ++){ //分多少块
            if(a[i - 1] < a[i]) dp[i][j] = dp[i - 1][j]; //相邻满足递增，不分块
            if(j > 0) for(int k = 0; k < i; k ++) if(a[k] < a[i]) dp[i][j] = min(dp[i][j], dp[k][j - 1] + (i - k - 1)); //不相邻，分块
        }
    }
    for(int j = 1; j <= n; j ++) cout << dp[n + 1][j] << ' ';
    cout << '\n';
}

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

被一开始的思路卡死了