wweiyiのblog

今天我重新创建了我的hexo驱动的blog，希望以后这个blog能够时常更新吧

期末复习 易错点 叶子结点以外的结点称为分支结点  时间复杂度  1.4 (1) O(nm)O(nm)O(nm) (2) O(n2)O(n^2)O(n2) (3) O(n2)O(n^2)O(n2) (4) O(log3n)O(log_3n)O(log3​n) 线性表  ![img](file:///D:\qq消息记录\2844938982\nt_q...

雪下得很大，我很喜欢你

【游记】NOIP2021 完全退役记 Day -11 啊，终于期中考试完了，考得也很炸呢~ 二十天没搞竞赛了，不知道还熟不熟 这，大概是最后一次比赛了吧，我还是比较希望我能有作为OIer的最后尊严的，不在这个比赛中爆零 是啊，别人都已经被保送了，我却还在这里苟延残喘，晦气，晦气 打完了之后，就回归文化课了吧 四年OI想说的好多啊 我也就只是在省内，顶多在市内扰起了一点小风小浪吧 Day -1 今天早上从襄阳出发 一早上起来，运气便不是非常好 早上八点钟起床，九点二十的车，然后八点二十打车，给我匹配了一个十几公里外的司机 直接取消，换车 到了火车站，结果还没有开始检票qaq 上火车之后，一个小时就到了武汉 然后来华科 结果进到酒店，从hust南一门进酒店，兜兜绕绕走了接近两公里 perfect 今天下午还要去和wjyyy Dew Zech Touch_kd walk_alone面基来着 最后一次OI比赛了，出不了成绩了，好好享受吧，enjoy myself！！ Day0?? 不知道为啥是day0 可能因为是NOIP2021的官方发的文件里面是day0吧 早上七点起床 然后我就皮了...

【全程NOIP计划】组合计数选讲 组合数基础 加法原理 加法原理，总共的等于各个相互独立的相加 乘法原理 两个不相干的事情同时发生，总共的情况是两种情况相乘 抽屉原理 容斥原理 排列数 从n个中选m个，考虑顺序 总的方案数为Pnm=n!(n−m)!P_n^m=\frac {n!} {(n-m)!}Pnm​=(n−m)!n!​，或者可以记录为AnmA_n^mAnm​ P5520 青原樱 思路 实际上就是两个幼苗之间至少有一个空位，然后m个幼苗之间必须有m-1个空位 所以把这m-1个位置空出来，然后剩下的位置乱插 答案就是An−m+1mA_{n-m+1}^mAn−m+1m​ 1234567891011121314151617181920#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;int type,n,m,p;long long A(int n,int...

【全程NOIP计划】图论算法 最短路算法 常用的最短路算法SPFA,Dijkstra,Floyd算法 最短路问题，就是对于有权图的两个点，找到一条连接两个点的路径，使得路径的权值和最小 在说最短路算法之前，必须了解松弛的概念 其实n简单，如果a→b+b→ca \rightarrow b+b \rightarrow ca→b+b→c的距离比a→ca \rightarrow ca→c的小，那么就可以用前者代替a到c的距离 各种各样 最短路实际上就是不断做松弛操作 Floyd 可以求出图中任意两点的最短路，过程很简单 首先枚举松弛操作的中间点，再枚举松弛的左右两个点，然后做松弛操作 由于Floyd算法暴力枚举的特性，所以用邻接矩阵很方便 很显然，复杂度为O(n3)O(n^3)O(n3) 1234for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=min(a[i][j],a[i][k]+a[k][j]); 正确性 怎么证明正确性？ 对...

【全程NOIP计划】数学推导选讲 常见不等式 柯西不等式 对于数列a和b,有以下恒成立 ∑i=1nai2∑i=1nbi2≥(∑i=1naibi)2\sum_{i=1}^na_i^2 \sum_{i=1}^n b_i^2 \ge (\sum_{i=1}^na_ib_i)^2i=1∑n​ai2​i=1∑n​bi2​≥(i=1∑n​ai​bi​)2令 A=∑ai2,B=∑aibi,C=∑bi2A=\sum a_i^2,B=\sum a_ib_i,C=\sum b_i^2A=∑ai2​,B=∑ai​bi​,C=∑bi2​ 构造以下式子 f(x)=Ax2+2Bx+c=∑(aix+bi)2≥0ai2x2+2aibix+bi2≥0f(x)=Ax^2+2Bx+c=\sum(a_ix+b_i)^2 \ge 0 \\ a_i^2x^2+2a_ib_ix+b_i^2\ge 0f(x)=Ax2+2Bx+c=∑(ai​x+bi​)2≥0ai2​x2+2ai​bi​x+bi2​≥0△≤0\triangle\le 0△≤0，然后就得证了 例子： 有x1,x2,…,x4n≥0x_1,x_2,\dots,x_{4...

【全程NOIP计划】树上问题 最近公共祖先 问题 给定一棵树，每次给两个点，求他们的祖先，且该祖先为深度最小 思路 一般来说，我们想到一个暴力做法 查询x,y的话，直接把x的祖先全部标记一遍，然后把y向上遍历，直到遍历到一个点，使得这个点被标记过，这个点就是x和y的最近公共祖先 或者，使得深度更大的第一个点一直向上跳，让x和y的深度一样，让他们一起一步一步向上跳，直到他们遇到同一个点，这样的方法正确性没有问题，它的复杂度和这棵树的深度是有关的 考虑倍增，对于刚才的做法进行优化 原来的方法：fa[i]fa[i]fa[i]表示i的父亲 倍增的方法：fa[i][j]fa[i][j]fa[i][j]表示i向上跳2j2^j2j到哪个点 怎么预处理呢? 123456f[i][0];for(int j=1;j<=logn;j++){ for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1];} 这样我们就维护出来了 所以倍增lca的步骤就是： 1.先让y的深度比x大，然后将y和x调到深度相同的位置 2.然...

【全程NOIP计划】简单数论 基础知识与记号 ∀\forall∀,∃\exist∃ 整除：如果a=bka=bka=bk,其中a,b,ka,b,ka,b,k都是整数，则bbb整除aaa，记作b∣ab|ab∣a 也称作b是a的约数（因数），a是b的倍数 如何求出n的所有约数？ 如果a是n的约数，则n/a也是n的约数，且a和n/a中必有一个小于等于根号n 所以我们直接枚举1到根号n之间的所有数，判断是不是n的因数就可以了 a和b的最大公因数记为gcd⁡(a,b)\gcd(a,b)gcd(a,b),或者(a,b)(a,b)(a,b) 特殊地 1.(a,a)=(0,a)=a(a,a)=(0,a)=a(a,a)=(0,a)=a 2.如果a∣ba|ba∣b，则(a,b)=a(a,b)=a(a,b)=a 3.(a,b)=(a,a+b)=(a,ka+b),(a,b)=(b,a mod b)(a,b)=(a,a+b)=(a,ka+b),(a,b)=(b,a \space mod \space b)(a,b)=(a,a+b)=(a,ka+b),(a,b)=(b,a mod b) 4.(ka,kb)=k...