CF1039DYouAreGivenaTree树形dp+贪心+根号分治题目是一个经典问题，可以用树形dp和贪心解决。设\(f_u\)表示以\(u\)节点为端点能够剩下的最长路径。考虑从叶子节点往上合并贪心，那么如果能够合并出包含\(u\)节点的大于等于\(k\)的路径，那么就合并，\(f_u=0\)；否

根号分治PS：本篇博客题目分析及内容（除代码）均来自于paulzrm根号分治，是暴力美学的集大成体现。与其说是一种算法，我们不如称它为一个常用的trick。首先，我们引入一道入门题目CF1207FRemainderProblem：给你一个长度为$5\times10^5$的序列，初值为$0$，你要完成$q$次操作，操作有如

数据结构专题.CF1192B动态修改边权,查询树直径.方法1:首先考虑常规的树上问题,即树剖一类方法不便于处理和合并直径这一类信息,于是考虑拍成序列做(树莫队就是这种想法).考虑任一条路径是由左右端点和LCA连成,因此考虑可以用于求LCA的欧拉序列,刚好可以用差分法把任意一条路

1. 无理数和有理数的定义      实数可以简单的分为有理数和无理数，有理数都可以采用分数   （其中a和b都是互质的整数）表示；而无理数不可以使用分数表示，并且无理数是无限不循环小数。2. 根号2是无理数的证明过程目前常见的证明是无理数的证明方法是反证法，

