分享今天心情 - 2024年3月
type: channel
link: http://tocry.cn/index.php/2024/03/
description: 鱼尚且有刺，人岂能无骨！
items: 线段树
items: 速通模拟退火
items: VScode安装c/c++环境

线段树
type: item
date: 2024-03-27T10:25:00+00:00
description: 速通线段树（入门）2023年3月15日第6次修订本内容必要条件：看懂代码的必要条件：c++的基本语法（数组、函数调用、结构体、输入输出）掌握逻辑的必要条件：掌握递归算法思想（不会的我无法保证你能看懂）warning-警告！！！ warning-警告！！！ warning-警告！！！（一）如果你没有了解过递归，我无法保证你能完全看懂本文。如果你执意学习，请做好可能失败的心理准备。（二）如果你没有学过C++基本语法（但是学过其他语言，也了解过递归），请翻阅下去，本文不会让你后悔。作者也是JAVA出身。作者保证你可以看懂除代码外的其它内容。如果你没有了解过递归，请至少学习斐波那契数列的递归实现或汉诺塔的递归（或者其它简单递归）的实现后再来观看！谢谢您的配合！如果你没有了解过递归，请至少学习斐波那契数列的递归实现或汉诺塔的递归（或者其它简单递归）的实现后再来观看！谢谢您的配合！如果你没有了解过递归，请至少学习斐波那契数列的递归实现或汉诺塔的递归（或者其它简单递归）的实现后再来观看！谢谢您的配合！非必要条件：会堆（Heap）这个数据结构（可以帮助你更快速入门）读者若是不会堆，作者也保证你可以看懂线段树0.观前提醒：递归和堆结构是递归且非动态开点的线段树的必要组成本文只教授递归式且非动态开点的线段树递归式线段树堆（Heap）式的、且空间以及开辟完成的、采用数组模拟内存的线段树如果你不会堆，本文可以保证你可以看懂。1.（重点）抓住线段树的精髓：维护区间信息线段树是一个数据结构区间信息：数据离散化（数据索引是有限的）成一条直线（数组），上面截出一段（数组的一部分）的信息（区间和，区间平方差和，最大最小值，异或值……）维护：如果你改了上面的一些数据，它仍然可以帮你查询出来请仔细理解维护区间信息这个内容，并牢记于心，仔细体会2.如何实现维护区间信息（思想）2.1.线段树的结构观前提醒：如果你是新手，在看这一节（2.1节）的时候，请你把大脑中“这个用代码怎么实现？”这种问题清除掉，我们只关注结构本身。请牢记：开始的时候，走的稳、走的慢，最后才能走的远。假设我们有以下的区间信息（下标从1到8一共8个内容），内容是随便取的不用纠结，因为下面用不到它线段树的做法利用分而治之的思想，将1-8的区间信息放入一个格子中，然后将其分成两段（其实是有多段实现的，但是我们只学习最基础的两段式）我们将顶点1-4和5-8的区间信息分开存储，周而复始，依次往下1-4分成1-2和3-4，5-8分成5-6和7-8，以此类推如果你无法理解什么是区间信息的话，你可以举例（假装）为这些格子的数字之和（假装现在区间信息就是这些数字之和）其实区间信息有很多种，我在第一节中就列出来了一些（区间和，区间平方差和，最大最小值，异或值……）（如果你没有好好看，请你回过去再仔细体会一下维护区间信息这个精髓说法）一图胜千言：你可能非常容易就发现了最底下的格子颜色与上面的不一样，因为他们是最小区间单位（也就是只存储一个格子的信息，所谓的2-2就是2到2，那就是2这个格子本身）。那么到此为止，读者肯定发现了一个问题：为什么我刚好选的是8，刚好是2的幂次？原因是这样好画，但是这不是问题的答案。因为我们必须也应该知道，不是2的倍数，不是2的幂次时线段树该如何建立譬如1到7时，我们该怎么建立呢？一般是向下取整建立分段（即7整除2答案为3，你可以理解为把余数全部去除）区间1-3分成1-2和1-1，区间4-7分成4-5和6-7（4加7是11，11整除2是5，所以以5位分界点）所以这样建立的图如下所示：2.1练习：绘画1-11的线段树大家可以在纸上自己绘画1-11的线段树区间信息段，然后与我的数据对照，重点关注绿色的最小区间单位节点是什么地方至此为止，其实你已经学了一半的线段树了，也就是线段树的数据存储方式（怎么画出线段树，每个格子是什么意思）作者这里想说一些话：假设不涉及代码，我们也可以画出线段树的格子，不是吗？代码固然重要，但是思路在其中占比至少也是50%如果你是初学者，画出了格子，那么你已经成功百分之50了。有些东西没有想象的那么难。2.2.核心思想一：儿子与父亲的关系从2.2开始，我们慢慢铺垫如何用代码实现，稍安勿躁。（也不会出现很多代码）如果你没有学过二叉树（Binary-Tree）和堆（Heap），那么可以仔细看看下面的内容。儿子和父亲是相对关系，上面的是父亲，下面的是儿子。树上的每一个格子我们称为结点请注意：儿子和父亲是一层之内的相对关系，儿子分左右，父亲只有一个，请对照下面的图进行理解（重点）堆(Heap)的结点编号系统我们接下来要干一个非常重要的事情：对每个结点进行编号，也是堆的核心思想。请仔细观察每个儿子与父亲编号的关系！！我们可以得出以下结论：所有的左儿子的编号是它父亲编号的两倍所有的右儿子…

