#bilibili #oi #school #China #life

#cplusplus #dev #oi #algorithm
摘要：支持 iostream(cin/cout) 的语法糖 cout<1<endl;
取余操作(当然是OI应该叫模数了 但我不OI) 隐式 int mod 上下文的宏，以及 (57 / 233) % 10007 == (mint(57) / 233).v 的快速模意义(mint)运算
支持 mic::graph::directed_weighted_graph<type> 这样命名的图对象，有 resize(n); link(a,b); edges(i) 甚至 is_tree() 等操作
题外话 C++ 什么时候支持 for (auto [a,b] : iter) 这种语法了…… std::pair 可能有用吧

此外有 random 生成 int/longlong(rng.rand<t>())/tree 数据(无重生成)的
e(1,2 +1) == 2

brackets(10) // [] seq
binary_tree(10) // size 10, depth (log2 10-1)+1
e.shuffle(a.begin(), a.end());

还有 ANSI terminal (term.h) 的
（当然，基于 escape code 可以与 std::cout 配套
[fg/bg]_color(red) 定义前背景色
(no_) underline/blink 选择风格
reset/error_color 便利 span
用 reset_line() 删除上一行制作单行动画(如进度条)
还有 cursor::right 及 hide/show 这样的光标API；整体可配合 std::cout.flush(); 使用

最后是一个数据生成及校验的（这个目标比较有趣，但只做了类似离线OJ的使用目标）

mic::random_engine rng;
ZEN_GEN/*to data/ folder*/("[name]", 20) {/*(id, out) ->*/
  int limit; switch (id){
    case 1 ... 5: limit = zen::map/*_range*/(1,5, 20,100);/*with step change*/; break;
    default: limit = 5000000; break;
  }
  out << rng(0, limit) << ' ' << rng(0, limit) << std::endl;
}

检验：

ZEN_CHECK("a.cpp", "b.cpp") {
  out << e(0, 20000) << ' ' << e(0, 20000) << std::endl;
}

对比逻辑是写死的，命令行 编译 clang 差异 diff

感觉不错， Mivik 大佬的接口复用设计能力比以前强了好多啊（一个月前上传的，大概是现在才想起来发） 🤔
这用途都不止 OI 了，而且命名都很优雅
原来现在 OI 才是 C++ cutting edge 语言特性的最大利用方啊

#oi #algorithm

#oi #algorithm #math #statics 包含答案和图表，这篇文章写了伪随机序列迭代生成引擎/shuffle/sample/平权括号序列/(二叉)树/图 以及相应统计学原理公式。

https://t.me/dsuset/9303 #oi #China #LGBT 又有女装跨性别OI大佬被送矫治了🌝
这次有主流媒体报道

https://t.me/dsuset/9303 #NEWS #OI #China #LGBT 又有女装跨性别OI大佬被送矫治了🌝
这次有主流媒体报道

可能有订户觉得 ::Echo 是技术频道，不应该发一些激进的社会争议性内容 🌚 #school #statement #oi #tech #science

但是这件事的当事人是一个 OIer ，信息学奥林匹克参加者，我觉得某种意义上，并不是和计算机科学无关的哦。

当然这个投票本身没有什么意义，欺凌者不会觉得自己有错，或者对自己的罪过有侥幸心理，这往往也是地区性的问题，一些开明地区的人不会以讥笑他人为乐、不会对受害者落井下石，但我还是想看看大家的真实想法。

https://t.me/Javaer/556285
#Python #algorithm 看讨论的方向是简单实现就写了两个，最后 #oi 大佬还来抒发了一下见解

topk 就是 n 个数据取降序 k 项，这里提供 MapReduce(某种负载均衡，子集归并排序)、选择排序 俩算法。（因为我就会 选择/插入/冒泡/快速 四种排序算法了……）
空间复杂度： O(k*k), O(1)
时间复杂度： O(baO(k*baO(n/k))) 其中 baO 为 sort() 复杂度, O(k*n)

其实前者的归并(topz)法也有更好的版本，原来需要 xxs[0:n] (已排序子表的前 n 项，注意整体合并完就是 n 项)的，实际上可以按 xxs[0] 排序一遍，再定一个集合，直到 key(xx) 填满 n 项取子表头一项 append 到 tops 即可。（划掉）
好吧，如果连续两子表头相等，就只能加全它俩了(断言不了整体大小的关系)，所以看来这个“优化”有没有价值还另说。

