ABC346 A-G题解
- A
- 题目
- AC Code：
- 时间复杂度
- B
- 题目
- 时间复杂度
- AC Code：
- C
- 题目
- 时间复杂度
- AC Code：
- D
- 题目
- 时间复杂度
- AC Code：
- E
- 题目
- 时间复杂度
- AC Code：
- F
- 题目
- 时间复杂度
- AC Code：
- G
- 题目
- 时间复杂度
- AC Code：
下面的内容不包括题目翻译，要想获取题目翻译，请参照 这篇教程 来获取题目翻译。
A
题目
循环处理每一个数字即可，不再赘述。
AC Code：
#include <iostream>
using namespace std;
int n, a[200100];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i < n; i++) cout << a[i] * a[i + 1] << ' ';
return 0;
}
时间复杂度
O ( N ) O(N) O(N)。
B
题目
由于键盘是有规律的，所以任何子串都可以从从 12 12 12 以内开始的子串提取出来。暴力即可， 200 200 200 够用了。
时间复杂度
O ( 20 0 2 ) O(200^2) O(2002)。
AC Code：
#include <iostream>
#include <cstring>
using namespace std;
int w, b;
string s = "wbwbwwbwbwbw";
string s1;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> w >> b;
for (int i = 0; i <= 20; i++) {
for (int j = 0; j < (int)s.length(); j++) {
s1.push_back(s[j]);
}
}
for (int i = 0; i < (int)s1.size(); i++) {
int cntw = 0, cntb = 0;
for (int j = i; j < (int)s1.size(); j++) {
if (w == cntw && b == cntb) {
cout << "Yes\n";
return 0;
}
if (s1[j] == 'b') cntb++;
else cntw++;
}
}
cout << "No";
return 0;
}
C
题目
我们发现，与其一个一个找没有出现在
A
A
A 里面的数，不如从小于等于
K
K
K 的所有数字里面寻找在
A
A
A 里出现过的数字。我们使用一个 map 记录这个数字有没有被去除。对于每一个
A
i
A_i
Ai，如果
A
i
≤
K
A_i \le K
Ai≤K 且没有被去除，就从所有小于等于
K
K
K 的数字的和里面减去这个数字，把这个数字标记为已去除。
时间复杂度
O ( N log ( 1 0 9 ) ) O(N\log(10^9)) O(Nlog(109))。
AC Code：
#include <iostream>
#include <map>
using namespace std;
int n;
long long k, a[200100];
long long ans;
map<long long, bool> m;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
ans = (k + 1ll) * k / 2ll;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (!m[a[i]] && a[i] <= k) {
ans -= a[i];
m[a[i]] = 1;
}
}
cout << ans;
return 0;
}
D
题目
我们发现，一个好字串无非就是可以从某个位置切成两个字串，字串里相邻两个字符不一样，字串切开的位置的字符相同。
我们计算前缀后缀以 0 或 1 开始的相邻两个字符不一样的代价，即使这个字串变为 10101... 的代价。对于每一个分割点，如果原串长度是偶数，那么这两个分割后的字串另外一边要一样，否则，不一样。计算代价，取最小值即可。
时间复杂度
O ( N ) O(N) O(N)。
AC Code：
#include <algorithm>
#include <iostream>
using namespace std;
int n;
char s[200100];
int c[200100];
long long sum[200100];
long long c00[200100], c01[200100], c10[200100], c11[200100];
long long ans = 1e18;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + c[i];
for (int i = 1; i <= n; i++) {
c00[i] = c00[i - 1] + ((i - 1) % 2 == s[i] - '0') * c[i];
c01[i] = c01[i - 1] + (i % 2 == s[i] - '0') * c[i];
}
for (int i = n; i >= 1; i--) {
c10[i] = c10[i + 1] + ((n - i) % 2 == s[i] - '0') * c[i];
c11[i] = c11[i + 1] + ((n - i + 1) % 2 == s[i] - '0') * c[i];
}
for (int i = 1; i < n; i++) {
if (n % 2 == 0) {
ans = min({ans, c00[i] + c10[i + 1], c01[i] + c11[i + 1]});
}
else {
ans = min({ans, c01[i] + c10[i + 1], c00[i] + c11[i + 1]});
}
}
cout << ans;
return 0;
}
E
题目
我们倒着考虑所有操作，对于每一个横排操作，如果之前（指更晚的操作）把这一排覆盖了，那么跳过这个操作，否则统计没被覆盖的列数，该颜色数量加上这个值，把这一排标记为操作了，剩余横排数量减一，结束。
如果这是一个竖列操作，如果这一列没有被覆盖，该颜色数量加上没被覆盖的横排数，把这一列标记为被覆盖，没被覆盖的列数减去一，结束。
时间复杂度
O ( 1 ) O(1) O(1)。
AC Code：
#include <iostream>
#define int long long
using namespace std;
int h, w;
int m;
int t[200100], a[200100], x[200100];
int c_h, c_w;
int cnt[200100];
int cnt1;
bool vis_h[200100], vis_w[200100];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> h >> w;
cin >> m;
c_h = h, c_w = w;
for (int i = m; i >= 1; i--) cin >> t[i] >> a[i] >> x[i];
for (int i = 1; i <= m; i++) {
if (t[i] == 1) {
if (c_h && !vis_h[a[i]]) {
c_h--;
cnt[x[i]] += c_w;
vis_h[a[i]] = 1;
}
}
else {
if (c_w && !vis_w[a[i]]) {
c_w--;
cnt[x[i]] += c_h;
vis_w[a[i]] = 1;
}
}
}
cnt[0] += c_h * c_w;
for (int i = 0; i <= 200000; i++) {
if (cnt[i]) cnt1++;
}
cout << cnt1 << '\n';
for (int i = 0; i <= 200000; i++) {
if (cnt[i]) {
cout << i << ' ' << cnt[i] << '\n';
}
}
return 0;
}
F
题目
如果重复三次的情况可以，那么二次，一次的情况也可以。如果重复四次的情况不可以，重复五次，六次也不可以。可以看出这东西满足单调性，可以二分。
我们判断这个情况可不可以时，如果暴力在重复 N N N 次的串中寻找的话， N N N 很大，会爆炸。我们记录现在找到了重复第几遍的串中的第几个字符，分情况讨论找完后会不会跳到下一遍即可。如果跳不到下一遍，找到刚刚好重复我们要重复的次数的位置，否则，让总共要重复的次数除以这一边中字符个数就是要重复的次数，还要考虑这个坐标多的次数。
如果重复了 N + 1 N+1 N+1 边才找完或没找完，就说明不行。
细节很多，考验你的调试技术。
时间复杂度
O ( ∣ T ∣ log ( N ∣ S ∣ ) ) O(|T|\log(N|S|)) O(∣T∣log(N∣S∣))。
AC Code：
#include <iostream>
#define int long long
using namespace std;
int n;
string s, t;
int cnt[200100][50];
int idx[200100][50];
bool check(int x) {
int now1 = 0, now2 = 0;
for (int i = 0; i < (int)t.size(); i++) {
if (!cnt[0][t[i] - 'a']) return 0;
if (cnt[now2][t[i] - 'a'] >= x) {
int tmp = x;
if (now2) tmp += cnt[0][t[i] - 'a'] - cnt[now2][t[i] - 'a'];
now2 = idx[tmp][t[i] - 'a'] + 1;
}
else {
int tmp = x;
tmp -= cnt[now2][t[i] - 'a'];
now1++;
now2 = 0;
if (cnt[0][t[i] - 'a'] >= tmp) {
now2 = idx[tmp][t[i] - 'a'] + 1;
}
else {
now1 += tmp / cnt[0][t[i] - 'a'];
now2 = idx[tmp % cnt[0][t[i] - 'a']][t[i] - 'a'] + 1;
if (tmp % cnt[0][t[i] - 'a'] == 0) {
now1--;
now2 = idx[cnt[0][t[i] - 'a']][t[i] - 'a'];
}
}
}
now1 += now2 / (int)s.size();
now2 %= (int)s.size();
if (now1 > n || (now1 == n && now2)) return 0;
}
return 1;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> s >> t;
for (int i = (int)s.size() - 1; i >= 0; i--) {
for (int j = 0; j < 26; j++) cnt[i][j] = cnt[i + 1][j];
cnt[i][s[i] - 'a']++;
}
for (int i = (int)s.size() - 1; i >= 0; i--)
for (int j = 0; j < 26; j++) idx[cnt[0][j] - cnt[i + 1][j]][j] = i;
int l = 0, r = n * (int)s.size();
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(mid)) {
l = mid;
}
else {
r = mid - 1;
}
}
cout << l;
return 0;
}
G
题目
我们可以找到对于每一个 A i A_i Ai，它的上一个和它相同的值的位置和下一个和它相同的值的位置。通过正序和倒序便利数组，存储这个值上一个出现位置，每遇到一个值将其上一个和它相等的值的位置更新为我们储存的这个值的位置，在更新这个值的上一个出现位置为现在遍历到的位置。
这样就算出了对于每一个只出现一次的数的区间范围，拿样例解释：
1 2 1 4 3 3 3 2 2 4
如果以第三个元素：1 为只出现一次元素的话，区间可以这么取：
1 [2 {1] 4 3 3 3 2 2 4}
其中中括号是左端点的范围，大括号是右端点的取值范围。
这样就有 2 × 8 2\times 8 2×8 为 16 16 16 种情况。
但是就这样会有重复的区间，朴素去重就是 N 2 N^2 N2 的时间复杂度了，怎么办呢？
我们可以把一个区间表示成一个点： [ i , j ] [i,j] [i,j] 表示成 ( i , j ) (i,j) (i,j)，如图 i , j i,j i,j 为 2 , 3 2,3 2,3：
那么两个区间里的点的组合是不是就可以表示成一个矩形？
那么样例中例子的矩形就是：
( 2 , 3 ) to ( 3 , 10 ) (2,3) \text{to} (3,10) (2,3)to(3,10)
这个矩形的面积就是这个值只有一个的区间的总和。
那么把这些矩形的面积并起来，求这个不规则图形的总面积就是我们要求的答案？
你应该可以想到 扫描线。
时间复杂度
O ( N log ( N ) ) O(N\log(N)) O(Nlog(N))
什么？你不会？我放的链接是拿来干嘛的？
AC Code：
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n, a[200100];
int l[200100], r[200100], l1[200100], r1[200100];
struct node{
int l, r, tag;
long long sum;
};
node t[1600100];
void maketree(int l, int r, int p) {
t[p].l = l;
t[p].r = r;
if (l < r) {
maketree(l, (l + r) / 2, p * 2);
maketree((l + r) / 2 + 1, r, p * 2 + 1);
}
}
void add(int l, int r, int p, int k) {
if (t[p].l > r || t[p].r < l) return;
if (l <= t[p].l && t[p].r <= r) {
t[p].tag += k;
if (t[p].tag) t[p].sum = t[p].r - t[p].l + 1;
else t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
return;
}
add(l, r, p * 2, k);
add(l, r, p * 2 + 1, k);
if (!t[p].tag) t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
}
struct segment{
int l, r, x, f;
};
segment seg[1600100];
int segcnt;
bool cmp(segment a, segment b) {
if (a.x == b.x) return a.f < b.f;
return a.x < b.x;
}
long long ans;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) {
l[i] = r1[a[i]];
r1[a[i]] = i;
}
memset(l1, 0x3f, sizeof(l1));
for (int i = n; i >= 1; i--) {
r[i] = l1[a[i]];
l1[a[i]] = i;
}
for (int i = 1; i <= n; i++) r[i] = min(r[i], n + 1);
for (int i = 1; i <= n; i++) {
segcnt++;
seg[segcnt].l = i;
seg[segcnt].r = r[i] - 1;
seg[segcnt].x = l[i];
seg[segcnt].f = 1;
segcnt++;
seg[segcnt].l = i;
seg[segcnt].r = r[i] - 1;
seg[segcnt].x = i;
seg[segcnt].f = -1;
}
maketree(1, n, 1);
sort(seg + 1, seg + segcnt + 1, cmp);
for (int i = 1; i < segcnt; i++) {
add(seg[i].l, seg[i].r, 1, seg[i].f);
ans += (long long)(seg[i + 1].x - seg[i].x) * (long long)t[1].sum;
}
cout << ans;
return 0;
}
