最近几天讲临项交换，突然想到以前洛谷网校模拟赛做到了这么一个有意思的题目，然后找了一下午，好几次都略过了这道题目但是就是没看出来就是我要找的那道题。开原题机发现是这道题目。 ▶INFO 题面 T529359 放的是网校的题面，题号也是网校的题号，防止自己忘记。和 QOJ 7787 是一道题目

▶INFO 题面 圣诞节到了，小 P 很孤独。 他只有一棵光秃秃的圣诞树，所以他决定玩玩它。不幸的是，这棵树被玩坏了，所以小 P 想将它复原。 小 P 的圣诞树是一棵 个节点的树，每个点是一个小球，第 个球上面有 个孔，孔之间是有区别的。小 P 需要用 条绳子将这些点连成一棵树。每个

▶INFO 题面 有 个物品，每个物品可以用二元组 表示，代表物品的体积、单价。 有若干个大小为 的背包，每个背包能装下任意多个体积和不超过 的物品，此外使用一个背包还需要花费代价，代价是此背包内所有物品单价的最大值。 现在，你需要将这 个物品放入任意多个背包中，使得所有背包的代价

看到一个视频才发现自己似乎对 C++17 之后的新特性不是很了解。这片文章记录了我发现的一些有趣的新特性。 本文的特性都是 C++17 之后的特性，而 NOI 系列赛事使用的是 C++14，请勿在考场上使用这些特性（目前最新版本的 GCC 默认标准是 C++17，要使用 C++14 需要手动指定 -std=c++14）。 C++17 C++14 之后的第一个版本。 inline 变量 继内联函数之

太困了，所有数据结构都忘光了，所以这个做法没什么数据结构。 首先我们发现，假如 ，考虑将 重排后的数组 满足 。显然，一个序列的 是非单调递减的，因此整个序列的 在第 项之后就没有变过。考虑将所有数除掉整个序列的 ，这样前 项的 就非 而后面的就全是 。 显然我们可以考虑枚举前 项的 ，如果有 个数整除这个 ，那我们就把这 个数放前面，答案至少为 。因此考虑维护一个数组 ，表

本文用 表示轮换位置 的元素（即，），用 表示交换位置在 的元素。 假如我们要进行的轮换是 。由鸽巢原理可知， 三个数中必有两个数是相同的元素。假如 ，我们可以将这个轮换写成 的形式。注意这个轮换和原来的轮换实际上是一个，相同的位置最终到的位置是不变的（可以代入试一下）， 的情况类似。因此任意轮换都可以写成 满足 的形式。 轮换有一个性质，，证明方法就是每个元素都代进去试一下。由于

本文记载了我看到这题时抽象的思路历程。 看到这个题目，首先花了 分钟否决掉了直接跑最短路的想法，因为你不好定义两个结果的序关系。 然后，开始考虑一种经典的优化方式，费用提前计算。注意到每个点的贡献和之后的边数有关，因此考虑 表示点 到第 个点，距离最后一个点距离为 的最小代价。那么转移的代价就是这个点的点权乘上距离。但是，我们发现，这是一张无向图，我们不好找到一个很好的顺序来转移（这对吗

写模拟赛的一道 F 题时想到的题目。但是这道题解法和那道题完全不同。 容易想到线段树优化建图，但是此题需要额外处理一个边权不同的问题。注意到这个距离函数有个美好的性质，对于任意 ，满足 。 我们考虑把一个点拆成两个点， 和 ，分别表示从左边和从右边到达 点。在这两个点之间连一条边权为 的双向边。 考虑一个点向右侧区间连边的情况。我们把边权拆成若干份。一个点 向线段树上节点 连边时，相当于先

首先可以将 与上一个非负的位置做差，得到这一段咖啡的数量。我们考虑维护每一段的数量，然后将这些段拼起来。我们记 表示以 开始的段，第一个位置和最后一个位置是否是咖啡的方案数。 我们先考虑从 个位置里选出 个不相邻的位置的方案数。考虑换个角度，不是从 个里面选出 个，而是将 个位置插入到剩下 个位置中间。 个位置之间有 个空位，因此答案就是 。 假如我们要钦定开头的位置必须是茶壶

题意简述： 给定 个数的数组 （），从中选出不相交且互质的两对数或输出无解。 首先不难想出一个 的解法，那就是枚举每对数尝试找到一组解。但是你注意到一个数需要花 的时间来枚举，如果没找到一组解这个时间就是十分浪费的。 考虑如何快速判断在数组里一个数是否在数组里有与其互质的数，有的话再枚举。这样最多只要枚举 遍。考虑将原问题强化，计算一个数在数组里与其互质的数的个数。 我们又注意到前