#java #cs #DontKnow Integer.valueOf 的缓存机制 (即 (Integer)x==x 的左范围)

#functional 妈的，函数式和 SICP 现在自造词还不一样了，应用序 vs. 传值、正则序 vs. 传表达式(或是传惰性?)...

#JS #CSS #PLT HTTP #backend #blog 大佬的面试经历 我终于知道cs是学啥了🤔 杂学

#rust #PLT #tt https://edward40.com/tagless-final-in-rust 呃... 看来Ray说自己很菜是有道理的，是我见得少了，没想到同道这么多🌝

https://9bie.org/index.php/archives/635/ 超星邀请码... 这又一个 pwn #Security 的

https://cnblogs.com/Dillonh #oi #dalao 是 cnblogs... 上次一个 commajia 大佬也是

#cplusplus #English #PLT #ce #parsing #llvm https://zhuyi.fan/post/write-a-bf-compiler-with-joy.html
🌝🌚 看来是 CS ，爱了爱了

https://raptazure.github.io/posts/purs-react/ #functional #JS #tt #English 草这又是个大佬... 类型论大佬都喜欢英语

#oi #school #life 这位同学亲切一点，好像还在学德语🤔

🌚 生草的时光总是过得飞快， DFS 没有寻到最短路径但是的确能用。 一个半小时就过去了
这时候我终于体会到 #OI 生的坚困难苦难艰困，实在是太强自不息息自强了。 😭

#share #oi #project
自动造数据机，支持多线程数据生成和 洛谷/UOJ 地等多格式导出（不过因为需要视觉效果所以只有 unix 终端可以用）：https://github.com/Mivik/mic

#thought #oi #cpp
论如何在毒瘤题中给变量取名

#oi #life M大几年NOIP故事。，直到最近的Mivik Round，我入门之前也接触过scratch。希望以后有机会做scratch编辑器😭

#haha #inm #bilibili 搜到了几个野兽先辈的自动化工具 😂 (好啊！来啊！ 啊！？啊啊啊啊啊！！！)
https://lab.magiconch.com/homo/ 数字论证生成(map:Int,Str 数据集里选最大不大 拼接)
https://wyusagi.github.io/Proof_Yajuu/ 自动迫害机(文字模板)
https://www.cnblogs.com/lcyfrog/p/13181450.html #oi C++ 数字论证cli

#api #web 波形可视化 https://collab-project.github.io/videojs-record/demo/audio-only.html

c=player.wavesurfer().surfer //play , handlers.audioprocess (所有播放器都在tick时重绘进度条, finish
b=c.backend.buffer, c.drawBuffer() //展示所录制的音频波形
b.length, b.getChannelData(0) //一般 %44100 pps, float 格式

#oi #math 这个就不是信号处理的FT了，它是针对多项式 各项系数/x-y联立 表示 ，一个分治法，一般用来加速高精度乘法
系数转点值的算法叫DFT（离散傅里叶变换）
https://blog.csdn.net/Flag_z/article/details/99163939 }

FFT 令原 Pk=f(t)*e^-i2pik dt ，P=震幅相位,k=频率。用sum写是 Pk=Sum[i=1~N]f(i)*e^-i2pik *(1/N) #math #algorithm
先把 e^-i2pik*(i/N) =cos,sin缓存为Wi=Wn ..
算法的核心是ωn矩阵和fn数组(列矩阵)做矩阵乘法运算，因为ωn是复数，所以运算出结果也是个复数rval + i * ival，最终频域的值其实上是其模值，但为什么模值需要乘以个bSi 是为平滑

e^{ix} = cos x + isin x; ωn = e^{-2πik/n} = cos(2πk/n) - i * sin(2πk/n)

然后for(k N/2)for(i nBuf)x+=cos*buf,y sinbuf
频谱的信号只需要分析N/2就可以了，另一半是共轭的。 总之是算一个频时把exp(kt)缓存(把圆N等分 就不迭t0~1) 且同频宽的计算量/2

https://www.cnblogs.com/RabbitHu/p/FFT.html
https://zhuanlan.zhihu.com/p/197450738 JS fft

高精度乘法是 10e6 以上位，longlong 都能溢出的整数乘法，可用 a[i-1]+a[i]/10,a[i]%=10 手动进位法。i in"1",j in "2" a[i+j]=parse(i+j) 后迭 i+1-2 次(倒位相乘处理进位,再倒回来)
也可做<10e6常量优化，不致溢出就机器乘；溢出6位数才竖式计算