速通模拟退火
type: item
date: 2024-03-27T10:01:14+00:00
description: 速通模拟退火（Simulated Annealing）作者：郭程(judgemeido@163.com)本教程为原创教程，转载请标明出处，禁止商业用途。本教程属于快速入门（Quick-Start)系列，不对具体退火细节深究，只论算法竞赛题目研究。1.是什么？为什么？怎么做？Q1:模拟退火是什么算法？模拟退火是模拟物理上退火方法，通过N次迭代（退火），逼近函数的上的一个最值（最大或者最小值）。比如逼近这个函数的最大值C点：Q2:模拟退火为什么可行？讨论这个问题需要理解一下物理原型是怎么样的，也就是原来是怎么“退火”的：模拟退火算法的思想借鉴于固体的退火原理，当固体的温度很高的时候，内能比较大，固体的内部粒子处于快速无序运动，当温度慢慢降低的过程中，固体的内能减小，粒子的慢慢趋于有序，最终，当固体处于常温时，内能达到最小，此时，粒子最为稳定。注意标粗字体：温度高->运动速度快（温度低->运动速度慢）温度是缓慢（想象成特别慢的那种）降低的温度基本不再变化后，趋于有序(最后内能达到最小，也就是接近最优)我们通过模拟这个操作，使得我们需要的答案“趋于有序”，也就是最靠近需要的值（最值）。Q3:怎么做？大方向首先，理解一下大方向：模拟退火就是一种循环算法。我们先设定一个初始的温度$T$（这个温度会比较高，比如2000）每次循环都退火一次。（具体怎么操作后面详解）然后降低$T$的温度，我们通过让$T$和一个“降温系数”$\Delta T$（一个接近1的小数，比如$0.99$)相乘，达到慢慢降低温度的效果，直到接近于0（我们用$eps$来代表一个接近0的数(比如0.00001)，只要$T>eps$就可以退出循环了）所以总的来说，用伪代码表示退火的流程是这样的：double T = 2000; //代表开始的温度 double dT = 0.99; //代表系数delta T double eps = 1e-14; //相当于0.0000000000000001 while(T > eps) { //-------------- //这里是每一次退火的操作 //-------------- T = T * dT; //温度每次下降一点点， T * 0.99 }退火详解我们要求解的答案无非是两个：自变量$x$和对应函数的最大值$f(x)$那么模拟退火的是怎么做到的呢？【下面车速很快，请系好安全带！】我们先随机找一点$x_0$ ，不论是哪个点都可以，随机！（不超过定义域就行）。这个点作为我们的初始值（相当于物体里的一个粒子）再找到一点$f(x_0)$,来代表$x_0$所对应的函数值现在正式开始退火！刚才我们说了$x_0$相当于是一个粒子，所以我们会进行一个无序运动，也就是向左或者向右随机移动是的，是随机移动，可能向左，也可能向右，但是请记住一个关键点：移动的幅度和当前的温度$T$有关。温度$T$越大，移动的幅度越大。温度$T$越小，移动的幅度就越小。这是在模拟粒子无序运动的状态。接受(Accept)更"好"的状态假设我们移动到了$x_1$处，那么这个点对应的$f(x_1)$很明显答案是优于（大于）当前的$f(x_0)$的因此我们将答案进行更新。也就是将初始值进行替换：$x_0=x_1,f(x_0)=f(x_1)$。这是一种贪心的思想。以一定概率接受(Accept)更差的状态这是退火最精彩的部分。为什么我们要接受一个更加差的状态呢？因为可能在一个较差的状态旁边会出现一个更加高的山峰如果我们鼠目寸光，只盯着右半区，很容易随着温度的下降、左右跳转幅度的减小而迷失自己，最后困死在小山丘中。而我们如果找到了左边山峰的低点，以一定的概率接受了它（概率大小和温度以及当前的值的关键程度有关），会在跳转幅度减少之前，尽可能找到最优点。那么我们以多少的概率去接受它呢？我们用一个公式表示（这个公式我们只需记住，这是科学家推导出来的结论）：$$ \Huge e^{\frac{\Delta f}{kT}} $$别慌！很简单！我们来理解一下这里面的变量：$e$是自然对数，约等于2.71。我们可以把右上角这一坨值$\frac{\Delta f}{kT}$看成一个整体$x$:$e^x$的图形画出来是这样的：因为我们想要函数$e^x$来代表一个概率值，所以我们只需要关注x为负数的部分即可：负数部分的值域是在$(0,1)$开区间内，x越小，越接近0，越大越靠近1。因为在0到1之间，所以这个值相当于是概率了。比如$e^x=0.97$，那么我们接受的概率就是$97\%$而正数部分的值域会大于1，也就是说概率会超过$100\%$，所以会一定选（其实是上一种找到更优的情况）$kT$$k$其实是个物理学常数，我们在代码中不会用到。$T$很简单，就是当前的温度。所以实际上这个分母就是$T$，$k…

