折腾小记 – Service Worker

0 序

退役了,文化课了。于是每天写代码的时间连 20min 都没有了。

但我还是想写!那就整点乐子吧

1 Service Worker

The service worker is designed first to redress this balance by providing a Web Worker context, which can be started by a runtime when navigations are about to occur. This event-driven worker is registered against an origin and a path (or pattern), meaning it can be consulted when navigations occur to that location. Events that correspond to network requests are dispatched to the worker and the responses generated by the worker may override default network stack behavior. This puts the service worker, conceptually, between the network and a document renderer, allowing the service worker to provide content for documents, even while offline.

https://www.w3.org/TR/service-workers/#motivations

翻译一下就是

Service Worker 提供了一种在请求前进行处理的 Web Worker。开发者可以通过此技术来拦截并修改每一个请求,并通过访问缓存等方式实现在网络较差甚至离线情况下对网页的访问。

Continue reading “折腾小记 – Service Worker”

NOI 2022 游记 SP – 上海之旅

漫天闪烁的繁星
伴着我独自前行
越过光年的距离
照亮我的眼睛

化作繁星

0 启程

上海,中国对外开放的中心。

这场上海之旅来之不易。伴随着紧急疏散的要求,我和抹茶和 dyf_dyf 一同打的前往花桥,乘坐上海轨道交通 11 号线,前往上海。

Continue reading “NOI 2022 游记 SP – 上海之旅”

NOI 2022 游记

0 序

今年是最感到时间如白马过隙的。每天窝在机房看自己不会的东西,每天都在想明天要学什么新的东西,然后日子就一天天的过去了。

想学的东西还没有学完,CCF 要求所有选手先到昆山的通告倒是先来了。不管如何,参赛为重,只得踏上前往昆山的旅途。

1 愉快的七天

因为雅礼人的高铁经过温州 & 他们订票的时候也没带上我,我就自己整了个别的列车。

在 08 月 13 日到达的昆山。

一到昆山就跑去找 dyf_dyf 和 Lucky_Yukikaze 聊天。

整理一下情况是几乎整个新疆省队都在一起(除了 Arachv)。接下来的日子就很简单了,蜜雪冰城,Among us,写模版,聊天。

简单欢乐的日子永远过的很快,眨眼见就到了 20 号。

Continue reading “NOI 2022 游记”

Codeforces Round 1699 解题报告

考试链接: https://codeforces.com/contest/1699

考试的时候 30min 写完 ABC 发现 D 没几个人就摸了。考完看了眼 E 发现一眼切。最后竟然上分了,我大受震撼。

A The Third Three Number Problem

求能否找到任意三个数字 $a,b,c$ 使得 $(a \oplus b) + (a \oplus c) + (b \oplus c) = n$ 。
容易发现奇数根本不可能,偶数随便构造。

B Almost Ternary Matrix

给表格染色。使得对于任意一个格子,有且只有两个相邻格子和这个颜色不同。
2x2 为一个单位,交叉构造即可。

Continue reading “Codeforces Round 1699 解题报告”

虚树

用途

对于大多数情况,树中只有很少一部分点是对当前要处理的信息是有意义的。

我们可以在保留这些有意义的点,不破原树结构的情况下得到一个很精简的树,这样我们就不用遍历整颗树了。

这种做法就叫虚树。

Continue reading “虚树”

斯坦纳树入门

0 序

这个东西看了半天没想明白为啥不是最小生成树,然后发现最小生成树实际上是最小斯坦那树的特殊形式
— 最小生成树里的所有点都是关键点。

最小斯坦那树是指在一个无向图中,求其最小生成网络使得其

  1. 包含所有关键点
  2. 总权值在满足 1 的情况下最小。
Continue reading “斯坦纳树入门”

XJOI 2022 游记

-1 序

寄啦,哈哈。

今年是新疆维吾尔自治区第一次组织省选。

今年有很多神奇的事情,比如特派员换了,新疆成立竞赛组委会了,办省选了,有 $\frac{1}{3}$ 了,有实体 NOI Linux。当然也不都是好事,疫情精准防控的代表上海已经被奥米克戎攻陷,全国疫情更是此起彼伏,见不到头。这种情况下信息学竞赛还能基本上「出淤泥而不染」,维持较为正常的赛季流畅已是相当不易。

在疫情的限制下,XJOI 最终未能选择新疆大学作为考点,而是选择了一所高中 — 乌鲁木齐市第一中学。

Continue reading “XJOI 2022 游记”

Atcoder Beginner Contest 246 解题报告

A Four Points

题目大意

给定矩形的三个顶点,求其剩下的顶点。

思路

签到

B Get Closer

题目大意

给定直线过点 $(0,0)$, $(a,b)$,求从 $(0,0)$ 出发,方向朝右,长度为一的线段的右端点。

思路

一开始是二分硬做的,然后被卡精度了。

求出两点距离,对 $a,b$ 分别除于这个这个距离即可。

Continue reading “Atcoder Beginner Contest 246 解题报告”

Codeforces 1208F Bits And Pieces

题目链接:https://codeforces.com/contest/1208/problem/F

1 题目大意

给定一个长度为 $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$

2 思路

先考虑 $a_j\&a_k$,显然可以通过 SOS DP 来求出对于任意 $s$,其最靠后 $j$ 的能够有 $k$ 使得 $s \subseteq a_j\&a_k$ 的位置。

然后考虑贪心来最大化按位或,从高位往低位处理,如果能够有一位新为 $1$,则有限选择位数高的。

Continue reading “Codeforces 1208F Bits And Pieces”