scmmm's blog

小萌新发现三分还没有复习，实在是太菜了。 很显然的，三分需要满足 f(x)f(x)f(x) 是一个单峰函数

前言 萌新在高中浅浅接触 OI\text{OI}OI ，就听说了换根 dp ，奈何当时太菜了，听不懂，所以只能在大学重新学学了 最基础部分 给定一个 nnn 个点的无根树，问以树上哪个节点为根时，其所有节点的深度和最大？ 深度：节点到根的简单路径上边的数量 这个是最经典的换根dp，而且经典到做了这道题你仅仅能了解什么是换根，其他代码照样写不出来。由于这道题太简单了，不写代码。 换根 dp\text{dp}dp 最广泛的操作就是，两个 dfs\text{dfs}dfs ,第一次统计子树内的，第二次转移子树外的。 例题 洛谷 P3047 [USACO12FEB]Nearby Cows G 给你一颗树，询问每个点周围距离小于等于 kkk 的权值和。 记 fi,jf_{i,j}fi,j​ 表示 iii 点距离为 kkk 的权值，那么第一次有一个从子树转移过来的，第二次统计子树外面的。 等等，有重复？ fi,lf_{i,l}fi,l​ 与 fj,l−1f_{j,l-1}fj,l−1​ 是包含关系，然而 fj,l+1f_{j,l+1}fj,l+1​ 又要从 fi,lf_{i,l}fi,l​ 转移过 ...

十月最后一场训练赛，成功花了两个小时做出来我校去参赛队伍五个小时的罚时。 参赛人数 222 参赛时间 333 小时（其实过了 444 题之后就在摆了），大概参赛的话能混个 Cu ,有希望 Ag 吧  October\text{\color{red} O\color{black}ctober} October 大神狂切题大显神威，scmmm\text{\color{grey}scmmm}scmmm 大菜鸡尽显菜鸡本色。 本菜鸡就做了两道题，神仙怒d：”我有你这个时间可以做两百道题“ E Draw a triangle 上帝视角来看， A 得第四多的题，可以算铜牌题？ 题目是给你三角形得两个点 (a1,b1),(a2,b2)(a_1,b_1),(a_2,b_2)(a1​,b1​),(a2​,b2​)，求你找出来第三个点，使得三角形面积最小，并且这个点一定得是整数点。 我们先考虑平行或者垂直于 xxx 轴的情况，显然这个时候最小面积是当前两点长度乘以二分之一 ，答案点是(a1+1,b1)(a_1+1,b_1)(a1​+1,b1​) 或者 (a1,b1+1)(a_1,b_1+1)(a1​,b ...

前言 这场比赛做的很失败，虽然出题人背了大锅，但是毕竟最后打铁的还是自己，好在自己只是 VP 了失败了快感，并没有真正的霸占学校 CCPC\text{CCPC}CCPC 名额坐牢 I 题目大意，询问长度为 nnn 的全排列 PPP ，有多少满足对于每一个 i∈[1,n]i \in [1,n]i∈[1,n] , PPP 的前 iii 个数前缀和满足 i∣2∗Sni | 2*S_ni∣2∗Sn​ 考场上面打表做的，具体就是发现从 333 开始，方案数都是前面的两倍。 关于证明，我想的是 Sn=n∗(n+1)2S_n=\frac{n*(n+1)}{2}Sn​=2n∗(n+1)​ 我们可以通过把 n+1n+1n+1 换进来，把 111 放在最后，实现前缀和变为 n∗(n+3)2\frac{n*(n+3)}{2}2n∗(n+3)​ 依然可以被 iii 整除 那为什么不能和 3,5,73,5,73,5,7 这些交换呢？此时 SSS 的表达式出现了丑陋的常数，消不掉，但是在 n≤3n\leq3n≤3 时候，常数不重要，因为手推发现能够除 H 坐大牢，三个人调试一摩尔时间，坐大牢。 给你三个数字 a ...

咕咕咕 fft 虚树 splay 计算几何 考古学习 网络瘤 线性基 背包9讲 题目/比赛报告 题目 比赛 CF 372C CF GR 831 gugugu

算法学习 写的题 20221020 沈阳ICPC 2019 L 感觉像铜牌题 完全图中剔除一棵树，询问剩下的图存在多少种边为n的匹配，很容易想到容斥，并且只剔除了一颗树，剩下的一定可以在剩下子图中匹配。 考虑 fi,j,0/1f_{i,j,0/1}fi,j,0/1​ 表示以 iii 为根的子树中包含 kkk 种匹配的方案数，那么显然有一个树形背包的转移方式。 123g[k+l][0]=(g[k+l][0]+1ll*f[x][k][0]*(f[j][l][1]+f[j][l][0]))%modp;g[k+l][1]=(g[k+l][1]+1ll*f[x][k][1]*(f[j][l][1]+f[j][l][0]))%modp;g[k+l+1][1]=(g[k+l+1][1]+1ll*f[x][k][0]*f[j][l][0])%modp; 根据容斥原理，总的方案数即为 ans=∑i=0n(−1)nf1,i,0/1ans=\sum_{i=0}^{n}\limits(-1)^n{f_{1,i,0/1}}ans=i=0∑n​(−1)nf1,i,0/1​ 12345678910111213141 ...

前言 本文只要写一些数论以及它的trick 最基础的部分 唯一分解定理 x=Πpikix=\Pi{p_i^{k_i}}x=Πpiki​​ 公约数 欧几里得求法 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)gcd(a,b)=gcd(b,amodb) 辗转相除法 gcd⁡(a,b)=gcd⁡(a−b,b)\gcd(a,b)=\gcd(a-b,b)gcd(a,b)=gcd(a−b,b) 显然的，小的哪个数应该放在后面，如果小的是 000 ，说明没有余数，最大公约数是 aaa 唯一分解定理 gcd⁡(a,b)=Πpimin⁡(k1i,k2i)\gcd(a,b)=\Pi{p_i^{\min(k1_i,k2_i)}}gcd(a,b)=Πpimin(k1i​,k2i​)​ exgcd 当我们想要ax+by=k∗gcd⁡(a,b),k∈Z,K≠0ax+by=k*\gcd(a,b),k\in Z , K \neq 0ax+by=k∗gcd(a,b),k∈Z,K=0的时候，这个时候就需要拓展欧几里得（至于为啥是这么多,看下面的证明） 假设我们现 ...

