1 题意
在第 $i$ 天，如果 $\gcd(a,b) = m – i + 1$，那么 $a,b$ 之间会建立一条边
给定 $a,b$，求 $a,b$ 最早什么时候连通
多组询问，离线
$1 \leq n ,q \leq 10^5, 1 \leq m \leq n, 1 \leq a, b \leq n$
$n,m,q,a,b \in \mathbb{Z}$
POJ 3071 Football
1 题目大意
给定 $2^n$ 个整数，从 $1$ 到 $2^n$ 编号
给定 $p_{i,j}(1\leq i \leq n, 1 \leq j \leq n)$
定义一次操作为
选中 $2k$ 和 $2k+1$ ( $0 \leq k, k \in Z, 2k+1 \leq n$ )
其中有 $p_{2k,2k+1}$ 的概率选中 $2k$
其中有 $p_{2k+1,2k}$ 的概率选中 $2k+1$
把所有选择的数字组成一个新的数列，大小为 $\frac{n}{2}$
显然最后会只剩 $1$ 个数字
问剩哪个数字的概率最大
LibreOJ 2789 「CEOI2015 Day2」世界冰球锦标赛
题意
给定 $m$ 和一个长度为 $n$ 数列 $a$
一种方案为从 $a$ 中选择 $k (0 \leq k \leq n)$ 个数字出来（在一个方案中，每一位只能选择一次）
一种合法的方案为选择的所有数字加起来不超过 $m$
$n \leq 40$
AtCoder Regular Contest 084 D Small Multiple
题意
要求 $ x = ak(a \in N) $，定义 $f(x)$ 为 $x$ 在十进制下每一位数字的和
思路
一开始肯定想的是大力枚举，但是很快就可以发现大力枚举可以被卡掉，因为另一个数字可以非常大
然后就考虑缩小另一个数字的范围
一开始的思路顺着质因数分解走的，但是想了半天没有想出来
考后发现顺着质因数的过于复杂，我们可以直接考虑 $x \bmod k$ 意义下的情况
从 $ x $ 到 $ x + 1 $，答案显然增加 1
但是如果 x 一直加 1 会加到 10 ，这个情况答案在事实上没有增加 1
我们可以发现只有其在某一步变成 10 倍才会发生这种事件，那么再加一条边
从 $x$ 到 $10x$，答案不增加
这样就构成了一条图，从 $0$ 到 $1$ 的最短路就是所求答案
Continue reading “AtCoder Regular Contest 084 D Small Multiple”
Codeforces Round #666 (Div. 2) 题目大意 & 解题报告
即 Codeforces Round 1397
比赛链接: https://codeforces.com/contest/1397
A Juggling Letters
题目大意
给你 $n$ 个字符串，问能不能打乱成相等的三个字符串
思路
因为可以随意打乱，所以统计每个字母个数，只要每个字母的个数模 $n$ 余 $0$ 即可
Continue reading “Codeforces Round #666 (Div. 2) 题目大意 & 解题报告”
Codefoces #1382 解题报告 & 部分翻译
A Common Subsequence
0 题目大意
给你两个序列 $a,b$，求两个序列最短的公共子序列
1 代码
对，是最短……
AC 自动机 — LOJ 3089 「BJOI2019」奥术神杖
0 说在之前
我吐了，这题我写了两天……
考虑到我自己写的博客还没有 AC 自动机的，我会简单写一下
1 AC 自动机
1.0 什么是 AC 自动机
有一个说烂但是很形象的说法 Trie + KMP
AC 自动机用于多模式串匹配
就是你拿一个字符串，和一堆字符串
然后 AC 自动机可以让你快速的知道这一堆字符串中，那些是你这一个字符串的子串
重学后缀数组 — LOJ 2122 「NOI2015」品酒大会
0 说在之前
jt 学长说的没错，SA 果然是写一次忘一次……
于是这次重新学了一次，发现之前的 Blog 问题比较多，于是重写一次算了
实际上这些东西就是变相重写 Oi Wiki 后缀数组那一页，不过是写给自己的罢了
笔记 — 如何快速的配置一台新手机到我想要的样子
0 事出有因
因为老手机被拿来腾讯会议了，加之确实也算得上时代的眼泪了（
所以换了一台 Redmi K30 5G picasso
那么，开始迁移吧
1 选择 ROM
拿老账号一下就解锁了，没有等待时间，赞美小米
到 XDA 论坛上看一眼没有什么坏处
目测这个手机没有什么好包，Lineageos 都只有一个 alpha 的非官方版，还是 3 个月前的产物了… 详情看这个帖子
不过有一个 eu 版的 miui 包，走起 在这个帖子里
事实上 CN 版的 MIUI 也不错，不过人在 CN 身不由己。我相信小米有保护用户信息的决心（至少 MIUI 12 中可见一二），但是不清楚小米能不能做到。
而且 EU 版有 Google 全家桶，so why not?
随记 – Firefox 扩展
0 事出有因
之前手滑执行了一次命令，导致 Firefox 的配置文件没了
然后操作失误，把云端备份的插件列表搞没了
万幸的是目前整理到的损失似乎只有这些，那就顺便整理一下自己的插件吧
1 插件
1.1 美化
事实上，Firefox 默认主题挺好看的
配合 Arc Theme 可以得到更好的显示效果，何乐而不为
Firefox 默认的标签页有点单调。啥都不显示没意思，显示的东西又没啥用……
所以使用 Tabliss 是一个不错的选择
1.2 标签页
当你标签页血多的时候，Firefox 会在标签栏提供一个滚动条
虽然很人性化，但是明显不够用啊
使用 OneTab 可以归档标签页。毕竟一般开那么多个标签页，真正在用的也没几个
使用 Tree Style Tab 可以给以树形结构管理标签页，改变线性的标签页整理方式
1.3 屏蔽一些恼人的东西
广告屏蔽，比 AdblockPlus 快多了
配合 cobaltdisco/Google-Chinese-Results-Blocklist 使用，可以在 Google 屏蔽掉大部分 SEO 站
什么时候中文互联网的 SEO 站能少一点
1.4 功能扩展
暴力猴，在 https://greasyfork.org/zh-CN 或者是 Github 上搞到脚本后就往这东西里面放
我使用的脚本有这些
- the1812/Bilibili-Evolved Bilibili 的功能越砍越残缺了，破站迟早药丸。这个脚本可以 增强/美化 Bilibili 的页面，省得被 Bilibili 强奸大脑
- CSDN 净化 这没什么说的，CSDN 你马死了
- woshiluo/syzoj-copy-button 给 SYZOJ 增加 Copy 样例到剪切版的功能。
请问 syzoj-ng 什么时候好
用这个可以通过快捷键直接把选中内容送到 Google Translate 里
Aria2 Download Manager Integration
捕获下载链接，直接传给 Aria2
后台挂两个 Aria2，配合这个使用体验不错
不过，这个插件自带的 webui 不太可用，会自动覆盖设置
不过你都后台挂两个 Aria2 了，顺手搭个 httpd 挂个 Aria2 webui 应该也很简单
1.5 安全性
重写一些 http 请求为 https，防止某些网站/运营商耍流氓
Firefox Multi-Account Containers
对于国内的毒瘤，除了独立沙箱，应该没有什么防的住 ta 作恶的
这个插件提供了容器功能，你可以把你觉得不太行的网页每次用指定容器打开
终于不用隐私模式用 Baidu 了
2 一点设置
把性能里的线程调小点
Firefox 的个性化可以避免一堆插件挤在你得地址栏上，毕竟你经常会调整设置的插件也就那么几个
3 为什么使用 Firefox
这个问题实际上是没有答案的，浏览器这种东西比较偏个人。你喜欢那个，那个就是对的
不过这里还是给几个理由
Firefox 曾经是比 Chrome 资源占用少很多。
不过现在 Firefox 也用默认多线程了，这个优势虽然还有一点，但也不算多了
所以找几个这之外的理由
- 隐私，像比较 Chrome 这种商业公司搞出来的东西，Firefox 在隐私上面要优秀很多
- 便捷，Google 账号同步比 Firefox 的账号同步困难不少
- 为用户着想，至少不会像 Chrome 一样说搞广告屏蔽器就搞，说砍什么就砍
出于时间原因，没有能力给这几个理由找依据
如果你不相信我的话，那么关闭这个页面就好