T1 通配文件 下文  均表示 。 先考虑一个文件、一个通配字符子串，怎么判断合法的方案数。 定义  表示已经考虑完了字符串中的前  个点，目前将所有*替换之后匹配了目标文件前  个字符的方案数。 转移显然：当  为字母，若文件第  字符与  相等，则 ；如果  为*，则 。 单个时间复杂度 （暴力转移）或 （前缀和优化），总体时间复杂度  至 。 我们考虑将所有子串的贡献统一处理。 定义  表示已经考虑完了字符串中的前  个点，目前将所有*替换之后匹配了目标文件前  个字符的方案数总和。 那么转移变成：当  为字母，若文件第  字符与  相等，则 ；如果  为*，则 。最后，令 （新增一个子...

T1 矩阵交换   题目提到行排序后看每列内部的关系。因此自然的分析列内的性质。   如果则直接输出YES容易解决，考虑。   考虑以第列元素为关键字对行进行排序，形成了的序列。认为是三个区间，其中，    。此时考虑第列元素，，即第列形成的个区间在第列内要满足非递减关系。   总结下是：前一列形成了若干个区间在当前列满足非递减关系。   采用上述方法从第列推到第列，该问题解决。   T2 砖块摆放 把三种颜色分别当作 0、1、2 三种数字、 假设相邻两个砖块的颜色为 ，那么通过大眼观察法可以发现上面的一个它们上面的砖块等于   意义下 根据公式可以发现砖块中每个数字和二项式定理（杨辉三角系数...

T1 学习异或 20pt 由于只有一个数字，输出这个数字即可。 40pt 考察枚举法 枚举对哪一个数字进行异或，假设将  异或，那么修改 ，然后对整个数组进行求和。 100pt 考察求最大值。 不管是对一个数字求异或还是什么别的运算，总之本题只能对一个数字用一次操作，那么计算总和就很简单，我们只需要保存原来所有数字的和，再看看本次操作时这个数字的改变，就可以知道新的总和了。 本题需要知道最大的和，所以我们可以对每个数字都试一遍，看看谁和  异或之后能够变大得更多，也就是求所有  的最大值，其中  为异或运算。  最后两个测试点注意开 long long 求最大值的时候初始值不要设成 0，要设成...

T1 求余来咯 考察枚举答案 由于  较小，所以我们考虑枚举所有可能的答案 ，对于每一个  来说，用所有数字都进行求余，得到求余的和，同时记录最小值。 时间复杂度  #include <bits/stdc++.h> using namespace std; int a, cnt[5005]; int main(){ int n, minn = 1e9, ans, l, r; cin >> n >> l >> r; for(int i = 1; i <= n; i++){ cin >> a; for(int j = l; j &l...

T1 同色三角形 考察容斥定理和计算贡献的思想 本题在计算同色三角形数量，难以计算，可以用总数减去异色三角形的数量——任选三个点的方案数为 ，减去异色三角形，就是同色三角形数量。 对于某一个点而言，假设有  条红色边， 条绿色边，那么它对异色三角形数量的贡献——任选一红边 P 一绿边 Q，都可以确定一个三角形（因为这是完全图，所以 P Q 之间也一定有一条边，又因为 P Q 这两条边是异色的，说明这个三角形肯定是异色的） 计算贡献：那么也就是说这个顶点就会参与  个异色三角形的组成。 统计所有点的贡献 ，请注意：一个异色三角形上有两个点会被统计贡献，所以  才是异色三角形的数量。题目保证这样的...

T1 减法和求余 求余题 考察求余的性质 观察到  的式子中一定有 ，也就是说求余的结果一定小于除数。假设给定的  个数字的最小值是 ，那么假设  作为除数，那么此题的答案一定小于 ，所以我们应该让  作为被除数。也就是说用  求余所有其它数字。 再观察求余的性质，观察到  的式子中，假如 ，则 。因为  小于其它所有数字，所以用  做被除数去求余其它所有数字，得到的答案是 。 本题的关键：每个数字只出现一次。 所以本题等价于求解最小值，是一道 for 循环入门题。 减法题 通过大眼观察法可以观察到样例的性质：所有数字之和减去两倍的最小值。 T2 回文串 要求至多改两个字符： 首先考虑先通过修...

T1 填数游戏 10% 爆搜答案即可。 另外30% 意味着每个数都要填到格子里，那么有一个很直观的贪心想法，大的数匹配大的数，小的数匹配 小的数就可以使答案最大了。 50% 主要要意是鼓励选手思考比较简单的  做法。 可以做  的前缀 max 优化 dp 做法。可以拿到 50 分。 100% 考虑另外 30% 的贪心。但是因为有一些数可以不选的，所以可以把数分为大于 0 和小于 0 的。 首先肯定是负数和负数匹配，正数和正数匹配。然后余下的数按照大的和大的匹配，小的和小的匹配的原则匹配即可。 复杂度 ，注意开 longlong。 T2 摆渡车 权值线段树。 显然会选取  中数字最小的若干个数字...