FFT蝶形系数换位 0~7 到 04261537 打表偶奇数|分割 实际是个 a[i]=a[~i] 的置换，向上还原
多项式每层(+)都要分为等长2部分，最高次项一定2幂
conj是自带求共轭复数。当复数模长为1时，共轭复数等于倒数
https://blog.csdn.net/zccz14/article/details/51592893 这里还有个咱方法的

（抱怨一句，同时我也感到数学的闲散了， 你说=xy点=向量还图示，不如直接说复数=向量，什么加减法则啊abcd废话都莫说了，直接说乘法咋用；还什么膜长，幅角，余数非得说是模数 还不挑明，还 modular math(转钟计算) ，还共轭复数(相反向量)，好像数学能模块化 还co-sine 余弦.. 叫竖弦咋样？噢带横竖就不可配不严谨。文绉绉的，好像只有数学家会看函数图一样，a+bi 哪有Pxy易读，非得入侵人家的领域表达法，带来不少无聊问题，起个名词 Complex(real,imag) ，复杂呵呵，一点语义都莫得，无意义的“运算符重载”，计算机没有real数，要SP却仍要拜数学为师了；它一装逼，下游应用名词全乱起来
一些废话说它何用，好像最后阅文的是机器，然鹅数学代码高亮都没得，记法和作用域混乱到机器用不了，还得人来翻译，可真两边不是人了，难怪被”憨蛋“们抱怨，啥事都插足包装，太爱整无意义担心了
复数给C引入了“向量计算”，我是不是还得谢谢数学啊 🌚 这么多文章天书一样重复的符号，看烂代码已经够累，还要看草记版公式上下标，数学的招牌。请问我的阅读顺序是 lr-tb 还是 tl-br 啊？我不是天才 真没精力了！

http://watmough.github.io/jsFFT/Example.html http://www.storiesinflight.com/jsfft/visualizer/index.html 那个 dsp.js 1.6k star

https://mivik.gitee.io/2021/life/dream/ 的 #oi #life 节选
我站起来时只能有一句“我拿到了提高组二等奖”，然后眼睛避着教练坐下去。后来教练单独谈话的时候问了个问题：

“你觉得你和那些拿一等奖的同学比有什么优势？”

是啊，那些没有优势的人，终点就是被淘汰。我也记不起当时说了什么，但这个问题至今还在我心中徘徊。

不知怎么的最后是被选进去了。不过这中间有件趣事。因为各个教练是在争夺学生的，然后信息教练让我去找 lzy（当时他是一营分数第一）。我和 deco（当时我并不认识他）一路，关键也不知道往哪儿找，瞎逛着碰见一个人，问了下他知不知道 lzy 在哪儿，那人：“我就是啊！”不过后来知道他已经被物理教练收了（貌似当时物理是比信息“有权势”的），于是也不了了之。话说如果 lzy 当初来信竞的话，今年应该得有三个集训队吧。

几次的联赛都是在电子科大考的。对生活只有学校和家两点的我，这无疑是新奇而令人兴奋的。当时初中的时候，在酒店看到几个穿着成都七中校服的学生，想着“我还考个啥啊”这样，最终荣获了提高组二等奖。

#algorithm #oi 字串-状态机
KMP是求 "abc".indexOf("bc") 即strstr的算法，单个子串搜索。最简解 (s,ss)=>rng(0,n(s)-n(ss)).find(i=> s.slice(i).startsWith(ss) ) ；即i于0~n-nSs 的所有ss可能位试等

find(s,ss){for(i in 0~n-m)for(j in 0~m){if(s[i+j]!=ssj)break if(j==m)yes} ;no}

要懂KMP，先听前缀树Trie的故事。若需搜索多个子串，strstr只能1次找1个，它只能比对一个ss，但针对相同前缀字符(好比嵌套文件夹 逐步深入) 可以组嵌套{}避免从0再试。

Trie=(t0,kv)=>{let t,k,K,v; for([k,v]of kv){t=t0;for(K of k){if(!t[K])t[K]={} ;t=t[K]} t['\0']=v } }
Trie(t0={}, "bin ban bun bah".split(' ').map((k,i)=>[k,"兵班崩巴"[i] ] ))

