Skip to main content

__debug's Home Keep it simple, stupid

NOIP2016 集训日记

如题.

主要是联赛集训期间每次模拟的总结和一些好题的题解.

<2016-11-04 Fri>

今天的过程非常坎坷…

开考刚 A, 不会做啊怎么办. 打了几个表, 猜了几个结论, 好像转化成一个经典问题了啊.

试着写了写, 好像 \(10^{14}\) 只要 2s 了… 但是卡常硬是卡不过去, 先放一放.

这时时间已经不多了. 赶快搞完 B, 看完 C 发现只会 80 分. 打完以后想了想, 还是回去卡常了.

于是加了一些玄学优化就卡进去了.

结束以后发现 B 有些地方忘记取模了… 竟然还有 80 分. 然后看了 A 的标算之后发现自己是个傻逼.

以后 A 这种题还是别想太复杂了. 如果不是因为 A 坑了我那么久时间, C 也许还是可以刚出来的吧.

A

Description

问有多少组正整数对 \((a, b)\), 满足

  1. \(a + b \leq n\)
  2. \(a + b \mid a b\)

\(n \le 10^{14}\)

Solution #1

令 \(d = \mathrm{gcd}(a, b)\), 不妨设 \(a = a' d, b = b' d\), 则 \(a' + b' \mid d\).

又因为 \((a' + b')d \le n\), 所以 \(a' + b' \le \sqrt{n}\).

不妨枚举 \(t = a' + b'\), 则其对答案的贡献为 \(\lfloor \frac{n}{t^2} \rfloor \varphi(t)\).

Solution #2

通过一系列的打表与猜想, 我们发现要求的实际上就是 $$\sum_{i = 1}^{n} f(i) - 1$$

其中 \(f(i)\) 为 \(i\) 最大的平方因子. (感觉是经典问题啊)

怎么做呢?

注意到 \(f(i)\) 的值是 \(\sqrt{n}\) 级别的, 所以枚举 \(t\), 求出 \(f(i) = t\) 的 \(i\) 的数量即可. $$\sum_{i = 1}^{\sqrt{n}} g\left(\left\lfloor \frac{n}{t^2} \right\rfloor\right) (t - 1)$$

其中 \(g(n)\) 为 \(\le n\) 的正整数中没有平方因子的数, 显然 $$g(n) = n - \sum_{i = 1}^{n} \mu^2(i)$$

根据数学知识 (233333) $$g(n) = \sum_{i = 1}^{\sqrt{n}} \left\lfloor \frac{n}{i^2} \right\rfloor \mu(i)$$

然后就做完啦. 复杂度感觉是 \(O(\sqrt{n} \ln n)\) 的样子, 要卡一下常才过的了.

然而还是不知道这两个解法有什么关系啊 QAQ

C

Description

给你一个深度为 \(N\) 的树, 根是一个白色节点, 每个白色节点都有一个黑色节点儿子, 而每个黑色节点则有一个白色和一个黑色节点儿子. 对于每一个 \(d = 1 \dots 2n\), 求出有多少对白色节点的距离为 \(d\).

\(N \le 5000\)

Solution

\(O(N^3)\) 的 DP 十分明显. \(dp(i, j)\) 表示一个以黑点为根, 深度为 \(i\) 的树中距离为 \(j\) 的白点对数.

时间瓶颈在一个类似卷积的操作上. 考虑优化.

由于树的结构十分特别, 算 \(dp(i, j)\) 的时候可以直接利用上 \(dp(i - 1, j)\) 的值, 这样就只要考虑最底层节点的贡献了. 这样是 \(O(N^2)\) 的.

<2016-11-05 Sat>

是第一天跟高一起考, 结果挂成狗了…

不会被认为是傻逼吧.

A 题很显然的贪心, 听说出题人想卡 long long? __int128_t 搞起来.

B 题想了一会儿想出一个同时 TLE 和 MLE 的算法, 但是没有什么别的想法了于是就开始打了.

