Codeforces-Till I Collapse 解题笔记
题目来源 Codeforces Round 406 (Div. 1) C. Till I Collapse Vjudge页面 题意简述 长度为 nnn 的正整数序列 aia_iai ，数字表示颜色。将序列划分成尽可能少的连续段，每段中颜色的数量不能超过 kkk 。对于所有的 k∈[1,n]k\in[1,n]k∈[1,n] 输出答案。 n≤1×105,ai≤nn\le1\times10^5,a_i\le nn≤1×105,ai≤n 解题思路 暴力的贪心做法是，对于一个确定的 kkk ，从左往右进行划分，尽可能把每一段划分得更长。因为所有的段都是连续的，一个接一个排列，显然，这样的贪心策略不会使得答案更劣。暴力的复杂度为 O(nk)O(nk)O(nk) 。 显然，确定一个区间端点后，区间长度越大，区间..
更多SPOJ Give Away 解题笔记
简直和 UVA-12003 Array Transformer 解题笔记 一模一样。 把这题写一遍单纯是为了巩固分块实现能力。 实际写起来还真的 WA 了一发，确实有很多易错的地方，绝知此事要躬行。 尤其是循环的对象问题。是循环原序列还是块序列？想清楚再写。 #include<bits/stdc++.h> #define N 500100 #define Q 100100 using namespace std; int n,x[N],q; int op,a,b,c; int id[N],len,num; vector<int> block[N]; inline void change(int a, int b){ int aid = id[a]; x[a] = ..
更多UVA-11990 Dynamic Inversion 解题笔记
题目来源 UVA - 11990 Dynamic Inversion Vjudge 页面 题意简述 将一个 n≤2×105n\le 2\times10^5n≤2×105 的排列逐个删去 m≤1×105m\le1\times10^5m≤1×105 个元素，问每次删除元素之前，排列中有多少个逆序对。 解题思路 本题和 UVA-12003 Array Transformer 解题笔记 几乎一模一样，都是分块并在每次修改后保持块内有序，由此可使用二分查找实现高效的查询。 在求逆序对数量初值的时候使用树状数组即可，此后每一次删掉一个数字就查询其左侧比它大的数的数量，在总逆序对数量中减掉即可。 保持块内有序的方式依然可以使用冒泡排序，减少一个 log\loglog 。 与 UVA-12003 实在太像了，代码略..
更多UVA-12003 Array Transformer 解题笔记
题目来源 UVA - 12003 - Array Transformer Vjudge 页面 题意简述 长度为 n≤3×105n\le 3\times10^5n≤3×105 的序列做 m≤5×104m\le 5\times10^4m≤5×104 次操作，每次操作询问 [L,R][L,R][L,R] 之间小于 vvv 的数的个数 kkk ，然后将 apa_pap 修改为 ⌊u∗kR−L+1⌋\displaystyle \left\lfloor \frac{u*k}{R-L+1} \right\rfloor⌊R−L+1u∗k⌋ 。 解题思路 显然这题用线段树是很容易解的，不过我把这个题当做分块的练习题来做，不使用任何树形数据结构。 假设块长为 sss 每次修改完后将 ppp 所在块内的数据排序，复杂度..
更多LOJ6280 分块入门 区间和 解题笔记
题目来源 LibreOJ 6280 数列分块入门 4 题意简述 序列区间加与查询区间和， n≤5×104n\le5\times 10^4n≤5×104 。 解题思路 分块，操作区间中不是整块的部分暴力求解，是整块的部分打标记。 重点在时间复杂度的计算上。 最坏复杂度为操作区间几乎覆盖整个序列时，此时中间的整块数量近似于 ns\displaystyle\frac{n}{s}sn ，两端的非整块长度为 2s2s2s 。忽略常数，单次操作最坏时间复杂度为 O(ns+s)\displaystyle O(\frac{n}{s}+s)O(sn+s) 。 运用基本不等式 ns+s≥2ns⋅s=2n\displaystyle\frac{n}{s}+s\ge2\sqrt{\frac{n}{s}\cdot s}=2\..
更多
高级数据结构 学习笔记
前言 本文主要根据 OIwiki 的数据结构部分展开，也按照常见的考点加入了一些图论、字符串领域的数据结构。本文只包含最基本的理论介绍，相关的实现方式、具体的解题思路和代码都放在站内其他文章中。 后续做到比较好的数据结构题也会添加进这篇文章中来。 块状数据结构 分块初步 经典例题1：参见站内文章 LOJ6280 分块入门 区间和 解题笔记 总体思路：寻找一种合理的分块方式，操作区间中不是整块的部分暴力求解，是整块的部分打标记。 寻找最优分块方式，通常是对最坏时间复杂度求最小值，取得最小值时的约束条件可以得到最优块长。 在分块的基础上，依然可以使用差分、前缀和等方式来优化算法。差分、前缀和不仅可以对原序列使用，也可以对块序列使用。 相关注意事项： 块长不一定等于块数。 区间两端点在同一个块中，必须特判..
更多
复变函数与积分变换 学习笔记
前言 本文由周国全老师的数学物理方法、翔翔的学习频道在B站上传的视频总结而来，借用了华中科技大学的复变函数讲义。 感谢周国全老师、UP主翔翔和华中科技大学！ 第一章 解析函数 第一节 复数及其运算 基本定义 对于复数 z=x+iy∈Cz=x+\mathrm{i}y\in\mathbb{C}z=x+iy∈C ，称 x=Rezx=\mathrm{Re}zx=Rez 为其实部， y=Imzy=\mathrm{Im}zy=Imz 为其虚部。两复数相等，当且仅当他们的实部和虚部分别相等。用 z‾\overline{z}z 或 z∗z^*z∗ 表示与 zzz 实部相等、虚部相反的共轭复数（complex conjugation）。 通过两个共轭复数可以得出实部和虚部，这个方法非常重要。 x=z+z‾2x=\fr..
更多概率论数理统计 学习笔记
前言 感谢B站up主高数叔！每次上课之前打个铃，很有仪式感。 第一章 随机事件与概率 随机事件关系及其运算 名称 符号 理解 集合定义 AAA 包含 BBB A⊃BA\supset BA⊃B 事件 BBB 发生必有事件 AAA 发生 BBB 是 AAA 的子集 AAA 与 BBB 相等 A=BA=BA=B 事件 AAA 发生必有事件 AAA 发生且事件 BBB 发生必有事件 AAA 发生 AAA 与 BBB 包含的样本点相同 AAA 与 BBB 的和 A∪BA\cup BA∪B 事件 A∪BA\cup BA∪B 发生 ⇔\Leftrightarrow⇔ 事件 AAA 发生或事件 BBB 发生 AAA 与 BBB 的并集 AAA 与 BBB 的积 A∩BABA\cap B \\..
更多科目一知识点整理
超员 车型 (0,20%)(0,20\%)(0,20%) [20%,50%)[20\%,50\%)[20%,50%) [50%,100%)[50\%,100\%)[50%,100%) [100%,+∞)[100\%,+\infty)[100%,+∞) 校、公、旅 6 12 12 12 7座以上载客汽车 6 9 12 其他车 3 6 12 超载 车型 (0,30%)(0,30\%)(0,30%) [30%,50%)[30\%,50\%)[30%,50%)或载客 [50%,+∞)[50\%,+\infty)[50%,+∞) 载货汽车 1 3 6 超速 科目一过了😁，此文断更
更多行为经济学导论 学习笔记
行为经济学导论 Edoardo Galllo, Cambridge 两本参考书籍： Thinking fast and slow, by Kahneman Nudge: Improving Decsions About Health, Wealth and Happiness, by Thaler 开卷考试，20个选择题，有多选 第一节 行为经济学导论介绍 凯恩斯选美比赛 规则：每人从1~100中选择一个自己眼中最美的数字，被最多人公认的数字为最美数字，选中最美数字的人胜出。 特点：所有人选择数字的依据不是自己的想法，而是其他大多数人的预期。 类比：选数字相当于选股票。 阿莱悖论 彩票组1： 彩票A：100%概率获得 £500,000\pounds500,000£500,000 ..
更多