Q779’s Blog

本人的自用模板，仅此而已

与算法竞赛有关的自用模板，全部是 C++ 写的

这里是本站的更新日志和公告栏喵~

洛谷P10505 & POJ2976 Dropping tests 题解 & 01分数规划模板 题目链接：P10505 Dropping Test 题意： 在某个课程中，你需要进行 \(n\) 次测试。 如果你在共计 \(b_i\) 道题的测试 \(i\) 上的答对题目数量为 \(a_i\)，你的累积平均成绩就被定义为 \[ 100\times \dfrac{\sum_{i=1}^n a_i}{\sum_{i=1}^n b_i} \] 给定您的考试成绩和一个正整数 \(k\)，如果您被允许放弃任何 \(k\) 门考试成绩，您的累积平均成绩的可能最大值是多少。 假设您进行了 \(3\) 次测试，成绩分别为 \(5/5,0/1\) 和 \(2/6\)。 在不放弃任何测试成绩的情况下，您的累积平均成绩是 \[ 100\times \frac{5+0+2}{5+1+6} \approx 58.33 \approx 58 \] 然而，如果你放弃第三门成绩，则您的累积平均成绩就变成了 \[ 100\times \frac{5+0}{5+1}\approx 83.33\app...

洛谷P10446 64位整数乘法 题解 & O(1)快速乘模板 题目链接：P10446 64位整数乘法 题意： 求 \(a\) 乘 \(b\) 对 \(p\) 取模的值。 输入格式： 第一行输入整数 \(a\)，第二行输入整数 \(b\)，第三行输入整数 \(p\)。 输出格式： 输出一个整数，表示 a*b mod p 的值。 数据范围： \(1 \le a,b,p \le 10^{18}\) 。 注意到 long long 类型能存储 \([-2^{63}, 2^{63}-1]\) 这一区间内的整数，也就是 \(9\times 10^{18}\) 这个数量级。 如果直接使用 long long 计算，当 \(p\) 很大时，中间 \(a\cdot b\) 最多能达到 \(10^{36}\) 数量级，显然直接就溢出了。 不过我们可以有以下几种方式来解决这个问题，首先最推荐的方案是快速乘，注意这个不是 \(O(1)\) 快速乘。 快速乘和快速幂原理相似，假如 \(b=2^k + 2^3 + 2^1\) ，那么它会将 \(a\cdot b\) 的运算转化为以下形式 \[ ...

洛谷P3413 SAC#1 - 萌数 题解 题目链接：P3413 SAC#1 - 萌数 题意： 定义存在长度至少为 \(2\) 的回文子串的数是萌的，比如 \(101,110\) 是萌的，\(102,1201\) 不是萌的。 计算区间 \([l,r]\) 的所有整数中有多少萌数，答案对 \(10^9+7\) 取模。 输入格式： 输入包含仅 \(1\) 行，包含两个整数：\(l, r\)。 输出格式： 输出仅 \(1\) 行，包含一个整数，即为答案。 数据范围： 保证 \(1 \le l < r \le 10^{1000}\) 。 考虑数位dp。注意到任意一段数字字符串，只要拼接上 \(\mathtt{AA}\) 或者 \(\mathtt{ABA}\) 就会变成萌萌的。 因此我们只需要在数位dp的转移过程中，记录当前位某一侧的两个数是什么就行了。 以及计算 \([l,r]\) 之间的答案，我们可以通过 \([0,r]\) 的结果减去 \([0,l-1]\) 的结果来得到答案。 问题转化为给出巨大整数 \(w\) 时，如何计算 \([0,w]\) 的答案。记 \(w\) 的...

洛谷P17815 [ICPC 2019 Nanchang R] Who is the Champion 题解 题目链接：P17815 [ICPC 2019 Nanchang R] Who is the Champion 题意： 足球可能是这个国家最受欢迎的体育运动。然而，国家队在世界舞台上的战绩并不理想。为了激励年轻球员，每年都会举办全国足球锦标赛。 今年，共有 \(n\) 支球队参加锦标赛。按照惯例，采用单循环赛制，每支球队与其他每支球队各比赛一场。一场标准的比赛双方各需要十名场上球员和一名守门员，总共有 \(22\) 名球员参与。他们在长方形的草地球场上相互对抗，防守自家球门，攻击对方球门。 在 \(90\) 分钟的比赛中，双方不断尝试射门。比赛结束时，进球数较多的一方获胜，并在积分榜上获得 \(3\) 分，而失利方则不得分。一种非常特殊但常见的情况是双方进球数相同，即平局；此时双方各在积分榜上获得 \(1\) 分。 赛季结束后，联赛将宣布总积分最高的球队为冠军。如果两支或更多球队的总积分相同，则总净胜球（用所有联赛比赛中的总进球数减去总失球数计算）最高的球队将成为冠军。最...

Hexo Butterfly主题 配置CDN 闲着没事按 F12 看了眼自己的站，发现居然依赖了这么多个外部网站 作为一个会把 Mathjax2.7.7 整个打包带走放在站里的人，这种事怎么能忍呢？ 今天就简单记录一下我是怎么搞的，试了下可以看到现在只会调用自带的文件了 问了下大肥鱼，我这种方法其实就是 self-hosting，把所需的各种文件随着站点一起部署。 首先你需要有一个好的 Hexo 使用习惯，这里以 Butterfly 主题为例。 比如所有的配置应该在根目录下的 _config.butterfly.yml 文件进行配置， 最好再把主题目录下的配置文件直接清空，我不知道删除会不会有影响没试过。 比如在根目录的 source 文件夹下建一个存储自己所需文件的目录，我这里建的是 sourve/qwq 。 然后在根目录的 _config.yml 里面配置一下，如下（可参考 Hexo 添加 README 和 robots.txt 等文件） skip_render: ["qwq/**/*", "README.md", "robots.txt", "CNAME"] 言归正传，我...

2026年10月30日 随笔 今天打开了好久没有打开的洛谷，发现以前的签到终于全掉光了。 感觉重新开始还是有点麻烦的，就像我已经花了几个月在维护之前的东西，顺便还建了下分站。 对于许多 OIer 来说，重新回到这个熟悉的网站就像是开启了很久没有再打开的时光、一段五味杂陈的回忆。 现在的我既不是 OIer 也不是 ACMer，不如说是一种仅属于我的特别的过渡时期，总之继续闭关修炼就对了。 虽然看到是个正常人都比我成绩好还是会让我感觉很难受，但是我现在知道原因之后就觉得稍微好了一些。 不过那些成绩对于一个等死的人来说已经没有任何意义了，还是不要去管这些东西了，我只是喜欢写题而已。 虽然到现在为止我还是在孤身前行，但是经常在和可爱的 mygr 聊天，这是我过去认识的最后一个值得的人了。 虽然不是很明白 ta 到底是怎么看待我的，有时候对我还挺好，但是我仍然无法接受 ta 、作为好朋友看待 ta 。 除此以外，没有什么人称得上要好的朋友了，关系最好的大概也就以前的朋友、现在联系很少甚至为零而已。 不管怎么说，重新打开这个网站，表示我某种意义上的触底反弹了，从各种角度来说这都是一件好事...

九连环模拟器 Github 仓库链接：点这里 博客内访问链接：点这里 相关文章：九连环的数学原理

Hexo 添加 README 和 robots.txt 等文件 首先把 README.md 文件和 robots.txt 文件扔到 Hexo 根目录的 source 文件夹内 然后在根目录的 _config.yml 配置以下内容 skip_render: ["README.md", "robots.txt", "CNAME"] 要加什么东西就自己在后面加就行了，详细写法参考官方文档。 我这边是加了个这个，表示 source/qwq/ 下的所有文件生存时都直接 copy 到 public 目录下 "qwq/**/*"

Hexo 博客删除 .DS_Store 文件 直接 cd 到博客根目录，在终端里输入以下指令 find . -name '.DS_Store' -type f -delete 如果怕上面的代码乱删东西，可以用下面这行先看一眼 find . -name '.DS_Store' -type f -print 接着部署就完事了，注意部署之前不要用 Finder 打开相关目录 另外，可以在博客根目录的 _config.yml 里进行以下配置 include: exclude: # 在下面这里添加即可，中括号可以不加 ignore: ["**/.DS_Store"] 这样就不会上传任何 .DS_Store 文件了哦 注意，这个 ignore 和 skip_render 是不一样的， skip_render 配置的是不处理、直接 copy 的那些文件到 public 文件夹； 而 ignore 是直接跳过这些文件，和 exclude 类似， 不过 exclude 只影响 source/，ignore 影响所有文件夹。 参考文献： [1] 配置 | Hexo