卡了好久, 空间还是差一点点. 先不管了, 刚 C 题去.

一看 C 题, 这不就是一个 BFS 嘛..

的确就是一个 BFS, 只是比较难打而已…

所以今天三题除了 B 题的 idea 有那么一点意思 (但是由于题目卡内存常数, 沦为垃圾题), 其他的题毫无思考价值.

所以题解也懒得写了, 哎.

不过还是写一下 B 题的 idea 吧: 对 \(10^6\) 个 \(10^7\) 以内的数进行质因数分解.

其实很简单, \(\ln\) 筛或是线性筛均可.

最后, 我是怎么挂的呢? (B 挂成 10 分了 QAQ)

大样例太水了…

以后一定要注意即使有大样例也要打对拍.

<2016-11-06 Sun>

本来以为今天是省选模拟, 结果三道水题砸过来.

啊, 原来是联赛模拟啊.

最近不知道怎么回事, 每次先把三题看完都觉得好难, 实际上几分钟就可以想出来的. 不过也不算是坏事, 前一阵子老是把题想简单, 现在好多了.

A 题 B 题无论是思路还是代码都很简单, C 题不是很好打.

我向来是比较反感代码题的, 不过平时练练代码能力也是挺好的吧.

去年的明天, 就是 NOIP2015 了.

哎, 现在回想起自己斗地主超代码长度限制, 还是挺遗憾的吧.

<2016-11-08 Tue>

今天的题比较好, 可惜自己炸了…

A 题是模拟, 没什么好说的.

到了 B 题就开始智障了. 我先是看错了一次题(子序列 -> 子串), 然后这个被我看错的题要用 01 分数规划. 发现看错题以后我比较慌, 不过发现原问题也可以 01 分数规划, 是 \(O(n \log^2 n)\) 的, 于是就开始码码码, 卡卡卡, 好像卡进去了. 期间有一个变量名打错了, 调了很久, 差点就要崩溃了.

后来只剩 1h 刚 C 题了, 看完题后发现这不就是 HNOI2014 画框吗, 于是也马上开始打, 用的是解析几何的方法… 于是没调出来.

结束之后发现 B 题挂成 80 了. 标算是观察一个性质, 然后就可以很简单 \(O(n \log n)\) 做了. 并且那个性质非常显然.

C 题我后来才意识到用向量方法写要好写得多.

这次最大的失误:

  • B 题看错题, 并且发现看错题之后仍然是想要把之前的做法套上来
  • B 题一个地方变量名写错, 调了很久

B

Description

给你一个 \(n\) 个点, \(m\) 条边的无向图, 每条边有一个复数边权 \(x + yi\).

对于任意两个复数 \(a, b\), 定义 \(a < b\) 当且仅当 \(|a| < |b|\).

求最大生成树.

\(n \le 50, m \le 200\)

Solution #1 - 凸包

对于每种可能的生成树, 将其用一个点 \((\sum x, \sum y)\) 表示, 那么这个生成树的模长就等于这个点到原点的距离.

容易证明最大生成树一定在这些点的凸包的某个顶点上. (证明分两种情况考虑: 在凸包内和在边界上)

并且, 对于随机的点集 \(S\), 其凸包的期望大小为 \(O(\log |S|)\). 在这里也就是期望 \(O(m)\).

然后就可以用 Quickhull 算法 解决此题了.

大体思想是: 先找出两个凸包上的点 \(A, B\), 然后找出在 \(\overrightarrow{AB}\) 左侧且距离最大的点, 那么这个点也一定在凸包上. 分治下去即可.

右边的情况也是一样的. 但是注意可能存在凸包退化为一条直线的情况, 这里要特判一下.

实现上强烈建议使用向量的方法而非解析方法, 比如说, 距离最大用叉积最大实现.

因为一条直线 \(Ax + By + C = 0\) 并没有左右之分, 而向量就非常方便了.

