Codeforces Round #698 (Div. 2) A-E解題報告與解法證明

題目解法總體概括

A Nezzar and Colorful Balls

#include <bits/stdc++.h> using namespace std;const int N = 110; int a[N], f[N];int main() {int t; cin >> t;while (t -- ){static int n;scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);int res = 1;for (int i = 1; i <= n; i ++ ){f[i] = 1;for (int j = 1; j < i; j ++ ){if (a[j] >= a[i]) f[i] = max(f[i], f[j] + 1);}res = max(res, f[i]);}cout << res << endl;}return 0; }

---

B Nezzar and Lucky Number

#include <bits/stdc++.h> using namespace std;typedef long long LL; LL x, n, d;bool Check() {if (x <= 9LL) return x % d == 0;else if (x < 10 * d){for (int i = 0; i < x; i += 10){if ((x - i) % d == 0)return true;}return false;}elsereturn true; } int main() {int t; cin >> t;while (t -- ){scanf("%lld%lld", &n, &d);for (int i = 1; i <= n; i ++ ){scanf("%lld", &x);if (Check())puts("YES");elseputs("NO");}}return 0; }

---

C Nezzar and Symmetric Array

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 200010, INF = 0x3f3f3f3f3f3f3f3f3f; LL a[N], d[N]; int n;bool cmp(const LL &t1, const LL &t2) {return t1 > t2; }int main() {int t; cin >> t;while (t -- ){scanf("%d", &n);for (int i = 1; i <= 2 * n; i ++ ) scanf("%lld", &d[i]);sort(d + 1, d + 1 + 2 * n, cmp);bool flag = true;d[2 * n + 1] = -INF;for (int i = 1; i <= n; i ++ ){if (d[2 * i] != d[2 * i - 1]){flag = false; break;}if (d[2 * i] <= d[2 * i + 1]){flag = false; break;}} /*for (int i = 1; i <= 2 * n; i ++ )printf("%lld, ", d[i]);cout << endl; */// 不滿足 d 的基本性質if (!flag){puts("NO");continue;}LL sum = 0; // 2(a1 + a2 + ... + a(i-1) )LL tmp;for (int i = 1; i <= n; i ++ ){tmp = d[2 * i] - sum;if (tmp % (2 * (n - i + 1)) != 0){flag = false;break;}else{a[i] = tmp / (2 * (n - i + 1));if (a[i] <= 0) // 必須是正數{flag = false; break;}sum += 2 * a[i];}} /*for (int i = 1; i <= n; i ++ )printf("%lld, ", a[i]);cout << endl; */if (flag)puts("YES");elseputs("NO");}return 0; }

---

D Nezzar and Board

兩個數字x, y的情況

三個數字的x,y,z的情況
使用x,y兩種情況的結論（引理）

#include <bits/stdc++.h> using namespace std;typedef long long LL; const int N = 200010; LL a[N]; LL n, k;LL gcd(LL a, LL b) {if (b == 0) return a;else return gcd(b, a % b); }bool cmp(const LL &t1, const LL &t2) {return t1 > t2; }int main() {int t; cin >> t;while (t -- ){scanf("%lld%lld", &n, &k);for (int i = 1; i <= n; i ++ ){scanf("%lld", &a[i]);}sort(a + 1, a + 1 + n, cmp);LL d = a[1] - a[2];for (int i = 3; i <= n; i ++ ){d = gcd(d, a[1] - a[i]);}if ((k - a[1]) % d == 0) puts("YES");else puts("NO");}return 0; }

---

E Nezzar and Binary String

#include <bits/stdc++.h> #define lson (pos << 1) #define rson ((pos << 1) + 1) using namespace std;const int N = 200010; int _l[N * 4], _r[N * 4]; int _zero[N * 4], _one[N * 4]; int _lazy[N * 4]; int n, q; char s[N], f[N]; int l[N], r[N]; bool flag;void pushup(int pos) {_zero[pos] = _zero[lson] + _zero[rson];_one[pos] = _one[lson] + _one[rson]; }void pushdown(int pos) {if (_lazy[pos] == -1) return;else{if (_lazy[pos] == 1){_one[lson] = _r[lson] - _l[lson] + 1;_zero[lson] = 0;_one[rson] = _r[rson] - _l[rson] + 1;_zero[rson] = 0;}else if (_lazy[pos] == 0){_zero[lson] = _r[lson] - _l[lson] + 1;_one[lson] = 0;_zero[rson] = _r[rson] - _l[rson] + 1;_one[rson] = 0;}_lazy[lson] = _lazy[rson] = _lazy[pos];_lazy[pos] = -1;} }void build(int pos, int l, int r) {_l[pos] = l, _r[pos] = r;_lazy[pos] = -1;if (l == r){if (f[l] == '0'){_zero[pos] = 1;_one[pos] = 0;}else{_zero[pos] = 0;_one[pos] = 1;}return;}else{int mid = l + r >> 1;build(lson, l, mid);build(rson, mid + 1, r);pushup(pos);} }void modify(int pos, int l, int r, int x, int y, int tar) {// all includedif (x <= l && y >= r){_lazy[pos] = tar;if (tar == 0)_zero[pos] = _r[pos] - _l[pos] + 1, _one[pos] = 0;else_one[pos] = _r[pos] - _l[pos] + 1, _zero[pos] = 0;return;}else{int mid = l + r >> 1;pushdown(pos);if (x <= mid){modify(lson, l, mid, x, y, tar);}if (y >= mid + 1){modify(rson, mid + 1, r, x, y, tar);}pushup(pos);} }void query(int pos, int l, int r, int x, int y, int &num0, int &num1) {// all includedif (x <= l && y >= r){num0 = _zero[pos];num1 = _one[pos];return;}else{int mid = l + r >> 1;pushdown(pos);int tmp1, tmp2;num0 = num1 = 0;if (x <= mid){query(lson, l, mid, x, y, tmp1, tmp2);num0 = tmp1, num1 = tmp2;}if (y >= mid + 1){query(rson, mid + 1, r, x, y, tmp1, tmp2);num0 += tmp1, num1 += tmp2;}return;} }int main() {int t; cin >> t;while (t -- ){// inputscanf("%d%d", &n, &q);scanf("%s%s", s + 1, f + 1);for (int i = 1; i <= q; i ++ ){scanf("%d%d", &l[i], &r[i]);}// initialflag = true;build(1, 1, n);// optfor (int i = q; flag && i >= 1; i -- ){static int num0, num1;query(1, 1, n, l[i], r[i], num0, num1);if (num0 == num1){flag = false;break;}else if (num0 > num1) // 變成 0{modify(1, 1, n, l[i], r[i], 0);/// printf("(%d, %d)->%d\n", l[i], r[i], 0);}else // 變成 1{modify(1, 1, n, l[i], r[i], 1);/// printf("(%d, %d)->%d\n", l[i], r[i], 1);}}// Checkif (!flag){// printf("因為之前的不行\n");puts("NO");}else{for (int i = 1; i <= n; i ++ ){static int num0, num1;query(1, 1, n, i, i, num0, num1);if (num0 == 1 && s[i] == '0'){continue;}else if (num1 == 1 && s[i] == '1'){continue;}else{flag = false;break;}}if (flag)puts("YES");elseputs("NO");}}return 0; } /* 1 5 2 00000 00111 1 5 1 3 */

---

總結

以上是生活随笔為你收集整理的Codeforces Round #698 (Div. 2) A-E解题报告与解法证明的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。