比赛链接
A
题意
给一个字符串每个物品对应的灯的照明方向，L/R 能照亮它左侧/右侧的所有物品（不包括自己对应的物品），现在能交换相邻两个灯一次（不改变照明方向），问能否找亮所有物品。
题解
知识点：贪心。
显然，如果存在 LR 或 RL 就可以照亮全部，否则全是 L 或 R 就不可行。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
string s;
cin >> s;
s = "?" + s;
for (int i = 1;i < n;i++) {
if (s[i] != s[i + 1]) {
if (s[i] == 'L') cout << i << '\n';
else cout << 0 << '\n';
return true;
}
}
return false;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
题意
构造一组数，使得任意相邻两项之和等于全部和。
题解
知识点：构造。
\(n\) 为偶数时，构造 \(1,-1,1,-1,\cdots\) 即可。
\(n\) 为奇数时，显然奇数项和偶数项要各自相等，随后由 \(a_1+\cdots+a_n = a_{n-1}+a_{n}\) 可以得到 \((n-1)a_1+(n-3)a_2 = 0\) ，取 \(a_1 = n-3,a_2 = 1-n\) 即可，只有 \(n=3\) 时无解（因为 \(a_1 = 0\)）。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool solve() {
int n;
cin >> n;
if (n & 1) {
if (n == 3) return false;
cout << "YES" << '\n';
for (int i = 1;i <= n;i++) {
if (i & 1) cout << n - 3 << ' ';
else cout << 1 - n << ' ';
}
cout << '\n';
}
else {
cout << "YES" << '\n';
for (int i = 1;i <= n;i++) {
if (i & 1) cout << 1 << ' ';
else cout << -1 << ' ';
}
cout << '\n';
}
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
C
题意
给一组数，可以修改元素变成其相反数。问最少修改几次，可以使得第 \(m\) 个前缀和 \(a_1+\cdots+a_m\) 是所有前缀和里最小的。
题解
知识点：前缀和，数学，贪心。
定义 \(a[l,r] = a_l+\cdots+a_r\) 。
当 \(k\in [1,m-1]\) 时
\[\begin{aligned}
a[1,k] &\geq a[1,m]\\
a[1,k] &\geq a[1,k] + a[k+1,m]\\
0 &\geq a[k+1,m]
\end{aligned}
\]
当 \(k\in [m+1,n]\) 时
\[\begin{aligned}
a[1,k] &\geq a[1,m]\\
a[1,m] + a[m+1,k] &\geq a[1,m]\\
a[m+1,k] &\geq 0
\end{aligned}
\]
所以只要保证任意 \(i\in[2,m]\) ，满足 \(a[i,m]\leq 0\) ；任意 \(i\in[m+1,n]\) ，满足 \(a[m+1,i] \geq 0\) 即可。
每次操作时，贪心地取最优的即可。
时间复杂度 \(O(n\log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200007];
bool solve() {
int n, m;
cin >> n >> m;
for (int i = 1;i <= n;i++) cin >> a[i];
int cnt = 0;
multiset<int> ms;
ll sum = 0;
for (int i = m;i >= 2;i--) {
sum += a[i];
ms.insert(a[i]);
if (sum > 0) {
sum -= 2 * (*prev(ms.end()));
ms.erase(prev(ms.end()));
cnt++;
}
}
ms.clear();
sum = 0;
for (int i = m + 1;i <= n;i++) {
sum += a[i];
ms.insert(a[i]);
if (sum < 0) {
sum -= 2 * (*ms.begin());
ms.erase(ms.begin());
cnt++;
}
}
cout << cnt << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
题意
给定一组头发长度 \(a_i\) ，以及理想头发长度 \(b_i\) 。
理发师有刀片 \(x_i\) ，每个刀片只能用一次，每次可以修减一段连续区间的头发，满足 \(a'_i = \min(a_i,x),i\in[L,R]\)。
问理发师能不能通过这些刀片将 \(a\) 修剪至 \(b\) 。
题解
知识点：单调栈。
显然 \(a_i<b_i\) 无解。
利用最大值单调栈维护刀片的值。以下按顺序满足：
- \(b_i\) 大于栈顶刀片，则栈顶刀片因为太小不能再用了，刀片需要出栈直至 \(b_i\) 小于等于栈顶刀片或栈空。
\(b_i = a_i\) ，说明 \(b_i\) 不需要修剪，什么都不用干。
\(b_i \neq a_i\) ，说明 \(b_i\) 需要修剪，此时如果 \(b_i\) 小于栈顶刀片或栈空，则需要使用新的刀片，满足 \(x = b[i]\) ，如果不存在这个刀片则无解。
全部满足后，即 YES 。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[200007];
int b[200007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= n;i++) cin >> b[i];
int m;
cin >> m;
map<int, int> mp;
for (int i = 1;i <= m;i++) {
int x;
cin >> x;
mp[x]++;
}
stack<int> st;
for (int i = 1;i <= n;i++) {
if (a[i] < b[i]) return false;
while (!st.empty() && b[i] > st.top()) st.pop();
if (a[i] != b[i]) {
if (st.empty() || b[i] < st.top()) {
if (mp[b[i]]) {
mp[b[i]]--;
st.push(b[i]);
}
else return false;
}
}
}
cout << "YES" << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << "NO" << '\n';
}
return 0;
}