VScode安装c/c++环境
type: item
date: 2024-03-27T10:00:04+00:00
description: VScode安装c/c++环境本文操作系统：windows10 22H2 专业工作站版（所有win10系统都可使用)本文目标人群：刚上手需要安装c/c++环境的新手同志们。或是单纯重装系统需要重新配置c++环境的。本文章解决问题：为什么我的vscode无法运行c++？0.在此之前的操作在开始之前，请你在此电脑页面中查看标签下确保你勾选了文件扩展名与隐藏的项目1.vscode下载与安装vscode在官网上可以下载：在百度中搜索vscode，点击下载即可安装安装环节不多赘述，下一步即可。选项默认。安装地址可以自行更改。2.编译器MinGW-64的安装（老手可跳过）你需要知道一个c++文件是如何才能在你的电脑中运行的：你写的是文本，而只有二进制才能运行。所以所谓的"编译器"就是解决将文本变成可执行文件的一个工具。vscode并不是一个IDE(集成开发环境)，它就是一个可以安装插件的可扩展文本编辑器。也就是说，你如果不装编译器，你的vscode是无法解决编译问题的。所以我们需要下载一个在windows电脑上可以帮你编译的编译器，也就是MinGW-64。MinGW的全称是Minimalist GNU on Windows。它实际上是将经典的开源C语言 编译器 GCC 移植到了 Windows 平台下，并且包含了 Win32API ，因此可以将源代码编译为可在 Windows 中运行的可执行程序。而且还可以使用一些 Windows 不具备的，Linux平台下的开发工具。一句话来概括：MinGW 就是 GCC 的 Windows 版本 。下载方式如下：首先搜索mingw-64 sourceforge找到地址为sourceforge.net的网站注意名字叫做MinGW-w64 - for 32 and 64 bit Windows，请确定是这个名字接着我们点击Files然后向下拉，找到这个文件x86_64-posix-seh点击就可以下载了。如果你5秒后没有弹出下载页面或者下载非常慢，请点击这个按钮点击direct link可以解决没有下载的问题。点击auto-select可以解决下载过慢的问题（会自动分配最好的镜像节点进行下载）请确认你的下载全名是x86_64-8.1.0-release-posix-seh-rt_v6-rev0，并且是7z压缩包，大小48213KB使用解压缩软件进行解压。如果你没有解压缩软件，你可以下载7-zip这个开源免费软件。当然也可以使用win-rar,360压缩等一系列软件进行解压。我现在演示7-zip这个软件,其他软件同理右键，使用7-zip打开，出现这样的页面解压到你需要的目录。这里我解压到了C:\Environment解压以后是这样的接下来我们配置环境变量。右键此电脑点击属性。在打开的窗口中依次点击高级系统设置，环境变量在打开的窗口中系统变量里找到Path，单击选中，然后点击编辑。（或者直接双击）在环境变量中点击新建，在生成的地方粘贴进去你的目录bin位置假如你解压的地方是c:\Environment，那么这里应该填写c:\Environment\mingw64\bin或者你打开刚才解压的位置，然后单击地址栏（注意在空白部分单击），进行复制设置完成后一定要点击确定，直到刚才的三个窗口全部确定且关闭、然后按下开始菜单键或者键盘上的win键，搜索cmd输入gcc，回车。若是出现以下情况，说明安装完成。3.vscode 的配置打开后，安装c/c++ 与 中文插件点击打开文件夹，选择一个你用来工作，放置c++文件的文件夹（最好是空的）请注意！：接下来的配置只能在此文件夹或者这个文件夹的子文件夹下生效请注意！：接下来的配置只能在此文件夹或者这个文件夹的子文件夹下生效请注意！：接下来的配置只能在此文件夹或者这个文件夹的子文件夹下生效打开后在左边右键新建文件，我新建了x.cpp，你也可以新建a.cpp、b.cpp等，以.cpp结尾的文件接下来输入测试代码#include <iostream> using namespace std; int main() { cout << "hello" << endl; return 0; }这个时候请按下Ctrl+Shift+P键盘上的三个键在弹出的框中输入edit configurations，选择编辑配置（UI）注意：如果你的默认配置就与我一样，那么就不需要改注意：如果你的默认配置就与我一样，那么就不需要改注意：如果你的默认配置就与我一样，那么就不需要改请选择刚才安装路径下g++.exe在IntelliSense 模式中选择windows-gcc-x64。并且此时你可以看到在左边出现了.vscode的配置文件c_cpp_properties.json在高级设置中清空所有设置最终文…