置顶太多文太难受了。于是就有了这个。
算法文：
[连载中] [18/12/19] 今天一天尽享多项式！Í dag er「多项式」æfa! 今日は一日「多项式」三昧！
[连载中] [18/11/06] 随便搞搞 ICG ( 公平组合游戏 ) 和其余的博弈
[18/09/28] 如何使用「构造函数法」去做Möbius反演
[18/07/03] 弦图,区间图,完美消除,MCS,TreeDecp,PQTree及其他
想法：
[18/05/03] reStructuredText – 一个轻量级的标记语言
[18/03/16] 提高调试效率 – GNAQ 的变量命名风格
[17/08/14] Tarjan – 求解有向图的强连通分量 (SCC)
[已弃坑] [17/08/14] A Set of Good Problems
成套题解：
本文是我在 10 月份期间开始的对一些见过或者想要学习的博弈模型的一个总结计划。本文篇幅较长，覆盖多种模型，以下是一份可以帮助阅读、理清主干的主题清单：
(待填充)
请注意本文分多页，可以在文末翻页
文章中数学证明、公式较多，请做好阅读理解的准备。这篇文不是闹着玩的，读就请认真读它。先说一句比较自以为是的话：
读这篇文学习博弈论的过程，并不是去背公式或者记性质，而是去熟悉并掌握处理博弈问题的一般思维方式。
Wythoff Game – 第 1 页
Nim Game – 第 2 页
从 Nim Game 到其他组合游戏 || 归纳与推广、泛化模型 – 第 3 页
SG 函数的构造 || 更进一步的推广 – 第 4 页
Anti-Nim 与 Anti-SG – 第 5 页
Multi-SG || Every-SG – 第 6 页
翻硬币游戏 || NimK || 扩展 NimK – 第 7 页
树上删边游戏 || 无向图的删边游戏 – 第 8 页
扩展阅读列表 – 第 页
对于集合，用 \mathbb{A} 的字体表示。
对于局面，用 \mathbf{a} 的字体或 \mathrm{S},\mathrm{T} 来表示。
\text{s.t.} → “ 使得 ” ， such that subject to 的缩写。
\forall \exists 分别为 “ 任意 ” 和 “ 存在 ” 的意思（数学量词）。
\oplus → 代表 xor ( 按位异或 ) 运算。
DAG → 有向无环图。
ICG → 公平组合游戏。
SG → Sprague-Grundy 函数
经典的 Wythoff 博弈模型。
这个模型的描述是这样的：地上有两堆石子，其中一堆有 m 个石子，另外一堆有 n 个石子。两名玩家轮流取走石子，规定每次要么从其中一堆石子中取走任意多个石子，要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了，谁就输了。也就是说，取到最后一个石子的玩家获胜。
这玩意其实还可以描述为：
把国际象棋棋子皇后放在棋盘上，两人遵循棋子的走法，轮流移动棋子，但只能将棋子往左方、下方或者左下方移动。谁先将棋子移动到棋盘的最左下角，谁就获胜。
我们知道博弈的关键就是局面，那么我们考虑用一个数学模型去描述局面好了。我们把局面记作一个无序二元组 (n,m) 。
我们先给出结论：所有先手必败的数对（我们称为奇异局面）分别是：
(1, 2), (3, 5), (4, 7), (6, 10), (8, 13)
更严格地来说，其实是：
\mathbb{S} = \{(\lfloor 1 \cdot \varphi \rfloor , \lfloor 1 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 2 \cdot \varphi \rfloor , \lfloor 2 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 3 \cdot \varphi \rfloor , \lfloor 3 \cdot \varphi^2 \rfloor ) \,,\, ( \lfloor 4 \cdot \varphi \rfloor , \lfloor 4 \cdot \varphi^2 \rfloor ) \}
其中的 \varphi 是 \frac{ \sqrt{5}+1 }{2}
关于这个结论最科学的推法（而不是什么打表找规律），这里有我整理的一份文档，可以读一读 : Wythoff Game
这里我们尝试证明这些状态的三个性质，从而证明这个构造是先手必败的(设状态为 \forall A \in \mathbb{S} ) :
这样我们的博弈策略是后手始终把当前状态转移到 \mathbb{S} 中的状态，从而可以胜利。
对于上面三条性质的证明，可以在这里找到。我有空再仔细补坑。
一切还要从 MS 在 2019 年发布了 Windows Terminal 这种东西，一举解决了伟大的 Windows 居然没有一个像样的官方终端之问题说起。当然，这个 MS 不是别人，正是微软。
当然，这个被吹上天的 Windows Terminal 最好是再配个 Powershell Core 一起食用，非常爽。
但是震惊G子一整年的是这个东西的配置文件居然是纯文本的 JSON。
好吧，也算不上震惊。最后G子跟着这篇教程配置了一气 Powerline，还顺手开了亚克力效果。反正最后，它就长上边儿那样。
哦，忘了提一句，包括上段的教程链接和后边的引用，内容都是英文的。不过 MS 的英语 《也就那水平》，读起来压力不大。
P.S. 这篇教程其实挺邪道的。毕竟是两个世界的玄学组合，G子也不知道它能不能长久有效。
Windows Terminal 这玩意太长了，用 WT 缩写代替算了。
首先去 Vim 官网搞个 Vim。G子嫌附赠的 gVim 太丑了，干脆就弃了。而且 gVim 这玩意本来就不在命令行上，一点不顺手。
用 Powershell 调 Vim 挺简单的。其实加个环境变量也……行
但还可以这么玩：
notepad $PROFILE
然后里边儿添一行：
set-alias vim "D:\Program Files\Vim\vim82\vim.exe"
当然G子是把 Vim 丢这个地方了，这个路径就看着改一下。
哦，顺便提一句，这个 $PROFILE 文件的位置其实就在 $USRDIR\Documents\PowerShell 里边儿，其实也可以开着 Explorer 一路翻过去。
然后试试，应该就能调起 Vim 来。
G子给 WT 配了 Powerline（就上面说过的那个），所以有 Cascadia Code 这字体。它至少是等宽的，还专门为代码设计，还有连字符（对，WT 甚至支持连字符），就很爽。
虽然G子平常是习惯用 Fira Code 的，但是那玩意和 Powershell 的 Paradox 主题（也是 Powerline 教程里的）兼容不好，最后还是算了。
然后你可以试试给 Vim 换配色方案，比如上个G子最爱的 Dracula。点左边这个链接就有步骤说明。
哦，顺便一提，Windows 下那个文件夹不叫 .vim，叫 vimfiles，不过也在 $USRDIR 下面。G子觉得你该知道 $USRDIR 是啥，不知道的话去搜下也不麻烦。
接着说，装完了之后开一下 gVim，就会发现起效了。但是 WT 里的 Vim 显示还是照旧。但这为啥呢。G子搞了一个小时还是没搞明白，最后去问 C10s。
C10s 说可能是 Powershell / WT 没有良好的声明自己的 terminfo，结果 Vim 认为它俩不支持 24-bit 真彩色显示。和这个问题很类似。
那没关系，去看看 Vim 怎么强制 24bit 彩色就行了。其实就是 _vimrc 里边加上一行：
set t_Co=256
然后你就会发现 Vim 显示的非常诡异，就像这样：
那咋办。查了下资料发现也有人遇上这个问题。
解决方法就还是在 _vimrc 里边加一句：
set t_ut=""
就可以了。这条的意思大概是强制 Vim 重绘终端的所有区域。
C10s 最后评价说也是 terminfo 的锅。MS，不愧是你。
无论如何，最后G子就有了一个 Vim Dracula 主题 + WT 亚克力透明效果都正常显示的漂亮玩意了。挺好。
G子假设你也配好了上边儿教程的 Powerline，或者至少开了个亚克力吧。毕竟这玩意挺好看，毛玻璃透明效果，有种朦胧美。
说是缺陷，其实大概是这样一回事。G子注意到他开了 WT 的亚克力效果之后，敲命令的时候遇到类似 -h --help 之类的选项，那些选项的代码会被高亮成一种 “也不灰也不白，总之十分晃眼还和亚克力背景全部糅杂在一起根本看不清” 的颜色。大概就这样。
后来G子去翻 MS 的文档。发现 WT 是有 colorScheme 也就是颜色主题这一说的。当然，它的颜色主题和 Powershell Core 的是分开的，别给弄混了。
所以G子突发奇想打算魔改一下配色，这样就能把那个诡异的高亮颜色修正过来，不然每次G子试图认出自己打了什么命令参数，都和瞎了眼一样。
原理大概是这样：魔改一套 WT 自带的配色（它自带了好几套），然后小修一下配色。
在这个地方是有告诉你怎么搞到 WT 内置配色的。去扒一份然后小改一下就行。
G子大概改成了这样：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
// Add custom color schemes to this array. // To learn more about color schemes, visit https://aka.ms/terminal-color-schemes "schemes": [ { "name": "One Half Dark GNAQ", "foreground": "#DCDFE4", "cursorColor": "#FFFFFF", "black": "#282C34", "red": "#E06C75", "green": "#98C379", "yellow": "#E5C07B", "blue": "#208FE9", "purple": "#C678DD", "cyan": "#56B6C2", "white": "#DCDFE4", "brightBlack": "#5BDFE6", "brightRed": "#E06C75", "brightGreen": "#98C379", "brightYellow": "#E5C07B", "brightBlue": "#61AFEF", "brightPurple": "#C678DD", "brightCyan": "#56B6C2", "brightWhite": "#DCDFE4" } ], |
哦，顺便G子还注意到一个事实，就是那个阅读障碍一般的配色，其名字居然还是 brightBlack……好家伙，MS，没人比你更会起名。G子也想知道你有什么本事，把这个灰不灰白不白的配色叫成是亮黑。
记得在 Powershell Core 7 （或者别的啥）的配置里加上 colorScheme。具体也可以去看上边那个 MS 的说明书。
这个小站也逐渐地没有人来了……
也许以后，它就是我一个人偷偷看的地方了。一想到这点，就有点丧失动力了，不知道该不该逼着自己写下去。
自己觉得，在写这种回忆性的文字的时候，脑子里的思维总是交织得过于复杂，导致产出了一些晦涩难读的东西。但是看了 KS 的 2020 年末总结（在这里）和 Mly 的《Broken 开发日志》（在这里）之后，还是想写一些记录性的文字。虽然，根本就没人会看。
也许最后会演化成我分享给学弟学妹/后辈，逼着他们（可能不怎么情愿地）看这个东西吧，哈哈。
年初，工大接到通知，要求 1 月 10 号必须放假。听到消息的时候，顿时感觉一切都乱了阵脚。匆匆忙忙地备考，匆匆忙忙地收拾。
考试前的一个周都没有什么课，于是就晚睡晚起，上午十点多或者中午吃过饭就去 ICPC 的活动室里看高数笔记，然后做点往年的题。活动室是屡次试图寻找集训场所，未果之后（大家都好能卷！）向学校申请得到的地方。目前还是只有我们队有钥匙。
仍然记得我那本《历年习题集》是从学长手里拿的二手，有不少印刷错误，有一个地方让我和两个朋友讨论了整晚，才发现是印刷有误。花了好长时间才消气。
高数也考完了，英语也考完了。剩下一门线代，闲在宿舍无聊，复习之余拉了几个好友建了一个退役 OIer 音游屋&睡觉社，主要是聊 Arcaea。这个点子的起源，还是之前和 Pb 在 OI 群里提了一嘴，没有 OIer 聊音游的地方啊。后来也知道 Menci 最近在打 Arcaea，就一起拉过来了。
至于睡觉社，纯粹是我的恶趣味。好几次和朋友口嗨，说一定要组织一个这样的社团，主要活动就是品质睡眠。于是乎就夹杂了一些私心。
起初群里挺冷清的。作为之前从来没有组织过这种群的傻傻，建群之后的一整下午都在慌张，生怕爆冷之后让我颜面尽失。第一次体验到那种生怕自己不够格的、提心吊胆的心情。
在几个 OI 群里宣群，反响也不大。还去私发给了所有我认识的、打音游的 OI/ACM 朋友。到最后，那天也就八九个人，聊天记录也就三四十条。其中一多半还都是我发的。
出乎我意料的是，之前和我不太熟悉的 Snakes 和 Menci 都爽快的来了。其实都是比较生冷的面孔。Menci 刚打阿珂娅不久，还问了很多平常会有的问题。还要感谢 Menci 把好多人拉入群，不然也没有以后的发展。
更尴尬的是，其实原本就有一个 OIer osu! 群的，而且存在时间也不短了，但我建群之后才发现有它。第一次去尝试组织这种兴趣群，态度也还是超级认真的，于是感觉压力不小。
又过两天，线代也考完了。一个多小时之后就耍帅交卷，走出考场还觉得自己能拿个满分。（结果后来还真的拿了满分）回想起期中考线代排在最后一个梯队的挫败感，觉得还是挺奇妙的体验。
于是就准备归宅。最后望着半空的箱子，一狠心一咬牙把 fufu 塞了进去。这小家伙，用手拿着确实挺尴尬的。
回家的前一晚整晚没睡。前半夜在打游戏，后半夜在收拾东西。早四点钟出了公寓楼大门，汽车、飞机、汽车……久经颠簸，十小时后才回到家里的床上。
有言曰，床就是我的老婆，而且可以多次享受，尽快享受。回到家终于有了大软床可以睡，还有荞麦皮枕头。真是至福。
寒假之前喜欢上了焦茶的插画。把电脑和手机的各种背景都换成了焦茶的画。当然，除了陪我好久的樱花任务桌面壁纸。
回家之后休息了四天，在家整天开游戏，中午出去买个华莱士。说到华莱士，还是刚归宅的前两天，骑着小车在外面转的时候发现的。从小区出门东行八百米，就是店面。里面东西都很廉价，不愧是贫民汉堡铺。可能是我离家之后新开的吧，之前是没有的。
从离校的时候开始，萌铁总和我商量要不要去武汉，或者去青岛之类的地方见一面。我一直在考虑，最后也没考虑出个什么。
然后被我妈催去练车。暑假的时候驾照考了一半，就猜得到寒假还得继续。于是每天六点钟起个大早，去城西郊的工业区驾校开小车车。也说不上是无趣还是有趣，大概就是在随便地应付。
练了不到一周车，考过了科目三。然后去约了年前的科目四。感觉也不是那么困难，一遍就满分过考了。开车还是要头脑冷静，然后就是熟悉各个部件的用途。别的反倒不那么重要了。
音游屋也逐渐活跃了起来，每天都有几百条消息。我逐渐也放心了。多亏了 Menci 和 fpd，群没有完蛋。大概自己也是经验者了吧，嘿嘿。
某天在知乎上闲逛，却发现了焦茶离世的新闻……天哪……
唉。心情复杂。这么有才华的年轻的画家，却这样就离去了，很不舍。想起 re: New Memory 是焦茶和 beignet 约的最后一稿，就去听了。一曲一曲放过去，还在想，这三个人的小团队也结束了。不知道以后 beignet 还会不会发歌。唉。
在家中午没人。实际上整个白天都没人，于是被逼无奈尝试做饭。第一次试了鸡蛋蘑菇汤，还留下了一些汤煮了点面条。意外的不怎么难吃。
然后就是炒芹菜、西红柿炖土豆、烤土豆片、烤披萨……逐渐放肆。做法有时候问我妈，有时候搜个食谱。感觉各种调味料掌握起来还是比较容易的，也许是从初中开始跟着我妈观摩的原因？谁知道呢。
最后甚至还尝试了烤土豆鸡翅，做意大利面（都是从原料开始）！土豆削皮切片，鸡翅腌好，煮出意大利面酱和面……
在 11 月的时候，萌铁给我介绍了一个叫 The Missing Semester 的课程。不过接连由于 ICPC、救援可橙、临近期末，一直没有时间去看。
寒假前几天在家是真的无事可做。在中学的时候还好，假期既短，也有繁重的作业，总之是忙中偷闲。但大学的第一个长假，却感觉是闲到原地长毛。抱着无所事事的心态，就去看了那套课程。
Missing Semester 是有在线讲义和课程视频两部分的。干读讲义太憋屈了，就在 Youtube 上看视频。
看了两讲就发现课程质量非常棒。不知道是哪里的神经元产生了一串电流，驱使着我去搜索了这套课程在国内有没有中文翻译。让我挺惊讶的是它却真的没有翻译。于是，我便产生了一个大胆的想法：
这么想的那一刻，我真的没有意识到我对翻译、对视频制作一窍不通。只是一时兴起。但是说干就干，两天之后，这个 Github 仓库就有了第一个 commit：
问了 zjr 和 Castor 来不来，两个人都爽快地答应来做翻译。三个人的小项目就开始了。开始的三天热情地每天都翻译好久。也慢慢找到了翻译的感觉。
和萌铁商量了许久，决定 21 号去潍坊见个面玩一玩。
20 号考完了科目三。21 号起了个大早，收拾齐全了书包，十一点钟坐上了到潍坊的 BRT。在路上和萌铁开了网易的一起听歌，听了超级多 V 家的曲子。到了之后在附近找到了一个麦当劳，坐到 1 点钟。
然后萌铁来了。和印象中，上次见面的时候变化不大。骑着共享单车陪她一起去医院做了个核酸，然后商量着去哪里。
结果还是无处可去，我本身也好久没来过潍坊了。无可奈何选了小时候常去的银座商城逛，骑着单车去，结果却发现银座和小时候印象里繁华的大购物中心一点都不一样，老旧的楼显得破烂而不景气。进去瞅了一眼，也没什么人，只好逃走。
然后萌铁提议去万达，那就去万达吧。万达也没什么特别的地方。四处走了一圈，最后还是去了超市买了点零食，然后去一楼的星巴克坐着休息。
之后回酒店叫了炸鸡外卖，玩电脑。和萌铁聊了不少大学和生活方面的事情，也聊了不少技术。偶尔提到可橙，还是叹口气。
晚上回去的时候起了浓雾。好心的司机冒险在能见度 30 米的雾里长途把我送回家。真的很感谢这么义气的司机师傅。
晚上在路上和学妹联络。学妹之前出了事故，我和萌铁原本以为她还在潍坊住院，就想去探望一下。没想到晚上八点多联络说回去了。
迅速商定好了碰面的计划，萌铁纠结之后也决定第二天打车过来。还是学妹的身体健康重要。
第二天也起了个大早，先去东边和萌铁碰头，然后骑着公共自行车去约好的一中北门。
漫长的等待。
可惜等了一个多小时也没等到学妹，也处于失联的状态，只好和萌铁在华莱士吃了午饭，然后送她回去。
晚些时候，学妹才发来消息，说她母亲最后因为疫情的理由不允许她出门。于是，就这样结束了。
话说回寒假伊始。
高中同学雨婷姐来找我问要不要合作。雨婷姐手里拿的是一个中国人民公安大学的校内创新赛项目，允许跨校组队，内容大概是创新信息科技+公安的融合。雨婷姐说可以共享奖金（虽然我并不怎么感兴趣奖金），还给我发来了其他人的立项选题。有数据挖掘，区块链，还有人工智能和计算机视觉类的创新项目。虽然显然大部分都是调轮子的工程类项目。
犹豫了许久，答应做技术+算法援助，有时间还帮写点代码。雨婷姐说内容大概是区块链+信息加密共享，当晚我就去找区块链和比特币原理介绍，区块链核心算法的书看。当然，到春节也没看多少，而且只是显浅的了解了大面上的构造。
考完科目四，回家的路上，和雨婷姐商讨了一个多小时，定下了大概的区块链信息交易系统和协议的设计方案。当然，这么夸张的项目，其实并不需要做个成品出来，只需要提交类似论文的东西就可以了。当然，这种论文，或者更像是报告，写起来也是比较复杂的。可能还需要嵌入大段代码描述算法。我说我年前时间不多，年后可能会帮忙看一下，写点算法代码。这种思维性的创新倒也省去工程开发了，反正和能力不足的我没啥关系。
主观来说，我年后的时间也并不多；客观来说，年关之后，雨婷姐可能就不知不觉去忙了别的项目，或者玩嗨了，总之没有联系我。但是她还是很强的，思考思维的能力给我留下了很深刻的印象。而且作为一个非计算机系、非理科院校的学生，敢于自己主动学习 Python、网络爬虫和 Anaconda 之类的技术，真的十分钦佩。
说回 Missing Semester，后来又拉了萌铁入组，做压制的工作。萌铁拿 Python 撸了一套工具链，大致是用无界面浏览器渲染字幕文本，和图片拼合之后生成视频。萌铁写码产出速度超快，还兼顾多线程高性能，把我都吓到了，真的好厉害。
我们给翻译出的文本加了代码高亮、译者注释，做了一些修正，还有一些很灵性的翻译（比如 Castor 的「啊，翻车了！」）。玩的挺开心。
拉了书屋群的 A179 和我一起打轴。我自己一个人兼任翻译、润色校对和时间轴，忙的团团转。后来又拉来了 kernel_bin 做技术校对。细心的 kb 总是和我讨论几个字的措辞问题讨论很久，纠结表达的准确与否。kb 比我还上心，遣词造句也非常给力，计划没有流产，也真的很感激他。
1 月 29 号压好了第一讲，万能的萌铁帮我搞定了 bili 注册账号的手机号。现在想起来，高中毕业以后好多问题，都多亏了她帮忙。有这样的朋友还是很幸福的，哼哼。
于是创了字幕组官号，做了封面，发了视频。到处宣传了一气。大概等了十天，播放和关注都还不错，略开心。
之后的几天，拉了不少人入组，基本都是做翻译。起初有几位的质量比较一般，我就更忙了，一边翻译，一遍全文校对文本，再加上临近年关，大家都在过年，各种不便无法提供帮助。其实我也理解，不过，留给我的活就变多了。还好后来 train 答应来打轴，我就彻底从时间轴上解脱出来了。179 和 train 打轴质量都特别高，是没有我的用武之地的。大年初二开始连着忙了三天，终于搞定了第二讲的大部分工作，开始收尾了。
大家都很积极地来帮助我，还是我点明没有回报的情况下，真的好感动。于是年前的某一天，晚上在翻译组群聊天的时候，突然想自费订一批纪念品送给大家。讨论了要制作什么纪念品。决定了书签、钥匙扣、鼠标垫和贴纸。其实本初的想法是胸针，不过好像这个东西也不会有人去别，就放弃了。
初二的时候设计好了书签、鼠标垫和钥匙扣。钥匙扣的前两个设计都怪怪的，发给群里的成员看的时候，也多亏了他们看在我努力设计的面子上，没有把话说得太难听。不过我自己也不满意，纠结了好久才突然产生了灵感。感觉对我来说，最后的成品还是比较合格的。之后又做了几版贴纸，打算一起邮给大家。
怎么说呢，感觉做项目本身，或者说创作的这个过程，其实就是很有趣的。不知不觉我就喜欢上了这样忙碌的过程，看到所有翻译校对工作完成的时候、设计纪念品稿子的时候，都特别开心。看到作品从空白到完整，和一起努力的同伴互动，真的很有趣。
忙且快乐着。我觉得对于每一个心里热爱创作的创作者来说，无论是写作、制作游戏、拍视频还是做翻译，可能都是这样的感受吧。至于创作出的作品，反倒不那么重要了。当然咯，如果作品能让观众察觉到我们的用心，那就是再好不过的事情了。
虽然还是挺闲，但寒假大部分时间，要么在凳子上，要么在床上，确实没怎么运动还变胖了，也比较痛苦。看着 dkw 瘦了，又很高兴。又痛苦又高兴，真去他妈的。体重管理，永远是一门玄学。
寒假照样也是哨戒班训练的大好时机。队名是明日夜空哨戒班，因为打 ACM-ICPC 的队伍里，加上我居然有两个橙厨，就挑橙曲曲名当队名吧！
还是由于各种计划变动，全竞赛队的短时留校集训的计划也泡汤了，只好各回各家。刚回家一个周不到，哨戒班开了一场比赛。大概挑了 ICPC19 上海，战果还不错，估计是 Au 的排名情况。
后面二十来号又开了 ICPC20 济南，我和 lo 两人作战，切掉七题，也顺利拿到 Au。
不过后来临近年关，翻译组和各种别的项目逐渐忙了起来，就一直没找队友开比赛。虽然有在认真学习，但是一声不吭确实也还是倍感惭愧。
总觉得对不起他们，实际上，也确实对不起他们。lo 为了拿奖，每天都拼命刷各种各样算法和题目，整个寒假的进步速度比我高二的时候还要可怕，总觉得，比逃避思维训练的我要高尚多了。从各种程度上来说，还是我对不起队友。以后，我得再努力一些才行。
工大许久之前就有「大一年度项目」这种事物存在了。今年，秋季学期半中间，「鸽病防治指南群」成立了。成员是我、ACM 的两位队友和项目组组长 Xeonacid，也是队友的高中同校。讨论好了选题是一个瞳孔定位和模糊匹配的类身份验证项目，还要做出实际能用的软件。C++、OpenCV、Qt 的架构设计，Linux 平台开发。X 神开发经验丰富，还维护 OI-Wiki，总觉得是他在带我们三个走向辉煌。当然，那可不是辉煌，是我蹭功劳划水的羞愧。
所以为了不成为罪人，还是拿出了旧笔记本，装好了 Ubuntu 开始配环境。本身我对 Linux 不是特别熟悉，加上网络问题，遇上了特别多困难。折腾了三整天，最后凭着一股劲儿，总还是排平了。最后看到 demo 成功跑起来，还是舒了口气。
不过好好想一想，我除了建好了 repo 和配好了环境，春节之前也没有开始做任何实质性的事情。配环境的时候还一声不吭，因为是怕寒假的前三周半都没有主动在鸽病防治群提过一句「我也要努力贡献进度！」的话，现在猛然提起「我连环境都才刚开始配」，负罪感爆棚。
lo 也尝试配环境，但是不知道为什么 Windows 有些许 bug，我承诺了要帮他看，最后太忙也抛之脑后了。说要帮他搞定全流程，最后也没做。现在想起来，真的很对不起认真的 lo。
总之，X 神最后已经做出了能看的瞳孔定位后端，照着论文实现了算法。而那个时候，我还刚刚配好环境。心里的疙瘩越扭越大。总觉得我是放人鸽子的罪人，还一声不吭逃避追责。这种情况真的不该出现第二次了，要好好反思才行。
其实一直有一个回校宣讲的梦，至少从高一就有了，当时觉得学长们特别帅气。快离校的时候，还顺手拿了两册宣传册和两个工大宣传垫板，打算回去若是天赐良机，就给用上。
谁知道年前疫情再次恶化，学校全封闭管理，不仅进校宣讲不成，进校探望老师也照样不成。很无奈只能宅家赋闲。
年关之前，各色高中同学们还拉了一个大群用于宣讲。最后他们很无奈的开了腾讯会议。也好吧。
后来 PKU 的两位找到我，说要组织小规模回校，大概只有 PKU、HUST 和工大回校宣讲，也就四个人，可以去教室。爽啦！
问 zjr 要到了招办的 PPT。其实也没有人给我任务，但是发现高中的学校近七年来除我，没人来到工大，还是感觉义不容辞。
宣讲那天是好天气，下午大太阳，临时兴起骑车去找高中同学遛弯，到五点半就匆忙往学校赶，路上随手买了一个面包应付。其实人家超想吃饭的。。。
回校见到了久违的高三教室。不知道为什么，再看高中感觉也没有特殊的感触，也不觉很怀念。大概只是感觉，见到学弟学妹挺高兴的。连着讲了高三+高二的三个班，好累，不过确实挺有趣的一次体验，值了。
讲完就放学了，时间也刚刚好。出了校门居然碰上了高三放学经常一起走的四人组，我这是撞了什么大运。好有趣，和高三放学一模一样。最后在学校旁边超市买吃的，出来站着聊一会天，真的和高三的时候一样。
出乎意料的相遇，惊讶之余也稍微有点怀念。高三每晚放学确实是相对快乐的时候。特别是我开发了一条偏僻的回家路线，有几段没有照明，抬头就可以看见荒野上空的星星。
「昏暗荒茫的大地，星星点亮的夜空，安静凉爽的夜风和歌。」
骑车也特意挑了高三晚上会听的歌。完美复现了一次高三放学，回到家的时间也刚刚好。稍微有点感动….
我在哪里 今天又是星期几
不要放弃 一切都还来得及
平凡日子 一如既往在继续
突然掉入 来自命运的陷阱
临近年关，音游屋里还挺热闹的。
Snakes 窜出来发了一条消息。点开一看，居然是一个奇怪的问答。
欸嘿，第一次看见挺头大的。过了半下午再点进去，感觉还蛮有意思的嘛。
那就来吧！各种方式猜猜猜，还借助了一把搜索引擎的力量。反正最后傍晚六点钟解出来啦！还是蛮有意思的，还拿到了红包，嘿嘿嘿。
可能和蛇蛇对上电波的人不多，最后我还是个第二。也许是无厘头猜谜确实挺吓人的，谁知道呢。
还记得大一年度项目吗？就在安装 VSCode 和 Qt 的过程中，我彻底体会到了移动网络感人的网络质量。看来大内网+垃圾公网名不虚传，连接 Qt 的服务器速度只有 16kbps，还隔三五分钟断连。
彻底受不住了，向家长提议换联通宽带。结果本地的联通没有月租宽带，包年的又因为在我走了之后浪费为由，总之放弃了。
当时恨手上没有钱恨得牙痒痒。一分钱难倒英雄好汉，也许吧。再加上很多身边退役的 OIer 收入也都很可观，也不可避免地受到些影响。
然后就去找工作做了。当时还傻傻地分不清「兼职」和「实习」的区别，还连简历都没有，面试也没接触过。当然咯，最后还是咬牙搞定了万难。具体的已经记下了，就看这里吧。
春节前群里突然通知要新增三个班次，就抢了大年初一晚的一班。初一晚就坐在老家昏暗破旧的电脑桌前敲机械键盘。积攒的问题特别多，从七点开始一直工作到十一点半，一直没有停下过。答疑、调试代码、编辑回答……前前后后敲了万字有余，答了至少三十个问题。
真的好累，回到自己家的床上，倒头就睡……虽然从小见到一万次「工作真的很辛苦」这种话，不过自己不体验一次，是感觉不到的。
大年初二这个尴尬的日期，因为我把班小群（不是通知群）屏蔽了，万万没想到学委会在班小群下通知。学校开了一门《思政实践课》，具体的内容大概是通过社会实践/调查走访/志愿服务的内容，体会主旋律精神和新时代精神。
和中译组各位成员玩得高兴的我，则全然没有意识到这个危机降临到了我头上。通知只给了两天的收集时间。而当导员再次在微信通知群提及这个事情的时候，已经在 DDL 之后又过去了两天。
更尴尬的是，我甚至没有意识到导员也在说这个事情，直到寝室群内一条消息，打破了安谧祥和的氛围。
妈呀，针扎屁股啦！！！这这这这这可怎么办啊，我还啥也不知道呢。
算了，破罐子破摔吧，别的事儿可多了，还更要紧，这边火还没烧眉毛，我就鸽着！
于是理所当然的鸽了三天。当然咯，这三天里每每都会想起这个事情，但是在短暂而无效的动力爆发之后，我照例还是继续鸽着……
日历又往后翻了一页。实在没有办法了，赶紧去各个地方把材料找齐，大致了解了一下课程流程和任务，也搞明白了要提交什么材料。赶忙儿在寝室群里把几个人忽悠出来，搞定了文件。
一看时间，0:00 AM……好尴尬。再拖一拖再给导员发吧。
又往后拖了一天，才去联系导员。导员之前因为这件事情，在群里发过一次火了。当然，怪他也不怪他。怪他是因为，真是的！哪有人会在大年初二下通知嘛！不怪他是因为……同学们提交材料真的都太应付了，我看了都蛮生气。
总之用了特别害怕的说辞，还是搞定了这个事情。提交之后，就计划过几天去联络我们当地的义工组织，看看能不能参加一次活动，完成我的任务。
有时候面对着键盘也不知道该敲什么，那基本就是反反复复在想各种不同的事情，所导致的后果。
说实话，我没有太搞清楚未来的方向。显然，大面上是有两个去处的：要么最后进入公司就职工作，要么成为各种科研实验室的一员。很可惜我哪一种都不甚了解，只是通过道听途说，有了些大概的印象。但另一方面我也很有幸能接触到有未来的明确方向的朋友。要么是同级生，要么是学长，希望科研、希望做技术的兼而有之。和他们交流给我的感受是，他们确实很热爱自己将来的方向。
虽然我觉得无论是做科研还是做技术都很有趣，但是相较而言，可能我更喜欢做技术吧。虽然是相较，但对这两者的兴趣其实也无太多差距。总而言之，才刚刚大一寒假，新生活的新起点，我对于未来是没有清晰的认知的，自然也会产生很多有偏差的观念；并且，也没有必要非要现在明白一切，那未免也太不自然。
但整个寒假带给我的另一个很明显的感受，就是「割裂感」。
这大概不是说我生活的割裂感，我觉得我的生活还算连续；但当我自寒假前夕，也即本文开头的时间段算起，到寒假近乎结束，也即本文结尾的时间段为止，观察了各种各样的人群，接触了他们，并且尝试和他们交流之后，这种割裂感便愈发明显。
在这段时间里，我主要接触的，该是寒假开始前，周围的大学同学们，寒假开头的重聚的高中同学和朋友，过年时的远房亲戚长辈，也就是那些「同乡的陌生人」，还有一直保持联络的，竞赛的朋友。
这所大学的特点还算鲜明。虽然上学期结课后除了体育，其他课程我都努力取得了 90 以上的高分，但是均分 93+ 在计算机大类里还是仅仅处于 130/470 的名次段。不过又据我的观察，平均分的分数段分布显然不是处于正态分布，而更像是——一个头部和屁股肿胀、上半身和腿细弱的人。一小半的同学，或许是焦虑驱动，或许是延续了高中思维，也或许只是当作了考研工厂、被成功学洗脑……在高强度的内卷。我不知道前十五名的情况，但我想，也许真的是用小数点后一位区分的吧。
而另一部分人，则终日游戏，多门挂科，看起来丝毫没有方向。也许是保留着一些稚气，也许只是逃避，也许还没有对社会和环境形成足够明晰的认识……他们倒像是和上半场那些，血拼的你死我活的家伙没生活在一个世界。
但我看去我的同学，那些我可能略知一二的人们，我又不止一次回想起某天的专业吹风讲座，还有那天那些尴尬的沉默。有时候我恨我喜欢上这样一个「热门专业」。我看向很多人，不禁去想，他们到底是为了什么来到这里……是为了未来能赚到的钱？为了顺应「父母的」高考志愿，解决就业结婚生子，过父母安排好的成功生活？还是因为电脑特别好玩，所以计算机专业看起来「有那么一点意思」，还听说专业前景好？还是只是没有梦想的从众者？也许都有。
我看到很多典型的、信息封闭式的高中走出来的同学，向新生活表达了自己的不习惯。
也许是我不该责怪他们。毕竟，无论如何计算，我在本专业的学习时间可远远不止一年，上大学继续选择计算机是理所当然，了解自己的未来，拥有自己的梦想也是水到渠成的步骤。也许大多数人，在这个时间点，都没有机会摆脱专业上信息渠道，思维方式和知识面的迷茫。
我慢慢相信大多数人是无谓专业的，只是普通的生活罢了。偶尔燃起一些热爱，但被形形色色的事情盖住了。
这些观察和交往，还是慢慢体现出巨大的割裂感。信息的不对等，观念的不同，一个喜欢此专业的人，和很多不喜欢此专业的人。我想，我还是得慢慢去适应。大多数人也不是全部人，总有些说得来话的朋友。
回家之后和高中同学反倒更加无话可谈。大家的生活完全都不一样——何必呢。互相讲讲段子，聊聊梗，吹捧一下北大的大佬，也就如此吧。
感觉这种割裂感，像是我违背了某种影视剧小说中拼命塑造出来的，高中同学相聚泪眼婆娑的潜规则。
但真的，就算不聊学术，聊生活也好，我的爱好又那么「偏」——何必呢。只好就此打住。
我甚至记得初三走亲的时候，某个远方亲戚关切地来问我哈尔滨工业大学是不是东北挺好的专科学校。我只能说「是个本科。」另外一次，社区的疫情防控志愿者向我确认「您说的是“哈工”大学吗？」
虽然这么说来，我只能在退役竞赛生，还有因为我的各种兴趣爱好结识的朋友周围，找到一点温暖。但我觉得我并没有在恋旧：很多纯竞赛话题的朋友现在也还是没有联系，常联系的是和我学习观念类似的朋友，我们都不想局限在算法竞赛里。所以慢慢觉得，面对这么严重的割裂感，自己还是有信心说「我站稳了！」的。
正月十五之前，联系到了当地义工的一位负责人，费了些周折总算是有了义工编号。雨天一反常态地起了个大早，六点多开始等了一上午活动报名消息。终于争取到了在下雨天的下午出门的机会。去了义工的办事处，借了义工服，去参加「爱心驿站」的挂牌签约活动。坐着小轿车满城转，和各个店主交流，然后往「爱心驿站」的挂牌背后涂玻璃胶，再把它们呼在墙上。还是蛮有趣的。
正月十五，元宵节。城市东边的桥上，和去年一样聚集了很多人。虽然是个大冷天，但还是专门去看了烟花。桥上接连不断的放了两个多小时的烟花，而我全程在用冻僵的双手按着手机相机拍照。虽然总感觉烟太多，但是最后采用了所谓「烟花」而不是「花火」的叫法，就是这样一回事吧。体验了一次动画片里那种烟花大会的感觉，也终于掰正了「烟花大会不就是站着看，好无聊」的臆想吧。
离开学没几天了，外面也慢慢暖和些了。总感觉大半个寒假都是在家坐板凳，最后几天实在坐不住了，还是出门骑车转转吧。外面景色还是挺好的，感觉春天快来了。偶尔也偷偷期待这座小城里熟悉的夏天，想想还是很喜欢的。
终于，到了回校的日子。坐上了飞机，又一次长途辗转。在飞机上睡啊睡，直到下降的时候也没醒过来，最后发现右耳朵耳膜被气压搞得怪难受，
走之前就有点讨厌开学了。来了学校，发现自己原来还是天马行空的理想型。
因为感觉这个假期，习惯了和关系很亲的朋友一起工作、玩闹，或者自己一个人去随便散心，来了学校的第一天，便很自然地没有往这方面去想。虽然到了学校已经是晚上了，所以除了室友我也没有和其它的人说过一句话。但我总又感觉除了室友之外，若我拿出我的纯粹感性的感受，在观察上来说，其他的人却都感觉那么冷漠。
从我的感性观察上来说，遇到不少同学的举止都让我觉得，他已经是那种“阴暗的大人”了。可能在我看不到的一面上，自己活得不累也不快乐，还麻木地去凶别人，虽然知道这样不好，但也没什么理由去改变，「大家都是这样的」。我不喜欢这种人。
而且，果然我还是讨厌这种集体氛围的，可讨厌了。也许就是这个寒假我在人际交往上活得太「舒服」了，但我又不觉得这么舒服是错的。
还能怎么办呢，慢慢去适应好了，适应不了的，就躲开咯。
慢慢加油吧。
嫌だ嫌だ嫌だ嫌だ
讨厌 讨厌 讨厌 讨厌
僕は世界を愛したい
我想要爱上这个世界
嫌だ嫌だ嫌だ
不要 不要 不要
僕は世界から愛されたい
我想要索求这世界的爱
嫌だ嫌だ嫌だ嫌だ
不要 不要 不要 不要
優しい大人なんていなかった
温柔的大人已经不存在了吧
心が死んでいく音がする
心灵已死 音色犹存
寒假因为各种原因也比较闲……（个头）……再加上各种破事，总让我觉得有点自由储蓄是比较好的。
当然这是主要原因……而且一来二去的感觉身边的人都在恰钱。dkw 和 zzh 在本地上课，萌铁直接去做运维了还有月稳定收入。
总觉得有点意难平。。
可能我这个人就这回事吧，这方面意外的要强。也许还不是单纯的要强，是要强和自暴自弃的量子叠加态……
总感觉有时候会有奇妙的自卑心理，也有时候会觉得自己也该行动了。
前周去潍坊和萌铁玩，也谈到了少儿编程的事情。
很多原因加起来，前几天下午闲的长毛，就去搜什么少儿编程实习讲师之类的。
然后顺藤摸瓜就发现计蒜客在招……就去打了个招呼，没想到 HR 意外地很快就回复了。
唔。 😕 。很怪。HR 当时马上要了简历但我承认我当时连简历都没有做。
赶紧知乎搜索简历，打开 VSCode 照着样儿写了个 markdown，导出 HTML 浏览器打印到 pdf 一气呵成。再附上获奖证明，半小时搞定。
然后就通知面试。第二天上午起了个大早，十点出头坐在桌儿前就一直等，等到十点半然后就开始面。
常规流程啊，自我介绍然后做题。。问了几个题，感觉状态异常的好，就凑巧都答对了。
然后又面了一会就说等通知吧，HR 第二天通知。
后来第二天又没给通知，下午三点让我晚上七点钟二面。。行吧，边回老家吃小年夜饺子，边开个电脑二面。
二面就比较划（水），随便搞搞就 OK 了。
然后今天上午十点出头，HR 微信发我，讲说下午发来就职文件，填一下就 OK 了。
面试官也是教学管理一线人员啥的……去问了一波待遇……感觉还可以。
估计 HR 明天上班了会交代一下怎么干活吧……
感觉蒜厂实习考核流程也蛮正规的，感觉增加了许多见识。。
还是要努力啊。。
exgcd 部分
世界其实挺魔幻的。
这几年每每会兴致大发，就会回想起接触国外音乐（那大概是小学六年级）以来流媒体发展的魔幻现实。我的印象中各大平台互撕版权已经足有五六年了。网易当初是靠丰富的欧美/日韩流行音乐+小众流派资源+社区模式成型的；后来这套模式被各方学去了。直到（我印象中）大概 17 年的时候，各家的流媒体音乐模式都基本成型了。（除了网易还在作死建设社交功能，结果后来很失败给砍掉了很多东西） 然后就开始转向拿版权吸引用户的这种奇怪的竞争模式。直到今天网易还是没有杰伦和五月天；不过暂且不谈这个。
网易一大好处是当初的时候音乐资源就有很多靠用户贡献的成分（直到今天也有），这就给海盗党带来了绝佳的机会。各种小众的专辑直接盗传+开放下载，讲实话人人都想就这么薅点羊毛。但是后期网易云版权化之后事情变得更加魔幻：
这样的情况其实很多。比如 MONO 只有一张新专的版权网易没拿到版权，灰了一张挺尴尬的。
所以在 18 年左右我就开始想办法自己做主……毕竟还是有很多喜欢的音乐……偶尔还想当当海盗……（笑）
暂且不谈这些历史，进入正题：
在流媒体时代建构本地音乐体系
写在前面：
毕竟前一阵子 Darkmp3 也整个没了，这里我就不大谈特谈怎么当海盗了，虽然经验挺丰富的……（笑）
有些站其实不错，比如 2cycd，还有各类百度云搜索，还有各个音乐茶会啥的……（到此为止）
其实做了海盗也挺抱歉。不过就现实而言，[0] 最主要的是我的音乐消费能力很低（就是说我没钱）[1] 一部分专辑国内没法买到实体， BC 不开放，Amazon Music 很贵，代购太不现实 [2] 很多小众专辑甚至没地方买电子音乐，那我也没办法（摊手）
有条件还是会去 BC | Amazon | etc. 买的，咱也明白当艺术家有多难。
我们还是从歌荒谈起。我自己就经常歌荒。
要是你听华语，那华语方面挺简单，社交媒体上到处都是新消息，随便找新歌（各大视频站+各大音乐平台+微博微信）。
要是你听 Anisong | OST | 影视相关，那也不用我介绍。
类似的还挺多的。
所以我们把目标放在小众流派。
第一是有挺多电台（比如「主唱死了」「细声电台」），可以去听，里面会推。
第二是关注各个独立厂牌。
还有各个音乐杂志，比如后摇领域 EDopamine 就在做）。
如果你常去各种音乐节 or Livehouse 的话可以认识不少乐队，照着听就行。
然后还有几个网络平台，比如 AllMusic. LastFM.
我常用的是 BC ，也就是 Bandcamp .
BC 有挺多有趣的地方的，比如音乐人发布专辑的时候可以设定「最低费用」，支付 ≥ 这个数值的费用就可以获得专辑。甚至可以 0 元获取，上面的图片就是一个例子。这是音乐人自己设定的，也就是所谓官方渠道，不算白嫖。
而且购买后你可以无限制获取低品质 MP3 到很高品质 AIFF （一首大约 100-200 MiB）范围的各种格式的整专辑打包下载。下载之后就是传统的音乐格式，没有加密。每个音乐文件的信息填的还可以，主要是准确。
这个平台主要是日本+欧美那边的独立音乐人或小厂牌在用，入驻的音乐家很多，流派也从电子音乐到各种摇滚到新古典都有。
下载歌曲除了 BC 还有 Amazon （这个指的不是 Amazon Music 那个流媒体服务），我也在用，这也是国际「大平台」了（笑）
（其实主要是美亚和日亚）
下载是 MP3 320K （大部分是 320K（小声）），没有加密。
还有就是 iTunes Store 了，老传统的平台了（这个指的也不是 Apple Music 那个流媒体服务），可惜我没用过，也不打算去搞清楚怎么用。不管他了。
Tidal 和 Qubuz 我也不太用……我记得好像 Tidal 不怎么开放下载。YT Music 就不说了……
Mac OS:
推荐 iTunes.
Windows:
推荐 iTunes | MusicBee
Linux:
他们说 Rythmbox （就 Ubuntu 自带那个）或者 Banshee 都不错，我没用过，我不知道.jpg
以下正文：
先说结论：这两个软件对歌词支持都很一般，远不如在线音乐平台那些播放器。
但这是我能挑出的唯一的缺点。在线音乐播放器也就只有这一个优点。
MusicBee 我很久之前用过一小会，就不管它了。功能和 iTunes 差不多，很多地方甚至更好。虽然我不用，但我首推这个。
* MusicBee 能播放 FLAC , 但 iTunes 不能
* 我不喜欢 FLAC , 我更喜欢 AIFF. （个人原因：我用 iPod ，它也不支持 FLAC ）
* FLAC 也是可以嵌入专辑图片和歌词的。具体方法……略
这玩意大概这样子：
它在 18 年之后 GUI 和交互逻辑取了 iTunes 的一些好的地方，除去了 iT 一些很非人类的逻辑，现在来说各方面相当漂亮。
再来谈谈 iT 。我平常就用它了。
添加到资料库的专辑可以按添加时间排序。
专辑选中之后可以看细节。甚至可以分光盘：
歌曲界面。有各种筛选器和排序方式，很灵活：
然后就是我最喜欢的歌曲信息 / 专辑封面 / 歌词编辑系统。支持编辑的都是直接写文件。当然，上面推的每个合格的播放器都有这个。
添加这信息图啥？好看吗？不，其实……
这智能播放列表也很强。还有搜索系统，不过合格的播放器都有。
上面这些功能 MBee 和 iT 都有，还有很多没提到的。这文章就不做软件说明书了……
个人来说，一直在用网易的时候没觉得网易的播放器不称心，也没觉得自己需要更高级的播放管理方式。
但是现在已经回不去了……不知道为什么。觉得网易缺功能，交互逻辑很粗暴很不灵活。
网易或 QQ 音乐做的播放功能都挺烦的。比如我有很多专辑都想整张听，我要么每张都做一个列表（这样只会加在播放列表的最后边，这很烦，我想马上能点进我最近添加的专辑）或者收藏，然后再找。我只想很省心的安排好我下一小时听的歌，太难了。
搜索的时候能不能只在我收藏 | 拥有| 听过的音乐内容之内，用（歌曲|专辑|歌手|流派|发行年份）匹配我的文本，然后不要把这些内容分页显示？ 每次搜歌都好烦的。这是致命一击。
对了，网易 | QQ 没有对每首曲子自定义流派分类的功能，也没有基于播放次数 / 最近播放的播放整理（笑）这是致命一击。
可以去 BC , 或者 Discogs。其实直接 Google 这个专辑就会获得很多信息。
就这样。
iOS 就直接买个 Apple Music 吧。这样可以和 iTunes 同步（可以插入电脑同步，直接自动过去），Apple Music 还有 iCloud 资料库的功能，可以把你的音乐文件（无论是什么）上传到 Apple iCloud 服务器（不占用你的 iC 空间，这些文件最多 2T），然后各个设备可以流媒体式播放你上传的内容。
Android 只推荐 Musicolet。这玩意功能和 MBee / iT 一样全。排序方式甚至更多。而且 GUI 很漂亮。
多的是支持多播放列表 / 倍速 / A-B Loop 的功能。还有记忆播放位置、歌词界面不息屏等等贴心的小功能。
我这三四个月用网易的时间不超过 1h，主要是歌荒了也上去找找歌。
不使用小众软件就来了什么优越感，但是网易播放就那样子（摊手）
而且我不用网易也没少什么有趣的东西。反而少了广告、小红点和傻子评论。
以上。
以前很多板子都是陆陆续续写的，也没有统一代码风格，有些还不全了。这次统一重新写一下，把这篇博客导出 pdf ，然后使用价格昂贵的彩印。
最后发现还是 LaTeX + TOC 比较舒适。这里就记录一下吧。
从并查集开始吧。
并查集 | 2020年10月25日23点51分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
// 普通并查集+路径压缩 namespace DSU { int dsu[100010]; // 初始化并查集. mode: 0=清空 1=指向自己 void Init(int st, int ed, int mode) { for (int i=st;i<=ed;i++) dsu[i] = ( (mode==0) ? 0 : i ); } // 查询集合 id 并做路径压缩. int Find(int u) { if (u!=dsu[u]) dsu[u]=Find(dsu[u]); return dsu[u]; } // 合并 a <- b. void Merge(int a,int b) { dsu[Find(b)]=Find(a); } } // 按秩合并 (aka 启发式合并) namespace DSU2 { struct Dsu_node { int fa,siz; } dsu[100010]; // 初始化并查集. mode: 0=清空 1=指向自己 void Init(int st, int ed, int mode) { for (int i=st;i<=ed;i++) { dsu[i].fa = ( (mode==0) ? 0 : i ); dsu[i].siz = (mode!=0); } } // 查询集合 id. int Find(int u) { while (dsu[u].fa!=u) u=dsu[u].fa; return u; } // 按秩合并 a 和 b, 若秩相同则 a <- b. void Merge(int a,int b) { int afa=Find(a), bfa=Find(b); if (dsu[afa].siz<dsu[bfa].siz) std::swap(afa,bfa); dsu[afa].siz+=dsu[bfa].siz; dsu[bfa].fa=afa; } } // 带删除并查集 namespace DSU3 { struct Dsu_node { int fa,siz,me; } dsu[100010]; int id[100010], cnt; // id[i]=0 表示不存在 || cnt 是 dsu 计数器 // 初始化并查集. mode: 0=清空 1=指向自己 void Init(int st, int ed, int mode) { cnt=ed; for (int i=st;i<=ed;i++) { dsu[i].fa = dsu[i].me = ( (mode==0) ? 0 : i ); dsu[i].siz = (mode!=0); } if (mode) for (int i=st;i<=ed;i++) id[i]=i; } // 查询集合 id. int Find(int u) { while (dsu[u].fa!=dsu[u].me) u=dsu[u].fa; return u; } // 按秩合并 a 和 b, 若秩相同则 a <- b. void Merge(int a,int b) { int afa=Find(a), bfa=Find(b); if (dsu[afa].siz<dsu[bfa].siz) std::swap(afa,bfa); dsu[afa].siz+=dsu[bfa].siz; dsu[bfa].fa=afa; } // 从集合中抠出 u (1) 或不可恢复地删除 u (-1). void Escape(int u, int mode) { if (mode==-1) id[u]=0; else { cnt++; dsu[cnt].fa=dsu[cnt].me=u; dsu[cnt].siz=1; id[u]=cnt; } } } |
朴素线段树 | 2020年10月26日20点07分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
// 朴素的线段树. 支持区间/单点加/乘, 区间/单点求和, 单点求 max(min). namespace SGT { struct Seg_Tree { int l,r; ll val, atag, mtag, maxv; } t[100010*4]; #define LCH (u<<1) #define RCH (u<<1|1) // 变量说明. // lx rx 为查询/修改的左右界 // vx 为修改的值 int lx,rx; ll vx; // 下推 u 的标记. void Pushdown(int u) { if (!t[u].atag && t[u].mtag==1) return; // boost ll at=t[u].atag, mt=t[u].mtag; t[u].atag=0; t[u].mtag=1; // 先乘后加 if (mt!=1) { t[LCH].mtag*=mt; t[RCH].mtag*=mt; t[LCH].atag*=mt; t[RCH].atag*=mt; t[LCH].val*=mt; t[RCH].val*=mt; } if (at) { t[LCH].atag+=at; t[RCH].atag+=at; t[LCH].val+=(t[LCH].r-t[LCH].l+1)*at; t[RCH].val+=(t[RCH].r-t[RCH].l+1)*at; } } // 用子树更新 u. void Pushup(int u) { t[u].maxv=std::max(t[LCH].maxv, t[RCH].maxv); t[u].val=t[LCH].val+t[RCH].val; } // L <-> R 建树. void BuildTree(int u,int L, int R) { t[u].l=L; t[u].r=R; t[u].mtag=1; // **这个标记要注意** if (L==R) { t[u].atag=t[u].maxv=t[u].val=0; return; } int m=(L+R)/2; BuildTree(LCH,L,m); BuildTree(RCH,m+1,R); Pushup(u); } // 单点/区间加 void Upd_Add(int u) { if (t[u].l>=lx && t[u].r<=rx) { t[u].val+=(t[u].r-t[u].l+1)*vx; t[u].atag+=vx; return; } Pushdown(u); int m=(t[u].l+t[u].r)/2; if (lx<=m) Upd_Add(LCH); if (rx>m) Upd_Add(RCH); Pushup(u); } // 单点/区间乘 void Upd_Mul(int u) { if (t[u].l>=lx && t[u].r<=rx) { t[u].val*=vx; t[u].atag*=vx; t[u].mtag*=vx; return; } Pushdown(u); int m=(t[u].l+t[u].r)/2; if (lx<=m) Upd_Mul(LCH); if (rx>m) Upd_Mul(RCH); Pushup(u); } // 查询区间/单点求和 ll Qry_Sum(int u) { if (t[u].l>=lx && t[u].r<=rx) return t[u].val; Pushdown(u); int m=(t[u].l+t[u].r)/2; ll ret=0; if (lx<=m) ret+=Qry_Sum(LCH); if (rx>m) ret+=Qry_Sum(RCH); Pushup(u); return ret; } // 查询区间/单点最大 ll Qry_Max(int u) { if (t[u].l>=lx && t[u].r<=rx) return t[u].maxv; Pushdown(u); int m=(t[u].l+t[u].r)/2; ll ret=0; if (rx<=m) ret=Qry_Max(LCH); else if (lx>m) ret=Qry_Max(RCH); else ret=std::max(Qry_Max(LCH), Qry_Max(RCH)); Pushup(u); return ret; } } |
朴素 FFT | 2020年11月7日22点13分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
// 朴素的 FFT namespace FFT { const double PI=3.14159265358; struct Complex { double r,i; Complex(double inr=0, double ini=0) { r=inr; i=ini; } Complex operator + (const Complex& B) { return Complex(r+B.r, i+B.i); } Complex operator - (const Complex& B) { return Complex(r-B.r, i-B.i); } Complex operator * (const Complex& B) { return Complex(r*B.r-i*B.i, i*B.r+r*B.i); } }; // 蝴蝶变换; 接受任意类型的数组和一个长度 (**可以是非 2^n 长度). int pre_len=-1,revt,rev[300010]; template<typename poly_arr> void BtFl(poly_arr *y, int len) { if (len!=pre_len) { pre_len=len; revt=0; int tmp=2; while (tmp<len) { tmp<<=1; revt++; } for (int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<revt); // 预处理反转位置 } for (int i=0;i<len;i++) if (i<rev[i]) swap(y[i],y[rev[i]]); // 反转 } // 法法塔; 要求 len 是 2^n; mode=1 实现 DFT, mode=-1实现 IDFT. void FFT(Complex *y, int len, int mode) { BtFl(y,len); for (int i=1;i<len;i<<=1) { const Complex wn( cos(PI/i), mode*sin(PI/i) ); for (int j=0;j<len;j+=(i<<1)) // Each Process Start Point { Complex w(1,0); for (int k=0;k<i;k++,w=w*wn) // Step size { Complex t1=y[j+k], t2=w*y[i+j+k]; y[j+k]=t1+t2; y[i+j+k]=t1-t2; } } } if (mode==-1) for (int i=0;i<len;i++) y[i].r/=len; } } |
gcd 和 exgcd | 2020年11月7日22点13分 | 有数学部分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// 求 a 和 b 的最大公约数 ll gcd(ll a, ll b) { if (!b) return a; return gcd(b,a%b); } // 解丢番图方程 ax+by=gcd(a,b). exgcd 的推广见数学手册 exgcd 部分. void exgcd(ll &x,ll &y,ll a,ll b) { if (!b) { x=1; y=0; } else { exgcd(y,x,b,a%b); y=y-x*(a/b); } } |
快速排序 | 2020年11月9日11点35分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
// 在数组中对 [l,r] 进行快排; 默认比较器: < template<typename arr_> void QuickSort(int l, int r, arr_ *seq) { int i=l,j=r,mid=seq[(l+r)/2]; while (i<=j) { while (seq[i]<mid) i++; while (seq[j]>mid) j--; if (i<=j) { swap(seq[i], seq[j]); i++; j--; } } if (i<r) QuickSort(i,r,seq); if (j>l) QuickSort(l,j,seq); } |
Splay – 无区间反转 | 2020年12月18日21点30分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
// Splay - 无区间反转 namespace SPL { #define LCH (t[inx].ch[0]) #define RCH (t[inx].ch[1]) struct Splay_Tree { int ch[2], siz, fa, w, val; } t[400010]; int tsiz,rt; // 更新节点数据 void Upd(int inx) { t[inx].siz=t[inx].w+t[LCH].siz+t[RCH].siz; } // 旋转一个节点 void Rotate(int inx) { int f=t[inx].fa, g=t[t[inx].fa].fa, dir=(t[t[inx].fa].ch[1]==inx); if (g) t[g].ch[t[g].ch[1]==f]=inx; if (t[inx].ch[!dir]) t[t[inx].ch[!dir]].fa=f; t[f].ch[dir]=t[inx].ch[!dir]; t[f].fa=inx; t[inx].fa=g; t[inx].ch[!dir]=f; Upd(f); Upd(inx); } // 把一个点旋转到 Targ 下面 void Splay(int inx, int targ) { for (;t[inx].fa!=targ; Rotate(inx)) { int f=t[inx].fa, g=t[t[inx].fa].fa; if (g!=targ) { if ( (t[g].ch[1]==f) == (t[f].ch[1]==inx) ) Rotate(f); else Rotate(inx); } } if (!targ) rt=inx; } // 求一个数的排名 int GetRank(int inx, int val) { if (t[inx].val==val) { Splay(inx, 0); return t[LCH].siz+1; } return GetRank(t[inx].ch[t[inx].val<val], val); } // 求排名为 val 的数的值 int GetVal(int inx, int val) { if (t[LCH].siz<val && t[inx].w+t[LCH].siz>=val) { Splay(inx, 0); return t[inx].val; } if (val<=t[LCH].siz) return GetVal(LCH, val); else return GetVal(RCH, val-t[LCH].siz-t[inx].w); } // 求值为 val 的结点下标 int GetInx(int val) { int inx=rt; while (t[inx].val!=val) inx=t[inx].ch[t[inx].val<val]; return inx; } // 求 [inx] 结点的 (0)前驱/(1)后继 int PreSuc(int inx, int dir) { inx=t[inx].ch[dir]; while (t[inx].ch[!dir]) inx=t[inx].ch[!dir]; return inx; } // 插入 val void Ins(int &inx, int f, int val) { if (!inx) { inx=++tsiz; t[inx].fa=f; t[inx].siz=t[inx].w=1; t[inx].val=val; Splay(inx,0); return; } t[inx].siz++; if (t[inx].val==val) { t[inx].w++; Splay(inx, 0); return; } Ins(t[inx].ch[t[inx].val<val], inx, val); } // 删除一次 val void Del(int val) { int inx=GetInx(val); Splay(inx,0); if (t[inx].w>1) { t[inx].w--; t[inx].siz--; return; } Splay(PreSuc(inx,0), inx); rt=LCH; t[LCH].fa=0; t[LCH].ch[1]=RCH; t[RCH].fa=LCH; Upd(LCH); } // 初始化树并插入两个哨兵结点 void Init_Tree() { tsiz=2; rt=1; t[1].w=1; t[1].siz=2; t[1].val=-2*1e9; t[1].ch[1]=2; t[2].w=1; t[2].siz=1; t[2].val=2*1e9; t[2].fa=1; } #undef LCH #undef RCH } |
FHQ_Treap 维护集合 | 2021年3月6日22点20分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 |
// 维护集合 | 基于大根堆的 fhq_treap -> 可重集结点合并策略 namespace fhq_treap { #define LCH (t[inx].ch[0]) #define RCH (t[inx].ch[1]) struct fhq_treap { int ch[2], siz, fa, val, key; }t[1000010]; int rt,tsiz; void Update(int inx) { t[inx].siz=1+t[LCH].siz+t[RCH].siz; } // 拆成 [min, val] 和 [val+1, max] void Split(int inx, int val, int &rt1, int &rt2) { if (!inx) { rt1=rt2=0; return; } // 好记的思路：拆哪边就接哪边。要往左拆的，当前点就归[2]，反之亦同 if (val<t[inx].val) { Split(LCH, val, rt1, rt2); LCH=rt2; rt2=inx; } else { Split(RCH, val, rt1, rt2); RCH=rt1; rt1=inx; } Update(inx); } // 将 rt2（DFS 序意义上）合到 rt1 后面. int Merge(int rt1, int rt2) { if (!(rt1*rt2)) return rt1+rt2; if (t[rt1].key >= t[rt2].key) { t[rt1].ch[1] = Merge(t[rt1].ch[1], rt2); Update(rt1); return rt1; } else { t[rt2].ch[0] = Merge(rt1, t[rt2].ch[0]); Update(rt2); return rt2; } } void Insert(int val) { int inx = ++tsiz; t[inx].val=val; t[inx].siz=1; t[inx].key=rand(); int rt1, rt2; Split(rt, val, rt1, rt2); rt = Merge(Merge(rt1, inx), rt2); } void Delete(int val) { int inx, rt1, rt2, rt3; Split(rt, val, rt1, rt2); Split(rt1, val-1, rt3, inx); inx = Merge(LCH, RCH); rt = Merge(Merge(rt3, inx), rt2); } // 求 val 数的 rank int Rank(int val) { int rt1, rt2, ret; Split(rt, val-1, rt1, rt2); ret = t[rt1].siz+1; rt = Merge(rt1, rt2); return ret; } // 求 val 数的 ID int ID(int inx, int val) { if (!inx) return -1; if (t[inx].val==val) return inx; else if (t[inx].val > val) return ID(LCH, val); else return ID(RCH, val); } // 求排名为 k 的数的 ID int Kth(int inx, int k) { if (k <= t[LCH].siz) return Kth(LCH, k); else if (k == t[LCH].siz+1) return inx; else return Kth(RCH, k - 1 - t[LCH].siz); } int Pre(int val) { int rt1, rt2; Split(rt, val-1, rt1, rt2); int ret = Kth(rt1, t[rt1].siz); rt = Merge(rt1, rt2); return ret; } int Suc(int val) { int rt1, rt2; Split(rt, val, rt1, rt2); int ret = Kth(rt2, 1); rt = Merge(rt1, rt2); return ret; } #undef LCH #undef RCH } |
无旋 Treap | 2021年3月6日22点34分
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
// 无旋 Treap. namespace Treap { #define LCH t[inx].ch[0] #define RCH t[inx].ch[1] struct Treap_tree { int ch[2], val, key, w, fa, siz; }t[100010]; int tsiz, rt; void Update(int inx) { t[inx].siz=t[LCH].siz+t[RCH].siz+t[inx].w; } // 0 代表左旋，1 代表右旋；动态更新结点编号 void Rotate(int &inx, int dir) { int ch=t[inx].ch[!dir]; t[inx].ch[!dir]=t[ch].ch[dir]; t[ch].ch[dir]=inx; Update(inx); Update(inx = ch); } // inx 是 ref，旋转时注意时机和写法。 void Ins(int &inx, int val) { if (!inx) { inx=++tsiz; t[inx].w=t[inx].siz=1; t[inx].key=rand(); t[inx].val=val; return; } t[inx].siz++; if (t[inx].val==val) { t[inx].w++; return; } bool flag=t[inx].val<val; Ins(t[inx].ch[flag], val); if (t[inx].key<t[t[inx].ch[flag]].key) Rotate(inx, !flag); } // 删除，注意旋转和只有单儿子的情况 void Del(int &inx, int val) { if (!inx) return; t[inx].siz--; if (t[inx].val==val) { if (t[inx].w>1) { t[inx].w--; return; } if (!(LCH*RCH)) { inx=LCH+RCH; return; } bool flag=(t[LCH].key<t[RCH].key); Rotate(inx, !flag); Del(inx, val); } else Del(t[inx].ch[t[inx].val<val], val); } // 前后驱，注意构造性写法 int Pre(int inx, int val) { if (!inx) return -2*1e9; if (t[inx].val>=val) return Pre(LCH, val); return max(t[inx].val, Pre(RCH, val)); } int Suc(int inx, int val) { if (!inx) return 2*1e9; if (t[inx].val<=val) return Suc(RCH, val); return min(t[inx].val, Suc(LCH, val)); } int Rank(int inx, int val) { if (!inx) return 0; if (t[inx].val==val) return t[LCH].siz+1; else if (t[inx].val>val) return Rank(LCH, val); else return t[LCH].siz+t[inx].w+Rank(RCH, val); } int ID(int inx, int val) { if (val<=t[LCH].siz) return ID(LCH, val); if (val>t[LCH].siz+t[inx].w) return ID(RCH, val-t[LCH].siz-t[inx].w); return inx; } #undef LCH #undef RCH } |
傍晚了，太阳慢慢地落下去，校园逐渐空旷。十七中，年代略显悠久的建筑和新修建的建筑散乱地混合在一起。又是秋天了，悠远的天空被丝雾般带状的云彩占满了一半。这种并非想象中的那种，棉花糖触感般厚实的夏云，而是线条硬朗的云，容易在鼻腔里唤起秋天的气味。校园后侧是一片空旷的场地，三面被高耸的铁丝网围了起来，夕阳就是从菱形的间隙透出光芒，将那一侧的天空染黄。对面几棵树叶转黄的树在风中摇摆，上面的天空星星已经隐约可见。透过铁丝网可以对这侧城市留下一个大致的印象，九十年代破旧的居民楼杂乱地分布着，窗户上积攒了灰尘，墙皮半剥落，偶尔从哪个窗户冒出一阵生活气息的水汽来。学校周围就分布着很多这样的居民楼。阳夏推着小车走到水泥地中央，却停住了。低下头，脚下还可以看见模糊的白线，可能以前，这里是作停车场吧。
密集的城市的一角，充满了市井嘈杂的街区，还能找到这种安静的地方，阳夏还是很开心。不过秋天了，慢慢觉得以前的回忆都飞过来，扑入她的胸口。
秋天是等待的季节，阳夏总觉得她在等待着什么。她总觉得以前，她就像是怀着使命待发的少年，随时就可能在某个晴天或雨天乘上到火车站的大巴，拖着笨重的行李坐在火车上打个盹，然后在赛场上见到很多很多像自己一样的少年，多到她要认真地记住他们的名字，甚至有时候望着少年们奔忙的人流，思考自己是怎样来到脚下这片地方。也有时候阳夏只是随着心中的激动迈开脚步，匆匆地去拥抱自己看到的这一切。
每次坐着大巴回到十七中，她都要重新认识一次这个城市。忙碌的人群，夜晚老旧居民楼窗户上透出昏黄的灯光，同样暗黄的路灯照亮的旧公路，整个城市很安静。看到熟悉却心爱的风景，她又变成了那个少年，怀着使命感，准备随时从这个地方出发，又要穿越夜色，去和其他少年们聚在一起。
但其实她心底明白城市的这一角很熟悉。夏末还有残热的时候，仍然可以在短袖外面披一件薄薄的风衣，敞开怀在路上踏步。放学晚归，虽然街道上一个人也没有，路灯、楼房、红砖人行道也都是冷冰冰的，但是走过去却感觉很温暖，是从心底滋生的暖意。她明白只需要在这儿慢慢地走，并且准备好，有那么一刻会跑着去到远方。
于是她离开，离开好多次；她没有细想的是，虽然她是去往远方，还有使命和向往，但是她从来都觉得自己不久就能回到这里，然后，偶尔地，期待下一次出发。
可能有时候，心怀这样感情的阳夏，在十七中度过每个傍晚的时候，去思考对未来那些光芒的期待，去准备好奔跑着离开、回来，总是比远赴赛场有趣得多。
可能正是因为，向往的感情都洒在了十七中的傍晚，洒在了这空无一人的旧停车场，透过高铁丝网对夕阳和旧楼的凝视当中，所以现在的她，每每想到向往、想到奔赴未来的征程，思绪总会回到这片地方，回到秋天，眼角收拢旧居民楼老玻璃窗上那残存的一丝蒸汽，鼻腔留下落叶和半天空星星的味道。
她不是总在准备着什么，但她的记忆里，那段为了上赛场并笑着回来的时间里，她确实是。
渐渐地过去几年，生活繁忙起来，天天的准备却总成了应对，那些向往的时间溜走了。
偶尔地，会听到一段旋律，这时阳夏又想起为了那些而等待的秋天，首先闯入脑海的却不是赛场上那些生动的故事，而是这段闲适而静美的时间。因为眼里都是向往，连眼前的景色，无论高铁丝网还是旧楼都染上同样的色彩。想起同样的风景，她并非思乡，但祈望重回那段时间。当时的感情那么纯粹，还没有被纷乱的任务搅乱。
所以在这场梦里她还是站在了这里。心里涌起过去的使命感。但这只是习惯所致，并没有什么赛场真的等在她面前，等着让她接近过去。这种不调和的矛盾让她不舒服了，眼角慢慢湿润……
秋风慢慢吹过去，太阳依旧温暖，云也不动，露出一半天空的星星，底下还有城市的轮廓。
A | B | C
过于傻逼。放个代码，估计连代码都没人看（摊手）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> typedef long long ll; using namespace std; template<typename int_t> void readx(int_t &x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } int main() { int T; readx(T); while (T--) { int x; readx(x); int ans=0; ans+=((x%10)-1)*10; int tmp=0; while (x) { x/=10; tmp++; } ans+=(tmp)*(tmp+1)/2; cout<<ans<<endl; } } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> typedef long long ll; using namespace std; int n,ai[1010]; template<typename int_t> void readx(int_t &x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } int main() { int T; readx(T); while (T--) { readx(n); int ans = 2*1e9; for (int i=1;i<=n;i++) readx(ai[i]); bool flag=1; int l=1,r=n; while (!ai[l]) l++; while (!ai[r]) r--; for (int i=l;i<=r;i++) flag=flag&ai[i]; if (flag) { printf("0\n"); continue; } for (int i=1;i<=n;i++) if (ai[i]) { int tmp=0; for (int j=l;j<i;j++) if (!ai[j]) tmp++; for (int j=r;j>i;j--) if (!ai[j]) tmp++; ans=min(ans,tmp); } printf("%d\n", ans); memset(ai,0,sizeof ai); } return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> typedef long long ll; using namespace std; ll n,a[300010]; template<typename int_t> void readx(int_t &x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } int main() { int T; readx(T); while (T--) { readx(n); for (int i=1;i<=n;i++) readx(a[i]); int aeq=a[1]; bool flag=1; for (int i=1;i<=n;i++) if (a[i]!=aeq) flag=0; if (flag) { printf("-1\n"); continue; } ll val=a[1]; int ans=1; for (int i=1;i<=n;i++) if (val<a[i]) { val=a[i]; ans=i; } if (a[n]==val) { for (int i=n;i>=1;i--) if (a[i]==val && a[i-1]!=val) { ans=i; break; } } else { for (int i=1;i<=n;i++) if (a[i]==val) ans=i; } printf("%d\n", ans); } return 0; } |
D | Districts Connection
是个构造题。
不同团块内部不能连，判断是否能构造生成树 (MST) 并输出方案。
考虑最经典的树——菊花图。我们强行选择第一个团块的第一个点。让它和其他不同团块的所有点都连一条边。
这样只有一号团块没在生成树里。我们拿出二号团块的第一个点把一号团块除第一个点都连一遍。OK
所以团块数 \leqslant 2 即可。不然无解。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> #include<map> typedef long long ll; using namespace std; int n,bel[10010]; map<int,int> mp; template<typename int_t> void readx(int_t &x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } int main() { int T; readx(T); while (T--) { mp.clear(); int id1, id2, tar, cnt=0; readx(n); for (int i=1;i<=n;i++) { readx(bel[i]); mp[bel[i]]+=1; if (mp[bel[i]]==1) cnt++; } if (cnt==1) { printf("NO\n"); continue; } printf("YES\n"); id1=bel[1]; for (int i=1;i<=n;i++) if (bel[i]!=id1) { id2=bel[i]; tar=i; break; } for (int i=1;i<=n;i++) if (bel[i]!=id1) printf("1 %d\n",i); for (int i=2;i<=n;i++) if (bel[i]==id1) { printf("%d %d\n", tar, i); } } return 0; } |
E | Two Round Dances
经典圆排列裸题。这里要分成等份的两部分。
让原题的输入是 N ，我们记 n \xlongequal{\mathrm{def}} \frac{N}{2}
我们就直接拿出圆排列公式：
Q_{n}^{r}=\frac{A_{n}^{r}}{r}=\frac{n!}{r\cdot \left( n-r \right) !}证明就无所谓了，百度百科就有（直球），或者 Polya 直接推。
代公式 ，OK。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> #include<map> typedef long long ll; using namespace std; ll ans1,ans2; template<typename int_t> void readx(int_t &x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } ll fac(ll x) { ll ret=1; for (ll i=1;i<=x;i++) ret*=i; return ret; } int main() { ll n; readx(n); ll n2=n>>1; if (n==2) printf("1\n"); else printf("%lld\n", fac(n/2-1) * (fac(n) / (n2*fac(n2)) ) / 2 ); return 0; } |
F | Zero Remainder Sum
总的来说这玩意类似一个背包。
一开始被那个 \lfloor \frac{m}{2} \rfloor 搞到怀疑人生。一直在找这条件有什么结论。
不过显然没有（摊手）其实你任给一个 lim 这题都能做。
设计状态 dp[i=当前行数][j=已选个数][k=当前行选 j 个且 mod K 余数为 k]
然后可以背包 – like 地转移。
然后最后把每行看成一个整体继续背包。完了。复杂度达到了惊人的 \mathcal{O}(n^4) ！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> typedef long long ll; using namespace std; int n,m,K; int a[80][80]; ll ans; int dp[80][80][80]; int dp2[80][80]; template<typename int_t> void readx(int_t &x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } int main() { readx(n); readx(m); readx(K); int lim=m/2; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) readx(a[i][j]); for (int i=1;i<=n;i++) for (int j=0;j<=lim;j++) for (int k=0;k<K;k++) dp[i][j][k]= -1 * 1e9; // dp[行数][选择个数][余数] for (int i=0;i<=n;i++) dp[i][0][0]=0; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) // 当前考虑 (i,j) { for (int k=lim;k>0;k--) // 选择个数 { for (int l=0;l<K;l++) // 余数 { int l1=(l+a[i][j])%K; dp[i][k][l1]=max(dp[i][k][l1], dp[i][k-1][l]+a[i][j]); } } } } for (int i=0;i<=n;i++) for (int j=0;j<K;j++) dp2[i][j]= -1 * 1e9; dp2[0][0]=0; // dp2[行][余数] for (int i=1;i<=n;i++) { for (int j=0;j<K;j++) // 当前余数 { for (int k=0;k<=lim;k++) // 该行选几个 { for (int l=0;l<K;l++) // 该行选了之后行之和的余数 { int j2=(j+l)%K; dp2[i][j2]=max(dp2[i][j2], dp2[i-1][j]+dp[i][k][l]); } } } } printf("%d\n", max(0,dp2[n][0])); return 0; } |
G | Reducing Delivery Cost
先对全图跑最短路， \mathcal{O}(n^2 \log n) 。
然后枚举边，把边权设为 0 之后统计答案。
总复杂度 \mathcal{O}(n^2 \log n) 。
我跑的就尼玛很慢，估计是 STL 的问题（大嘘）。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> #include<queue> typedef long long ll; using namespace std; int G[1010][1010]; int tdis[1010][1010]; int n,m,k; vector<int> des[1010]; vector< pair<int,int> > ed; template<typename int_t> void readx(int_t &x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } struct _Node { int dis; int cod; bool operator < (const _Node& B) const { return dis>B.dis; } }; priority_queue<_Node> que; int dis[1010]; bool vis[1010]; void Dijkstra(int src) { _Node cac1,cac2; int u; memset(vis,0,sizeof vis); memset(dis,0x3f,sizeof dis); dis[src]=cac1.dis=0; cac1.cod=src; que.push(cac1); while (!que.empty()) { cac1=que.top(); que.pop(); u=cac1.cod; if (vis[u]) continue; vis[u]=1; for (int v=1;v<=n;v++) if (v!=u) { if (dis[v]>dis[u]+G[u][v]) { dis[v]=dis[u]+G[u][v]; cac2.cod=v; cac2.dis=dis[v]; que.push(cac2); } } } for (int i=1;i<=n;i++) tdis[src][i]=dis[i]; } int main() { memset(G,0x3f,sizeof G); readx(n); readx(m); readx(k); ll ans2=1000000000000000000LL; int u,v,w; for (int i=1;i<=m;i++) { readx(u); readx(v); readx(w); G[u][v]=G[v][u]=w; ed.push_back( make_pair(u,v) ); } for (int i=1;i<=k;i++) { readx(u); readx(v); if (u==v) continue; des[u].push_back(v); } for (int i=1;i<=n;i++) Dijkstra(i); for (auto e:ed) { int fi=e.first, se=e.second; ll ans=0; for (int i=1;i<=n;i++) for (auto vv:des[i]) { u=i; v=vv; ans+=(ll) min(tdis[u][v], min(tdis[u][fi]+tdis[se][v], tdis[u][se]+tdis[fi][v])); } ans2=min(ans2,ans); } cout<<ans2<<endl; return 0; } |
A XORwice
答案是 a \oplus b 。证明：显然。
B Putting Bricks in the Wall
由于只能左右上下动，结果就是限定移动的砖块只有 (1,2) \quad (2,1) \quad (n,n-1) \quad (n-1, n) 。
然后就 if 一下分情况讨论就可以了。代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> #include<queue> #include<map> #include<set> typedef long long ll; using namespace std; char g[210][210]; int n; template<typename int_t> void readx(int_t &x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } int main() { int T; readx(T); while (T--) { readx(n); for (int i=1;i<=n;i++) scanf(" %s", g[i]+1); int sim=0; if (g[2][1]==g[1][2]) sim++; if (g[n][n-1]==g[n-1][n]) sim++; // case 1 if (sim==2) { if (g[2][1]==g[n-1][n]) { printf("2\n2 1\n1 2\n"); continue; } else { cout<<0<<endl; continue; } } if (sim==1) { if (g[2][1]==g[1][2]) { printf("1\n"); if (g[n][n-1]==g[2][1]) printf("%d %d\n", n, n-1); else printf("%d %d\n", n-1, n); } else { printf("1\n"); if (g[2][1]==g[n][n-1]) printf("2 1\n"); else printf("1 2\n"); } continue; } if (!sim) { printf("2\n"); printf("1 2\n"); if (g[n][n-1]==g[2][1]) printf("%d %d\n", n, n-1); else printf("%d %d\n", n-1, n); continue; } } return 0; } |
C Palindromifier
是这样构造的：
然后就没了。代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> #include<queue> #include<map> #include<set> typedef long long ll; using namespace std; char ch[100010]; template<typename int_t> void readx(int_t &x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } int main() { scanf(" %s", ch+1); int len=strlen(ch+1); if (len==3) { printf("4\nL 2\nR 3\nL 4\nL 2\n"); return 0; } printf("4\n"); printf("L %d\n", len-1); len+=len-2; printf("R %d\n", len-1); len++; printf("L %d\n", len-1); len+=len-2; printf("L 2\n"); return 0; } |
D Hexagons
首先可以贪心地证明一定是只选择两个方向走最优。
选的话一共 12 种组合，挨个判断一下，然后更新答案。
粉兔の怒：
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<cstdio> #include<iostream> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> #include<vector> #include<queue> #include<map> #include<set> typedef long long ll; using namespace std; template<typename int_t> void readx(int_t &x) { x=0; int_t k=1; char ch=0; while (ch<'0' || ch>'9') { ch=getchar(); if (ch=='-') k=-1; } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=k; } int main() { int T; readx(T); while (T--) { ll c1,c2,c3,c4,c5,c6; ll ex,ey; readx(ex); readx(ey); readx(c1); readx(c2); readx(c3); readx(c4); readx(c5); readx(c6); swap(ex,ey); ll ans=2100000000000000000LL; if (ex>=0 && ey>=0) //c2 c6 OK ans=min(ans, ex*c2+ey*c6); if ((ex-ey)>=0 && ey>=0) // c2 c1 OK ans=min(ans, ey*c1+(ex-ey)*c2); if ((ex-ey)>=0 && ey<=0) // c2 c4 OK ans=min(ans, (-ey)*c4+(ex-ey)*c2); if (ey<=0 && ex>=0) //c2 c3 OK ans=min(ans, ex*c2+(-ey)*c3); if ((ex-ey)<=0 && ey>=0 && ex>=0) // c1 c6 OK(?) ans=min(ans, (ey-ex)*c6+ex*c1); if (ey>=0 && (ex-ey)<=0) // c1 c5 OK(?) ans=min(ans, (ey-ex)*c5+ey*c1); if (ex>=0 && (ex-ey)>=0) //c1 c3 OK ans=min(ans, ex*c1+(ex-ey)*c3); if (ey>=0 && ex<=0) //c6 c5 OK ans=min(ans, ey*c6+(-ex)*c5); if (ex<=0 && (ex-ey)<=0) // c6 c4 OK ans=min(ans, (-ex)*c4+(ey-ex)*c6); if (ex<=0 && ey<=0) // c5 c3 OK ans=min(ans, (-ey)*c3+(-ex)*c5); if (ey<=0 && (ex-ey)<=0) // c5 c4 OK ans=min(ans, (ey-ex)*c5+(-ey)*c4); if (ex<=0 && (ey-ex)<=0) // c4 c3 OK ans=min(ans, (-ex)*c4+(ex-ey)*c3); printf("%lld\n",ans); } } |
E
还没补，咕着先。
