Codeforces 比赛复盘与题解分析
实际考试时间为11月5日，因当天有Codeforces比赛，次日状态不佳。
总分：100 + 50 + 0 + 35 = 230 分，校内排名第二。[点击查看链接]
题目 T1：组合计数优化
本题考察对组合恒等式的理解与动态规划优化能力。 核心思路是枚举0的个数，通过组合数递推关系 $ C_n^i = C_{n-1}^i + C_{n-1}^{i-1} $ 推导出状态转移方程。 定义： - $ f_i $：长度为 $ i $ 且包含偶数个0的方案数； - $ g_i $：长度为 $ i $ 且包含奇数个0的方案数。 初始值：$ f_1 = m, g_1 = 1 $ 转移方程： $$ \begin{cases} f_i = m \cdot g_{i-1} + f_{i-1} \\ g_i = m \cdot f_{i-1} + g_{i-1} \end{cases} $$ 该递推可表示为矩阵形式，使用矩阵快速幂可在 $ O(\log n) $ 时间完成状态转移，整体复杂度 $ O(d^3 \log n) $，其中 $ d=2 $。 进一步数学推导可得闭式解： $$ \text{ans} = \frac{(m+1)^n + (m-1)^n}{2} $$ 此公式可通过单位根反演或生成函数方法证明。
#include
#define int long long
using namespace std;
const int mod = 998244353;
int n, m;
struct Matrix {
int a[2][2];
Matrix operator*(const Matrix& y) const {
Matrix z;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j)
z.a[i][j] = (a[i][0] * y.a[0][j] + a[i][1] * y.a[1][j]) % mod;
return z;
}
void set(int a00, int a01, int a10, int a11) {
a[0][0] = a00; a[0][1] = a01;
a[1][0] = a10; a[1][1] = a11;
}
} ans, base;
signed main() {
cin >> n >> m;
m %= mod;
--n;
ans.set(m, 1, 0, 0);
base.set(m, 1, 1, m);
while (n) {
if (n & 1) ans = ans * base;
base = base * base;
n >>= 1;
}
cout << ans.a[0][0];
}
题目 T2：数值稳定性与乱搞策略
本题涉及高精度数值计算，正解需使用自然对数将乘积转为求和，并结合泰勒展开截断前100项近似。 关键思想： - 对每个值取 $ \ln(1 - x) $，在区间 $ (0, 1) $ 内可用泰勒级数逼近； - 维护加法结果后还原指数； - 由于精度限制，仅保留前 $ d=100 $ 项即可满足要求。 时间复杂度约为 $ O(q \cdot d \cdot \log n) $，常数较大。 然而，数据设计存在明显缺陷： - $ O(qn) $ 的暴力做法仍可通过部分测试点； - 部分分设置不合理，导致大量选手通过随机化或启发式剪枝通过； - 甚至存在构造数据可使常见"乱搞"算法崩溃。 因此，一种可行的投机策略是： - 利用性质：当 $ x < 0.991 $ 时，经过约1300次迭代后其影响趋于零； - 使用线段树维护更新次数，若某节点更新超过阈值（如1300）则停止传播； - 在随机数据下表现良好，但易被构造数据卡死。 该方法在开启编译优化（O2）时可通过，但在某些环境下会因浮点精度问题失败。
#include
using namespace std;
const int MAXN = 1e5 + 10;
int n, q, opt, l, r, B;
double x;
struct tree {
double val;
int cnt;
} t[MAXN << 2];
void build(int l, int r, int rt) {
if (l == r) {
cin >> t[rt].val;
t[rt].val = 1 - t[rt].val;
return;
}
int m = (l + r) >> 1;
build(l, m, rt << 1);
build(m + 1, r, rt << 1 | 1);
t[rt].val = t[rt << 1].val * t[rt << 1 | 1].val;
}
double query(int l, int r, int L, int R, int rt) {
if (L <= l && r <= R) return t[rt].val;
int m = (l + r) >> 1;
double res = 1.0;
if (L <= m) res *= query(l, m, L, R, rt << 1);
if (m < R) res *= query(m + 1, r, L, R, rt << 1 | 1);
return res;
}
void update(int l, int r, int L, int R, int rt) {
if (t[rt].cnt > B) return;
if (l == r) {
t[rt].val = t[rt].val * x + (1 - x);
++t[rt].cnt;
return;
}
int m = (l + r) >> 1;
if (L <= m) update(l, m, L, R, rt << 1);
if (m < R) update(m + 1, r, L, R, rt << 1 | 1);
t[rt].val = t[rt << 1].val * t[rt << 1 | 1].val;
t[rt].cnt = min(t[rt << 1].cnt, t[rt << 1 | 1].cnt);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> q;
build(1, n, 1);
B = q;
if (n * q > 100000000) B = 1300;
while (q--) {
cin >> opt >> l >> r;
if (opt == 0) {
printf("%.6lf\n", query(1, n, l, r, 1));
} else {
cin >> x;
if (x == 1) continue;
update(1, n, l, r, 1);
}
}
}
题目 T3：动态规划状态设计难题
未掌握核心状态转移方式，未能写出正确解法，暂无补题记录。题目 T4：树上深度贪心结论题
观察到答案具有结构性特征：对于一棵树，设 $ s_i $ 表示深度大于等于 $ i $ 的节点数量，则最优答案为： $$ \max_{1 \le i \le \text{maxdep}} \left( i + \left\lceil \frac{s_{i+1}}{k} \right\rceil \right) $$ **解释逻辑**： - 深度 $ i $ 以内的点可以在当前层处理完毕； - 剩余的 $ s_{i+1} $ 个节点必须按 $ k $ 个一组分配，每组至少消耗一层； - 当 $ i $ 太小，$ \left\lceil \frac{s_{i+1}}{k} \right\rceil $ 被浪费； - 当 $ i $ 太大，$ i $ 本身贡献过大而 $ s_{i+1} $ 过小，不划算。 因此，最大值一定出现在某个平衡点。 **实现方法**： - 离线处理所有询问； - 将询问按 $ k $ 排序； - 使用双端队列维护凸包，利用斜率单调性进行决策点维护； - 类似于斜率优化中的"单调队列"技巧。 最终复杂度：$ O(n + q \log q) $，瓶颈在于排序。
#include
using namespace std;
const int MAXN = 1e6 + 10;
int n, T, a[MAXN], d[MAXN], cnt[MAXN], mxdep;
int head = 1, tail, q[MAXN], ans[MAXN];
struct ask {
int k, id;
bool operator<(const ask& other) const {
return k < other.k;
}
} t[MAXN];
long double slope(int x, int y) {
return 1.0 * (cnt[x + 1] - cnt[y + 1]) / (x - y);
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> T;
++cnt[1]; d[1] = 1;
for (int i = 1; i <= T; ++i) {
cin >> a[i];
t[i] = {a[i], i};
}
sort(t + 1, t + T + 1);
for (int i = 2; i <= n; ++i) {
cin >> a[i];
d[i] = d[a[i]] + 1;
++cnt[d[i]];
mxdep = max(mxdep, d[i]);
}
for (int i = mxdep - 1; i >= 1; --i)
cnt[i] += cnt[i + 1];
for (int i = 1; i <= mxdep; ++i) {
while (head < tail && slope(q[tail - 1], q[tail]) < slope(q[tail - 1], i))
--tail;
q[++tail] = i;
}
for (int i = 1; i <= T; ++i) {
while (head < tail && slope(q[head], q[head + 1]) > -t[i].k)
++head;
ans[t[i].id] = q[head] + ceil(1.0 * cnt[q[head] + 1] / t[i].k);
}
for (int i = 1; i <= T; ++i)
cout << ans[i] << " ";
}