注意t0嵌套结构。可写批量替换 rep=s=>buildStr(ad=>{let t=t0,K,v; for(K of s){t=t[K];if(!t)t=t0,ad(K); if(v=t['\0'])ad(v),t=t0 }})
buildStr=f=>{let s='';f(c=>s+=c);return s}
于是可 rep("bahbunbinban")

也可玩个花的：将嵌套字典编号为状态转移表；行=状态号 列=字符-新态 组

cell=[], nb=t=>{let d=[],k;
if(k=t['\0'])return k; for(k in t)d.push(k,nb(t[k])) ;return cell.push(d)-1}

OI常用这个cell，n行列=最长字串长,ASCII符集长
也可以把'\0'压缩掉，只有创路遇t属值时t={['\0']:t,}再继续走，我之前一个放弃的web字典就这；当然我现在用后缀树了。C++无值序时hash表(std::unord_map)更好

但我们没想过性能。若找"abc" 而 t0=abd bcd ，c!=d 时t=t0 ，再从t="a.."开始缩小集合，可b不会有第二次，对"abcd" 则bcd也无法匹配了。当然可 for-of 变i++，每t=t0 记位置，若失配跳回'a'后1字，"bcd"能见

你肯定稀奇，编程的if 为啥没有“无匹配”的问题——if 总有else或同{}后随项。 只要给"a.."等所有节点加else分支，它就知道失配回退哪，"abd"里b回退到从t0 走同前缀的"bcd"子树,a回t0,.. 。这其实和rep() 是一个流程，它叫AC自动机。

KMP是AC的简版。"cadcab" 对前后缀里重复串设置正确的fail指针，"cadca" 的ca是在t0可达的前缀，故失配移到dc.. 重试

未完待续，(注意我也在理解 NFA DFA 这些，虽说我能讲些基础的，却知道不多)

aho-corasick algorithm 应该就是AC（有 fail 回路的 Trie 匹配）

大概就是 e[s[i++]||key.next()]._empty= 同前缀的e’ 这样 ，例如 abc:1, bd:2 的子串匹配 "abd" 时，会往回走1次

#security 回顾 regreSSHion: RCE in OpenSSH server<9.8
https://www.bilibili.com/video/BV11U411U78q
这一漏洞的描述听起来像是 WannaCry(SMB) 和 Log4Shell 级别的。实际上，该漏洞的利用不太可能。
2014年，OpenSSL加密库中的一个缓冲区溢出漏洞被公开。该缺陷被称为“心脏出血”，这次是它的回归

由glibc free() 数据竞争，导致heap链表 use-after-free 而使得glibc __free_hook 指向黑客在待连接的120s(异步 sigalarm)分配的地址
要利用这一漏洞，攻击者平均需要在没有firewall,fail2ban和Nx的 x86 ASLR 上进行约 10,000 次尝试，每台服务器需要 6 到 8 小时。

漏洞利用需要精心构造的heap链表布局，并发登录ssh以尝试fake key-exchange
https://www.offsec.com/blog/regresshion-exploit-cve-2024-6387/

管理员可以将登录超时设置为零（在 etc/sshd_config 中设置 LoginGraceTime 0）
🤓☝️ https://www.qualys.com/2024/07/01/cve-2024-6387/regresshion.txt

#learn
事实上： 只有基于更慢的ROP才能实现基于 heap 的RCE。默认设置下，该漏洞的利用根本是不可能的，x64缓冲区注入与SQL注入一样被 #linux 等内核修正了，对它的研究可以理解为另一种 #OI ，并不能对线上系统产生威胁
地址空间布局随机化 (ASLR)使注入代码的攻击在64位平台上变得几乎不可能成功，因为所有函数的内存地址都是随机的。
在32位系统中，ASLR能够提供部分防护，因为只有16位地址可供用于随机化，这可以用暴力攻击在很少的几分钟内破解。 这也是为何所有PoC都是针对x86

实现今天唯一可用的ROP（2010 年Adobe Reader被曝出了一个严重的漏洞，攻击者可以通过伪造恶意的 PDF RCE），需要在C语言的缓冲区溢出上，达成这三件事情:
找到system函数地址
找到字符串“/bin/sh”地址。
system函数参数应该放在栈的什么位置，并且不能被canary发现栈已经溢出。

#dalao #blog https://mudongliang.github.io/

#English #OI #tool #dalao https://www.peterjxl.com/yingyutu/grammar/preposition/#前言

堪比 菜鸟教程