OI集训 Day19
Content：欢乐 ACM
Date：2025.8.4
内容
休息一天喵o(〃＾▽＾〃)o~
All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
Related Articles
2025-08-08
OI集训 Day23
Content：交互、通信、提交答案题 Date：2025.8.8 题目 CodeForces-P1672E notepad.exe 题目大意 交互题。 有 nnn 个长度分别为 lil_ili 的单词，要求将这些单词排放在一个记事本当中，每两个单词之间需要空格（换行不需要）。你最多可以询问 n+30n+30n+30 次，每次可以询问一个宽度 www，裁判会告诉你至少需要高度为 hhh 的记事本才可以放下所有的单词，求 min{hw}\min\{ hw \}min{hw}。 思路 考虑先用 30 次找出将所有单词放在一行所需的最少宽度 w0w_0w0，然后对于每一个 1≤i≤n1 \le i \le n1≤i≤n，询问排列成 iii 行需要的最少行数，询问次数正好 n+30n + 30n+30 次。 提交记录：Link CodeForces-1010B Rocket 题目大意 交互题。 你可以问裁判 60 次问题，裁判会根据一个循环节长度为 nnn 的数组回答你的问题：如果 ai=0a_i = 0ai=0，则第 iii 次回答的是假话；如果 ai=1a_i = 1ai...
2025-07-17
OI集训 Day1
Content：Data Structs Date：2025.7.17 内容 并查集 ST表 线段树 关于树状数组 一维树状数组 单点修改，区间查询 对于这一类最普通的树状数组，没有什么好说的，直接维护前缀和即可。 struct BIT { long long tr[N]; static int lowbit(int x) { return x & (-x); } void add(int pos, long long value) { for (int i = pos; i <= n; i += lowbit(i)) tr[i] += value; } long long query(int pos) { long long retval = 0; for (int i = pos; i > 0; i -= lowbit(i)) retval += tr[i]; return retval; }} ...
2025-07-28
OI集训 Day12
Content：模拟赛 Date：2025.7.28 Problem-A 排序 题目大意 优化程序： #include <algorithm>#include <cmath>#include <iostream>const int N = 3e7 + 5;int n, seed;double a[N];void gen_input(const int n, const int seed) { double x = (double)(seed); unsigned int iseed = seed; for (int i = 0; i < n; ++i) { iseed = iseed * 1664525 + 1013904223; x = (std::sin(iseed % 4096) + 1) / 2; a[i] = std::fabs(x * (iseed >> (iseed % 30))) + 1e-9; }}int main() { std...
2025-07-26
OI集训 Day10
Content：dp优化 Date：2025.7.26 例题 洛谷-P1886 滑动窗口 思路 直接单调队列维护即可，具体操作如下： 每次查看队尾的元素，维护单调性。 对于队头不在当前滑动窗口的元素，弹出。 提交记录：link 洛谷-P2365 任务安排 思路 定义 dpidp_{i}dpi 表示第 iii 个任务完成所花费的最小代价。转移如下： dpi=min1≤j≤idpj+(s+Ti−Tj−1)×(Fn−Fj−1)dp_{i} = \min_{1 \le j \le i} dp_{j} + (s + T_i - T_{j-1}) \times (F_{n} - F{j - 1}) dpi=1≤j≤imindpj+(s+Ti−Tj−1)×(Fn−Fj−1) 对于本题数据范围 n≤3000n \le 3000n≤3000，O(n2)O(n^2)O(n2) 可过。 提交记录：link 洛谷-P10979 任务安排 2 思路 dpdpdp 的方式和定义与前面相同，但是 O(n2)O(n^2)O(n2) 的复杂度无法接受，所以考虑优化。 将 dpdpdp 的式子...
2025-07-27
OI集训 Day11
Content：矩阵 DP Date：2025.7.27 Review 矩阵基本操作：link Example1 - 洛谷-P1962 斐波那契数列 题目描述 给定 nnn，求斐波那契数列的第 nnn 项 fnf_nfn。 fn={1n=0,1fn−1+fn−2oterwisef_n = \begin{cases} 1 & n = 0,1 \\ f_{n-1} + f_{n-2} & oterwise \end{cases} fn={1fn−1+fn−2n=0,1oterwise 数据范围：n<263n < 2^{63}n<263。 思路 首先显然 O(n)O(n)O(n) 的递推是不行的了，我们考虑将递推式转化为矩阵乘法的形式： [fn−1fn−2]×[1101]=[fnfn−1][fn−2fn−3]×[1101]2=[fnfn−1]…[f0f1]×[1101]n−2=[fnfn−1]\begin{aligned} \begin{bmatrix} f_{n - 1} \\ f_{n - 2} \end{bmatrix}...
2025-07-31
OI集训 Day15
Content：组合数学 Date：2025.7.31 课堂内容 容斥原理 其主要思想为：把禁止违反哪些规则改为钦定违反了哪几条规则，并赋予 (−1)k(-1)^k(−1)k （即违反 kkk 条规则）的容斥系数。 二项式反演 g(n)=∑i=0n(ni)f(i)⇔f(n)=∑i=0n(−1)n−i(ni)g(i)g(n)=∑i=nN(in)f(i)⇔f(n)=∑i=nN(−1)i−n(in)g(i)\begin{aligned} g(n) &= \sum_{i=0}^n \binom{n}{i} f(i) \Leftrightarrow f(n) = \sum_{i=0}^n (-1)^{n-i} \binom{n}{i} g(i) \\ g(n) &= \sum_{i=n}^N \binom{i}{n} f(i) \Leftrightarrow f(n) = \sum_{i=n}^N (-1)^{i-n} \binom{i}{n} g(i) \end{aligned} g(n)g(n)=i=0∑n(in)f(i)⇔f(n)=i=0∑n(−1)n−i(...
