Contestant. Rank 1761. Rating +54.

A. Lame King

题意

给定一个坐标系，其中 。给定一个坐标 ，输出按规定从 走到 需要的最短时间。

规定若需要连续从相同方向移动，需要间隔一秒。

思路

首先，若我们需要一直向右，那么停留一秒绝对比向垂直方向绕路快，所以，我们不妨以折线的方式移动，直到横坐标或纵坐标等于终点时，向同一方向间隔移动。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

void init(){}

void solve() {
    int a, b;
    cin >> a >> b;
    a = abs(a), b = abs(b);
    cout << (a + b) + (a != b ? abs(a - b) - 1 : 0) << '\n';
}

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

画个图的事情（（

B. Vaccination

题意

对于 个病人，每个病人需要在 时间内被扎一针。在某个时间点 ，可以拿出一个包含 个剂量的包装，这个包装会在 时过期。给定整数 ，输出需要拿出的包装的最小数量。

思路

为了要当前的包装可以包括更多的人，我们不妨在某一个病人的 时刻拿出包装，并枚举后面有多少个 小于 ，这样即可贪心地求出最小值。

就这样，没了。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

void init(){}

void solve() {
    int n, k, d, w;
    cin >> n >> k >> d >> w;
    int ans = 0;
    vector<pii> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i].first;
        a[i].second = a[i].first + w;
    }
    int i = 0;
    while(i < n){
        int l = a[i].second, r = l + d;
        int now = i;
        for(int j=0;j<k;j++){
            if(i + j >= n || a[i + j].first > r) break;
            now ++;
        }
        ans ++;
        i = now;
    }
    cout << ans << '\n';
}

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

这还需要证明吗，这还需要证明吗（

C. Pull Your Luck

题意

给定一个圆盘，按顺序写好了 ，换言之， 相邻。规定可以转动 秒，第一秒将当前值增加 ，第二次增加 ，以此类推。对于给定的起点，输出是否可以进行一次 秒的转动，使终点为 。

思路

首先，我们很容易列出一个式子：

但这个式子推不了什么。

有趣的是，若我们一直循环加上数的话，在取到 之后，所有数均会变小，但值得注意的是这些数因均相邻而出现了周期。

因而，在一个周期内，若出现了 ，输出即可。能保证最后的复杂度足够小。

时间复杂度：不大就对了

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

void init(){}

void solve() {
    int n, x, p;
    cin >> n >> x >> p;
    int cur = x;
    for(int i=1;i<=min(p, 2*n);i++){
        cur = (cur + i) % n;
        if(cur == 0) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

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

捏吗，一直在想怎么搞式子

D. Accommodation

题意

给定 个长度为 的二进制串，满足 ，将字符串分割为 个长度为 的子串和 个长度为 的子串。输出所有含 子串个数总和的最大值和最小值。

思路

若我们需要让个数尽可能大，我们当然希望将 分割开，也就是构造非 的大窗，那么，我们不妨枚举所有含有 的可能的大窗，拿掉这些后，剩余的作为小窗，即可让个数尽可能大。

相反地，要让个数尽可能小，我们就希望尽可能不将 分割开，也就是主动构造为 的大窗，这时，能构造多少个， 的个数就能减少多少。

有趣的是，只要分割出 个长度为 的子串，剩余的一定长度均为 ，且恰好 个；反之亦然。

当然，如果这题数据量小的话，可以 。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

void init(){}

void solve() {
    int n, m;
    cin >> n >> m;
    int mn = 0, mx = 0;
    while (n--) {
        string s;
        cin >> s;
        int c1 = 0, c2 = 0, tot = 0;
        for (int i = 0; i < m; i++) tot += s[i] - '0';
        for (int i = 0; i < m - 1; i ++)
            if (s[i] == '1' && s[i + 1] == '1') c1 ++, i ++;
        for (int i = 0; i < m - 1; i ++)
            if (s[i] == '0' || s[i + 1] == '0') c2 ++, i ++;
        mn += tot - min(c1, m / 4);
        mx += tot - max(0ll, m / 4 - c2);
    }
    cout << mn << ' ' << mx << '\n';
}

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

似了，在想怎么dp，贪心还没贪对（一直想着拆