最近更新：2023.3.26 本来想将上大学以来的日记都写在这里，然而还是有些难以启齿的事情，需得分开来发布才可以加密。因此，有内容完全相同的博客文章独立发布，并且自以上日期之后日记不在这里更新。 这里仅做留档。连起来看一遍还挺有意思的。 I ❤ SJTU 这个家伙愉快地踏入了上海交通大学的大门。 他将在上海交通大学闵行校区度过他的若干年大学生活。 让我们看看他会变成...

军训已经几周了。如果算上之前 ACM 队训练的一个月，时间也许更长。 上海交通大学，全国最大的校区，我即将在这里度过四年或更长的时间。虽然我已经在这的一会相对来说只是很短的一部分，但是却有开启我成年人生的重大意义。 学校课程还未确定，但真正的课早已开始。军训开幕当晚我请教母亲针线活，参加军乐团，训练和报名 ACM，打听消息、咨询学长自行车的事宜，并且从家里借了第一笔钱。我很幸运这里基本...

2022.7.6 昨天是清北强基计划出结果的日子。班里许多同学都考上了清北。至于我，早已被上海交通大学数学与应用数学系录取。 我不知道心里面是什么滋味。在班里能前往我心心念念学校的同学中，没有我的名字。 或许有人会说，行了吧，上交还不够吗？相当于上海的清北嘛，虽然总排名差了一点。或许我的家长会说，不错了，现在你是家里学历最高的人了。上交对于你来说不一定比清北差。诚然。在我此前的无数篇碎...

City of stars Are you shining just for me City of stars There's so much that I can't see Who knows I felt from the first embrace I shared with you That now our dreams They've finally come true ...

问题描述 SAT(satisfiabality) 是适应性的缩写，一般称 k 的适应性问题为 k-SAT。适应性问题指有 \(n\) 个布尔变量 \(\{x_i\}\)，加入一些限制然后求限制内的解的问题。 因为 \(k>2\) 的 k-SAT 问题是 NP 完全问题（没有一定的算法和正解），我们只讨论 2-SAT 问题。 Tarjan 一般来讲，我们会想到把变量 \(x...

AC来自一个大佬的名字，并不是写了就可以自动AC的意思 XD AC自动机是建立在trie树上的一种优化手段。trie在每次查询一个字符串时，如果在一个子树查不到就会回溯再查，效率会很低。我们考虑在给每个节点加一个如果查不到就跳转的指针fail，那么如果找不到的话直接跳转到fail就可以了。fail代表的是拥有该点的最大后缀的点的位置。 那么怎么寻找这个fail呢？因为我们要寻找最大后缀，...

成品 B站链接 Wallpaper Engine 可用：搜索 Alice_StarCried 简述 参考了B站的两个自学教程，都是直接搜能搜到的。PS、AE 零基础。因为需要渲染所用电脑配置有一定需求，额外用了数位板。AE 使用了现成脚本。从学习到制作完成总用时不过四天。 所需技能为 PS 基本使用，包括抠图、补图等，以及 AE 基本使用和脚本使用，都很简单。最耗时的部分实际...

AT2390 Games on DAG 题意 \(n\) 个点 \(m\) 条边的 DAG，每条边 \((u,v)\) 有 \(u<v\)。\(1,2\) 号点各一个石头，Alice 和 Bob 轮流每次沿边移动一个石头，不能动者输。求所有连边子集中先手胜的情况。两个石头可以重合。\(n\leq 15\)。 思路 发现对于两个石头的 SG 函数是独立的，输者两个石头 SG 函...

AT2304 Cleaning 题意 一个树上每个节点有一些石子，每次只能选取两个叶子节点并将路径间的所有点上的石子数量减1，问是否能将所有石子取完。 思路 设 \(f_x\) 表示从 \(x\) 节点向上的路径条数，\(s_x\) 为子节点的 \(f\) 值的和，则有： \[ a_x=\frac{s_x-f_x}{2}+f_x\\ f_x=2a_x-s_x \] 我们只需要保...

CF1032G Chattering 思路 对于每一个位置，它转移的范围是确定的。 对于一段可以走到的区间，我们可以求出区间中所有点再能走到区间范围。 于是这个就可以倍增进行转移。 如何快速求出一段区间能走到的区间范围？也就是分别求出一段区间向左跳的位置的最小值和向右跳位置的最大值，发现这其实就是一个RMQ问题。但是因为还有倍增的时间复杂度，而且是没有修改的，那么我们可以利用ST...