时间复杂度期望 \(O(m^2 \log m)\).

Solution #2 - 向量投影

如果我们已知答案的单位向量为 \((a, b)\), 那么可以将每条边权值设为 \((x, y)\) 在 \((a, b)\) 上的投影, 然后做一边 MST 即可.

但是枚举角度显然不现实. (其实用一些技巧枚举是可以 A 的) 考虑观察一些性质.

观察 Kruskal 算法的过程可以得到一个结论: 最大生成树的形态只与边权的相对大小有关, 而与具体权值无关.

那么我们只需要求出每两条边的大小改变时的角度 \(\theta\) (有两个), 然后做这么多次 MST 即可.

别忘了向量的投影大小就是点积, 所以解个方程就可以了.

<2016-11-09 Wed>

今天的题也很好, 不过被高一小哥踩飞啦…

一看 A 题, 有循环节的最长不降子序列. 感觉很好做啊. 结果发现过不了大样例, 原来是想简单了… 于是认真想了想, 发现也很傻逼, 就拍上了. 这时时间已经不多了. (我在干嘛啊?)

看 B 题, 想了一会儿, 不会啊. 于是打完 30 分暴力, 去刚 C. 一看 C, 发现黑色不会变回白色, 说不定可以用一些比较暴力的方法? 又发现好像可以分治. 但是斟酌了一下, 发现都没时间想了, 更没时间打了. 于是直接暴力 \(\sqrt{N}\) 重构, 发现随机数据 T 飞了. 然后就没有然后了.

后面发现 C 题竟然有 80 分, 原因是树链剖分求 LCA 在一条链的时候快得飞起. 然后由于高一的一位大爷做过 B 题, 再加上自己傻逼, 于是就被踩了.

以后遇到简单的题也要谨慎思考. 也并不是不能猜结论, 但是 猜的时候一定要意识到自己是在猜.

B

Description

有 \(n\) 个物品 \(V_1, V_2, \dots V_n\), 每种物品无限多. 但是所有 \(V_i \ge L\) 的物品一共最多使用 \(C\) 个

现在有 \(m\) 个询问, 每次询问是否存在一种方案恰好凑出 \(W_i\).

\(n \le 50, m \le 10^5, W_i \le 10^{18}, V_i, L \le 2 \times 10^4, C \le 50\)

Solution

之前一直没做过这一类的题, 看来做的题还是太少了.

先不考虑 \(L\) 的限制.

发现一个类似循环的性质: 如果我们可以凑出 \(W\), 那么一定可以凑出 \(W + V_i\). 那么是不是只要随便选一个 \(V_i\), 看 \(\pmod{V_i}\) 意义下些哪些容量可以被凑出来就可以了?

显然不是. 举个例子, 如果能凑出 \(W \bmod 3 = 2\), 但是 \(W\) 至少是 \(11\), 那么虽然 \(8 \bmod 3 = 2\), 但是 \(W = 8\) 时是无解的. 所以现在要求的就是 \(\pmod{V_i}\) 意义下, 凑出每种模意义下的值实际上至少需要容量有多大.

这里最短路就可以了. 为了方便, 先给 \(V\) 从小到大排个序, 在 \(\pmod{V_1}\) 意义下做.

设状态 \(dp(i, j)\) 表示正在考虑第 \(i\) 个物品, 在 \(\pmod{V_1}\) 下凑出 \(j\) 的值, 实际容量最小需要多大. 转移会有环, SPFA 即可. 当然, 经过一些观察, 这里也可以不用 SPFA, 因为每个点的出度, 入度都是 \(1\), 并且整张图都是由一些简单环组成的.

最后, \(L\) 的限制也是很简单的, 因为 \(C\) 非常小, 增加一维状态即可. 时间复杂度 \(O(n V (C + \mathrm{SPFA}(V, 2V)) + m)\).

