Contestant. Rank 2205. Rating -13.

A. Garland

题意

给定 盏灯的颜色，颜色为 内的任意数字。初始状态所有灯均关闭，打开一盏灯的条件是之前打开的灯的颜色与其不一致，第一次可以打开任意一盏灯。输出将所有灯打开所需最小次数。

思路

首先，这题只有 盏灯。

所以，我们直接分类讨论即可。

我们先将灯按照颜色代码升序排序，那么如果第一个数和最后一个数相等，输出 ；

否则，前三个数相等或者后三个数相等时，需要 次；

否则， 次足矣。

时间复杂度：

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

void init(){}

void solve() {
    string s;
    cin >> s;
    sort(s.begin(), s.end());
    if(s[0] == s[3]) cout << -1 << '\n';
    else if(s[0] == s[2] || s[1] == s[3]) cout << 6 << '\n';
    else cout << 4 << '\n';
}

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

我居然没看到只有4个…

B. Points on Plane

题意

给定整数 ，代表当前有 个点。将这些点放入平面直角坐标系，满足坐标均为整数。在限制任意一对点的距离都严格大于 的条件下，输出最小的总代价。其中，对于一个点 ，单点的代价为 ，总代价为所有点的代价最大值。

思路

我们来固定 看 ：

1. ，那么 ；

2. ，那么 ；

归纳可得，对于 的所有正数取值， 的取值总数为 ；

同理， 为负数时， 的取值总数为 。

那么，我们可以得到总和 。

那么，最后的答案即为 。

注意精度问题即可。

时间复杂度：

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

void init(){}

void solve() {
    int n;
    cin >> n;
    int ans = sqrt(n);
    if(ans * ans < n) ans ++;
    cout << ans - 1 << '\n';
}

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

离谱的是在 C++ 17 下， 可以作为答案卡过去

C. Sum on Subarrays

题意

构造一个序列，满足所有连续子序列的和均不为 ，且和为正数的序列数量为给定值 。

思路

首先，我们不妨打表， 为 个数的连续子序列个数，即 。

那么，我们不难发现，。

那么，在 个数的基础上，我们再添加 个数，就可以等于 。

更具体地说，我们不妨在序列前面放上 个相同的正数 ，其中 为 中第一个不大于 的值。

那么，我们还需 个数，我们不妨在后面放一个负数 ，让 以这个数作为结尾的 子序列的和 为负数 的个数为 。

这样的话，以 为头，负数 为尾的子序列的和就是正数了。

剩下还有一些空位，我们填上负无穷大，也就是最小值 即可。

当然，正数 不能为 ，这样会让某个总和变为 ，那么我们取 即可。

在取 的条件下，负数 。

当然，我们用递增的序列取代这些相等的正数也是可以的。

时间复杂度：

对应AC代码1

#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;

vector<int> s = {0};

void init(){
    for(int i=1;i<=1000;i++)
        s.emplace_back(i *  (i + 1) / 2);
}

void solve() {
    int n, k;
    cin >> n >> k;
    int q = upper_bound(s.begin(), s.end(), k) - s.begin() - 1;
    int cnt = k - s[q];
    for(int i=0;i<q;i++) cout << 2 << ' ';
    if(cnt != 0) cout << -(q - cnt) * 2 - 1 << ' ', q ++;
    for(int i=q;i<n;i++) cout << -1000 << ' ';
    cout << '\n';
}

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

对应AC代码2

#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;

vector<int> s = {0};

void init(){
    for(int i=1;i<=1000;i++)
        s.emplace_back(i *  (i + 1) / 2);
}

void solve() {
    int n, k;
    cin >> n >> k;
    int q = 0;
    while(s[q + 1] <= k) q ++;
    for(int i=0;i<q;i++) cout << q - i + 1 << ' ';
    k -= s[q];
    if(k != 0) {
        cout << -1 * (s[q - k] + q - k + 1) << ' ';
        q ++;
    }
    for(int i=q;i<n;i++) cout << -1000 << ' ';
    cout << '\n';
}

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

我怎么就这么蠢.jpg

D. Binary String Sorting

题意

给定一个二进制字符串，规定操作为下面两个任选一：

1. 交换两个相邻元素；

2. 删掉一个元素

第一个操作的代价为 ；第二个操作的代价为 。

输出让整个字符串变为不递减序列的最小代价。

思路

首先，这题可以 ，但是我们不妨来想想怎么贪心。

我们下面有四种方案，取最小值即可：

1. 删掉所有的 ；

2. 删掉所有的 ；

3. 遍历所有的 ，将前面的 删掉，后面的 删掉；

4. 遍历所有的 ，若前面为 ，那么把这个 和当前的 交换，然后删去前面剩余的 ，以及后面的 。

前面三者是显然的，而对于第四个，我们不妨考虑其他的移动情况。

显然， 和 没必要交换； 不用管，因为满足递增； 交换即可；剩余的情况，我们都需要移动至少两次，那还不如删掉呢。

因此，贪心是成立的。

时间复杂度：

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

void init(){}

void solve() {
    int x = 1e12;
    string s;
    cin >> s;
    int n = s.size();
    s = " " + s;
    vector<vector<int>> pre(n + 1, vector<int>(2, 0));
    int cnt0  = 0;
    for(int i=1;i<=n;i++){
        int now = s[i] - '0';
        if(now == 0) cnt0 ++;
        pre[i][now] = pre[i - 1][now] + 1;
        pre[i][1 - now] = pre[i - 1][1 - now];
    }
    int ans = min(cnt0, n - cnt0) * (x + 1);
    for(int i=1;i<=n;i++){
        if(s[i] == '0') {
            ans = min(ans, (pre[i][1] + cnt0 - pre[i][0]) * (x + 1));
            if(s[i - 1] == '1') ans = min(ans, x + (pre[i][1] + cnt0 - pre[i][0] - 1) * (x + 1));
        }
    }
    cout << ans << '\n';
}

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

赛时一看到dp就溜了（（