Sophonの博客

题意 输入一个整数 \(n\) ，一个字符 \(c\) 和一个长度为 \(n\) 的字符串 \(s\)。 选择若干个数 \(x\)，对于 \(s\) 的第 \(i\) 个字符 \(s_i\)，如果 \(i\) 不能被 \(x\) 整除，\(s_i\) 就会被替换为 \(c\)。 求最少的操作次数和任意一种方案。 思路 本题的关键是，不论 \(s\) 的内容如何，答案最多只为 \(2\)。因为选取了 \(n\) 和 \(n - 1\) 后肯定会将 \(s\) 的所有字符全部变成 \(c\)，所以只需要考虑是否只需要一步就能解决问题即可，如果不能就直接输出 2 和 n n - 1。 对于只需要一步的情况，直接枚举即可，复杂度 \(O(n \ln n)\)。 代码 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<iostream>using namespace std;const int MAXN = 300000 + 5;cha ...

题意 有 \(n\) 个玩家和 \(m\) 句话，每个玩家可能是船员或内鬼，每句话的形式为“玩家 \(i\) 说玩家 \(j\) 是船员/内鬼”，求最多可能有多少个内鬼。（如果自相矛盾，输出 \(-1\)。） PS：题目背景出自国外的著名游戏 Among Us ，中文名为《我们之中》，也被叫做《内鬼杀》或《太空狼人杀》。游戏背景设置于太空，玩家将扮演船员（英语：Crewmate）或内鬼（英语：Impostor）之一。船员的目标是找出伪装者并完成任务，而伪装者的目标是杀死所有船员而不被发现。 思路 这种题目很容易让人联想到并查集。就像 NOI2001 食物链 一样，这道题可以用“扩展域”并查集来解决。 用 \(x\) 表示玩家 \(x\) 是船员，\(x + n\) 表示船员 \(x\) 是内鬼。 对于一句话，如果是“玩家 \(x\) 说玩家 \(y\) 是船员”，就意味着： 如果这句话为真，那么玩家 \(x\) 和玩家 \(y\) 都是船员。 如果这句话为假，那么玩家 \(x\) 和玩家 \(y\) 都是内鬼。 同理，如果是“玩家 \(x\) 说玩家 \(y\) 是内鬼”，就意味着 ...

引言 对于很多想要了解函数式编程（Functional Programming）或者是 Haskell 的 OIer 而言，Monad 是一个非常不友好的概念，但当你理解了它之后你就会不理解为什么你之前不理解它（ 一个单子（Monad）说白了不过就是自函子范畴上的一个幺半群而已，这有什么难以理解的？ （上面这句话其实并不是 Monad 的严格定义，因为是“自函子范畴上的一个幺半群”的东西不一定是 Monad，比如 Applicative 也符合上述定义。） 由于 Monad 这一概念本身对新手并不友好，大众 Monad 的误解有一箩筐，包括但不限于： Monads are impure. Monads are about effects. Monads are about state. Monads are about imperative sequencing. Monads are about IO. Monads are dependent on laziness. Monads are a “back-door” in the language to perform si ...

Hexo 博客的自动部署 使用 Hexo 发布博客最原始的方法自然是直接编辑完文件后 hexo clean && hexo g && hexo d，但这种做法长期来看存在以下问题： 迁移不便，在其他地方编写博客时，要么把笔记本背着到处跑，要么将整个文件夹复制到 U 盘里然后带着，并且事后同步博客也很不方便。 需要在本地配置 Node.js 环境，并且可能因为 Node.js 出现各种奇奇怪怪的问题。 本地部署消耗资源。 所以自动部署就成了 Hexo 博客的常见部署方式。 CI / CD 服务 常见的自动部署服务有 Travis CI、Netlify、Vercel 等，但这些自动部署服务大多在国内访问都不通畅，部署到 GitHub Pages 则需要通过 Token 这种不安全的方式。相较之下，GitHub Actions 就脱颖而出了：它是 GitHub 直接集成的！这就意味着 GitHub Actions 可以直接使用 GitHub 仓库的密钥，用 SSH 推送到 GitHub Pages 仓库。并且 GitHub Actions 的速度也足够快， ...

缘起 上一篇文章中提到了利用自定义域名搭建可以在国内访问的 Blogger 博客的方法，但经过讨论和测试，这个方法存在以下几个问题： 文章中的图片等资源会被 Google 服务器自动缓存。对国外的用户来说，这一机制可以大大提高页面加载的速度，但对国内用户来说则恰恰相反。目前除了在 Markdown 编辑器的预览中直接复制富文本外还没有别的解决方案。 地址 ghs.google.com 并不一定能解析到一个国内可以访问的地址。虽然只要使用自定义域名就可以规避 DNS 污染和 SNI 阻断，但是 Google 的服务器受到的是特殊待遇，直接针对 IP 地址进行阻断，自定义域名也经常抽风。 反观另一个同样无法访问的网站 Pixiv，网上给出的解决方案是直接在本地运行 Nginx 进行反代就可以访问。这个解决方案本质上是利用了 SNI 协议的漏洞，即为了区分前往同一地址的不同域名，SNI 协议中会以明文展示你需要前往的域名。明文展示显然会导致在特定的地区访问不稳定等种种问题，所以互联网领域的开发者们创造了 ESNI，后来又再 ESNI 的基础上创造了 ECHO，然后是 ECH……然而根本问 ...

