OI集训 Day19
Created|集训总结(2025暑)
|Word Count:17|Reading Time:1mins|Post Views:
Content:欢乐 ACM
Date:2025.8.4
内容
休息一天喵o(〃^▽^〃)o~
Author: FallenLeaf
Copyright Notice: 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(...
Announcement
欢迎来到我的博客喵~
Contents
Recent Posts
