模拟退火学习笔记
模拟退火，RP检测器，玄学算法，yyds。 看什么学习笔记，当然是看日报了。 过程 就是模拟冶金学的退火过程，乱搞，具体理论的证明我也不是很懂。 流程图(自己懂就好)： 优化/乱搞 温度T的初始值设置问题。 温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。 退火速度问题。 模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。
差分约束学习笔记
给定 $n$ 个形如 $a-b≤c$ 的式子，求一组解或求两个变量间的最值 转化为图论问题跑最短/长路即可。 例：P3275 [SCOI2011]糖果 。 简化题意：给定一串约束条件，求所有元素的最小值。 稍微转换一下，就是使两个元素差值尽可能小。 例如 $x_1+c≤x_2$ 如果用最短路去约束，则会取到最小值，所以应该用最长路去维护。 具体原因我也解释不来屮。 又因为题意对每个元素都有大于等于1的约束，所以从超级源点向每个元素的边边权要设为1。 这题就做完了，但是有些些小细节。 #include<bits/stdc++.h> #define N 200005 #define int long long using namespace std; inline in..
牛客提高第七场T2 武义寺 题解
题意简述 对于一个排列 ${p= \{ 1,2,...,n\}}p={1,2,...,n}$，记 $\text{val}(p)$ 等于最小的 $i$ 满足 ${i}> a_ii>a$ ，如不存在则 $\text{val}(p)=n+1$ 。求 $\text{val}(p)$ 的期望值，答案对 $998244353$ 取模。 题解 令 $k=n+1-i$ ，枚举 $a_i=j$ ，则前 $i-1$ 个数的可行的方案为: $sum_i=$ $\sum \limits_{j=1}^{i-1}(k+1)^{i-1-j} \times k^j$ 大力观察发现是等比数列。 等比数列求和公式： $\sum \limits _{k=0}^{n-1}(x \times a^{k}) = ..
NOIP 2021 游记
$\mathrm{Day} -9$ 打模拟赛 ： $A$ 题不会啊，dp 真难。 $B$ 题按板子打完部分分之后开始乱搞，想着把每个不同的字串拿出来搞一下再取和。没想到再来一次 dp 很可惜 (话说为什么有两道dp) 。 $C$ 题暴力，啥是数论分块？ $D$ 题暴力，啥是重心？重心咋求？ $20 + 70 + 35 + 50 = 175$ 被 wyy332623 和 rouxQ 巨佬吊打。 打 generals：被全机房吊打。 $\mathrm{Day} -8$ 又打模拟赛： $A$ 题二分+特判乱搞，搞过去了，话说二分怎么打。 $B$ 题傻逼dp ，然而赛时还是没有调出来。对自己dp 式子理解有误，tcl。 $C$ 题欧拉序+大力观察，下午补的时候忘了前向星反向历遍心态调炸了..
FHQ- Treap学习笔记
FHQ-Treap 与Treap都保证在第一关键字有序的情况下，维护第二关键字以达到平衡的目的。 但是Treap用的是旋转，FHQ-Treap 用的是分裂和合并。 FHQ-Treap 与Treap不同的地方： 优美的分裂和合并。 非旋。 支持区间修改 FHQ-Treap 与Treap相同的地方： 都保证在第一关键字有序的情况下，维护第二关键字。 本质上都是BST(二叉搜索树)。 注意点 合并时要保证第一棵树的权值小于第二棵树的权值(因为合并操作只比较随机值)(仅指作为平衡树时的操作)。 排名分裂维护的是书的中序遍历。(例题) Code of P3369 【模板】普通平衡树 #include<bits/stdc++.h> #define N 200005 using na..
乘法逆元小结
什么是乘法逆元 当有 $ a*x ≡ 1 \pmod {p} $ 时，则 $a$是模 $ p$ 意义下的乘法逆元。 费马小定理求逆元 费马小定理 $a ≡ a^{p-1} \pmod {p} $ 所以 $a^{p-2} ≡ 1 \pmod {p} $ 求 $a^{p-2} \bmod p$即可。 当且仅当 $p$ 为质数且 $a,p$ 互质时可用。 int ksm(int x,int k){ int sum=1; while(k){ if(k&1) sum=sum*x%p; x=x*x%p; k>>=1; } return sum; } signed main(){ px=read(),p=read(); ans=ksm(x,p-2); return 0; } 扩展欧几..