(其实在 \(V_1 \ge L\) 时还需要特判)

C

Description

给你一个 \(n\) 个点的有根树, 根为 \(1\). 每个点有一个正整数权值 \(W_i\). 每个点可以是黑色或是白色, 一开始全是白色.

两种操作, 共 \(m\) 个:

  1. \(\text{Modify } v\): 将 \(v\) 改为黑色
  2. \(\text{Query } v\): 找到一个权值最大的节点 \(z\), 使得存在一个黑色点 \(u\), \(\mathrm{LCA}(u, v) = z\). 不存在输出 \(-1\).

\(n \le 10^5, m \le 2 \times 10^5\)

Solution

这题我当时是写的暴力重构, 有 80 分, 挂了几个随机的点… 结合一下暴力就 A 了呀.

标算非常简单.

观察到每个点只会由黑色变成白色. 这样每次一个点变成黑色, 我们只需一步步暴力往上爬, 更新当前点的子树 (除了 \(u\) 所在的子树), 然后如果这个点已经被更新过了, 那么退出. 这样做的更新次数是 \(O(n)\) 的.

用线段树维护 DFS 序即可, 区间最多只会被拆成两段.

<2016-11-10 Thu>

好题! (虽然都没做出来)

花了一大半的时间在 A 题卡常上, 后来才发现我的复杂度比标算多了个 \(\log\)… 最后大概只剩 1h 了, 看完 B, C 就开始打暴力. (我 B 题其实还有些想法的, 可惜了)

然后最后成绩出来后, 发现 A, C 都挂了几分:

  • A 一个特判没用 __builtin_popcountll 而直接用了 __builtin_popcount
  • C 题无解特判打错

(以后再来补 B, C 题的题解)

B

Description

给你两个 \(1 \dots n\) 的排列 \(A, B\), 每次等概率随机选择一个三元组 \((a, b, c) (a \ne b \ne c)\), 然后将 \(A\) 中 \(a, b, c\) 三个位置上的数按顺序交换一下位置. (即, \(A \to B, B \to C, C \to A\)).

问你在 \(m\) 步之内将 \(A\) 变为 \(B\) 概率有多大.

\(n \le 14, m \le 10^9\)

Solution

\(m\) 这么大, 估计是矩阵乘法优化 DP. 然而 \(n!\) 实在是太大了, 考虑压缩状态.

不妨先把 \(B\) 变为 \(1, 2, \dots, n\) 的形式, 当然 \(A\) 同时也要相应的变化. 然后我们需要想出一种排列的表示方式, 满足

  1. 若两个排列在这个表示方式下相同, 则对于每个 \((a, b, c)\), 它们变出来的排列在这个表示方式下仍然相同.
  2. 没有其他排列与 \(1, 2, ..., n\) 在这个表示方式下相同

如果我们把这个排列视作一个置换, \((a, b, c)\) 看作一个轮换, 实际上相当于把它们乘起来. 想到置换的轮换分解.

比如说, 置换 \(\begin{pmatrix}1 & 2 & 3 & 4 \\ 2 & 3 & 1 & 4 \end{pmatrix}\) 分解为 \((1 \; 2 \; 3) (4)\). 进一步, 我们可以将其表示为 \(<1, 3>\) 表示有两个个大小分别为 \(1, 3\) 的轮换.

我们发现这样的表示方法是满足之前讲的两个条件的. 而这种表示的数量就是拆分数, 在 \(n = 14\) 时只有 \(150\) 左右.

然后矩阵快速幂就好了. 时间复杂度 \(O(D_n n^3 + D_n^3 \log m)\). 其中 \(D_n\) 为 \(n\) 的拆分数个数.

C

Description

给你一个 \(n\) 个点 \(m\) 条边的有向图, 问单独删去哪些点之后会变成一个 DAG.

\(n \le 5 \times 10^5, m \le 10^6\)

Solution

即求哪些点在图中所有环的交中.