T1 集合从 1 到 中每个数可选可不选，共有 个非空子集。现在考虑每个非空子集的和的贡献，子集和的取值范围是 ，可以 求每一种子集和的方案数，然后枚举子集和 ，我们又知道子集和的方案数 ，那么根据题意全部相乘就是 ，需要用快速幂解决。由于 较大的时候 数组会超过 long long 存储范围，而 数组是不能求余 998244353 的（它存储的内容的含义是 中的幂次 ）注意到子集和与模数 998244353 一定是互质的，所以考虑欧拉定理或者费马小定理，对 数组求余 。T2 出租考虑什么时候是无解的。当出现任意一段区间 的租户满足它们人数的和比 还多的时候，说明无论如何也无法给 中的所有人都...

T1 神秘金币 考察大眼观察法，由于 均不相同，而我们又可以每个时刻收集一枚金币，那么我们只需要选出前 大的金币，然后按照 从小到大的顺序收集起来就好了，不会有任何金币消失。 T2 学习乘法 考察乘法的性质 两个数字的和一定，大小越接近，乘积越大。 和一定是因为本题的交换数位只能交换相同的数位，所以交换之后的和是不变的。现在我们考虑如何使得两个数字 尽量接近： 从高位向低位开始看，假设对应位置相同，则继续看下一位，不同，那么我们可以钦定 b&preview=true">，也就是说把大的数字交换到  的当前位，小的数字给 。但是我们又希望两个数字尽量接近，所以我们应该将所有更低位...

T1 情景剧 对于 subtask1：  可以  暴力枚举每个区间。  对于 subtask2-3：  以防万一大家是  之类的解法。 以防万一大家开的 int 或者 long long。  对于 subtask4 ：  虽然大家应该基本上会但是还是多啰嗦几句 ? 因为要求的是某个达到最值的区间，一个思路是看拿个什么数据结构维护下，能不能得到所有区间的价值，另一个思路是考虑枚举其中一个值或两个值，然后贪心地让乘积最大。 这道题我们选择枚举最小值，因为最大值随区间扩大是不降的，所以在枚举最小值的情况下，一定是选取枚举值为最小值的最大区间，这样就只有  个可能为答案的区间。 对于每个值为最小值的区...

T1 学习求余 本题是考察加法、乘法、求余运算的综合题 观察  这个式子。 情况 1：如果  的话，那么 。这样的话，这道学习求余就变成了学习加法。 当然，此题是一道综合题，还需要学会乘法的性质才能做出此题——两个数字的和一定，差值越小，乘积越大。所以如果想要让乘积尽量大，那么肯定要让  尽可能地接近。如果  是奇数的话，那么可以写出这样的式子： ，答案就是  如果  是偶数的话，可以写出这样的式子： ，答案就是  情况 2：，那么 ，其中  表示  除以  的商，且至少为 2。显然，这样算出来的  值之和肯定没有情况 1 大，那么最终得到的乘积也没有情况 1 大，故舍弃这种情况。 T2 提取...

T1 喷泉   根据初中数学知识，可以知道，一个定点到圆上点的最大（小）距离等于其到圆心的距离加（减）半径的长度，而一个定点到一条线段的最大距离显然是到线段两端之一，最小距离是垂线段长度（题目保证垂足在线段上）。  于是输出圆心到线段距离减半径，到两端点的最大距离加半径即可。  别溢出了。  具体证明问初中数学老师，剩下的就是解析几何计算了。         #include <bits/stdc++.h> using namespace std; signed main(){ #define int long long int t, x1, y1, x2, y2, x3, y3,...

T1 复读   考察基础的字符串匹配， 表示当前匹配到 字符串的第 位， 表示当前匹配到 字符串的第 位，两两比较，如果 等于 ，说明一遍已经复制完了，从零开始重新匹配（题解中用取模表示这一效果）      #include<bits/stdc++.h> using namespace std; string s, t; int main() {     int T;     cin >> T;     while(T--) {         bool flag = 0;         cin >> s >> t;         for(i...

T1 制裁复读机   要注意的是：每次重复是当前数字之前的所有字符，而不是只重复单个字符或部分字符。  剩下的还是考察模拟能力：  开一个答案字符串。  每次循环，若为小写字母，则在答案字符串上加上当前字符。   若为数字，向后统计，并移动当前循环指针 ，将答案字符串复制拼接 次即可，其中 是数字大小。         #include<bits/stdc++.h> using namespace std; int t,n,tmp,pos; string a,b,c;  int main(){ cin >> t; while(t--){ cin >> n &...