A代码

#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;}

B代码

#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;}

C题目

给一个只包含数位的原串 \(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;}

D题目

给定一个长为 \(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;}

关键词：