不妨先特判掉无解的情况. 然后可以随便找到一个环, 我们要找的点一定在这个环上.

接下来就比较麻烦了…

不妨把每个点拆成两个点 \(u_1, u_2\), \(u_1\) 只连进来, \(u_2\) 只连出去, 然后 \(u_1 \to u_2\). 显然删去一个环上的边后图一定变为一个 DAG.

首先从某个点开始, 对环上的点编一个号, 使得 \(\mathrm{id}(1) \to \mathrm{id}(2) \to \cdots \to \mathrm{id}(p) \to \mathrm{id}(1)\). (断环为链) 然后讨论两种路径:

  1. 从 \(\mathrm{id}\) 小的点连向 \(\mathrm{id}\) 大的点的路径
  2. 从 \(\mathrm{id}\) 大的点连向 \(\mathrm{id}\) 小的点的路径

显然第 1 种路径会导致中间一段的点都不合法, 而第 2 种则会导致除了中间一段的点都不合法.

我们可以在拓扑序上 DP 求出 \(mx(u)\), 表示 \(u\) 点通过一些边能到达的环上 \(\mathrm{id}\) 最大的的点. 然而我们只能利用 \(mx(u)\) 求出第 1 中路径的影响, 而不能求出第 2 种的. 因为对于一个点 \(u\), 我们必须知道在它能到的节点中, \(\mathrm{id}(v)\) 最大且满足 \(\mathrm{id}(v) < \mathrm{id}(u)\) 的 \(v\), 这样才能知道情况 2 的最大的不合法区间. 这样并不好做.

但是, 为什么非要知道情况 2 中以每个环上的点为起点的最大不合法区间呢?

不妨这样考虑: 只要一个环上的点可以走到 \(\mathrm{id}\) 比它小的点, 那么 \(\mathrm{id}\) 比它大的点一定不合法了; 同理, 只要一个环上的点可以被 \(\mathrm{id}\) 比它大的点走到, 那么 \(\mathrm{id}\) 比它小的点一定不合法了.

所以我们只需再求出 \(mn(u)\) 表示 \(u\) 点通过一些边能到达的环上 \(\mathrm{id}\) 最小的的点, \(rmx(u)\) 表示 \(u\) 点 逆着 一些边能到达的环上 \(\mathrm{id}\) 最大的的点, 即可解决情况 2.

最后, 不合法的区间标记怎么打都是可以的. 利用差分实现比较方便.

时间复杂度 \(O(n + m)\).

<2016-11-11 Fri>

今天三道水题, 但是!!!

我又看错题了…

并且, 又是子串看成了子序列…

看题一定要仔细! 并且做完一道题/检查一道题的时候一定要再看一遍题!

<2016-11-12 Sat>

今天拿到题一看, A 题就不会做啊. 结果发现是看错题了…

B 题也是一眼秒, 前两题大概只搞了 1h 左右.

然后就看 C, 发现实质上是要动态维护一个森林, 支持加边, 删边, 查询最长链. 这不就是维护虚边信息的 LCT 吗? (@QTREE4)

发了一会儿呆之后马上开始打, 大概 30min 就打完了, 然后就是痛苦的调试. 大概调了 1.5h 吧, 在最后 20min 调出来了, 原来就是 pushupchkmax 之前忘记清零了…

虚.

就一句话而已, 一个半小时啊… (目前我并不知道 LCT 有什么好的调试方法, 哎)

后来看题解才发现, 这个东西很容易用线段树离线来转化为只有加边和询问, 这样就可以 并查集 + LCA 了. 虽然这个方法的代码量跟 LCT 比并没有什么优越性, 但是!!!

好调啊.

不管怎样, 以后打 LCT 的时候一定要特别小心, 尽量不要依赖调试. 并且打 LCT 之前要思考一下能否通过一些技巧避免删边, 然后用更简单的数据结构如并查集解决.

<2016-11-13 Sun>

