本场全部题解见此 更好的阅读体验 C 牛牛的凑数游戏 题意简述 对于一个多重数集 ，对于一非负整数 ，若存在 且 中所有数字之和恰好等于 ，则说 可以表示 。 给定一个序列，多次询问一个给定的区间中的数构成的多重数集最小的不能表示出的数。 算法标签 题目性质发掘 主席树/树状数组 算法分析 我们发现直接处理多重数集很难，因此考虑其等价条件。 引理： 将一个多重数集升序排序，记为 ，求 的前缀和为 ，则第一个满足 的位置对应的数，即 为这个多重数集不能表示出的最小的数。 证明： 充分性显然， 只有可能由小于它的数的加和表示，因此仅可以使用 ，而将这些数都加起来都...

本场全部题解见此 更好的阅读体验 B 牛牛的猜球游戏 题意简述 有一个 的排列，初始为 。 有 次操作，第 次操作可以用两个数 表示，表示交换从前往后第 个数和第 个数。 现有多次询问，每次询问用 表示，询问一个初始排列在依次经过 中每一个交换操作后的排列。 算法标签 前缀和 线段树 置换 算法分析 一次操作的本质可以看做是一个排列到另一个排列的置换，而置换有结合律，因此可以直接上线段树维护，时间复杂度 。 更进一步，置换还具有可减性，因此我们可以直接用前缀和维护置换，时间复杂度 。 代码实现 考场上没想起来置换的可减性，就直接写了线段树，实现难度其实并不是很大。 #i...

本场全部题解见此 更好的阅读体验 A 牛牛的方程式 题意简述 给定 ，询问是否存在一组整数解 ，满足 。 多测， 。 算法标签 数论 同余 算法分析 如果只有两项，即 这种形式，可以直接套用裴蜀定理，该方程有整数解等价于 。 由上面的式子，我们不难发现， 可以表示所有整除 的数。 那么原方程有整数解等价于 有整数解。 同理，这个方程有整数解等价于 。 注意特判 ，即 的情况。 代码实现 #include<bits/stdc++.h> using namespace std; #define maxn 1000005 #define maxm 2000005 ...

这是T1-T4所有题目的题解综合。 更好的阅读体验 A 牛牛的方程式 题意简述 给定 ，询问是否存在一组整数解 ，满足 。 多测， 。 算法标签 数论 同余 算法分析 如果只有两项，即 这种形式，可以直接套用裴蜀定理，该方程有整数解等价于 。 由上面的式子，我们不难发现， 可以表示所有整除 的数。 那么原方程有整数解等价于 有整数解。 同理，这个方程有整数解等价于 。 注意特判 ，即 的情况。 代码实现 #include<bits/stdc++.h> using namespace std; #define maxn 1000005 #define maxm...