- 2024-08-18虚树总结
之前学了一些算法,没有写算法总结,未来会陆续补一些。前置知识:树形\(dp\),\(lca\),\(dfs\)序。我们考虑\([HEOI2014]\)大工程这道题。显而易见,假如这道题只有一次询问,我们可以直接树形\(dp\),快速求出答案,时间复杂度\(O(n)\)。但是,梦想是梦想,现实是现实,这题多组询问,假如一
- 2024-08-15CodeForces 1575F Finding Expected Value
洛谷传送门CF传送门考虑单个序列如何求答案。考虑鞅与停时定理。定义一个局面的势能为\(\sum\limits_{i=0}^{K-1}f(b_i)\),其中\(f(x)\)是一个关于\(x\)的函数,\(b_i\)为\(i\)的出现次数。那么我们要构造\(f(x)\),使得每次操作,局面势能期望减少\(1\),那么期望步数
- 2024-08-15GPHP Vol.1 Math
GPHPVol.1MathIntroduction:本计划将记录杂题,采用循序渐进的方法,先给出Hint,然后给出Solution,力求还原思维过程。记录什么题随缘。这是GPHP第一期。每期计划4-5个题目。TableofContent<luogu>P3312[SDOI2014]数表P3312[SDOI2014]数表P3312[SDOI2014]数
- 2024-08-14Stolz 定理
第一公式数列若\(\{a_n\}\uparrow\)且\(\lim\limits_{n\to\infty}{a_n}=+\infty\),又数列\(\{b_n\}\)满足\[\lim\limits_{n\to\infty}\dfrac{b_{n+1}-b_{n}}{a_{n+1}-a_{n}}=l\]其中\(l\)有限或为正负无穷(无穷不可),则有\[\lim\limits_{n\to\infty}\dfr
- 2024-08-142024.8.14 鲜花
OnlyMyRailgun放て!心に刻んだ梦を未来さえ置き去りにして限界など知らない意味无い!この能力(チカラ)が光散らすその先に遥かな想いを歩いてきたこの道を振り返ることしか出来ないなら…今ここで全てを壊せる暗闇に堕ちる街并み人はどこまで立ち向かえるの?加
- 2024-08-14MX Weekly 赛时/VP 记录
感觉题目质量比较高,所以挖了个坑((。X2前三题简单不写洛谷-P10855傻逼赛时想出两种正确思路都他妈的没仔细想,真糖丸了不妨将题目中要求的式子化简。\[\begin{equation}\begin{split}\sum\limits_{i=1}^n\sum\limits_{j=1}^i\gcd(j,i\oplusj)^k&=\sum\limits_{j=1}^n\su
- 2024-08-13Atcoder nomura2020F Sorting Game
首先考虑如果固定了\(a\),如何判定这个\(a\)是否能被排序。如果存在\(a_i>a_j(i<j)\),那么\(a_i\)肯定要交换到\(a_j\)后面,那么就肯定会交换\(a_i,a_j\)。于是合法条件就是如果存在\(a_i>a_j(i<j)\),那么\(a_i,a_j\)只相差一个二进制位。那就还能知道此时一
- 2024-08-13生活在hzoi上 题解
生活在hzoi上题解考虑有两棵树怎么做,显然是\(y^{n-k}=y^{n-\left\vertE_1\capE_2\right\vert}\)其中\(E_1\)和\(E_2\)是两棵树的边集发现上边那个\(k\)是两棵树边集交构成的图的连通块个数\(\left\vertE_1\capE_2\right\vert\)就是两棵树交的连通块数量
- 2024-08-12ABC366D 题解
Solution题意简述给你一个正整数\(N\)和\(N^3\)个非负整数,表示为\(A_{x,y,z}\)其中\(1\leqx,y,z\leqN\)。您将得到以下格式的\(Q\)个查询,必须按顺序处理。对于第\(i\)次查询\((1\leqi\leqQ)\),您将得到一个整数元组\((Lx_i,Rx_i,Ly_i,Ry_i,Lz_i,
- 2024-08-12ABC366E 题解
Solution题意简述二维平面上有\(N\)个点\((x_1,y_1),\dots,(x_N,y_N)\)和一个非负整数\(D\)。求有多少对点对\((x,y)\)满足\(\sum\limits_{i=1}^N(|x-x_i|+|y-y_i|)\leD\)。思路发现\(x_i\)与\(y_i\)的捆绑关系不强(其实是几乎没有关联),所以我们分开考虑,也就是先
- 2024-08-11高等数学学习笔记(一)
高等数学学习笔记最近入门了高等数学,特此记录一下学习到的重点。Chapter1实数与实数集这部分内容高中已经接触过很多了,仅补充一些未曾了解过的。1.完备性实数集不仅对加减乘除开方运算封闭,并且对于极限运算也封闭,这个性质被称为“完备性”。实数中的集合通常称为数集。2.
- 2024-08-10ABC201E Xor Distances 题解
ABC201EXorDistances题解题目大意给定一个带权树,求树上每两点的简单路径上的边权的异或和的和。形式化的,定义\(dis(i,j)\)为\(i\)到\(j\)的简单路径上的边权的异或和,求\(\large\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\text{dis}(i,j)\)。Solve令\(\largef(u)=
- 2024-08-10CF908D New Year and Arbitrary Arrangement 题解
Description给定\(k,pa,pb\),有一初始为空的序列。每次有\(\dfrac{pa}{pa+pb}\)的概率往序列后面加一个a。每次有\(\dfrac{pb}{pa+pb}\)的概率往序列后面加一个b。当出现大于等于\(k\)个形如ab的子序列(a和b不一定相邻)时停止。求序列最终的ab子序列期望数。So
- 2024-08-07min-max 容斥
前置知识请牢记二项式定理:\((a+b)^n=\sum\limits_{i=0}^{n}{\dbinom{n}{i}a^{n-i}b^i}\)或另外一种形式:\((a+1)^n=\sum\limits_{i=0}^{n}{\dbinom{n}{i}a^{n-i}}\)min-max容斥min-max容斥的主要思想是给每个子集分配一个系数(然后每个属于子集的\(a_i\)的系数加上该
- 2024-08-06Contest5385 - FFT
ContestA签到题BFFT/NTT快速傅立叶P3803【模板】多项式乘法(FFT)&P1919【模板】高精度乘法|A*BProblem升级版参考资料:炫酷反演魔术-博客-vfleaking的博客题解P3803【【模板】多项式乘法(FFT)】-洛谷专栏FFT总体思路FFT处理循环卷积问题,而卷积问题通用的
- 2024-08-062024暑假集训测试18
前言比赛链接。这次有大量外校人员参加,\(90\)来个人,T1胡了个结论上去结果大小样例都过了,造hack还没hack了,索性交了,但是有捆绑感觉会爆零,没想到结论是对的,直接A了;打完T1就罚坐了,三个小时就弄出来\(5\)分,当时都绝望了,想到了很多东西。因为感觉T1A不了,后面状态不
- 2024-08-06T240806【2-(一)-1】
[T240806]设连续函数\(C:~z=z(t),~t\in[\alpha,\beta]\),有\(z'(t_0)\neq0~~(t_0\in[\alpha,\beta])\),试证明曲线\(C\)在点\(z(t_0)\)处有切线.证:先证明曲线\(C\)存在无重点的\(z(t_0)\)邻域.由题设知\(\exists\delta>0\),对\(\forallt_1\inU_{\delta}^
- 2024-08-03Noip 真题笔记
Noip2023A事实上只需要比较最大一个和最小一个就可以了。注意排序后的字符串是递增或递减的,是用递增字符串与其他的递减字符串比较。B考场不会。综述:对DFS的详细描述:Noip2022悲惨的一年,对这一年真题有问题别问学长。A签到。当时我写了个三方还艹过去了。对于三
- 2024-08-02二项式定理+二项式反演
序(感谢9G对本博客证明的大力支持)前置知识1:排列组合2:多步容斥\[\dbinom{n}{m}=\binom{n}{n-m}=\mathrm{C}_n^m=\mathrm{C}_n^{n-m}\]\[\dbinom{n}{m}*\binom{m}{s}=\dbinom{n}{s}*\binom{n-s}{n-m}\]\[\dbinom{n}{x-1}+\binom{n}{x}=\dbinom{n+1}{x}\]证明:\(\dbinom{n}{x
- 2024-08-02[USACO20OPEN] Exercise P
有意思的计数题。题目链接题意求所有长度为\(n\)的排列的所有环长的\(\text{lcm}\)的乘积。\(n\leq7500\)解法先min-max容斥把\(\text{lcm}\)换成\(\gcd\)。求\(\prod\limits_{\sigma}\prod\limits_{T\neq\emptyset}\gcd(T)^{(-1)^{|T|}}\),其中\(T\)表
- 2024-08-02ACM notes
动态规划(DP)树形DP数学位运算异或异或前缀和\(s(n)为1到n的数的异或和\)\(s(n)=\begin{cases}1,~~~n\%4==1\\0,~~~n\%4==3\\n,~~~n\%4==0\\n+1,~~~n\%4==2\\\end{cases}\)代码实现如下:autoxorprefix=[&](ll
- 2024-08-01P9308 「DTOI-5」#1f1e33 题解
声明:截止\(2024.8.1\),拿下洛谷最优解最短解,代码长度不到1k。复杂度\(O(n\log\logn)\)。先骂:官方题解菜!这种纯洁的数论题居然敢引入NTT作为标算,说明出题人不会推式子。还有题解区一车\(\log\)的题解凭啥顶那么上面,推的一坨狗屎推出来的复杂度还不优秀。说明:下面除法默
- 2024-08-01奇怪数学题 (更新至 20240801)
1\[\color{#40865d}(2)\]\(f(x)=x^{2}-a(x+a\lnx)(a\neq0)\),若\(f(1)+f'(1)=0\)且\(a\gt0\),问可以得到什么最值相关的不等式结论\[\texttt{Sol.}\]\[f(x)=x^{2}-ax-a^{2}\lnx\]\[f'(x)=2x-a-\frac{a^{2}}{x}\]\[2-a-a^{2}+1-a=0\]解得\(a_{1}=1,
- 2024-08-01SP3912 MTREECOL - Color a tree
前言NOIP模拟考到了这题,整场比赛死磕这题,最后悲痛拿下\(\text{0+30+0+0=30pts}\)的高分。Solution题意很清楚。每一次染色操作当且仅当父亲节点染过色。每一个节点贡献的价值是点权乘上时间。求贡献和最小。设当前权值最大的节点为\(x\),那么如果\(x\)之前的节点
- 2024-08-01组合数学学习笔记(二)(2024.7.4)
一、鸽巢原理1.鸽巢原理将\((\sum\limits_{i=1}^n{p_i})-n+1\)放入\(n\)个盒子,一定存在一个盒子\(i\),使得第\(i\)个盒子至少装了\(p_i\)个物品。练习一有十个数\(a_1,a_2\dotsa_{10}\)满足\(\forall_{1\leqi\leq10}{1\leqa_i\leq60}\),证明能够从\(a_i\)中挑