大型建站公司,智能网站建设系统,免费设计logo的手机软件,营销点子ABC346 A-G题解 A题目AC Code#xff1a;时间复杂度 B题目时间复杂度AC Code#xff1a; C题目时间复杂度AC Code#xff1a; D题目时间复杂度AC Code#xff1a; E题目时间复杂度AC Code#xff1a; F题目时间复杂度AC Code#xff1a; G题目时间复杂度AC Code#xff… 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;
maplong 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 N1 N1 边才找完或没找完就说明不行。
细节很多考验你的调试技术。
时间复杂度 O ( ∣ T ∣ log ( N ∣ S ∣ ) ) O(|T|\log(N|S|)) 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
题目
我们可以找到对于每一个 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;
}