博客标准： 与其说是标准，不如是规划： 目前准备接着上一代的基础，规划为以下几个部分 生物学部分 OI(ACM) AI 一些没啥用的基础 算法学习笔记 图形分析 可能有些软件使用方法？ XCPC 游记 NLP 可能有些算法学习？ 日常刷题记 python R语言 应该会有很多重合的，不一定会这么弄，但是这个表格也会更新的。 20221029 草我怎么在考古式学习 20221101 我瑞曲星了，居然才知道 mathjax\text{mathjax}mathjax 换行要爆炸，可能我会考虑改成 katex\text{katex}katex ? 20221107 每周练题都放在训练记里面，里面不弄算法学习，如果自己觉得有很好的 tricks\text{tricks}tricks 就会放在别的博客里。

删去 butterfly 的在页脚标识 这个太丑了，因此删去 找到 "\themes\butterfly\layout\includes\footer.pug" 改成 123456789101112131415161718#footer-wrap if theme.footer.owner.enable - var now = new Date() - var nowYear = now.getFullYear() if theme.footer.owner.since && theme.footer.owner.since != nowYear .copyright!= `©${theme.footer.owner.since} - ${nowYear} By ${config.author}` else .copyright!= `©${nowYear} By ${config ...

经过接近两年的 AFO\text{AFO}AFO 本蒟蒻终于上了威海某个世界一流大学，但是专业并不理想，但并不会放弃 ACM,CTF\text{ACM,CTF}ACM,CTF 等 CS\text{CS}CS 东西，并且准备搞生物信息学 目前会放一些算法学习笔记，并且重置一下初高中写过的东西，也许现在太菜了，并且自己有完美主义（实际上应该是每个人都应该具备的学术严谨），可能会很咕。