洛谷B2042 判断一个数能否同时被 3 和 5 整除 题解
洛谷B2042 判断一个数能否同时被 3 和 5 整除 题解 题目链接:B2042 判断一个数能否同时被 3 和 5 整除 题目描述: 判断一个数 \(n\) 能否同时被 \(3\) 和 \(5\) 整除。 输入格式: 输入一行,包含一个整数 \(n\)。 输出格式: 输出一行,如果能同时被 \(3\) 和 \(5\) 整除输出 YES,否则输出 NO。 数据范围: \(-10^9<n<10^9\) 很容易想到取模两次,不过很显然这样是效率更低的,除法很慢、常数大。 注意到,如果一个数能同时被 \(3\) 和 \(5\) 整除,那么它一定可以写做 \(3\times 5 \times \cdots\) 的形式 于是我们只需要判断这个数是否能被 \(15\) 整除即可。 时间复杂度 \(O(1)\) 代码: #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f template<typename T> void ...
UVA511 Do You Know the Way to San Jose? 题解
UVA511 Do You Know the Way to San Jose? 题解 题目链接:UVA511 Do You Know the Way to San Jose? 题目描述: 互联网现在提供了多种交互式地图设施,用户既可以查看大范围地理区域的概览地图,也可以“放大”到某条具体街道,有时甚至能查看某栋具体建筑所在的更详细地图。例如,圣何塞市中心可能同时出现在加利福尼亚州地图、圣克拉拉县地图以及一张详细街道地图中。 假设你拥有大量矩形地图,并希望设计一个浏览设施,用来处理一系列针对不同地图细节级别地点的地图请求。地点使用地点名称表示。每个地点名称都有唯一的一对实数坐标 \((x,y)\)。每张地图都是唯一的,并带有用于标识的地图名称,且由两对实数坐标 \((x_1,y_1)\) 和 \((x_2,y_2)\) 定义,这两对坐标表示地图的两个对角点。所有地图的边都平行于标准笛卡尔 \(x\) 轴和 \(y\) 轴。地图和地点可以同名。地图的高宽比定义为其高度与宽度之比,其中宽度沿 \(x\) 方向度量,高度沿 \(y\) 方向度量。 一张地图的细节级别可以用该地图所表示的...
洛谷P1171 售货员的难题 题解 & 旅行商问题(TSP 问题)模板
洛谷P1171 售货员的难题 题解 & 旅行商问题(TSP 问题)模板 题目链接:P1171 售货员的难题 题目描述: 某乡有 \(n\) 个村庄,有一个旅行商 qry,他要到各个村庄去售货。 各村庄之间的路程 \(e(i,j)\) 是已知的,且 \(A\) 村到 \(B\) 村与 \(B\) 村到 \(A\) 村的路大多不同(有向图)。 为了提高效率,qry 从商店出发到每个村庄一次,然后返回商店所在的村。 假设商店所在的村庄为 \(1\),他不知道选择什么样的路线才能使所走的路程最短。 请你帮他选择一条最短的路。 输入格式: 第一行是一个整数,表示村庄数 \(n\)。 接下来 \(n\) 行,每行 \(n\) 个整数,第 \(i\) 行的第 \(j\) 个整数表示 \(i\) 到 \(j\) 的单向路径的距离 \(e(i,j)\)。 输出格式: 一行一个整数表示最短的路程。 数据范围: 保证 \(2 \leq n \leq 20,~1 \leq e(i,j) < 10^3,~e(i,i) = 0\)。 考虑状压dp。方便起见,把节点记为 \(0\) 到 \(...
洛谷P10447 最短 Hamilton 路径 题解 & 最小哈密顿路径模板
洛谷P10447 最短 Hamilton 路径 题解 & 最小哈密顿路径模板 题目链接:P10447 最短 Hamilton 路径 题目描述: 给定一张 \(n\) 个点的带权无向图,点从 \(0 \sim n-1\) 标号,求起点 \(0\) 到终点 \(n-1\) 的最短 Hamilton 路径。 Hamilton 路径的定义是从 \(0\) 到 \(n-1\) 不重不漏地经过每个点恰好一次。 输入格式: 第一行输入整数 \(n\)。 接下来 \(n\) 行每行 \(n\) 个整数,其中第 \(i\) 行第 \(j\) 个整数表示点 \(i-1\) 到 \(j-1\) 的距离(记为 \(a[i-1,j-1]\))。 对于任意的 \(x,y,z\),数据保证 \(a[x,x]=0,a[x,y]=a[y,x]\) 并且 \(a[x,y]+a[y,z] \ge a[x,z]\)。 输出格式: 输出一个整数,表示最短 Hamilton 路径的长度。 数据范围: 对于所有测试数据满足 \(1 \le n \le 20\),\(0 \le a[i,j] \le 10^7\) 。...
CF765F Souvenirs 题解
CF765F Souvenirs 题解 题目链接:CF765F Souvenirs 题目描述: qry 正在度假,想给两位队友买纪念品。街道上一共有 \(n\) 家纪念品商店。在第 \(i\) 家店里,qry 可以花 \(a_i\) 美元购买一件纪念品,但每家店最多只能买一件。 为了避免队友互相嫉妒,他希望购买的两件纪念品价格尽可能接近。 qry 总共逛了这条街 \(m\) 次。但在第 \(i\) 天时,只有第 \(l_i\) 到第 \(r_i\) 家店铺开门(听起来很离谱对吧?但为了设计区间查询题目的背景设定也只能这样了)。 对于每次逛街,qry 都想知道在当天开门的店铺中,能买到的两件不同纪念品的最小价格差。 换句话说,对于 qry 的每次逛街,你需要找出满足 \(l_i\le s, t \le r_i,s \ne t\) 时,\(|a_s - a_t|\) 的最小可能值。 输入格式: 第一行,一个整数 \(n\;(2\le n\le 10^5)\)。 第二行,\(n\) 个整数 \(a_1,\cdots, a_n\;(0 \le a_i \le 10^9)\)。 第三行...
洛谷P4767 [IOI 2000] 邮局 加强版 题解
洛谷P4767 [IOI 2000] 邮局 加强版 题解 题目链接:P4767 [IOI 2000] 邮局 加强版 题目描述 高速公路旁边有 \(n\) 个村庄。高速公路表示为整数轴,每个村庄的位置用单个整数坐标标识。两个位置之间的距离是其整数坐标差的绝对值。 现在要建立 \(m\) 个邮局,邮局将建在一些,但不一定是所有的村庄中。为了建立邮局,应选择他们建造的位置,使每个村庄与其最近的邮局之间的距离总和最小。 你要编写一个程序,已知村庄的位置和邮局的数量,计算每个村庄和最近的邮局之间所有距离的最小可能的总和。 输入格式 第一行包含两个整数,分别表示村庄的数量 \(n\) 和邮局的数量 \(m\)。 第二行共 \(n\) 个整数,表示每个村庄的坐标,第 \(i\) 个整数表示第 \(i\) 个村庄的坐标 \(a_i\)。 输出格式 输出一行一个整数表示答案。 数据范围 \(1\le m \le 300, m \le n \le 3000, 1 \le a_i \le 10000\) 。 先写了本题加强版,请参考 洛谷P6246 [IOI2000] 邮局 加强版 加强版 题解 。
Hexo 对Butterfly主题的自定义修改
Hexo 对Butterfly主题的自定义修改 本站目前使用的是 Butterfly 5.7.0 ,然后本文是记录我自己做了哪些代码层面的修改。 我注释掉冲突的原文本,然后加上自己加入的文本,下面的代码就都这么记录了。 本文不会与本站最新的方案修改方案保持一致,就是说很小的改动不一定会写在这,请各位自己摸索 标签页设计修改 效果: 如果你不想要这种黑白效果,下面的代码里改颜色的可以不用改,具体自己看吧。 只修改了 /themes/butterfly/scripts/helpers/page.js 中的以下段落 const generateStyle = (size, unit, page, color) => { // const colorStyle = page === 'tags' ? `background-color: ${color};` : `color: ${color};` const colorStyle = page === 'tags' ? `background-color: $...
洛谷B3621 枚举元组 题解
洛谷B3621 枚举元组 题解 题目链接:B3621 枚举元组 题目描述 \(n\) 元组是指由 \(n\) 个元素组成的序列。例如 \((1,1,2)\) 是一个三元组、\((233,254,277,123)\) 是一个四元组。 给定 \(n\) 和 \(k\),请按字典序输出全体 \(n\) 元组,其中元组内的元素是在 \([1, k]\) 之间的整数。 「字典序」是指:优先按照第一个元素从小到大的顺序,若第一个元素相同,则按第二个元素从小到大……依此类推。详情参考样例数据。 当 \(n=2,k=3\) 时就是下面这样 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 输入格式 仅一行,两个正整数 \(n, k\)。 输出格式 若干行,每行表示一个元组。元组内的元素用空格隔开。 数据范围 对于 \(100\%\) 的数据,有 \(n\leq 5, k\leq 4\)。 可以发现,我们每一行需要输出 \(n\) 列数字,并且输出的方式就像是套了 \(n\) 层循环,每层从 \(1\) 到 \(k\) 。 找到规律就知道怎么做了,考虑 dfs 来控制输出...
洛谷P14671 [ICPC 2025 Seoul R] Clean Arrangement 题解
洛谷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\) ,它的每个儿子...
洛谷P2210 Haywire 题解
洛谷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 & 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...





![洛谷P4767 [IOI 2000] 邮局 加强版 题解](/qwq/img/p96.webp)


![洛谷P14671 [ICPC 2025 Seoul R] Clean Arrangement 题解](/qwq/img/p140.webp)




![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p216.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p233.webp)

