考试LIST [2020.09]

2020.09.05

$\texttt{Location:NOIP2020}$

得分:$\texttt{130/300,Rank3}$。

[09.05]-错误

$\texttt{T1}$ 很快想到了正解,写得却很慢,浪费了很多时间。

$\texttt{T1}$ 空间计算不准,导致差点爆 $0$。

$\texttt{T2}$ 多种情况的树形 $\texttt{dp}$ 少算了一种情况,导致 $\texttt{WA}$。

$\texttt{T3}$ 部分分策略错误。选择先刚了 $\texttt{1h+}$ 的正解,暴力一分没写,又写了很久的随机化,最后少拿了 $\texttt{10pts}$ 的部分分。

[09.05]-部分正解

$\texttt{T1}$

最大子矩形裸题,直接悬线法。

$\texttt{T2}$

多状态树形 $\texttt{dp}$,对每一种节点形态设一个状态做 $\texttt{dp}$。注意考虑一个点拉下去一条链,再接着两条链的情况。

$\texttt{T3}$

原题 P2050 [NOI2012]美食节

考虑费用流。发现对于第 $i$ 个通过的鸟,后面有 $n-i$ 个等待,因此可以对每一个洞,拆成很多时刻,不同时刻对总时间的贡献是不一样的,具体来说就是乘上一个时间戳。

这样边数太多了,但是我们发现如果一个洞还没有一只鸟通过,那么显然时间戳第 $2$ 及后面的边都没必要连。所以我们可以直接用 $\texttt{SPFA}$ 找到增广路后暴力更新 $1$ 的流量,然后对那些跑满了的点继续动态加边。

复杂度比较玄学,不过貌似是 $O(nmp)$。


2020.09.06

$\texttt{Location:NOIP2020}$

得分:$\texttt{300/300,Rank1}$。5个并列

[09.06]-错误

做题策略不够好,先肝了好久的 $\texttt{T1}$,脑袋糊掉了,导致后面写题很慢。

[09.06]-部分正解

$\texttt{T1}$

直接设 $dp[n][k]$ 为把 $n$ 个相同的弹珠分进 $k$ 个相同的盒子里的方案数。

为了保证不重复,令弹珠个数单调不减。

考虑最左边那个放多少弹珠,枚举一个 $i$ 为这里放多少个弹珠,那么后面所有位置最少都要放 $i$。但我们的 $\texttt{dp}$ 不好处理放 $0$ 个的情况,因此我们可以先在最左边放 $i$ 个,后面每个位置放 $i-1$ 个,然后去掉最左边那个继续 $dp$。因此有方程:

$$dp[n][k] = \sum_i dp[n-i-(i-1)\times (n-1)][k-1]$$

发现 $i$ 的枚举是有界限的,类似于调和级数,因此直接记忆化即可。

$\texttt{T2}$

点分治板子,加个 $\texttt{set}$ 判断一下就可以了。

$\texttt{T3}$

这题很有意思,写下题面:

给定 $n$,求有多少正整数对 $(a,b)$ 满足 $a,b\le n$ 且 $\texttt{gcd}(a,b)=a\texttt{ xor }b$。

$n \le 10^7$。

我们发现对于二元组 $(a,b)$,不妨令 $b \le a$,有 $\texttt{gcd}(a,b)\le a-b$,这个直接更相减损。$a \texttt{ xor } b \ge a-b$,也就是最差情况下 $b$ 的所有为 $1$ 的二进制位 $a$ 都为 $1$,此时答案最差,为 $a-b$。因此如果他们相等,那么这个值一定要等于 $a-b$。

考虑枚举 $c=\texttt{gcd}(a,b)$, $a$ 显然是其倍数。暴力枚举其倍数,然后考虑到 $gcd(a,a-c)=c$,因此 $b=a-c$。然后又 $a\texttt{ xor }b=c$,所以只需要判断 $a\texttt{ xor }c$ 是否等于 $a-c$ 即可。

复杂度 $O(n\log n)$。


2020.09.12

$\texttt{Location:NOIP2020}$

