mip001's Blog

比赛链接：https://www.luogu.com.cn/contest/147008

虽然现在状态还是很答辩，不过 NOIP 但凡有现在一半的状态都不至于原地退役。

前言

你总说退役遥遥无期

转眼就各分东西

——《退役的你》

初闻不解曲中意，再闻已是曲中人。以前总喜欢看别人的退役记，现在轮到我来写了。

CSP 和 NOIP 双双爆炸，本来是冲着省队去的，没想到最后以省二草草收场。

本文可能比较长，可以在上方目录选择感兴趣的内容阅读，太久没写过了，文笔相当垃圾。

谁能想到会如此早退役呢。

前情提要：CSP 2023 死磕 T2 炸得很彻底，所以 NOIP 换了非常保守的比赛策略，不过这次感觉过于保守了，T3 和 T4 光顾着打暴力去了，如果能留出一些时间想正解的话 T3 或者 T4 应该能过掉一个。

不太记得具体时间了，所以时间可能不太准确

传送门

容易发现对于第 $i$ 秒，Bob 的选择是固定的，所以可以用线段树 $O(n\log n)$ 预处理出来 Bob 每一秒选择的 $w_i$ 和 $d_i$。

然后考虑倒着 dp，我们设 $f_{i,j}$ 表示第 $i$ 到 $n$ 秒干扰 $j$ 次收集到的最少钱数，转移方程就是：

$$f_{i,j}=\min(f_{d_i+1,j}+w_i,f_{i+1,j-1})$$

时间复杂度 $O(nm)$。

这篇其实早就写好了，只是一直搞忘了放上来。

题意：给定长度为 $n$ 的序列 $a$，令 $f(l,r,x)$ 为 $a[l,r]$ 内 $x$ 的出现次数，$m$ 次询问，找到一个 $p$ 使得 $f(1,p,x)\times f(p+1,n,y)$ 最大，输出最大值。

$1\leq n,m\leq 10^5,1\leq a_i\leq 10^9$

纪念我本场唯一一道赛时过的题

题意：有一个长度为 $10^9$ 的序列 $a$，初始均为 $0$。给定 $n$ 个序列上的区间 $[l_i,r_i]$。进行 $m$ 次操作，每次给定 $p,x$，表示让 $a_p$ 加上 $x$。每次操作之后，令区间 $[l_i,r_i]$ 的权值为 $\sum\limits_{j=l_i}^{r_i} a_j$，你需要找到这 $n$ 区间中的最大权值。

$1\leq n,m\leq 4\times 10^5$

题目传送门

题目翻译：

给定长度为 $n$ 的序列 $a$。对于 $1\leq i<j\leq n$，若不存在 $k\in[1,n]$ 使得 $a_k\mid a_i$ 且 $a_k\mid a_j$ 那么 $(i,j)$ 是好的。求出好的数对数量。$a_i,n\leq 10^6$。

注意到若 $a_k\mid a_i$ 且 $a_k\mid a_j$，那么 $a_k$ 一定也能整除 $\gcd(a_i,a_j)$。那么我们可以通过枚举 $g$，找出最大公约数为 $g$ 的数对的个数 $f_g$，最后答案即为 $\sum f_g[\forall 1\leq k\leq n,a_k\nmid g]$。

传送门

简要题意：求长为 $n$ 的排列的波动序列的个数。

考虑 DP，设 $f_{i,j}$ 表示长度为 $i$ 的排列中，不合法元素有 $j$ 个的方案数，其中不合法元素指的是一个排列里既不是山峰也不是山谷的元素。显然我们最后要的答案即为 $f_{n,0}$。下面考虑转移

可以考虑如何从 $f_i$ 推 $f_{i+1}$。这其实相当于在长度为 $i$ 的排列中插入一个数 $i+1$，显然 $i+1$ 就是是这个排列里最大的数了。容易发现，插入这个数后这个排列的不合法元素要么不变，要么加一，要么减一，那么我们分别分析这三种情况。