CS奇妙

之前RXZ说做了一道题没感觉就没必要写笔记，所以一直没写，但是今天遇到了一道题。非常有意思，是一种我不知道的做法。 洛谷 P1141 01迷宫由于放链接会发生一些不妙的事情，请自行去洛谷查看。 题意没有任何的弯弯绕绕。 看到题的tag是广搜就先写了个bfs，然后Tle了3个点。 bfs tle代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475#include <cstdio>#include <queue>#include <utility>#include <cstring>using namespace std;const int MAXN = 1e3 + 5;const int dx[] = {-1, +1, 0, 0};const int dy[] = {0, 0, + ...

前言忽然想起自己考前还报了一个acwing的课,似乎内容比洛谷的还多,报名人数3.5w不是瞎说的。 (听完第一节课感觉讲的甚至比RXZ还好。) 排序快排之前已经在很多地方学习过了,RXZ与yxc所说的暴力方法有点不一样，但是很相似,是不得已才使用的。 暴力方式暴力的方式是指重新开一个数组，将小于哨兵的放入排序数组，大于哨兵的放入tmp数组，放完大于后从tmp数组中取出大于哨兵的放入排序数组。这样做常数有点大。 优美的方法yxc讲一个非常优美的做法，起初有2个指针，l和r分别在区间头部和区间尾部。 当l指向的数小于哨兵时，继续移动，直到遇到大于哨兵的数为止。 此时开始移动r指针，当r指向的数小于哨兵时停止。 此时将l和r指向的数交换。 是不是非常优美，常数也不大，要付出的代价只是指针的移动罢了。 12345678910111213void quick_sort(int q[], int l, int r){ if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; whi ...

余幼学便知$oi$。初学之时，因余居于五线，故余之学甚难。尝费重金学之，但余之师仅教余何为$C++$,$STL$等余之师仅知，不知怎用。此后，余两载未学$oi$。 偶得知何为$OJ$,一$OJ$曰洛谷。余甚奋，欢喜间进入，进入洛谷后甚是欢喜。但当余写题之时，余险些因惊而亡。余甚至不会$C++$,余不知全局变量默为$0$，余不知$scanf$需&。余悲愤间购书做题，余题解中学习，余他人之嫌中学习。每当吾请教余他人，他人曰：“汝之教练未教汝？”余便曰：“吾无师，无教练，仅因兴趣学之$oi$。望神犇教吾为何此题如此。” 余学习如此一载后，仅能做出红题。余甚是悲愤，偶知洛谷网校，故余一年正月报一课。该课讲师之水平参差不齐，余仅能听进一师曰阮行止之课。其师之课，余堪略懂。 阮行止之课甚好，余一遍便能懂其八九。惜乎！该课仅有阮行止之课一节，余甚憾。 后余报之$CSP-jonior$,仅得二等,且因需备考，暂离$oi$。 今年余得知阮行止开班，当日便咨询余阮行止。当余与阮行止交谈，余甚是激动，次日便报此课。阮行止之课甚妙！当余听一课之时便泪目。 自余知何为$oi$以来，未有人教余如初学。余昔 ...

上次去某个日本注册商撸了几个域名，然后直呼：“啊！我这无处安放的域名！”就打算用vercel部署几个镜像站。 镜像站是个好东西，主站炸了也不至于人没了。 去github新建一个仓库，用于存放hexo生成的静态文件。注意：是静态文件，可以使用hexo d直接上传。 1234- type: git repo: 你的github仓库地址 branch: master message: blog_update github 仓库自然不必多说。 进入vercel官网：https://vercel.app 点击new project创建新项目。 选择你刚刚新建的github仓库： 部署即可。 记得选择香港节点！！！！ 如果没选择，可以到： 更换节点，更换后记得重新部署。 还可以到侧边栏的domain绑定域名。 This post was written on Aug 15, 2022.

虽然说：“一般普及组集训不会讲线段树，所以即便听不懂，也没有什么关系。” 但是我们也必须学好。 线段树是快速的查找某一个节点在若干条线段中出现的次数，RMQ也常常使用线段树来实现。 线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。 —— 百度百科 eg1:《动态成绩查询》一个班里有n名学生，他们的学号是1~n 起初，所有人的成绩都是0，有m次操作。 给x加分或者减分 给定l,r求区间和 数据范围是很经典的$10^{5}$。 建立一个树，根是1~n的区间和，左孩子和有孩子是1 ~ mid和mid ~ n，叶子节点为单个学生。 给x加分即给x的所有父节点加分，这就是线段树。 我们使用堆式存储存下整个树。 虽然说是有10w个节点，但是我们不能只开10w，我们要开2的整次幂，且接近10w。而$2^{17}$可以满足条件。 我们定义w[]存储一 ...

今天要学习数据结构进阶了！今天的课表有： hash表 并查集 线段树 晚上还可以要学习st表。（虽然这些都是提高组的内容，但是谁知道出题人会怎么想呢？） 但是作为衔接还是不错的。 hash表静态教务系统 今有某大学，里面有 n(≤ 100000) 名学生。 每个学生有学号，学号在 [1, 109] 范围内分布。给定所有学生的学号和成绩。有 m(≤ 100000) 次查询，每次查询是给出一个学号，问其成绩。 直接用桶储存会出事的，因为不可能存开1e9的数组会爆空间。 因为n≤100000所以我们可以开一个结构体，有id和score两个属性，这样即可存下100000个学生。 但是仔细一想，嗯？这样只能遍历来查找了，查找的时间复杂度为$O(n)$。有m次查询，所以整个算法的时间复杂度为$O(nm)$，而n≤100000，m≤100000则最大时间复杂度为$10^{5}$*$10^{5}$即为$10^{10}$。这是不可接受，远远大于普遍算力两千万/s，必然会超时。 我们可以优化一下，先排序，然后使用二分进行查找，这样查找的时间复杂度为$O(logn)$。时间复杂度为$O(nlogn) ...

Note:vector的学习vector是STL(Standard Template Library)中的动态数组，功能非常的强大，在不存东西的时候几乎不占空间。 他可以做到： 尾部插入 获取长度 随机访问 清空 排序 vector 初始只占用很小的空间。随着内部元素增多，空间将会随之扩增。 OI 中，需要动态数组的场合，我们一般倾向于使用 vector，因为 vector 大小可变、提供了充足的 API。 eg:洛谷P1177 1234567891011121314151617181920212223242526272829303132#include <bits/stdc++.h>using namespace std;int n;vector <int> v;void input() { cin >> n; for(int i=0; i<n; i++) { int x; cin >> x; v.push_back(x); // x 追 ...

发现在wls中无法使用ohmyposh的主题，于是打算安装官网的linux教程配置，但是发现国内用homedrew和下载有亿点慢。所以使用了官网的手动安装教程：Linux | Oh My Posh 手动安装把手动安装脚本改成： 12sudo wget https://download.fastgit.org/JanDeDobbeleer/oh-my-posh/releases/download/v8.22.1/posh-linux-amd64 -O /usr/local/bin/oh-my-poshsudo chmod +x /usr/local/bin/oh-my-posh 然后执行： 12345mkdir ~/.poshthemeswget https://github.com/JanDeDobbeleer/oh-my-posh/releases/latest/download/themes.zip -O ~/.poshthemes/themes.zipunzip ~/.poshthemes/themes.zip -d ~/.poshthemeschmod u+rw ~/.posh ...

在把自带主题几乎都用了一次后，感觉还是自己魔改方便和适合我。 我把cert主题魔改了一下: 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960{ "$schema": "https://raw.githubusercontent.com/JanDeDobbeleer/oh-my-posh/main/themes/schema.json", "blocks": [ { "alignment": "left", "segments": [ // { // "background": "#E36464", // "foreground": ...