ABC346 A-G 题解

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)$。

B

题目

时间复杂度

$O(200^2)$。

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

题目

时间复杂度

$O(N\log (10^9))$。

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

题目

时间复杂度

$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)$。

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

题目

时间复杂度

$O(|T|\log (N|S|))$。

AC Code：

#include <iostream>
#define int long longusing 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

题目

1 2 1 4 3 3 3 2 2 4

1 [2 {1] 4 3 3 3 2 2 4}

时间复杂度

$O(N\log (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;
}