2024年5月26日我在银河系·太阳系·地球·亚洲·中国·广东省·广州市·南沙区参加了有史以来第二场CCPC这次是中文题目谢天谢地，不像上次是个蛇皮英文。这次比赛和一个6年级巨学和5年级巨学组队。共同拼搏得到了0分+20多次罚时的好成绩。比赛中签到题想的几个做法都假了(都磕了

797-E题目大意给定一个长为\(n\)序列\(a\)，有\(q\)次询问：给定\(p,k\)，你需要反复执行操作\(p=p+a_p+k\)，直到\(p>n\)为止，问你要执行多少次操作。Solution考虑两种思路：1、暴力回答询问，每次反复模拟操作，直到\(p>n\)为止，时间复杂度\(O(q·\frac{n}{k})\)。2、预处理出

1.方程的解要写x=2023.12.10晚上周测填空题第\(2\)题，方程的解写成了\(7\)而不是\(x=7\)。2.分类讨论选填的最后一题。3.去绝对值看清楚符号（某个）4.列竖式时要补上\(0\)挑战杯初赛要计算\(24\times150\)列竖式时写成了\(24\times15\)原本\(3600\)变\(360\)

题目\(m\)组询问求\(\sum_{l\leqi,j\leqr}[a_i\bmoda_j==0],n,m,a_i\leq5\times10^5\)分析设\(f(l,r,x)\)表示\(i或j\in[1,x],i或j\in[l,r]\)时的答案，\(g_x\)表示\([1,x]\)的答案，根号的做法可以通过三秒由于涉及区间内的求值，需要在莫队的基础上二次离线，那

1、算术基本定理（唯一分解定理）每个正整数都能够唯一的表示成它的质因数的乘积2、n中最多只有一个大于根号n的质因子因为如果有两个以上的话，乘积会大于n。因此只需要从2遍历到根号n即可。#include<iostream>usingnamespacestd;intmain(){ intn; cin>>n; for(int

由数据范围反推算法复杂度以及算法内容一般ACM时间限制是1-2秒这种情况下，c++代码操作次数控制在1e7~1e8下面给出在不同数据范围下，代码时间复杂度和算法如何选择1.n<=30，指数级别，dfs+剪枝，状态压缩dp2.n<=100=>O(n3),floyd,dp,高斯消元3.n<=1000=>O(n2),O(n2logn),dp,二分，朴

本文为本人为应付学校科技节写的屑作。写得比较仓促，可能存在不严谨或错误之处，欢迎批评指正。在本文中若无特殊说明，\(n\)表示元素数量，\(m\)表示询问数量，\(V\)表示值域范围为\([1,V]\)。一、分块分块，即将数据划分为多个块，并在操作时对整个块进行整体处理的思想。分块并非一

CF710DTwoArithmeticProgressions根号分治薄纱数论看日报学习的根号分治：暴力美学——浅谈根号分治-paulzrm的博客。开始想学ODT的映射思想的推广-金珂拉的博客，结果先学了ODT，又学了根号分治，才搞懂前置知识。什么是根号分治根号分治，是暴力美学的集大成体现。与

20240321每日一题题解Problem已知\(f(x,n)=\sqrt{n+\sqrt{(n-1)+\sqrt{(n-2)+\sqrt{...+2+\sqrt{1+x}}}}}\)。计算\(f\)的值。输入\(x\)和\(n\)​。输出这个函数值，并且注意需要保留两位小数。例如，输入4.210，则应该输出3.68Solution递归？循环？说实话这道题是有一定思考

来看一下一般的根号算法的思路过程，见这篇题解重点是这句话所以一般来说，我们先写出最暴力的版本，然后考虑是否可以根号算法优化那为什么我们要设置\(dp\)数组呢？其实这里仍然运用了转换对象法这个思想，因为每次修改的数只有一个，但是模数却有很多个，所以我们可以尝试去统计贡献

调和平均\(\leq\)几何平均\(\leq\)算数平均>\(\leq\)平方平均\(\frac{2}{\frac{1}{a}+\frac{1}{b}}\leq\sqrt{ab}\leq\frac{a+b}{2}\leq\sqrt{\frac{a^2+b^2}{2}}\)\(\sqrt{\frac{ab+\frac{1}{2}(a^2+b^2)}{2}}=\frac{1}{2}\)根式，是数学的基本概

CF1491HSolutionlink考虑分块。按照点的编号分块，维护\(b_i\)表示\(i\)往上跳遇到的第一个与\(i\)异块的点。对于散块修改，直接暴力重构整块的\(b\)。重构方式是，如果\(a_i\)与\(i\)异块，则\(b_i\getsa_i\)；否则\(b_i\getsb_{a_i}\)。对于整块，打标记维护整体减了多

CF1446D2Solutionlink首先，最终答案区间中的众数一定包括整个序列的众数\(K\)。证明：设这个区间中众数出现次数为\(cnt\)。如果上述不成立，由于\(K\)在这个区间中出现次数小于\(cnt\)，我们将区间向两边延申，\(K\)的出现次数应当不断增加直到等于区间的众数出现次数。这样子

注意下文中fail树和trie树的不同。考虑给询问离线，然后差分成\([1,r]-[1,l-1]\)的前缀询问来做。先对于\(s_{1\dotsn}\)建立AC自动机。从左到右扫描询问，当扫描到\(i\)时就对fail树上的子树\(i\)全体\(+1\)，使用树状数组维护即可。答案即为\(s_k\)在trie树

1.根号分治与分块在预处理与询问的复杂度之间寻找平衡的一个算法，通常以根号为分界线。属于智慧的暴力。1.1.根号平衡使用数学不等式对于阈值取一个值，使得复杂度最优。如果有阈值\(B\)，若问题有一部分暴力可以\(O(B)\)解决，另一部分可以\(O(\frac{n}{B})\)解决。那么根据基

许多题如果用\(O(\sqrtp)\)的\(\texttt{BSGS}\)会超时，下面是我见过的若干解决办法。前置知识：原根，离散对数，阶，BSGS。下文设原根为\(g\)，\(\text{ord}_r(a)\)表示\(a\)模\(r\)的阶。科技重新平衡复杂度可以\(O(B+\frac{np}{B})\)求出\(n\)个数的离散对数，只是把原来

P3515[POI2011]LightningConductor此处主要记录不用决策单调性的做法。我们发现根号的取值是\(O(\sqrt{n})\)级别的。于是在每一个位置枚举根号取值然后在对应前后缀中查询\(a_j\)最值，这样算法是\(O(n\sqrt{n})\)的。使用贡献法，对于每一个位置\(i\)考虑对别的位置

题目传送门分析首先把距离变成深度，用dfs序转成区间问题，考虑分块，散块直接改问题是整块，如果模数比较大，可以以深度为第一维下标差分标记，这样查询时就可以前缀和知道答案如果模数比较小，那么给该块打标记，查询时枚举模数即可，然后块长取1000，模数阈值取300，就能尽量减少时间代码#in

模拟赛不知道对于\(d(n)\)很大的数可以做根号质因数分解，直接输完了。中午在外面吃饭，去了一家很有创意和技术的餐馆，西安菜还是有辣的，而且还挺不错。晚上看RMR，A队进了，小蜜蜂能不能进呢，不知道。跳跃DP形式形如高维偏序，于是考虑怎么样来做这个东西。常规做法有点菜，考虑高维

题目传送门分析如果\(x\)比较大那么可以暴力修改，\(x\)比较小的话可以用数组打标记查询的时候对于暴力修改的部分可以分块，暴力修改的同时需要给块打标记如果\(x\)比较小的情况，一段区间相当于是中间很多段周期加上前后缀（当然可以直接区间减但是我被卡常了）我调的块长是160

本文介绍了笔者由一道题的根号做法受到启发，独自摸索出来的一个数据结构。由于笔者能力和精力有限，无法查找已有的资料，如果有哪位巨已经提出来了记得踩我一脚。介绍这个数据结构维护凸包，支持以下操作：\(O(\sqrt{n})\)在线加入/删除任意一条线段\(O(\sqrt{n}\log\sqrt{n})\)在