前情提要：CSP 考炸了，但勉强还是通过了全国 1= 线。 Day -14~-1： 加训加训。 Day 0： 在家复习。打了场 NOIP 模拟赛，$100+30+8+0=138$。 Day 1： 早上 $8:00$ 不到到考场。 进机房，没碰电脑。$8:15$ 看了考前须知。 $8:30$ 看 T1，感觉贪心题，解了一…

很典的分块题啊。 对于每个块内维护一个 Trie，每次加就块内暴力重构，建出 Trie 树，然后同时也可以删除节点，每次询问就块内询问并取最大值，注意到 $k$ 长区间其实就是 $s_i$ 与 $s_{i-k}$ 的异或和最大，这不就是 Trie 板子吗。 时间复杂度 $O(n \sqrt n \log V)$，略微卡…

5pts： 直接爆搜。$O(n^{2k})$。 40pts： 发现可能可以 DP。记 $f_{i,j}$ 为前 $i$ 个数中选 $j$ 个区间，则转移方程： $f_{i,j}=f_{i-1,j}$。（不选区间） $f_{i,j}=f_{l-1,j-1}+w_{l,i}$。（选区间） 时间复杂度 $O(n^2k)$。…

简单。 考虑一个 $s$ 里的字符被交换 $2k+1$ 次之后，就变成 $t$ 里的对应的字符，$2k$ 次就变成原来的了。同理，$t$ 是类似的。只要维护更改的次数，用什么数据结构都行。这里使用的是树状数组。 时间复杂度 $O((n+q) \log n)$。 AC Code： ``` #include using n…

考虑到 $a^k$ 与 $a^{k \bmod 998244352}$ 模 $998244353$ 是同余的（费马小定理）。所以就可以把 $a^{2^k} \bmod 998244353$ 转化为 $a^{2^k \bmod 998244352} \bmod 998244353$ 就可以快速幂了。 这时候再进行线段树维…

数据范围 时间复杂度 求解方法 $n \le 10$ $O(n!)$ 暴力枚举全排列 $n \le 20$ $O(2^n)$ 暴力 DFS，状压 DP。 $n \le 50$ $O(n^6)$ 高维 DP。 $n \le 100$ $O(n^4)$ 高维 DP。 $n \le 500$ $O(n^3)$ 三维 DP，区…

我们首先显然的，知道一个队列如果是合法的（就是可以在时间内实现出的），则设男生为 $-1$，女生为 $1$，后缀和永远小于 $2$（因为男多女少是不可能合法的）。 首先判无解。总后缀和大于等于 $2$ 时显然不行。如果是 $1$ 呢？那么第一个男生就会出现矛盾，所以只要总后缀和为正数就不行。 然后如果有解，怎么计算答案…

我们发现只有 $\gcd(p-1,q-1)=1$ 时 $(p,q)$ 才能被看到。证明也不难证，因为存在一个点 $(\dfrac{p-1}{\gcd(p-1,q-1)}+1,\dfrac{q-1}{\gcd(p-1,q-1)}+1)$，其与 $(p,q)$ 和 $(1,1)$ 共线。 所以考虑所有 $\gcd(p-1,…

该题放在 NOIP 模拟赛 T1。 显然的，发现我们最多也就是 $q$ 量级的输出，于是考虑线段树。 线段树里维护两个变量。是否存在 $1$，以及最小值。最后要求的就是在尽量靠近自己的小于当前可乘坐人数或者是 $1$ 的编号，然后如果那个团队的人数大于可乘坐人数就将可乘坐人数变成 $0$，并将该团队人数减掉剩下人数，并…

本游记没有 Day 0。 Day -inf： 初赛。 就去考了 S 的，因为 J 的我有 GESP 的成绩，免考了。 S 组最终初赛 $83.5$. Day -31~Day -24： 集训。 中间有两天参加了某神秘考试。 分数大致在 $125 \sim 260$ 之间。 Day -23 ~ Day -1： 模拟赛 +…

最近几十天总算把线段树的一些模板题吃透了。 【例 1】：序列，单点加 $k$，区间求和。（洛谷 P3368） 代码： ``` #include using namespace std; typedef long long ll; const ll N=500009; struct Segment{ ll l,r,sum…

首先，暴力的复杂度为 $O(nk)$，只能获得 14pts。 考虑为什么暴力抛这么慢。原因是暴力抛一个一个抛，太慢了，应该一段一段抛。 一段一段跳，就可以想到倍增，记 $p_{u,j}$ 为 $u$ 开始抛 $2^j$ 次抵达的位置，转移显然：$p_{u,j}=p_{p_{u,j-1},j-1}$。 然后最后求 $u$…

简单题。场切了。 考虑 $\sqrt n$ 下取整什么时候能被 $n$ 整除。 记 $\sqrt n$ 下取整为 $k$，则 $k^2 \le n 2$ 时 $k^2+ak>k^2+2k$，$a using namespace std; #define int long long const int Q=100009;…

