Educational Codeforces Round 151 (Rated for Div. 2) A-D-天天热点评
#include using namespace std;using ll = long long;bool solve() { int n, k, x; cin >> n >> k >> x; if (x != 1) { cout << "YES" << "\n"; cout << n << "\n"; for (int i = 1;i <= n;i++) cout << 1 << " \n"[i == n]; } else { if ((n & 1) && n >= 3) { if (k <= 2) cout << "NO" << "\n"; else { cout << "YES" << "\n"; cout << (n - 3) / 2 + 1 << "\n"; cout << 3 << " "; for (int i = 1;i <= n - 3;i += 2) cout << 2 << " \n"[i == n - 3]; } } else if (!(n & 1)) { if (k == 1) cout << "NO" << "\n"; else { cout << "YES" << "\n"; cout << n / 2 << "\n"; for (int i = 1;i <= n;i += 2) cout << 2 << " \n"[i == n - 1]; } } else cout << "NO" << "\n"; } return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;} #include using namespace std;using ll = long long;bool solve() { int xa, ya, xb, yb, xc, yc; cin >> xa >> ya >> xb >> yb >> xc >> yc; int ans = 1; if (1LL * (xa - xb) * (xa - xc) > 0) ans += min(abs(xa - xb), abs(xa - xc)); if (1LL * (ya - yb) * (ya - yc) > 0) ans += min(abs(ya - yb), abs(ya - yc)); cout << ans << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;} 给一个只包含数位的原串 \(s\) ，以及长为 \(m\) 只包含数位的两个串 \(l,r\) 。
判断能否构造长为 \(m\) 的串，满足第 \(i\) 个数位在 \([l_i,r_i]\) 内，且不是 \(s\) 的子序列。
题解知识点：子序列自动机，贪心。
(资料图片仅供参考)
子序列自动机实际上就是 \(nxt_{i,j}\) ，表示位置 \(i\) 往后（不包括 \(i\) ）最近一个字符 \(j\) 的位置，可以逆推的形式构造出来。
通过这个自动机我们构造串的每个数位，显然如果当前位置能找到一个接下来不存在的数位，那么我们必定选它，否则我们选择出现位置最晚的那个数位。这样贪心保证如果存在解，那我们一定能取到。
时间复杂度 \(O(n+m)\)
空间复杂度 \(O(n)\)
代码#include using namespace std;using ll = long long;int nxt[300007][10];bool solve() { string s; cin >> s; int n = s.size(); s = "?" + s; int m; string l, r; cin >> m; cin >> l >> r; l = "?" + l; r = "?" + r; for (int i = 0;i <= 9;i++) nxt[n][i] = n + 1; for (int i = n - 1;i >= 0;i--) { for (int j = 0;j <= 9;j++) nxt[i][j] = nxt[i + 1][j]; nxt[i][s[i + 1] - "0"] = i + 1; } int pos = 0; for (int i = 1;i <= m;i++) { int mx = 0; for (int j = l[i] - "0";j <= r[i] - "0";j++) mx = max(mx, nxt[pos][j]); if (mx == n + 1) { cout << "YES" << "\n"; return true; } pos = mx; } cout << "NO" << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;} 给定一个长为 \(n\) 的整数数组 \(a\) ，现在从左往右累和。
现在规定一个数 \(k\) ，使得累和过程中若和一旦大于等于 \(k\) ，那么之后不会再小于 \(k\) 。
找到一个 \(k\) ，使得结果最大。
题解知识点：前缀和，贪心。
\(k\) 的作用是使得让和小于 \(k\) 的位置，经过它们之后的结果等于 \(k\) 。所以规定一个 \(k\) 之后，所有会让经过后的和小于 \(k\) 的位置是可以无视的。
实际上，我们可以把第一个位置到最后一个位置当作连续的一段，一起无视。原因是，假设有两个使得结果会小于 \(k\) 的相邻位置 \(i,j\) ，那么一定有经过 \([1,i]\) 后结果是 \(k\) ，之后再经过 \([i+1,j]\) 之后结果也是 \(k\) ，相当于从 \([i,j]\) 的位置全部被无视了。
因此，对于一个 \(k\) ，最终结果等于总和减去一段被无视的连续段的和，理论上答案最大不会超过总和减去最小和子段。问题变为，找到一个 \(k\) ，其无视的一段连续段的和最小。
我们发现，实际上总是会有一个 \(k\) ，能满足被他无视的一段就是最小和子段，使得结果是理论最大值。只需要找到整个数组最小和的那个连续段 \([l,r]\) ，随后 \(k\) 即为 \([1,l-1]\) 的和。
结论的证明：
我们规定 \([1,l-1]\) 为 \(k\) ，并不会使得 \([1,l-1]\) 的和改变，变得大于 \(k\) ，而 \(k\) 即为 \([1,i-1]\) 的和所经历的最大值。因为， \([1,l-1]\) 一定是 \([1,i],i \in[1,l-1]\) 中最大的前缀和，否则若 \([1,i],i \neq l-1\) 是最大的前缀和，那么显然 \([i+1,l-1]\) 的和一定是负的，则 \([i+1,r]\) 为最小和子段，这就矛盾了。在这个 \(k\) 下， \([l,r]\) 一定是被无视的一段，即经过 \([l,r]\) 后结果还是 \(k\) 。首先结果不会小于 \(k\) ，若结果大于 \(k\) ，那么 \([l,r]\) 一定存在一段后缀是正的，否则我们从 \(l\) 开始从 \(0\) 累加，一旦和为负则累和归零继续，因为不存在一段后缀是正的，最后结果累和一定为 \(0\) ，结果也不可能大于 \(k\) 。因此，我们把这段后缀去掉会得到更小和的子段，与 \([l,r]\) 是最小和子段矛盾。而 \([r,n]\) 是不会被无视的，如果有一段被无视，那么其一定有一个前缀是负的，同样可以类似反证，因此和 \([l,r]\) 合并会得到更小和的子段，矛盾了。实际上，一开始证明答案的上限也可以得到这个结论。综上，我们只需要找到最小和子段 \([l,r]\) ，并让 \(k\) 为 \([1,l-1]\) 的和，那么 \([l,r]\) 一定是有且仅有的被无视的一段，且 \([1,l-1]\) 的和不会改变，那么结果即为总和减去最小和子段，是理论最大值。
以上整个过程，有两种实现方法：
枚举每个右端点 \(r\) 在 \([1,r]\) ，则 \([1,r]\) 中的最大前缀和作为 \(k\) ， \(k\) 取 \([k+1,r]\) 最小值位置时的值。枚举每个 \(k\) ，则在 \([k+1,n]\) 中找到最小前缀和（最大后缀和）作为 \(r\) ， \(k\) 取 \([k+1,r]\) 最小值位置时的值。时间复杂度 \(O(n)\)
空间复杂度 \(O(1)\)
代码#include using namespace std;using ll = long long;bool solve() { int n; cin >> n; ll l = 0, r = 0, mi = 0; ll k = 0; for (int i = 1;i <= n;i++) { int x; cin >> x; r += x; l = max(l, r); if (r - l < mi) { mi = r - l; k = l; } } cout << k << "\n"; return true;}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << "\n"; } return 0;} 关键词：
