赞
踩
#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; }
#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; } else return 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"); else puts("NO"); } } return 0; }
#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"); else puts("NO"); } return 0; }
两个数字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; }
#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 included if (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 included if (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 -- ) { // input scanf("%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]); } // initial flag = true; build(1, 1, n); // opt for (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); } } // Check if (!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"); else puts("NO"); } } return 0; } /* 1 5 2 00000 00111 1 5 1 3 */
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。