Contestant. Rank 1755. Rating +54.
A. Lame King
题意
给定一个坐标系，其中 \(x \in [-100, 100], y \in [-100, 100]\)。给定一个坐标 \([s, t]\)，输出按规定从 \([0, 0]\) 走到 \([s, t]\) 需要的最短时间。
规定若需要连续从相同方向移动，需要间隔一秒。
思路
首先，若我们需要一直向右，那么停留一秒绝对比向垂直方向绕路快，所以，我们不妨以折线的方式移动，直到横坐标或纵坐标等于终点时，向同一方向间隔移动。
时间复杂度：\(O(1)\)
对应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
题意
对于 \(n\) 个病人，每个病人需要在 \([t_i, t_i + w]\) 时间内被扎一针。在某个时间点 \(x\)，可以拿出一个包含 \(k\) 个剂量的包装，这个包装会在 \(x + d + 1\) 时过期。给定整数 \(n, k, d, w\)，输出需要拿出的包装的最小数量。
思路
为了要当前的包装可以包括更多的人，我们不妨在某一个病人的 \(t_i + w\) 时刻拿出包装，并枚举后面有多少个 \(t_j\) 小于 \(t_i + w + d\)，这样即可贪心地求出最小值。
就这样，没了。
时间复杂度：\(O(n)\)
对应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
题意
给定一个圆盘，按顺序写好了 \(0, 1, 2, ..., n - 1\)，换言之，\(0, n - 1\) 相邻。规定可以转动 \(p\) 秒，第一秒将当前值增加 \(p\)，第二次增加 \(p - 1\)，以此类推。对于给定的起点，输出是否可以进行一次 \([1, p]\) 秒的转动，使终点为 \(0\)。
思路
首先，我们很容易列出一个式子：
\(n - x + kn = \frac{p(p+1)}{2}\)
但这个式子推不了什么。
有趣的是，若我们一直循环加上数的话，在取到 \(n-1\) 之后，所有数均会变小，但值得注意的是这些数因均相邻而出现了周期。
因而，在一个周期内，若出现了 \(0\)，输出即可。能保证最后的复杂度足够小。
时间复杂度：不大就对了
对应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
题意
给定 \(n\) 个长度为 \(m\) 的二进制串，满足 \(m \bmod 4 = 0\)，将字符串分割为 \(\frac{m}{4}\) 个长度为 \(2\) 的子串和 \(\frac{m}{2}\) 个长度为 \(1\) 的子串。输出所有含 \(1\) 子串个数总和的最大值和最小值。
思路
若我们需要让个数尽可能大，我们当然希望将 \(11\) 分割开，也就是构造非 \(11\) 的大窗，那么，我们不妨枚举所有含有 \(0\) 的可能的大窗，拿掉这些后，剩余的作为小窗，即可让个数尽可能大。
相反地，要让个数尽可能小，我们就希望尽可能不将 \(11\) 分割开，也就是主动构造为 \(11\) 的大窗，这时，能构造多少个，\(1\) 的个数就能减少多少。
有趣的是，只要分割出 \(\frac{m}{4}\) 个长度为 \(2\) 的子串，剩余的一定长度均为 \(1\)，且恰好 \(\frac{m}{2}\) 个；反之亦然。
当然，如果这题数据量小的话，可以 \(dp\)。
时间复杂度：\(O(nm)\)
对应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，贪心还没贪对（一直想着拆