Q779’s Blog

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

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

肯定包括了本站几乎所有数学公式的写法

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

洛谷P14671 [ICPC 2025 Seoul R] Clean Arrangement 题解 题面链接：P14671 [ICPC 2025 Seoul R] Clean Arrangement 题目描述（简化版） 给出一棵 \(n (2\le n \le 5000)\) 个节点的树，根节点为 \(1\) 。 让你把所有节点映射到 \(1\sim n\) 的整数数轴上，边 \((u,v)\) 的新长度就是数轴上 \(u\) 和 \(v\) 的差的绝对值。 要求最小化所有边的边长和，并且边不能交叉、不能覆盖根节点（比如下图的图三就是不合法的）。 图一和图二是题目的样例2的解法。 输入格式 第一行输入 \(n\) ，接下来 \(n-1\) 行每行输入两个数 \(u,v(1\le u,v \le n)\) 表示存在一条边 \((u,v)\) 。 输出格式 一行，答案。 可以去 Csacademy 画一下然后玩玩看，很容易就能看出这个题怎么做了。 首先，像图三这种红线很明显是亏的，数轴有的是空间，你干什么放到这么远的地方去呢？ 进一步地，对于每个节点 \(u\) ，它的每个儿子...

C++语法 坑点总结 不保证本文内容完全正确，仅仅是个人总结！！暂时还没空整理，比较乱 islower，isalpha，isdigit 这种函数，返回值不是bool！！ 在不同的机器上跑出来是不一样的！！！！不要直接加上它！！! lower_bound(begin,end,x,greater<int>()) 返回第一个小于等于 \(x\) 的位置 去重 m=unique(b+1,b+1+n)-b-1; string 的 == 和 find() 是 \(O(n)\) 的！ 注意 char 数组后面有个 \0 ，因此多测一般不用清空，但是\0后面的不会被清空！ next_permutation(a+1,a+1+n) 是下一个排列！到了5 4 3 2 1这种就结束了！！ 同理有 prev_permutation(a+1,a+1+n) 凡是位运算都加个括号，比如 \(\&\) 的优先级比 == 还要低！！！（待考证） 判断两数的奇偶性是否相同不可以用异或！因为高位还有数！ __gnu_pbds的头文件可以用 #include <bits/extc++.h>...

洛谷P2210 Haywire 题解 题目链接：P2210 Haywire 题目描述 Farmer John 有 \(N\) 只奶牛（ \(4 \leq N \leq 12\)，\(N\) 是偶数）。 他们建立了一套原生的系统，使得奶牛与他的朋友可以通过由干草保护的线路来进行对话交流。 每一头奶牛在这个牧场中正好有 \(3\) 个朋友，并且他们必须把自己安排在一排干草堆中。 一条长 \(L\) 的线路要占用刚好 \(L\) 堆干草来保护线路。 比如说，如果有两头奶牛分别在草堆 \(4\) 与草堆 \(7\) 中，并且他们是朋友关系，那么我们就需要用 \(3\) 堆干草来建造线路，使他们之间能够联系。 假设每一对作为朋友的奶牛都必须用一条单独的线路来连接，并且我们可以随便地改变奶牛的位置，请计算出我们建造线路所需要的最少的干草堆。 输入格式 第 \(1\) 行：一个整数 \(N\)。为了方便，我们给奶牛用 \(1\sim N\) 的数字进行编号。 第 \(2, 3, \cdots, N + 1\) 行：每一行都有三个在 \(1\sim N\) 中的整数。第 \(i+1\) 行的数...

排版表示证毕的小方块 如果直接用 $\square$ 的话，会出现这样的情况 证明 这是一些文本。\(\square\) 虽然能看懂，但是非常不好看。现在给出一个非常简单的办法。 直接在你写的 markdown 文本后面加上 <span style="float: right;">$\square$</span>就好了 注意不要换行，直接跟在后面就行了。实际效果如下： 证明 因为所以，对对对。 然后呢，啊对对对，嗯。\(\square\) 目前不知道兼容性如何，反正我用的 Typora 和 Hexo 都能正常显示，那我就懒得管了。

洛谷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\ap...

洛谷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\) 分。 赛季结束后，联赛将宣布总积分最高的球队为冠军。如果两支或更多球队的总积分相同，则总净胜球（用所有联赛比赛中的总进球数减去总失球数计算）最高的球队将成为冠军。最...