漫天闪烁的繁星
化作繁星
伴着我独自前行
越过光年的距离
照亮我的眼睛
0 启程
上海,中国对外开放的中心。
这场上海之旅来之不易。伴随着紧急疏散的要求,我和抹茶和 dyf_dyf 一同打的前往花桥,乘坐上海轨道交通 11 号线,前往上海。
Continue reading “NOI 2022 游记 SP – 上海之旅”「Jump up HIGH!!」
漫天闪烁的繁星
化作繁星
伴着我独自前行
越过光年的距离
照亮我的眼睛
上海,中国对外开放的中心。
这场上海之旅来之不易。伴随着紧急疏散的要求,我和抹茶和 dyf_dyf 一同打的前往花桥,乘坐上海轨道交通 11 号线,前往上海。
Continue reading “NOI 2022 游记 SP – 上海之旅”今年是最感到时间如白马过隙的。每天窝在机房看自己不会的东西,每天都在想明天要学什么新的东西,然后日子就一天天的过去了。
想学的东西还没有学完,CCF 要求所有选手先到昆山的通告倒是先来了。不管如何,参赛为重,只得踏上前往昆山的旅途。
因为雅礼人的高铁经过温州 & 他们订票的时候也没带上我,我就自己整了个别的列车。
在 08 月 13 日到达的昆山。
一到昆山就跑去找 dyf_dyf 和 Lucky_Yukikaze 聊天。
整理一下情况是几乎整个新疆省队都在一起(除了 Arachv)。接下来的日子就很简单了,蜜雪冰城,Among us,写模版,聊天。
简单欢乐的日子永远过的很快,眨眼见就到了 20 号。
Continue reading “NOI 2022 游记”考试链接: https://codeforces.com/contest/1699
考试的时候 30min 写完 ABC 发现 D 没几个人就摸了。考完看了眼 E 发现一眼切。最后竟然上分了,我大受震撼。
求能否找到任意三个数字 $a,b,c$ 使得 $(a \oplus b) + (a \oplus c) + (b \oplus c) = n$ 。
容易发现奇数根本不可能,偶数随便构造。
给表格染色。使得对于任意一个格子,有且只有两个相邻格子和这个颜色不同。
以 2x2
为一个单位,交叉构造即可。
对于大多数情况,树中只有很少一部分点是对当前要处理的信息是有意义的。
我们可以在保留这些有意义的点,不破原树结构的情况下得到一个很精简的树,这样我们就不用遍历整颗树了。
这种做法就叫虚树。
Continue reading “虚树”和后缀和。
求
$$
b_k = \sum_{i|k}a_i
$$
或
$$
b_k = \sum_{k|d}a_d
$$
都一样,没啥区别。
Continue reading “Dirichlet 前缀和”这个东西看了半天没想明白为啥不是最小生成树,然后发现最小生成树实际上是最小斯坦那树的特殊形式
— 最小生成树里的所有点都是关键点。
最小斯坦那树是指在一个无向图中,求其最小生成网络使得其
寄啦,哈哈。
今年是新疆维吾尔自治区第一次组织省选。
今年有很多神奇的事情,比如特派员换了,新疆成立竞赛组委会了,办省选了,有 $\frac{1}{3}$ 了,有实体 NOI Linux。当然也不都是好事,疫情精准防控的代表上海已经被奥米克戎攻陷,全国疫情更是此起彼伏,见不到头。这种情况下信息学竞赛还能基本上「出淤泥而不染」,维持较为正常的赛季流畅已是相当不易。
在疫情的限制下,XJOI 最终未能选择新疆大学作为考点,而是选择了一所高中 — 乌鲁木齐市第一中学。
Continue reading “XJOI 2022 游记”给定矩形的三个顶点,求其剩下的顶点。
签到
给定直线过点 $(0,0)$, $(a,b)$,求从 $(0,0)$ 出发,方向朝右,长度为一的线段的右端点。
一开始是二分硬做的,然后被卡精度了。
求出两点距离,对 $a,b$ 分别除于这个这个距离即可。
Continue reading “Atcoder Beginner Contest 246 解题报告”给定一个长度为 $n$ 的序列 $a$
求最大 $a_i|(a_j\&a_k)$ 满足 $i < j < k$
$3 \leq n \leq 10^6, 0 \leq a_i \leq 2 \cdot 10^6$
先考虑 $a_j\&a_k$,显然可以通过 SOS DP 来求出对于任意 $s$,其最靠后 $j$ 的能够有 $k$ 使得 $s \subseteq a_j\&a_k$ 的位置。
然后考虑贪心来最大化按位或,从高位往低位处理,如果能够有一位新为 $1$,则有限选择位数高的。
Continue reading “Codeforces 1208F Bits And Pieces”给定 $n$ 个长度为 $3$,字符集为 a-x
的字符串。
对于 $s, s \subseteq [ \texttt{a}, \texttt{x} ]$,有 $f(s)$ 表示有多少个给定字符串和 $s$ 交集非空。
输出 $\sum^{\oplus}_s f(s) * f(s)$
注意到基本上是 SOS DP 的模版,除一个问题 — 对于一个字符串可能会被统计多次。
简单容斥即可。
Continue reading “Codeforces 383E Vowels”