这次模拟什么事也没有发生…

A 题水题.

B 题暴搜水过.

C 题目意思没讲清, 于是暴力分都没拿到. 其实还是一道好题.

C

Description

一个 \(N\) 个点 \(N (N - 1) / 2\) 条有向边的竞赛图 (每对点之间都有连边), 现在随机给每条边定向, 问 \(1\) 号点所在的强连通分量的期望大小. (简化了一下原题, 不过差不多)

\(N \le 3000\)

Solution

考虑竞赛图的一个性质: 对一个竞赛图拓扑排序, 每一层的点一起组成了一个强连通分量.

所以这道题递推枚举的思路: 考虑拓扑排序中最后一层点, 也就是最后一个强连通分量.

由于每个点最后所在强连通分量的期望大小是一样的, 不妨求出每种情况中每个点所在强连通分量大小的和的和, 最后除以点数 \(\times\) 情况数即可.

设 \(g(n)\) 为 \(n\) 个点时, 每种情况中每个点所在强连通分量大小的和的和, 则有 $$g(n) = \sum_{i = 1}^{n} \binom{n}{i} f(i) \left( g(n - i) + 2^{\frac{(n - i) (n - i - 1)}{2}} i^2 \right)$$ (枚举最后一个强连通分量的大小为 \(i\))

其中 \(f(n)\) 为 \(n\) 个点的竞赛图中, 整张图是强连通图的个数. 显然有 $$2^{\frac{n (n - 1)}{2}} = \sum_{i = 1}^{n} 2^{\frac{(n - i) (n - i - 1)}{2}} \binom{n}{i} f(i)$$ (枚举最后一个强连通分量的大小为 \(i\))

然后就有递推式 $$f(n) = 2^{\frac{n (n - 1)}{2}} - \sum_{i = 1}^{n - 1} 2^{\frac{(n - i) (n - i - 1)}{2}} \binom{n}{i} f(i)$$

\(O(N^2)\) 递推解决, 其实可以 NTT.

<2016-11-14 Mon>

h10 的欢乐赛!

今天在虚拟机里试了试 NOI Linux, 结果 A 题明明一个 \(O(n)\) 的算法跑了好几秒… 后来换回来发现只要 0.2s. 吓得我再也不敢在虚拟机里做题了.

然后做 B, 比较简单, 但是我的做法比较傻逼, 并且常数很大.

C 题挺有意思的, 见后面的题解. 于是就愉快地 AK 啦.

C

Description

对于给定的正整数 \(n\), 求有多少个二元组 \((i, j)\) 满足

  1. \(1 \le i < j \le n\)
  2. \(j + i\) 与 \(j - i\) 互质

多组数据, 共 \(T\) 组.

\(n \le 10^7, T \le 10^5\)

Solution

原题是要求 $$\sum_{1 \le i < j \le n} [\mathrm{gcd}(j + i, j - i) = 1]$$

即求 $$\sum_{1 \le i < j \le n} [\mathrm{gcd}(2i, j - i) = 1]$$

如果令 \(t = j - i\), 再枚举一个 \(j\), 则问题转化为有多少对 \((i, t) (1 \le i, t \le j)\), 满足 \(i + t = j\) 且 \(\mathrm{gcd}(i, t) = 1\), 同时 \(t\) 为奇数. 分 \(j (j > 1)\) 的奇偶讨论即可.

  • \(j \bmod 2 = 0\), 此时 \((i, t)\) 的对数为 \(\varphi(j)\)
  • \(j \bmod 2 = 1\), 此时 \((i, t)\) 的对数为 \(\frac{\varphi(j)}{2}\)

然后 \(O(n)\) 预处理出上面这个东西的前缀和, 每次 \(O(1)\) 回答即可.

<2016-11-16 Wed>

这一场最劲的是 C 题, 详见 C 题题解.

其他的没什么好说的.

Comments

Comments powered by Disqus