Panda2134's Blog

Not only coding

高考80天倒计时

高考还有八十天。好好努力吧，毕竟这是我唯一的路了。祝即将省选的各位取得好成绩。各位高考后见。 19.3.26 一点随想。现在是个彻头彻尾的半专业文化课选手了。总是怕想起曾经是OIer的那些事，那些人。总是强迫自己忘掉，可是这很难做到。偶然无意打开hboi其他同学的blog，心里就一阵酸。当初一起走过，最终还是各奔东西。可是再想，那些日子也一去不复返了啊。...

Posted by panda_2134 on March 19, 2019

[SDOI2014]数表

思路考虑没有 $a$ 限制怎么办。 \[\text{Let }n = \max(n, m) \\ \begin{align*} \sum_{i=1}^n \sum_{j=1}^m \sigma(\gcd(i, j)) &= \sum_{g=1}^n \sigma(g)\sum_{g \mid d} \mu(\frac{d}{g}) \left\lfloor\frac{n}{d}...

Posted by panda_2134 on July 14, 2018

NOI知识点总结

NOI 在即，对所有做过的题进行复习，并总结常用算法和数据结构的技巧。参考了这个技能树。原作者不清，但是是在廖哥博客下载的，感谢原作者和廖哥。动态规划数据结构哈夫曼树学会把题目加入的新限制转为数据结构原有的限制！对于 $k$ 叉哈夫曼树，如果 $(n-1)\bmod{k-1} \ne 0$，那么就要补点使得 $(n-1)$ 是 $(k-1)$ 的倍数，这样才能使得深...

Posted by panda_2134 on July 14, 2018

利用多项式算法优化常系数齐次线性递推

才听 @Sparky_14145 说这玩意已经是 NOIP 难度辣！为了避免自己没有 NOIP 水平，特来学习。下面若无说明，均有 $n \le 10^9, k \le 10^5$. 强烈推荐 shadowice1984 的讲解。（老哥稳.jpg） \(\newcommand{bm}{\boldsymbol}\) Caylay-Hamilton 定理矩阵的特征值和特征向量二者以符...

Posted by panda_2134 on July 13, 2018

[NOI2017]泳池

神仙DP题。 ORZRQY! 感谢_rqy的题解。如果以下内容有错误请指教。题意给出一个 $n \times 1001$ 的矩形，每个格子有 $q$ 的概率是安全的，要求选出一个与底边相邻且最大的安全矩形区域。求这个最大矩形区域面积恰好为 $k$ 的概率。思路建立状态转移方程直接做根本做不了，考虑差分-前缀和之思想。类似悬线法，我们把每根悬线加入状态。称下标 $n...

Posted by panda_2134 on July 13, 2018

比赛注意事项

找最大值的时候用 $\ge$ 而非 > ！尤其是要确定最大值的位置的时候！（fst*1）交代码之前一定要检查：文件名部分分对应关系（包括数组！）（因为这个爆掉部分分）内存占用（windows也可以使用MinGW中的size！）（因为这个爆0一次）认真用 5min 读题+划重点，尤其是CodeForce...

Posted by panda_2134 on July 10, 2018

[NOI2014]动物园

一直以为自己是学过 KMP 的，然而却并没有真正理解它的精华。做了这个题，总算是加深了对 KMP 的理解。参考了 @Tony1312 的题解，讲的非常棒。题意对于一个长度为 $n$ 的串的每个前缀，求出它的不重合的相同前后缀个数。$n \le 10^6$. 思路对于此题取 1-indexed 的字符串较为方便。看到 border 显然想到 KMP. 我们不妨设 cnt[i...

Posted by panda_2134 on July 6, 2018

[SDOI2014]重建

题意给出一个无向图，每个边有个存在概率 $p_{<u, v>}$ ，求所有存在边恰好组成生成树的概率。思路第一眼感觉是裸的矩阵树定理，后来发现自己 $\text{Naive}$！滚去膜拜 dkw 聚聚的题解，学会了一种矩阵树定理的化简技巧。我们显然可以知道答案是下式： \[\sum_{T}\left(\prod_{<u, v> \in T} p_...

Posted by panda_2134 on July 6, 2018

[WC2014]紫荆花之恋

动态点分治入门题。人生成就题。题意给出一棵树，点和边都有权值，初始只有一个节点。动态支持以下 2 种操作：在某个点处连接一个新点。查询满足 $\text{dist}_{i, j} \le r_i + r_j$ 的点对数目。 $n \le 10^5$. 思路看到查询点对或者路径，就要想到点分治。这里查询点对，显然地告诉我们第一个 Tag：点分治。考虑...

Posted by panda_2134 on July 6, 2018

基础多项式算法

约定：设 $\deg(A(x))$ 为多项式 $A(x)$ 的次数。 FFT 和 NTT 可以参见 Miskcoo’s Blog 多项式求逆定义：对于 $n$ 次多项式 $A(x)$ ，求出多项式 $B(x)$ ，满足 $A(x) \times B(x) \equiv 1 \pmod{x^p}$. 用数学归纳法的思路。在 $ \text{mod } x $ 的意义下， $A...

Posted by panda_2134 on July 1, 2018