A 小花的糖果
知识点：数学
我们不妨把奇偶两个礼盒看成一组，每组可以容纳 $2k+1$ 颗糖果。设我们需要 $t$ 组礼盒，最后剩下 $d$ 颗糖果，即 $t(2k+1) + d = n$。
对于这 $d$ 颗糖果，由于前面的礼盒两两一组，所以下一个礼盒编号一定是奇数，也就是容纳 $k$ 颗糖果。所以我们检查 $d$ 颗糖果是否能全放到这个礼盒中，如果不能则需要再加一个礼盒。根据除法的性质，必然有余数 $d$ 小于除数 $2k+1$，所以至多需要额外加入两个礼盒，刚才的讨论已经能够覆盖所有情况了。
时间复杂度 $\mathcal O(1)$。
void solve() {
int n, k;
cin >> n >> k;
auto [t, d] = div(n, 2 * k + 1);
cout << 2 * t + (d != 0) + (d > k) << endl;
}B 小花的快递
知识点：数学，思维
对于一个任意的包裹 $i$，我们往里追加一个包裹 $j$，它的邮费要么是 $a_i + a_j$，要么是 $b_i+b_j$。
然后在此之上，我们追加一个包裹 $k$，它的邮费要么是 $a_i+a_j+a_k$，要么是 $b_i+b_j+b_k$。
也就是说，最后的邮费要么全是 $a$ 给出的，要么全是 $b$ 给出的，不会出现 $a,b$ 混合的情况，所以分别进行求和即可。
时间复杂度 $\mathcal O(n)$。
void solve() {
int n, a = 0, b = 0;
cin >> n;
for (int i = 0, x; i < n; ++i) cin >> x, a += x;
for (int i = 0, x; i < n; ++i) cin >> x, b += x;
cout << max(a, b) << endl;
}C 小花的星图
知识点：图论，构造
首先考虑边界，增加 $m$ 条边，至多减少 $\min(n-1, m)$ 个连通块，至少减少 $x:\frac{x(x+1)}{2}\ge m$ 个连通块（其中 $\frac{x(x+1)}{2}$ 条边构成了大小为 $x+1$ 的完全图）。所以如果 $n-\min(n – 1, m) > k$（此时等价于 $n-m>k$）或 $n – x < k$（此时等价于 $\frac{(n-k)(n-k+1)}{2} < m$，证明如下）。
定理. 设 $x^*=\min{x\in\mathbb Z_{\ge0}:\frac{x(x+1)}{2}\ge m}$，则
$$n-x^*<k\iff \frac{(n-k)(n-k+1)}{2}<m\qquad(1\le k\le n).$$
证明. 记 $f(t)=\frac{t(t+1)}{2}$。
引理. $t\ge 0$ 时 $f$ 严格递增，故 $t<x^*\iff f(t)<m$。
证. $f(t+1)-f(t)=t+1>0$，严格递增；再由 $x^*$ 的最小性与可行性即得。
由 $1\le k\le n$ 得 $n-k\ge0$，代入引理：
$$n-x^*<k \iff x^*>n-k \iff n-k<x^* \iff f(n-k)<m,$$
即 $\dfrac{(n-k)(n-k+1)}{2}<m$，证毕！
于是我们进行构造，如刚刚所言，我们可以将 $n-k$ 个点连成一个连通块，再同构造完全图的方法一样，将边放进去。
时间复杂度 $\mathcal O(m)$。
void solve() {
int n, m, k;
cin >> n >> m >> k;
if (n - m > k || m > (n - k) * (n - k + 1) / 2) return cout << -1 << endl, void();
vector<pii> e;
for (int i = 1; i < n - k + 1 && m-- > 0; ++i) e.push_back({i, i + 1});
for (int i = 1; i <= n - k + 1 && m > 0; ++i) {
for (int j = i + 2; j <= n - k + 1 && m-- > 0; ++j) {
e.push_back({i, j});
}
}
for (auto [u, v] : e) cout << u << " " << v << endl;
}D 小花的奶茶
知识点：模拟
我们用 $f$ 表示每杯奶茶的结束时间，$g$ 代表取走的时间。按照点单时间（取餐号）从小到大处理每一个订单（记点单时间 $u$，到店时刻 $v$，制作时间 $w$）：
- 每杯奶茶必须要等到上一杯结束后才可以开始制作，所以有 $f(i) = \max(f(i – 1), u) + w$。
- 每杯奶茶必须要顾客到店之后才能被拿走，所以有 $g(i) = \max(f(i), v)$。
- 每杯奶茶必须要窗口内的前一杯被取走后才能被取走，一共 $10$ 个窗口，所以这个窗口的上一杯是的取餐号为 $i-10$，所以有 $g(i) = \max(g[i], g[i-10]),;i > 10$。
时间复杂度 $\mathcal O(n)$。
void solve() {
int n;
cin >> n;
vector<array<int, 4>> a(n);
for (int i = 0; i < n; ++i) {
auto &[u, v, w, id] = a[i];
cin >> u >> v >> w, id = i;
}
ranges::sort(a);
vector<int> f(n + 1), t(n + 1), ans(n);
for (int i = 1; i <= n; ++i) {
auto [u, v, w, id] = a[i - 1];
f[i] = max(f[i - 1], u) + w;
t[i] = max(f[i], v);
if (i > 10) t[i] = max(t[i], t[i - 10]);
ans[id] = t[i] - v;
}
for (auto v : ans) cout << v << " ";
cout << endl;
}E 小花的彩带
知识点：计数，动态规划
对于“把序列划分成若干块、每块要满足某条件”这样的题，几乎都是枚举最后一块的范围，前面的部分递归成子问题。
对于本题，设最后一段是 $s[j..i]$，颜色为 $c$。那么
- 它的长度 $i-j+1\in[L,R]$；
- 它内部必须全为 $c$；
- 它前面 $s[1..j-1]$ 必须是一个合法串，且以 $1-c$ 结尾（否则两段会合并）。
于是整个串的计数 $=$ 对 $(j,c)$ 求和”前面那部分的计数”。于是我们考虑使用动态规划进行求解。
最朴素的想法是用 $dp[i][c][\textrm{len}]$ 表示填到 $i$、最后一位是 $c$、当前段已经长 $\rm len$。但 $\rm len$ 有 $R$ 种取值，显然通过不了。所以我们考虑降维，因为只要知道”最后一段从哪开始”，$\rm len$ 自然就是 $i-j+1$。于是把状态换成”第 $i$ 位是某一段的结尾”，长度维度就被求和消掉了：
$$dp_c[i]=\sum_{\substack{t:\ i-t\in[L,R]\ s[t+1..i]\ \text{可以全为}\ c}} dp_{1-c}[t]$$
由于段内不能出现固定的异色字符，所以窗口的左端点要被最近一次出现的固定异色字符卡住：
- 记 $l_0 / l_1$ 为最近一次固定 $0 / 1$ 的位置；
- $0$ 段的起点必须在 $l_1$ 之后 $\rightarrow$ 前缀和的下界取 $\max(i-R,\ l_1)$。
对于这样求和式的 $\tt dp$ 转移，我们显然可以使用前缀和去维护。
时间复杂度 $\mathcal O(n)$。
using Z = MInt<mod>; // 自动取模
void solve() {
int n, l, r;
string s;
cin >> n >> l >> r >> s;
s = '@' + s;
vector<Z> p0(n + 1), p1(n + 1);
p0[0] = p1[0] = 1;
int l0 = 0, l1 = 0;
Z dp0, dp1;
for (int i = 1; i <= n; ++i) {
if (s[i] == '0') l0 = i;
if (s[i] == '1') l1 = i;
int R = i - l;
auto ask = [&](const vector<Z> &p, int l, int r) -> Z {
if (l > r) return 0;
return p[r] - (l ? p[l - 1] : 0);
};
dp0 = ask(p1, max(i - r, l1), R), dp1 = ask(p0, max(i - r, l0), R);
p0[i] = p0[i - 1] + dp0;
p1[i] = p1[i - 1] + dp1;
}
cout << dp0 + dp1 << endl;
}F 小花的面包
知识点：计数，组合数学，容斥，状压枚举，Lucas定理
回文要求 $c_i=c_{m+1-i}$，所以只需决定前 $\lfloor m/2\rfloor$ 组：
- 每一对 $(i,;m+1-i)$ 取同一个值 $x_i$，贡献 $2x_i$，取值范围 $1\le x_i\le c_i$，其中 $c_i=\min(a_i,a_{m+1-i})$；
- 若 $m$ 为奇数，正中间那一组 $y=c_{(m+1)/2}$ 单独贡献 $y$，$1\le y\le a_{\lfloor m/2\rfloor}$。
于是方案数 = 下面这个方程的解数：
$$2\sum_{i=1}^{q}x_i+[\text{$m$ 为奇数}]\cdot y=n .$$
令 $y=b+2z$（$z\ge0$）、$x_i=1+u_i$（$u_i\ge0$）。记 $q=\lfloor m/2\rfloor$。因为 $2\sum x_i$ 永远是偶数，所以：
- $m$ 是偶数：$n$ 必须是偶数，令 $b=0$；
- $m$ 是奇数：$y\equiv n\pmod 2$，最小可行值 $b=1$（$n$ 奇）或 $b=2$（$n$ 偶）。
方程变成
$$\sum_{i=1}^{q}u_i+z=t,\qquad t=\frac{n-b}{2}-q .$$
约束只剩上界：$u_i\le c_i-1$，$z\le\lfloor(a_{q+1}-b)/2\rfloor$。
这是一个比较经典的模型，不带上限的解数是 $\binom{t+d-1}{d-1}$（$d$ 个变量），带上限就需要用容斥计算：
$$\text{ans}=\sum_{\text{mask}}(-1)^{|\text{mask}|}\binom{t-\sum_{i\in\text{mask}}c_i+d-1}{d-1},$$
即”至少这些变量超上界”的方案数，超上界的处理就把 $c_i$ 从上界里扣掉。
由于 $n\le10^{17}$ 远超模数 $998244353$，$\binom{N}{k}\bmod p$ 不能直接用阶乘预处理，这里套一个 $\tt Lucas$ 定理的板子就可以了。
时间复杂度 $\mathcal O(2^{m/2}\cdot m\cdot\log_p n)$ 。
using Z = MInt<mod>; // 自动取模
struct Comb {...} C; // 组合数学
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(m);
for (auto &v : a) cin >> v;
int q = m / 2, b = (m & 1) ? ((n & 1) ? 1 : 2) : 0;
if (n < b || (n - b) % 2 || ((m & 1) && a[q] < b)) return cout << 0 << endl, void();
vector<int> c;
for (int i = 0; i < q; ++i) c.push_back(min(a[i], a[m - 1 - i]));
c.push_back((m & 1) ? (a[q] - b) / 2 + 1 : 1);
int t = (n - b) / 2 - q;
if (t < 0) return cout << 0 << endl, void();
int d = c.size(), lim = 1LL << d;
vector<int> sum(lim);
for (int mask = 1; mask < lim; ++mask) {
int bit = __builtin_ctzll(mask);
sum[mask] = sum[mask ^ (1LL << bit)] + c[bit];
}
auto L = [&](int n, int m) -> Z {
if (n < 0 || m < 0 || m > n) return 0;
Z ans = 1;
while (n || m) {
int x = n % mod, y = m % mod;
if (y > x) return 0;
for (int i = 1; i <= y; ++i) ans *= x - y + i;
ans *= C.ifac(y);
n /= mod, m /= mod;
}
return ans;
};
Z ans = 0;
for (int mask = 0; mask < lim; ++mask) {
int r = t - sum[mask];
if (r < 0) continue;
Z cur = L(r + d - 1, d - 1);
ans += (__builtin_popcountll(mask) & 1) ? -cur : cur;
}
cout << ans << endl;
}约定
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int, 2>
#define endl "\n"
void solve() {}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int t = 1;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}使用到的算法模板见 $\tt Github$ 仓库 林月的XCPC模板库