Contestant. Rank 2183. Rating -13.
A. Garland
题意
给定 \(4\) 盏灯的颜色，颜色为 \([0, 9]\) 内的任意数字。初始状态所有灯均关闭，打开一盏灯的条件是之前打开的灯的颜色与其不一致，第一次可以打开任意一盏灯。输出将所有灯打开所需最小次数。
思路
首先，这题只有 \(4\) 盏灯。
所以，我们直接分类讨论即可。
我们先将灯按照颜色代码升序排序，那么如果第一个数和最后一个数相等，输出 \(-1\)；
否则，前三个数相等或者后三个数相等时，需要 \(6\) 次；
否则，\(4\) 次足矣。
时间复杂度：\(O(4 \log 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() {
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
题意
给定整数 \(n\)，代表当前有 \(n\) 个点。将这些点放入平面直角坐标系，满足坐标均为整数。在限制任意一对点的距离都严格大于 \(1\) 的条件下，输出最小的总代价。其中，对于一个点 \((x, y)\)，单点的代价为 \(|x| + |y|\)，总代价为所有点的代价最大值。
思路
我们来固定 \(x\) 看 \(y\)：
\(x = k\)，那么 \(y = 0\)；
\(x = k - 1\)，那么 \(y = -1, 0, 1\)；
归纳可得，对于 \(x\) 的所有正数取值，\(y\) 的取值总数为 \(1 + 2 + \ldots + (k + 1) = \frac{(k + 1)(k + 2)}{2}\)；
同理， \(x\) 为负数时，\(y\) 的取值总数为 \(1 + 2 + \ldots + k = \frac{k(k+1)}{2}\)。
那么，我们可以得到总和 \((k + 1) ^ 2\)。
那么，最后的答案即为 \(\lceil \sqrt n \rceil - 1\)。
注意精度问题即可。
时间复杂度：\(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;
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 下，\(\lfloor \sqrt{n - 1} \rfloor\) 可以作为答案卡过去
C. Sum on Subarrays
题意
构造一个序列，满足所有连续子序列的和均不为 \(0\)，且和为正数的序列数量为给定值 \(k\)。
思路
首先，我们不妨打表，\(s_i\) 为 \(i\) 个数的连续子序列个数，即 \(s_i = \frac{i(i + 1)}{2}\)。
那么，我们不难发现，\(s_{i + 1} - s_i = i + 1\)。
那么，在 \(s_i\) 个数的基础上，我们再添加 \(x \in [0, i]\) 个数，就可以等于 \(k\)。
更具体地说，我们不妨在序列前面放上 \(q\) 个相同的正数 \(x\)，其中 \(s_q\) 为 \(s\) 中第一个不大于 \(k\) 的值。
那么，我们还需 \(cnt = k - s_q\) 个数，我们不妨在后面放一个负数 \(p\)，让 以这个数作为结尾的 子序列的和 为负数 的个数为 \(q - cnt\)。
这样的话，以 \(t \in [1, cnt]\) 为头，负数 \(p\) 为尾的子序列的和就是正数了。
剩下还有一些空位，我们填上负无穷大，也就是最小值 \(-1000\) 即可。
当然，正数 \(x\) 不能为 \(1\)，这样会让某个总和变为 \(0\)，那么我们取 \(2\) 即可。
在取 \(2\) 的条件下，负数 \(p = -2(q - cnt) - 1\)。
当然，我们用递增的序列取代这些相等的正数也是可以的。
时间复杂度：\(O(n \log n)\)
对应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
题意
给定一个二进制字符串，规定操作为下面两个任选一：
交换两个相邻元素；
删掉一个元素
第一个操作的代价为 \(1e12\)；第二个操作的代价为 \(1e12 + 1\)。
输出让整个字符串变为不递减序列的最小代价。
思路
首先，这题可以 \(dp\)，但是我们不妨来想想怎么贪心。
我们下面有四种方案，取最小值即可：
删掉所有的 \(1\)；
删掉所有的 \(0\)；
遍历所有的 \(0\)，将前面的 \(1\) 删掉，后面的 \(0\) 删掉；
遍历所有的 \(0\)，若前面为 \(1\)，那么把这个 \(1\) 和当前的 \(0\) 交换，然后删去前面剩余的 \(1\)，以及后面的 \(0\)。
前面三者是显然的，而对于第四个，我们不妨考虑其他的移动情况。
显然，\(11\) 和 \(00\) 没必要交换；\(01\) 不用管，因为满足递增；\(10\) 交换即可；剩余的情况，我们都需要移动至少两次，那还不如删掉呢。
因此，贪心是成立的。
时间复杂度：\(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;
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就溜了（（