Warning: session_start(): open(/tmp/sess_3d66253dde449235bd6a92b03004e41b, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7 [CVBB ACM Team]

用户工具

站点工具


2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7

到此差别页面的链接

两侧同时换到之前的修订记录 前一修订版
后一修订版
前一修订版
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7 [2020/08/07 01:45]
qxforever
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-7 [2020/08/20 17:36] (当前版本)
nikkukun add CGIJ
行 140: 行 140:
  
 </​code></​hidden>​ </​code></​hidden>​
 +
 +\\
 +
  
  
行 154: 行 157:
  
 将 $n,m$ 进行类似辗转相除的过程即可保证组数最小。 将 $n,m$ 进行类似辗转相除的过程即可保证组数最小。
 +
 +
 +
 +
 +
 +
 +===== C - A National Pandemic =====
 +
 +Upsolved by nikkukun.
 +
 +==== 题目描述 ====
 +
 +给一棵 $n$ 个结点的树,初始所有节点权值都为 $0$,接着有 $q$ 次操作:
 +
 +  - 给定 $u$ 和 $w$,将树中所有节点 $v$ 的权值加上 $w - \mathrm{dis}(u,​ v)$;
 +  - 给定 $u$,将 $u$ 的权值与 $0$ 取最小值;
 +  - 给定 $u$,询问 $u$ 的权值。
 +
 +==== 解题思路 ====
 +
 +操作 2 实际就是一个单点加减,查询后记录一个变化量就行。
 +
 +对于操作 1,$w - \mathrm{dis}(u,​ v) = w - \mathrm{dep}(u) - \mathrm{dep}(v) + 2 \cdot \mathrm{dep}(\mathrm{lca}(u,​ v))$,其中前三项都可以通过全局记录一个变化量维护,关键在后者。这里考虑一个很 tricky 的技巧,每次将 $u$ 到根的路径全部加 $2$,那么查询 $v$ 到根的路径和时,获得的就是 $2 \cdot \mathrm{dep}(\mathrm{lca}(u,​ v))$,树剖做一下即可。
 +
 +树上两点路径相关的东西,可以先考虑固定其中一个点到根的路径,然后在走另一个点到根的路径上维护相关信息,它们第一次相遇的位置正是 LCA。例如 [[https://​atcoder.jp/​contests/​agc047/​tasks/​agc047_d|AGC047 D - Twin Binary Trees]] 和本题就是这样的思路。
 +
 +
 +
 +
 +
 +
 +
  
 ===== D - Fake News ===== ===== D - Fake News =====
  
 前缀平方和是完全平方数的正整数只有 $1$ 和 $24$  前缀平方和是完全平方数的正整数只有 $1$ 和 $24$ 
 +
 +
 +
 +
 +
 +
 +
 +===== G - Topo Counting =====
 +
 +Upsolved by nikkukun.
 +
 +==== 题目描述 ====
 +
 +{{.:​drg-example.png}}
 +
 +给一个以参数 $n \leq 5\ 000$ 控制的烤肉架图(如上图),求它的拓扑序个数模一个给定的质数 $P$ 的值。
 +
 +==== 解题思路 ====
 +
 +题解和[[https://​blog.nowcoder.net/​n/​67dd005e3ff4477aab7b75b2bc028883|这篇博客]]讲得非常清楚了,实际就是根据不同状态下烤肉架由哪些位置的点控制得到转移关系,进而计算即可。
 +
 +
 +
 +
  
 ===== H - Dividing ===== ===== H - Dividing =====
行 167: 行 226:
 定义 Legeng Tuple 如下, 定义 Legeng Tuple 如下,
  
-  - (1, k) 是 +  - $(1, k)是 
-  - 如果 (n, k) 是,那么 (n + k, k) 也是 +  - 如果 ​$(n, k)是,那么 ​$(n + k, k)也是 
-  - 如果 (n, k) 是,那么 (n * k, k) 也是+  - 如果 ​$(n, k)是,那么 ​$(nk, k)也是
  
 给定 $N,K$ ,问对任意 $1\le n\le N,1\le k \le K$ 一共有多少 Legeng Tuple。 $N,K\le 10^{12}$ 给定 $N,K$ ,问对任意 $1\le n\le N,1\le k \le K$ 一共有多少 Legeng Tuple。 $N,K\le 10^{12}$
行 177: 行 236:
 分两种情况考虑 分两种情况考虑
  
-  - 进行过 ​*k 操作,那么可以表示为 p k  +  - 进行过 ​$\times ​k操作,那么可以表示为 ​$\times ​k 
-  - 没有进行过 ​*k 操作,那么可以表示为 p k + 1 +  - 没有进行过 ​$\times ​k操作,那么可以表示为 ​$\times ​k + 1
  
 答案是 $\sum_{i=1}^{k}(\lfloor\frac{n-1}{i}\rfloor+\lfloor\frac{n}{i}\rfloor +1)$ ,可以平方分块,也可以暴力算到 $\sqrt n$ ,后面就是一些 $0$ 和 $1$ 。 答案是 $\sum_{i=1}^{k}(\lfloor\frac{n-1}{i}\rfloor+\lfloor\frac{n}{i}\rfloor +1)$ ,可以平方分块,也可以暴力算到 $\sqrt n$ ,后面就是一些 $0$ 和 $1$ 。
 +
 +
 +
 +
 +
 +
 +
 +
 +===== I - Valuable Forest =====
 +
 +Upsolved by nikkukun.
 +
 +==== 题目描述 ====
 +
 +给定质数 $P$,接着 $q \leq 5\ 000$ 次询问,每次询问求 $n \leq 5\ 000$ 个点的森林中,每个点度数的平方和模 $P$ 的值。
 +
 +==== 解题思路 ====
 +
 +首先显然所有点地位相同,只要随便算一个点再让结果乘 $n$ 即可。和度数相关的东西可以想到 [[http://​wiki.buaaacm.com/​doku.php?​id=2020-2021:​teams:​i_dont_know_png:​nikkukun:​pruefer-sequences|Prufer 序列]],令 $f(n)$ 表示 $n$ 个点的树中,1 号点对答案的总贡献,则有
 +
 +$$
 +f(n) = \sum_{d=1}^n d^2 \binom {n-2}{d-1} (n-1)^{(n-2) - (d-1)}
 +$$
 +
 +实际就是钦定序列中哪 $d-1$ 个位置是 1 号点,其他点随便放。记 $g(n)$ 为 $n$ 个点的带标号森林个数,枚举 1 号点所在连通块的大小,则总答案为
 +
 +$$
 +\sum _{i=1}^n f(i) \cdot g(n-i)
 +$$
 +
 +现在考虑如何计算 $g(n)$。记 $h(n)$ 为 $n$ 个点的带标号树个数,由 Cayley 定理有 $h(n) = n^{n-2}$,故类似地枚举森林中 1 号点所在连通块的大小,有
 +
 +$$
 +g(n) = \sum _{i=1}^n h(i) \cdot g(n-i)
 +$$
 +
 +综上,总时间复杂度为 $O(\sum n^2)$。
 +
 +
 +
 +
 +
 +===== J - Pointer Analysis =====
 +
 +Upsolved by nikkukun.
 +
 +==== 题目描述 ====
 +
 +很长,摸了,请参考原题。
 +
 +==== 解题思路 ====
 +
 +暴力记录每个指针能指向的变量分别都有啥,每次都用所有赋值关系更新至无法更新即可。
 +
 +赛场上写麻烦了,而且最后只过了 99.04% 的数据也太惨了吧。
 +
 +
  
  
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-7.1596735934.txt.gz · 最后更改: 2020/08/07 01:45 由 qxforever