wweiyiの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)^2 ∑i=1n​ai2​∑i=1n​bi2​≥(∑i=1n​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≥0 f(x)=Ax^2+2Bx+c=\sum(a_ix+b_i)^2 \ge 0 \\ a_i^2x^2+2a_ib_ix+b_i^2\ge 0 f(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,\dot...

【全程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=bk ,其中,其中,其中a,b,k都是整数，则都是整数，则都是整数，则b整除整除整除a，记作，记作，记作b|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...

【全程NOIP计划】思维与构造题 什么是构造题？ 不同于维护数据结构并回答询问的数据结构，寻找最大值和最小值的最值问题，计数问题，但构造体致力于让你给出一组方案，使得在一定的限制内满足某些条件，方案通常不唯一，构造方法也可以不唯一 比如： 1.给定一个排列，允许元素交换操作，输出一组操作使之排序 2.输入一个数，输出一个边长为整数的非直角三角形，且该三角形的面积为n 3.没有输入 解题方法 比如二分，分治，排序，图论，网络流，2-sat，最短路等 再比如数学公式直接求出来 还比如归纳法，先考虑通过构造小的情况，再通过小的情况构造大的情况 考虑特殊情况，比如要求构造一个特定的图，可以自己添加条件限制范围，比如特定的二分图，特定的树，特定的链等，一个常见的条件为对称性，构造具有数学美的答案 CF1438D 思路 如果只有三个数的话，一次就能操作完了 如果n=4的话，一次操作变成了aaab，或者abbb，如果a不等于b，那么就是无解 n等于5的话 a,b,c,d,e 于是我们发现了一个好办法，如果三个数是aab的形式，可以变成bbb 如果我们把数弄成aabbccdd…fff的形式，那么...