搜索到
11
篇与
的结果
-
CF Round1045 Div.2 A当 $n, a, b$ 同奇偶，显然成立。由于按顺序的，所以只能由 $b$ 覆盖 $a$，所以当三者奇偶性不相同但是 $n$ 与 $b$ 同奇偶时，也成立。除了这两种情况以外都不成立。#include<bits/stdc++.h> #define ll long long int T; void solve() { int n, a, b; std::cin >> n >> a >> b; if(n % 2 == a % 2 && a % 2 == b % 2) std::cout << "YES\n"; else if(n % 2 == b % 2 && a < b) std::cout << "YES\n"; else std::cout << "NO\n"; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cin>>T; while(T--) { solve(); } return 0; }B当 $k$ 为奇数时，只需把每个数都加成偶数即可。当 $k$ 为偶数时，需要找到一个奇数 $b$ 使得 $b$ 不是 $k$ 的因数，然后将所有的数都加成 $b$ 的倍数，可以证明每个数加的次数一定都小于 $k$ 。$b$ 的求法，可以将 $k$ 一直除以 $2$ 直至为奇数，然后再加上 $2$ ，这样一个值即为一个符合条件的 $b$ ，时间复杂度 $O(\log k)$.知道了 $b$ 后，如何将 $a[i]$ 加成一个 $b$ 的倍数？有 $a[i] + kx = by$ ，所以即为同余方程 $kx + by = a[i]$，由上述 $b$ 的求法，显然 $b$ 与 $k$ 互质，所以这个同余方程一定有解，用扩展欧几里得算法求解即可，得到 $x_0, y_0$.题目中要求加的次数不超过 $k$ ，所以有 $-k \le x \le 0$，而有 $x = x_0 + tb$，代入解得 $\dfrac{-k-x_0}{b} \le t \le \dfrac{-x_0}{b}$，取 $t = \Big\lceil\dfrac{-k-x_0}{b}\Big\rceil$ 再进行调整即可得出 $x$.$a[i]$ 最终的值即为 $a[i] - kx$.#include<bits/stdc++.h> #define ll long long int T; void Exgcd(ll a,ll b, ll& x, ll& y) { if(!b) x = 1, y = 0; else { Exgcd(b, a % b, x, y); int t = x; x = y, y = t - a / b * y; } } void solve() { ll n, k; std::cin >> n >> k; std::vector<ll> a(n + 1); for(int i = 1; i <= n; i++) { std::cin >> a[i]; } if(n == 1) { std::cout << a[1] + k << "\n"; } else { if(k & 1) { for(int i = 1; i <= n; i++) { if(a[i] & 1) a[i] += k; } for(int i = 1; i <= n; i++) { std::cout << a[i] << " "; } std::cout << "\n"; } else { ll b = k; while(b % 2 == 0) b /= 2; b += 2; ll x, y; Exgcd(k, b, x, y); for(int i = 1; i <= n; i++) { ll X, Y; X = x * a[i], Y = y * a[i]; ll t = ceil((double)(-k - X) / b); if(X + b * t < -k) t++; if(X + b * t > 0) t--; X += b * t; a[i] -= X * k; } for(int i = 1; i <= n; i++) { std::cout << a[i] << " "; } std::cout << "\n"; } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cin>>T; while(T--) { solve(); } return 0; }C先考虑奇数项，把其变成左右两个偶数项中的较小值。再考虑偶数项，经过了上一步操作，每次一个子区间往后/往前扩展两个位置时，偶数项增量一定比奇数项增量大，所以只需考虑偶数项与其左右两个奇数项构成的子区间。从前往后考虑每个子区间 $[a, b, c]$，其中 $b$ 为偶数项，如果 $b \ge a + c$ 则不用操作，否则令 $sub = a + c - b$，贪心地把这个 $sub$ 尽可能全用在 $c$ 上即可。#include<bits/stdc++.h> #define ll long long int T; void solve() { int n; std::cin >> n; std::vector<ll> a(n + 1); for(int i = 1; i <= n; i++) { std::cin >> a[i]; } ll ans = 0; for(int i = 1; i <= n; i += 2) { ll minn; if(i == 1) minn = a[i + 1]; else if(i == n) minn = a[i - 1]; else minn = std::min(a[i - 1], a[i + 1]); if(minn > a[i]) continue; ans += a[i] - minn; a[i] = minn; } for(int i = 2; i <= n; i += 2) { if(i == n) continue; ll sum = a[i - 1] + a[i + 1]; if(sum <= a[i]) continue; ll sub = sum - a[i]; ans += sub; if(sub > a[i + 1]) a[i + 1] = 0; else a[i + 1] -= sub; } std::cout << ans << "\n"; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cin>>T; while(T--) { solve(); } return 0; } -
-
-
-