30pts： 纯送分。 直接暴力枚举 $i,j$ 并暴力计算 $[i,j]$ 区间的和，时间复杂度 $O(n^3)$。 ``` #include using namespace std; typedef long long ll; const ll N=500009; ll a[N],s[N],n,m,ans; int…

很明显的贪心。 注意到最优秀的两个一定是换出来的比原先的要大很多的，于是我们考虑分别把差值先计算并放入两个数组中，再从大到小排序，最后求出最大值之和即可。 但是，这种方法有一个漏洞，就是两个最大差值的数的编号完全有可能相等。于是我们考虑如果相等时，就将一个换为第二大的数，至于怎么换呢，如果 $C-A$ 的第二大值和 $…

发现平均值等于区间和除以区间长度，而每个居民可以看作一个区间，然后就发现就是区间增加 $1$，区间求和，考虑线段树，是个模板。 但是题目中存在这样一句话：“需注意，部分居民可能在前一天深夜开始观看电视（例如 $23:45:30$），并在次日结束观看（例如 $01:15:00$）。” 然后我们考虑将这些区间分成两块，一块…

定义一个人的做题分数 $= \red 红 \times 1+\orange 橙 \times 2+黄 \times 3+\green 绿 \times 4+\blue 蓝 \times 5+\purple 紫 \times 6+ 黑 \times 7$，我到现在（写文章刻）为止，分数为 $18 \times 1+104…

三角函数是什么： $\sin \alpha$ 是正弦，就是对边比斜边。 若直角三角形 $ABC$，$C$ 是直角顶点，则 $\sin ∠A=\dfrac{BC}{AB}$，同理 $\cos \alpha$ 是余弦，是邻边比斜边，即 $\cos ∠A=\dfrac{AC}{AB}$，$\tan ∠A$ 是正切，是对边比邻…

首先考虑 $a=b$ 时，显然答案为 $0$。 再考虑 $a=1$ 时，答案显然为 $p$。 $b=1$ 同理。 然后分类讨论。 $\gcd(a,b) = 1$ 且 $a,b \ge 2$ 时，答案可能为 $p$。但也存在整数 $k$，使得 $\gcd(a,k),\gcd(b,k) \ge 2$，就比如 $k=ab$…

注意到 $A_i,A_j$ 必须是 $A_k$ 的因数，考虑先 $O(V \log V)$ 存下所有可能的因数，用 vector 存下之后再考虑枚举 $k$，然后枚举 $A_k$ 的所有因数 $x$，平均为 $O(\log V)$ 个，然后再用 map 记录所有出现的数的位置，由于只有 $10^6$，可以不用 map，…

虽然这题是数列分块题，但是这题也可以用线段树的方案解决，可以发现是单点查询区间更新问题，所以需要懒标记，设 toAdd 表示懒标记，则我们每次在线段树上更新时候，就采用区间三分离的方法，当无贡献的时候就直接返回，当整体贡献的时候这个整体的懒标记都加上 $c$，否则就在子树中递归，直到整体贡献为止，就实现了一个基本的区间…

这题主要求出现最多的字符，考虑模拟。用一个桶记录每个字符出现的次数，然后求最大值 $m$。输出时输出每个出现次数为 $m$ 的字符出现次数。时间复杂度 $O(n)$，其中 $n$ 是 $S$ 的长度。 AC 代码： ``` #include using namespace std; string s; int cnt[…

这题比较简单，难度大约普及-到普及/提高-。这题涉及到的就是数学期望。 针对 $20\%$ 的数据： 大暴力，时间复杂度 $O(nmk)$。 针对 $40\%$ 的数据： 大暴力带点常数优化，时间复杂度依然 $O(nmk)$。 针对 $60\%$ 的数据： 注意到每次射箭的期望得分是相同的，时间复杂度 $O(nm)$。…

本文大约 $3 \times 10^3$ 个字，阅读起来大约需要 $10$ 分钟。 DP 题目一般都是有 DP 的状态，状态转移方程和答案组成，我们每个 DP 的例题都会进行详解。 【例 1】（01 背包问题）你有 $n$ 个物品和一个载重为 $m$ 的背包，第 $i$ 个物品的重量为 $w_i$，价值为 $v_i$，…

观察到一个性质，这个牌组为顺子当且仅当它在排完序的数组里面正好是公差为 $1$，项数为 $K$ 的等差数列，很容易证明。 然后只要询问这样的等差数列存不存在就可以了。 对于这样的询问，我们考虑排序后的数组 $a$。 假设我们当前遍历到第 $i$ 个数。 如果 $a_i=a_{i-1}+1$，那么最长的顺子的长度就加 1…

题意概述： $N$ 个数的不降序列 $A_i,B_i$，求 $A_i+B_j$ 的前 $N$ 小，$N \le 10^5$。 $1.$暴力，考虑把所有 $N^2$ 个和加入堆中，求前 $N$ 个即可。时间复杂度 $O(N^2 \log N)$。 $2.$优化，注意到 $A_i,B_j$ 在这 $N$ 个和中当且仅当 $…

T1： 题意概述： 有 $n$ 次操作，有两种形式： 1.获得 $x$ 元或 $0$ 元。 2.获得 $y$ 元或 $[0,\frac{y}{2}下取整]$ 元的随机数。 问能不能通过 $n$ 次操作获得 $m$ 元。$T$ 组数据。 30pts： 枚举。 100pts： 数学题。 $m$ 的上界是 $ny$，$m>n…

T1 魔法森林 原题：P9504 题意概述：有一个 $n$ 个点 $m$ 条边的无向简单连通图，有两个属性 $A$ 和 $B$，每经过一条边 $A$ 就少 $1$，每条边有边权 $w$，若你在经过某条边时，属性 $A$ 的值为 $k$，则你的属性 $B$ 值会掉 $\dfrac{w}{k}$，若你需要从 $s$ 到 $…

很明显，这题就是一个 rsq，只不过是两个数组的 rsq 而已，而且还是静态的，很明显可以用前缀和，时间复杂度 $O(n)$。 代码： ``` #include using namespace std; typedef long long ll; ll r[N],d[N],s1[N],s2[N],n,m; int ma…

题意概述：有一个 $n$ 个数和一个 $m$ 个数的序列 $a_i$，$b_i$，询问存不存在 $a_i \times b_j=k$，$n，m \le 5 \times 10^5$。 针对 $50\%$ 的数据：$n \le 3000,m \le 3000$。 暴力（$50pts$）： 一看到 $n \le 3000$…