Contestant~. Rank 856. Rating +27 (+77 -50).
A. Morning Sandwich
题意
规定三明治的顶部和底部分别是两块面包片，中间由若干层火腿肠或芝士组成，每层之间由面包片分隔。
现在，给定面包片，芝士和火腿肠的数量，输出最大的层数。
思路
如题，推一个式子即可。
时间复杂度：\(O(1)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int b, c, h;
cin >> b >> c >> h;
cout << min((b - 1) * 2 + 1, (c + h) * 2 + 1) << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}签到
B. Monsters
题意
给定 \(n\) 个怪物，每个怪物有 \(a_i\) 的血量。
现在，规定每次只能扣除血量最高的且下标更小的怪物的血量，每次扣除给定整数 \(k\) 的血量，当一个怪物的血量 \(\leq 0\) 时怪物死亡。
输出怪物死亡的时间顺序。
思路
首先，我们不难发现，在若干次操作后，最后序列中的所有数都会剩下 相同的 需操作的次数。
到这个分界点之后，我们一定只能按照一个特定的顺序扣血。
因而，我们直接考虑还剩一次操作的情况。此时，如果 \(a_i \bmod k = 0\)，还剩 \(k\) 点血量，否则还剩 \(a_i \bmod k\) 点血量。
我们按这个排序，即可得到死亡顺序。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, k;
cin >> n >> k;
vector<pii> a(n);
for(int i=0;i<n;i++){
cin >> a[i].fs;
a[i].sc = i + 1;
a[i].fs %= k;
if(a[i].fs == 0) a[i].fs = k;
a[i].fs = -a[i].fs;
}
sort(all(a));
for(int i=0;i<n;i++) cout << a[i].sc << ' ';
cout << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}暴力模拟肯定 \(tle\)
C. Binary String Copying
题意
给定一个二进制字符串，将其复制 \(q\) 份。
对于被复制的第 \(i\) 份，给定两个整数 \(l_i, r_i\)，将 \([l_i, r_i]\) 内的字符升序排序，得到新字符串。
现在，输出 被复制的所有字符串 被处理后 得到的 \(q\) 个字符串中 有多少个 不同的 字符串。
思路
与其比较排序后的结果，我们不妨考虑一下我们在排序的时候对原字符串的影响。
显然，对于一个形如 \(00101011\) 的字符串，我们的排序区间就可以缩减到 \(1010\)，并且这个排序区间内的数在排序后一定和原字符串不同。
那么，如果两个字符串处理后是相同的，他们的排序区间就一定是相同的。
也就是说，这个排序区间，就是表征两个字符串排序后是否相等的依据。
那么，我们可以预处理出 \([l, r]\) 中最左边的 \(1\) 和最右边的 \(0\) 所在位置 \(i, j\)，用 \([i, j]\) 作为本次排序后的字符串特征。
最后，有多少个不同的 \([i, j]\)，就有多少个不同的字符串了。
至于处理，我们直接正反跑一遍递推即可。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n, m;
cin >> n >> m;
string s;
cin >> s;
s = "#" + s;
vector<int> pre(n + 1), suf(n + 1);
int l = 1, r = n;
for(int i=1;i<=n;i++){
if(s[i] == '0') l = i;
pre[i] = l;
}
for(int i=n;i>0;i--){
if(s[i] == '1') r = i;
suf[i] = r;
}
int ans = 0;
map<pii, bool> cnt;
bool f = false;
while(m --){
cin >> l >> r;
int L = suf[l], R = pre[r];
if(L < R){
if(!cnt.count({L, R})) ans ++;
cnt[{L, R}] = true;
}else f = true;
}
cout << ans + (f ? 1 : 0) << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) solve();
}硬着去哈希就寄了
D. Array Painting
题意
给定一个由 \(0, 1, 2\) 组成的字符串，一开始所有格子都是蓝色的。
现在，根据下面的规则，将所有的格子涂成红色：
花费一个金币，将一个蓝色格子涂成红色；
如果某个红色格子值大于 \(0\)，那么可以以 \(-1\) 的代价，将相邻的某个蓝色格子变成红色
输出让所有格子变成红色的最小代价。
思路
我们可以先进行预处理。
因为操作的传递，连续的 \(1\) 等价于一个 \(1\)，连续的 \(2\) 等价于一个 \(2\)，因此我们对连续的 \(1, 2\) 进行等价替代。
同时，因为不好处理 \(12\) 连在一起的情况，我们直接将一个 "\(12\)" 其等价为一个 \(2\)。
如上预处理后，我们直接贪心即可。
我们从左向右枚举，贪心地将 \(1\) 的左端点做上标记，如果之前已经做标记，那就给右端点做标记。
同时，对于 \(2\)，我们直接将其左右端点都做标记。
那么，最后没有做标记的，就是我们需要花费金币填色的格子。
上述贪心是显然的，因为这样就可以避免出现 \(1\) 不知道取哪边而造成一定的浪费。
注意端点的判定。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> a(1);
for(int i=0;i<n;i++){ //reduce
int cur;
cin >> cur;
if(a[a.size() - 1] == 1 && cur == 2) a[a.size() - 1] = 2;
else if(cur == 0 || !a[a.size() - 1]) a.pb(cur);
}
n = a.size() - 1;
a.pb(0);
vector<bool> ok(n + 2);
for(int i=1;i<=n;i++){
if(a[i] == 1){
if(i - 1 >= 1 && !ok[i - 1]) ok[i - 1] = true;
else if(i + 1 <= n && !ok[i + 1]) ok[i + 1] = true;
}else if(a[i] == 2) ok[i - 1] = ok[i + 1] = true;
}
int ans = 0;
for(int i=1;i<=n;i++)
if(!ok[i]) ans ++;
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
//cin >> t;
while (t--) solve();
}别问我为什么挂了这么多发（
E. Max to the Right of Min
题意
给定一个序列，对于所有其连续子序列 \([l, r]\)，统计 最大值 在 最小值 右边 的区间个数。
思路
我们考虑枚举最大值和最小值的位置。
对于最大值的下标 \(i\)，最小值的下标 \(j\)，\([i\) 左边第一个比它大的元素的下标 \(+1, i\) 右边第一个比它大的元素的下标 \(-1]\) 和 \([j\) 左边第一个比它小的元素的下标 \(+1, j\) 右边第一个比它小的元素的下标 \(-1]\) 这两个区间的交集即为 \([i, j]\) 最大可左右扩展的区间范围。
我们可以用两个单调栈预处理，得到 \(l_{max}, r_{max}, l_{min}, r_{min}\) 四个数组，表征字面意思。
关于枚举，我们也可以开一个单调栈，用于维护从左到右遍历时，以第 \(i\) 位作为最大值，前面比它小的元素的下标。
那么，我们可以得到下面的暴力写法：
int ans = 0;
vector<int> s(1, -1);
for(int i=0;i<n;i++){ //枚举第i位作为最大值所在点
for(int j=1;j<s.size();j++){ //枚举第j位作为最小值所在点
ans += max(0ll, (s[j] - max(lmax[i], s[j - 1]))) * max(0ll, (min(rmax[i], rmin[s[j]]) - i));
}
while(s.size() > 1 && p[i] < p[s.back()]){
rmin[s.back()] = i;
s.pop_back();
}
s.pb(i);
}
cout << ans << '\n';上述代码是 \(tle\) 的，因而我们考虑优化。
首先，我们先去掉两个和 \(0\) 取 \(max\) 的操作。因为单调栈 \(s\) 递增，我们直接二分 \(s\)，找出第一个大于 \(l_{max}[i]\) 的点 \(l\)，那么即可去掉两个外围 \(max\)。
其次，因为上述二分，对于 \(l + 1\) 及以后的点，\(max(l_{max}[i], s[j - 1]) = s[j - 1]\)，所以我们将 \(j = l\) 的情况单独提出，剩余的部分就可以改为 \(s[j] - s[j - 1]\) 了。
我们再考虑后者。因为 \(s\) 和 \(r_{min}\) 自身的单调性，我们可以得知，\(r_{min}[s[j]]\) 也是单调的，从而我们可以找到第一个满足 \(r_{min}[s[j]] > r_{max}[i]\) 的点 \(m\)，从而将两者分开，得到 \((s[j] - s[j - 1])\times(r_{max}[i] - i)\) 和 \((s[j] - s[j - 1]) \times (r_{min}[s[j]] - i)\)。
对于左式，因为都有公因子 \(r_{max}[i] - i\)，我们将其提出并合并同类项后，可得 \((s[m - 1] - s[l]) \times (r_{max}[i] - i)\)。
对于右式，我们将其拆开得到 \((s[j] - s[j - 1]) \times r_{min}[s[j]]\) 和 \((s[j] - s[j - 1]) \times i\)。那么，左边的可以用前缀和优化，右边的可以合并到上面的左式中。
如上，即可通过本题。
时间复杂度：\(O(n \log n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
//#define FLOATING_OCEAN
#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
void solve() {
int n;
cin >> n;
vector<int> p(n);
for(int i=0;i<n;i++) cin >> p[i];
vector<int> lmin(n, -1), lmax(n, -1), rmin(n, n), rmax(n, n); //当前位置i 第一个左边比他小，左边比他大，右边比他小，右边比他大
vector<int> smin, smax; //单调栈
for(int i=0;i<n;i++){
while(!smin.empty() && p[i] < p[smin.back()]){
rmin[smin.back()] = i;
smin.pop_back();
}
if(!smin.empty()) lmin[i] = smin.back(); //满足单调性后自然可得
smin.pb(i);
while(!smax.empty() && p[i] > p[smax.back()]){
rmax[smax.back()] = i;
smax.pop_back();
}
if(!smax.empty()) lmax[i] = smax.back();
smax.pb(i);
}
int ans = 0;
vector<int> s(1, -1), sum(1, 0); //单调栈 前缀和
for(int i=0;i<n;i++){ //枚举第i位作为最大值所在点
// for(int j=1;j<s.size();j++){ //枚举第j位作为最小值所在点
// ans += max(0ll, (s[j] - max(lmax[i], s[j - 1]))) * max(0ll, (min(rmax[i], rmin[s[j]]) - i));
// }
while(s.size() > 1 && p[i] < p[s.back()]){
rmin[s.back()] = i;
s.pop_back();
sum.pop_back();
}
int l = upper_bound(all(s), lmax[i]) - s.begin(); //规避外围两个max
if(l < s.size()) {
ans += (s[l] - max(lmax[i], s[l - 1])) * (min(rmax[i], rmin[s[l]]) - i); //提出第二个max
//因为s单调，自然rmin[s[j]]也单调，最后会出现一个partition point，从而分开min
int m = partition_point(s.begin() + l + 1, s.end(), [&](int x) -> bool{
return rmin[x] > rmax[i];
}) - s.begin();
ans += (s[m - 1] - s[l]) * rmax[i]; //化简
ans += sum.back() - sum[m - 1]; //前缀和处理 sum((s[j] - s[j - 1]) * rmin[s[j]])
ans -= (s.back() - s[l]) * i;
}
sum.pb(sum.back() + (i - s.back()) * rmin[i]);
s.pb(i);
}
cout << ans << '\n';
}
signed main() {
# ifdef FLOATING_OCEAN
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
# endif
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) solve();
}代码参考了 \(\mathtt{jiangly}\) 的 视频，做了一些注释方便理解