OI集训 Day23
Content：交互、通信、提交答案题
Date：2025.8.8
题目
CodeForces-P1672E notepad.exe
题目大意
交互题。
有 个长度分别为 的单词，要求将这些单词排放在一个记事本当中，每两个单词之间需要空格（换行不需要）。你最多可以询问 次，每次可以询问一个宽度 ，裁判会告诉你至少需要高度为 的记事本才可以放下所有的单词，求 。
思路
考虑先用 30 次找出将所有单词放在一行所需的最少宽度 ，然后对于每一个 ，询问排列成 行需要的最少行数，询问次数正好 次。
提交记录：Link
CodeForces-1010B Rocket
题目大意
交互题。
你可以问裁判 60 次问题，裁判会根据一个循环节长度为 的数组回答你的问题：如果 ，则第 次回答的是假话；如果 ，则第 次回答的是真话。你并不知道这个数组 。你需要猜一个数 。每次询问你可以问裁判一个数，他会回答你这个数是 大于(1)、等于(0)、小于(-1)（遵守之前的规则）。
思路
首先范围 ，所以我们可以先用 30 次机会，每次询问 1，就可以得到数组 。然后二分答案 就可以了，总询问次数为 60 次。
提交记录：Link
Luogu-P1337 平衡点 / 吊打 XXX
题目大意
求 个点的带权费马点。
思路
考虑使用模拟退火，随机检查，剩下的就交给阳寿吧（WA 6）。
提交记录：Link
Luogu-P5285 [十二省联考] 骗分过样例
写这道题上来只是小小的心灵受到了大大的震撼。怎么做到再 组数据中找规律的啊！
All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
Related Articles
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(...
2025-07-29
OI集训 Day13
Content：平衡树 Date：2025.7.29 具体内容 Leafy Tree 和 Un-leafy Tree Leafy Tree：表示将所有的数据存放在叶子节点的树形数据结构，类似 线段树 和 WBLT 平衡树。 Un-leafy Tree：与 Leafy Tree 相反，将数据存放在每个树节点的数据结构。 替罪羊树 替罪羊树是最简单的平衡树，也是 Un-leafy 的，其核心思想是定义一个常数 α\alphaα，对于树上任意节点 uuu，若 max(sizlsu,sizrsu)≥α×sizu\max(siz_{ls_{u}}, siz_{rs_{u}}) \ge \alpha \times siz_umax(sizlsu,sizrsu)≥α×sizu，则将整棵树拍平成数组，对整棵树重构，使其保持平衡性。 替罪羊树的复杂度是 O(nlogn)O(n \log n)O(nlogn) （均摊）的，同时 α\alphaα 的取值对复杂度的影响是直接的，当 α\alphaα 在区间 [0.5,1][0.5,1][0.5,1] 之间时，复杂度时最优的，一般取 α=...