关于 Blogger 阮一峰曾经提出过博客的“三个阶段”理论： 第一阶段，刚接触Blog，觉得很新鲜，试着选择一个免费空间来写。 第二阶段，发现免费空间限制太多，就自己购买域名和空间，搭建独立博客。 第三阶段，觉得独立博客的管理太麻烦，最好在保留控制权的前提下，让别人来管，自己只负责写文章。 这一理论在现实中未必正确，因为在有个人服务器的情况下，更多的人还是愿意选择 WordPress 或 Typecho 等自建的动态博客。但在没有服务器时，按照阮一峰老师的说法使用 Hexo、Jekyll 等静态页面生成器并部署在 GitHub Pages 上同样不失为一个好的选择，但所需要的技术对部分人并不友好。 所以部分人更愿意在简书、CSDN 等博客平台上写作，由博客平台直接提供软件，自己只需要写作内容。这类博客平台的优点是便捷，SEO 好，缺点是界面单调，广告繁多，并且有时内容并不由自己控制。博客园是这类平台中较为优秀的一个，可以自定义网页样式，吸引了大量的用户，但前段时间的网站整改让很多人心寒。相较之下，Blogger 创立二十余年，作为世界上最早的博客平台之一，在被 Google 收购 ...

缘起 第一次接触 Hexo 是在一片教程上，当时采用的是教程中使用的 Next 主题。作为一款非常流行的 Hexo 主题，Next 确实十分优秀，外观简洁且功能完备，但在网络上还是太千篇一律。后来又改用了 Material 主题，但因为该主题长期未更新，换成了风格类似的 Melody 主题，过了一段时间又换成了基于 Melody 但功能更丰富的 Butterfly 主题。 博客美化就和 Linux 桌面美化一样纠结。 为什么要自己写 当你看到你用的主题出现在两个以上的博客的时候，那你就要考虑自己写一个了。 ——《Hexo 主题开发指南》 这句话或许太过暴论，但确实说明了一点：博客主题应该是自己个人需要的主题，而不是直接从流行的教程上复制。虽然 Butterfly 主题功能丰富而且美观，但抱着写一个完全符合自己审美的主题以及锻炼前端水平的想法，最终仍然决定进行 Ringo 主题的开发。 但说来说去还是在用别人的设计。 Ringo 过程 Ringo 主题最初来自 memset0 开发的 Typecho 主题 typecho-theme-ringo。但贫穷的 Sophon 并没有多余的零 ...

缘起 因为更新后的的butterfly主题需要新版的Hexo，所以将Hexo更新到了5.4.0。但直接npm install hexo产生了一堆Warning，修改package.json有可能会破坏依赖。查找了相关资料后才得知更新Node.js项目需要使用npm-check和npm-upgrade两个包。 更新 安装 12npm install -g npm-checknpm install -g npm-upgrade 使用 运行npm-check会检测可用的更新。 12345678910111213141516hexo 😍 UPDATE! Your local install is out of date. https://hexo.io/ npm install --save hexo@5.4.0 to go from 5.0.1 to 5.4.0hexo-abbrlink 😕 NOTUSED? Still using he ...

题意简述 求不定方程： \[\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}\] 的正整数解 \((x, y)\) 的数目。 题目分析 数学推导 这道题给人的第一印象是难以解决，因为\(n!\)是一个很大的数，不可能一一枚举答案。所以我们必须对题目中给出的式子进行处理。 \[\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}\] \[\frac{x + y}{xy} = \frac{1}{n!}\] \[n!(x + y) = xy\] 可得 \(x \geq n!, y \geq n!\)，代入\(x = n! + a, y = n! + b\)得 \[n!(n! + a + n! + b) = (n! + a)(n! + b)\] \[n!(2(n!) + a + b) = (n!)^2 + n!(a + b) + ab\] \[2(n!)^2 + n!(a + b) = (n!)^2 + n!(a + b) + ab\] \[(n!)^2 = ab\] 因为每一组不同的\((a, b)\)都对应一组正整数解\((x, ...

前置知识 莫比乌斯反演 上面的标题应该改为后置知识 前言 最近在嗑莫比乌斯函数时嗑到了这个知识点，本质上是一个经常与莫比乌斯反演一起出现的小技巧，包括在很多莫比乌斯反演的题目中。 算法过程 整除分块通常被用来处理类似下方的式子： \[\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor\] 暴力 首先我们可以暴力解决： 1234int ans = 0;for(int i = 1; i <= n; i++) { ans += n / i;} \[N \leq 10^9\] 然后就歇菜了 规律 我们可以通过打表的方式来寻找\(\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor\)的规律 当\(n=5,sum=5+2+1+1+1\) 当\(n=9,sum=9+4+3+2+1+1+1+1+1\) 当\(n=12,sum=12+6+4+3+2+2+1+1+1\) 可以看到有很多数是重复的，当\(n\)更大时，重复的数会更多。可以证明，这些数的数量是\(O(\sqrt{n})\)的。换句话说，我们可以将每一段连 ...