得分:$\texttt{250/300,Rank2}$。

[09.12]-错误

$\texttt{T1}$ 没有 $\texttt{\#define int long long}$,然后少开了几个地方的 $\texttt{long long}$,成功 $\texttt{100 -> 60}$。

$\texttt{T2}$ 提答的部分分复制错了一个数字,然后就挂了一个点。

[09.12]-部分正解

这场三道题的名字分别是 $\texttt{tsm,ihp,qmras}$。

惊奇地发现翻转一下变成 $\texttt{mst,phi,sarmq}$。于是就是正解了......

$\texttt{T1}$

发现就是一个最小生成树的板子再套一个 $\texttt{nim}$ 的板子,只是需要支持加边。$n \le 5000$,加边 $\le 1000$,因此可以每次对 $\texttt{mst}$ 中的 $n-1$ 条边和新加的 $1$ 条边做一次 $\texttt{Kruskal}$,然后暴力重构最小生成树。

或者直接 $\texttt{LCT}$。

$\texttt{T2}$

显然的是:

$$\sum_{d|i} \varphi(d)=i$$

也就是:

$$1 * \varphi=\text{Id}$$

这是 $\texttt{Phi}$ 的性质。所以这个 $f$ 就是 $\varphi$,直接线性筛一下即可。

对于后面两个提答的部分分,直接单点求 $\texttt{Phi}$ 。

$\texttt{T3}$

建出 $\texttt{SA}$,然后求出 $\texttt{Height}$。显然的是,在 $sa$ 数组中排名 $i,j(i\le j)$ 的两个后缀之间的 $\texttt{lcp}$ 是:

$$\min_{i\le p\le j} \texttt{Height}[p]$$

如果定义以上为 $(i,j)$ 的权值的话,我们需要的就是所有权值 $\le k$ 的二元组的权值之和。

考虑设置 $dp[i]$ 为二元组第二个是 $i$ 的权值和。每个位置 $i$ 向前找,找第一个 $\texttt{Height}[p] < \texttt{Height}[i]$ 的位置 $p$,那么 $p$ 及往前的所有 $\min$ 都与 $\texttt{Height}[i]$ 无关。然后 $[p+1,i]$ 的话,每一个点的 $\texttt{Height}$ 都 $\ge \texttt{Height}[i]$。因此他们对答案的贡献都是 $\min(\texttt{Height}[i],k)$。

找 $p$ 的话,直接 $\texttt{st}$ 表二分即可。


2020.09.13

$\texttt{Location:NOIP2020}$

得分:$\texttt{240/300,Rank1}$。

[09.13]-错误

$\texttt{T1}$ 做法锅掉了,暴力也出现了同样的问题,因此没拍出来。所以不是拍了很多组就万事大吉了。

$\texttt{T3}$ 差点又少开 $\texttt{long long}$ 了......

$\texttt{T3}$ 神仙 $\texttt{rhdeng}$ 数组开大了,因此以后要手算内存!!!

[09.13]-部分正解

$\texttt{T1}$

首先可以发现,子弹个数不会增加,实际上,打到 $\texttt{bonus}$ 的砖块最后相当于花费 $0$ 的代价拿到他的贡献。

但是打这样的砖块,至少需要有一颗子弹!!! 我就这么错的

不难发现,只有一列无法在已经打了分配的所有子弹后,无法继续打接下来的 $\texttt{bonus}$ 砖块。因为其他的列都可以从这一列先借一颗子弹,打到所有能打到的 $\texttt{bonus}$。

因此我们可以考虑设 $dp[i][s][0/1]$ 为:考虑前 $i$ 列,一共花费 $s$ 颗子弹,前面是否出现可以借子弹的列的最大贡献。令 $val[i][j]$ 为:第 $i$ 列打 $j$ 个砖块对答案的贡献,$c[i][j]$ 为:第 $i$ 列打 $j$ 个砖块所需要的子弹颗数。

那么有:

对任意列 $i$ 任意一个 $j$ ,都有:

$$dp[i][s][1]=dp[i-1][s-c[i][j]][1]+val[i][j]$$

也就是如果之前已经有可以借子弹的列,那么这一列可以取 $\texttt{bonus}$。

对于任意列,打到一个非 $\texttt{bonus}$ 的砖块的 $j$,有:

$$dp[i][s][1]=dp[i-1][s-c[i][j]][0]+val[i][j]$$

意思是,如果这一列不是 $\texttt{bonus}$ 结尾,那么别的列就可以从他来借子弹。

对于任意列,打到一个 $\texttt{bonus}$ 的砖块的 $j$,有:

$$dp[i][s][0]=dp[i-1][s-c[i][j]][0]+val[i][j]$$

意思是,这一列打到一个 $\texttt{bonus}$ 结尾,且前面所有的列都没有可以借子弹的,因此借子弹的列一定出现在后面。

最后的答案就是:

$$\max_{i=0}^k dp[m][i][1]$$

也就是一定要出现一个可以借子弹的列。当然第一维可以滚掉。

还有个想法,可以枚举哪一列作为借子弹的列,然后从左往右、从右往左各维护一个 $\texttt{dp}$ 数组表示可以借子弹时候的情况,然后把两个 $\texttt{dp}$ 数组再做一遍背包。没打 不过应该没问题?

$\texttt{T2}$

首先有以下等式:

$$(a+b+c)^2=a^2+b^2+c^2+2ab+2ac+2bc$$

那么有:

$$ab+ac+bc=\dfrac{(a+b+c)^2-(a^2+b^2+c^2)}{2}$$

同时有类似的柿子:

$$(a+b+c)^3=a^3+b^3+c^3+3a^2b+3ab^2+3a^2c+3ac^2+3b^2c+3bc^2+6abc$$

可以得到:

$$abc=\dfrac{a^3+b^3+c^3+3(a+b+c)(ab+ac+bc)-(a+b+c)^3}{3}$$

现在考虑对于一个幂 $p(p\ge 4)$,假设我们已经知道 $\le p$ 的所有次幂的答案,那么:

$(a^p+b^p+c^p)(a+b+c)$
$=a^{p+1}+b^{p+1}+c^{p+1}+ab^p+ac^p+a^pb+bc^p+a^pc+b^pc $
$=a^{p+1}+b^{p+1}+c^{p+1}+a^{p-1}(ab+ac)+b^{p-1}(ab+bc)+c^{p-1}(ac+bc)$
$=a^{p+1}+b^{p+1}+c^{p+1}+(a^{p-1}+b^{p-1}+c^{p-1})(ab+ac+bc)-(a^{p-2}+b^{p-2}+c^{p-2}) \times abc$

因此如果令 $a^i+b^i+c^i=S_i$,那么有:

$$S_{p+1}=S_p\times S_1 - S_{p-1}\times (ab+ac+bc)+S_{p-2}\times abc$$

直接递推即可。由于需要输出分数,因此还需要维护一个分数类。

$\texttt{T3}$

看到异或,就要想 $\texttt{Trie}$ —— 鲁迅

很简单的 $\texttt{01Trie}$。每次考虑一个新数 $a_i$,之前所有数字自低位向高位加入 $\texttt{01Trie}$。

每次考虑数字 $a_i$ 某一位与字典树中数字对答案的贡献,显然对于自低向高的第 $p$ 位,其贡献为 $2^{p-1}\times s$,其中 $s$ 是满足前 $p-1$ 位与 $a_i$ 相同,这一位与 $a_i$ 不同的数字个数。这个在字典树上表现为:从根向下查询,如果现在要向 $\texttt{v}$ 儿子 $\texttt{v=0/1}$ 走,那么与 $a_i$ 在这一位构成 $\texttt{lowbit}$ 的数字个数即为:$siz[ch[x][!v]]$,应该很显然。

时间复杂度 $O(n\log\texttt{值域})$。


2020.09.19

$\texttt{Location:NOIP2020}$

得分:$\texttt{170/300,Rank2}$。

[09.19]-错误

$\texttt{T1}$ 写 $\texttt{LIS}$ 写挂了,常数太大。

$\texttt{T2}$ 正解,但是常数太大被卡了 $\texttt{30pts}$。

$\texttt{T3}$ 简单题,但是花费的时间太多了。

[09.19]-部分正解

$\texttt{T1}$

考虑使用哈希或者 $\texttt{map}$ 的方式把字符串映射成数字,然后跑 $\texttt{LCS}$。但是正常的 $\texttt{LCS}$ 复杂度下线貌似是 $O(n\times m)$,无法通过。

发现有一个序列没有相同的元素,称其为 $\texttt{S}$,另一个为 $\texttt{T}$,可以把 $\texttt{T}$ 中,每一个值表示为 该值在 $\texttt{S}$ 中的出现位置,跳过那些没出现过的值,因为他们显然不在 $\texttt{LCS}$ 中。然后对新的序列跑 $O(n\log n)$ 的 $\texttt{LIS}$。

$\texttt{T2}$

莫队板子。

直接套一个线段树维护最长的连续值域长度即可,每次单点 $\texttt{+1 -1}$,很好写。

注意常数!!!

可以考虑开个桶,每次记录每一个点上被加多少次,只有在 $\texttt{0->1}$ 或者 $\texttt{1->0}$ 的时候才更新线段树。

还有可以根据离散化之后的 $\texttt{vector}$ 的 $\texttt{size}$ 来分块,貌似快一些。

$\texttt{T3}$

首先注意:所有的物品都只能买一个!!

首先将所有物品从大到小排序,然后可以发现:如果钱无法购买物品 $i$ 了,那么 $i$ 以前不论是已经买过或是没买,都买不了了。所以考虑枚举最小的,不买的物品,那么比他更小的物品都要买,即一个后缀和的形式,前面的就是一个背包了。

还需注意一点,以上枚举的所有情况都是至少有一个不买的情况,但是如果所有的物品都能买下,那么答案 $\texttt{+1}$


2020.09.20

$\texttt{Location:NOIP2020}$

得分:$\texttt{230/300,Rank3}$。

又$\texttt{AK}$失败了西八

[09.20]-错误

$\texttt{T1}$ 的结论没有及时推出,数学方面还是菜......

$\texttt{T3}$ 满分想法只有 $\texttt{30pts}$,实现貌似有问题。

[09.20]-部分正解

$\texttt{T1}$

设现在的概率是 $P$,选的人概率分别是 $p_1,p_2...p_k$。

考虑新加入一个点 $p_x$,他会让答案变成:

$$P\times (1-p_x)+p_x\times \prod_{i=1}^{k}(1-p_i)$$

变一下成为:

$$P+p_x\times (\prod_{i=1}^{k}(1-p_i)-P)$$

由于 $P$ 和之前选的 $p_1,p_2...p_k$ 都固定,所以这个柿子在 $p_x$ 越大时就越大。

把 $p_x$ 从大到小排序,依次判断是否加入即可。

感性理解

$\texttt{T2}$

直接树形背包即可,设 $dp[0/1][x][i]$ 为从 $x$ 出发,向下走 $i$ 步,最后回到/不回到原点,能获得的最大价值。

注意一下树形背包其实是 $O(n^2)$ 的。

$\texttt{T3}$

考虑将所有边按照其权值下界排序,枚举下界。

每次枚举一个下界,把所有下界 $\le$ 他的全部加入,然后看上界最大可以是多少时,$1$ 和 $n$ 仍然联通。

这个东西可以跑最大生成树,同样可以并查集。

如果追求更优秀的复杂度,可以直接上 $\texttt{LCT}$。


2020.09.26

$\texttt{Location:NOIP2020}$

得分:$\texttt{300/300,Rank1}$。

其实格式错误了一题kk

[09.26]-错误

$\texttt{T1}$ 的换行写成了空格......眼瞎......

[09.26]-部分正解

$\texttt{T1}$

$\texttt{sbt}$,第一问数叶子,第二问直接模拟。

$\texttt{T2}$

考虑使用 $\texttt{ExKMP}$,或者叫 $\texttt{Z Algorithm}$。

这个东西可以在 $\mathcal{O}(n)$ 求一个字符串 $S$ 和另一个字符串 $T$ 的每一个后缀的 $\texttt{lcp}$,当然 $T$ 可以等于 $S$,称其为 $\texttt{Z}$ 函数。

$z[i]$ 表示以第 $i$ 个字符开始的后缀与整个串的最长公共前缀长度。首先显然可以暴力跳,但是为了充分利用之前的 $z$,做出以下的优化:

令 $l,r$ 为当前已经得到的匹配中,右端点最大的区间为 $[l,r]$,如果现在的 $i \le r$,那么可以令 $z[i] = \min(z[i-l+1],r-i+1)$,可以这样理解:首先 $[l,r]$ 与 $[1,r-l+1]$ 相同,所以从 $i$ 开始的后缀 和 从 $i-l+1$ 开始的后缀有相同的前缀,但在 $r-i+1$ 之后的部分超出限制,不能确定,因此取 $\min$。然后直接暴力匹配,同时更新 $l,r$ 即可。尤其注意特判 $z[1]=n$,因为不特判就没法保证 $\mathcal{O}(n)$ 的复杂度了。

那么现在考虑用每个后缀与自己的 $\texttt{lcp}$ 来记录答案。发现对于一个 $z[i]$ ,其对答案的贡献是 $\lfloor \dfrac{z[i]}{2} \rfloor$ ,意思是这个后缀和原串的最长公共前缀为 $z[i]$,偶数长度的就是 $\lfloor \dfrac{z[i]}{2} \rfloor$。

$\texttt{T3}$

分层图 $\texttt{Dijkstra}$ 。注意 $k$ 条边不一定用得完,在总边数 $m < k$ 的时候根本用不到 $k$ 条边,特殊判断即可。


2020.09.28

$\texttt{Location:NOIP2020}$

得分:$\texttt{300/300,Rank N/A}$。

请假了

[09.28]-错误

保龄选手......

[09.28]-部分正解

$\texttt{T1}$

柿子里的绝对值不太爽快,排序之后删掉:

$$x_i-x_j \ge w_i + w_j$$

换一下位置变成:

$$x_i-w_i \ge x_j+w_j$$

这可以看作两个区间:中心为 $x$,半径为 $w$,也就是 $[x-w,x+w]$。然后这两个区间代表的点之间有边也就是这两个区间不相交(可以在端点重合)。$\mathcal{O}(n\log n)$ 随便搞。

$\texttt{T2}$

对于任意 $a \le x$ ,有 $x \mod a \le \dfrac{x}{2}$,所以一个数字 $x$ 能被模 $\mathcal{O}(\log x)$ 次变成 $0$。线段树记录区间 $\max$ 和区间和,如果区间 $\max$ 大于等于模的数就暴力进去改。

时间复杂度待补

$\texttt{T3}$

定义 $f(n,k)$ 为 $[n+1,2n]$ 中,二进制下恰好有 $k$ 个 $1$ 的数字个数。

考虑 $f(n,k)$ 到 $f(n + 1,k)$,发现区间从 $[n+1,2n]$ 到了 $[n+2,2n+2]$,少了一个 $n+1$,多了 $2n+1,2n+2$,注意到 $2n+2=(n+1)\times 2$,那么 $2n+2$ 只不过是在 $n+1$ 后面加个 $0$,不改变 $1$ 的个数。因此 $f(n,k)$ 到 $f(n+1,k)$ 单调不减。

然后就可以二分了。

现在考虑 $f(n,k)$ 怎么求。

考虑直接求 $1-n$ 的满足条件数字个数,然后减一下。每次考虑从每一个 $1$ 断开,然后就可以组合数了,例如 $101001$ 可以分成:

$$[0,100000),[100000,101000),[101000,101001),\{101001\}$$

然后用类似数位 $\texttt{dp}$ 的方式组合数即可。答案可能很大,注意调整二分上界。

添加新评论