题意 给你一个长度为的数组，求数组中元素两两之差的绝对值之积。但是乘积可能会很对，所以对进行取模后输出。 题解 先看数据范围，由于较大，但是模数较小。根据鸽巢原理\抽屉原理，当比大时，必存在两个元素对取模后相等，也因为。所以可以认为当大于时，答案肯定为。那么对于小于的部分我们只用去模拟运算一遍即可。 复杂度 时间复杂度或 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int a[N]; int main() { int n,m; long long ans = 1; scanf(&quo...

题意 给你一个长度为的数组，从数组中选择两个元素且，使得最大。 题解 首先我们可以将数组进行排序，对于一个数，若他作为模数能得到的余数范围在，所以能得到的最大值就是，那么由于取模的性质都是可以得到这样最大的值的。也就是说，我们需要去找倍数左边的数，即比倍数稍微小一点的数，这样的数对取模后能得到较大的余数。那么我们可以对排序的数组中去寻找比倍数小的第一个数，这里用利用二分去寻找，若是c++可以利用来找这个数。对于每个数我们遍历一变其所有的倍数就可以了。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> using namespace std; const i...

题意 给你一个组合数，下面进行游戏，牛牛作为第一个人，选择一个，要求且整除，并将传给下一个人。若当前人手上的数字等于了，游戏则结束，问最多能让多少个人参与进来。 题解 考虑最多的人参与进来的话就需要每次的尽量要小，所以取组合数的质因子就好了，也就是问题转化为了求组合数有多少个质因子。由于组合数实际上是阶乘的乘除，那么质因子的个数也就是阶乘质因子的加减了。那么可以考虑预处理阶乘的质因子。考虑每个质数作为因子的贡献，在将质数筛出来的同时存入数组中。  for(int i=2;i<N;i++) { if(dp[i]==0) { for(int j=i;j<N;j+=i)//考虑每个i的倍...

题意 给你一个长度为的数组，数组中若相同的数字相邻那么他们是联通的，即时，若修改其中一个数字，其他相同且联通的数字就会一并修改为相同值，每次操作可以选择一个数字进行修改，问最后让数组统一为一个数字，最少的修改次数是多少次呢。 题解 考虑区间。设为从统一为同一个数字时的最小操作次数，我们可以再创建一个辅助数组，数组记录的是一共有多少块不同的区域，即将原数组中所有联通部分看作一个数字。原问题就转化到了数组上的问题,那么可以得到转移方程： if(b[l]==b[r]) dp[l][r]=dp[l+1][r-1]+1; else dp[l][r]=min(dp[l][r-1],dp[l+1][r])+...

题意 给你个整点，两点之间能够形成一条直线，问所有的直线当中，相交的有多少对呢。 题解 考虑一共由多少条直线有条不同的直线，然后在考虑有多少条直线的组合呢。条直线组合，所以答案会超过范围需要开。那么考虑如何去求有多少条直线相交呢。考虑直线的一般式。若两条直线平行那么他们的就会相等，我们可以开个来映射有多少条直线是平行的。在我们遍历直线的时候，我们可以考虑这条直线的贡献是多少，为当前枚举过的直线数减去和当前这条直线平行的直线数。这是当前这条直线的贡献。这样计算每条直线的贡献就不会算重和算露了。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using na...

题意 给定一个的迷宫，迷宫由和组成其中表示可以出发去探索的初始位置，表示可以走的地点。求由每个出发所能经过的所有地点数量，并数量对10取模后替换后输出。 题解 若对每一个进行再进行替换的话肯定会超时。那么考虑进行预处理后再进行替换，对于可以看成一个联通块。我们先对进行，对于相连的联通块存入整个联通块的大小，这方面可以利用和实现，预处理完的联通块之后对于查询复杂度就会变成。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int N=1e3+5; int dx[4]= {1,-1,0,0}; int dy...

题意 给一个长度为的数组，每次可以选择一个，让。问操作多少次，最终得到的数组。 题解 最简单的一个方法就是让数组总的，那只要让所有的数变为偶数即可。那么我们可以考虑相连两个数的不同情况。$  和都为偶数，那么不需要进行操作。 和都为奇数，对于操作来说就是两个奇数进行加减，两个奇数的加减得到的都是偶数，所以只需要操作一次就可以了。 为奇数为偶数，奇数减偶数为奇数，偶数加奇数变为奇数。所以操作一次和都变为奇数，再操作一次可以都变为偶数。 为偶数为奇数，由于要求操作次数最少，那么不与进行操作，优先与进行判断，若，那么只能进行两次变化变为偶数。复杂度 时间复杂度代码 #include<bits/...

题意 给定个对，表示花费可以获得的能力，能力表示可以往前或往后跳步，一开始在问可以跳到任意位置的话需要的最小花费。若无解输出 题解 若要能够跳跃到任意一个位置需要能力能够凑出来往前或往后跳，例如，可以往前跳再往后跳可以实现跳。再转化一下就可以发现，若使用的能力集合，整个的最大公约数为，就可以实现跳跃到任意一个位置了，那么题意转化一下就变成，找到花费最小的集合使得集合的为。这就可以考虑用动态规划了。我们用来存储之前遍历获得的集合出现过的。若新的未出现过，那么就直接记录，否则判定一下新的值的花费和原先花费哪个小。 复杂度 时间复杂度 代码 #include<bits/stdc++.h>...

题意 给你个序列，每个序列的长度为。求能否找到两个序列，从和中分别删除一个元素后剩下的元素之和相等，若可以输出并输出选择的序列编号和要删除的元素下标，否则输出。 题解 由于总的序列长度和也不超过，所以我们可以考虑整体遍历一遍。我们可以开个来存储。存储删除某个数后其序列的和。和存储，该和所对应删除的序列号和下标号。我们在读入一个新的序列的时候可以对该序列的每一个元素进行处理一下，判断删除该值后该序列的和是否出现过，若出现过则表示存在之前某个序列删除某个元素和当前序列删除当前元素的和是相等的。直接输出即可。 复杂度 时间复杂度 代码 #include <bits/stdc++.h> u...

题意 给你一个长度为的数组，求最长的下降子序列，要求子序列相邻元素相差为。若答案不唯一任意输出一组即可。 题解 我们可以开一个来记录。为以作为下降子序列结尾的序列长度。那么我们可以遍历一遍数组，然后得到最长的子序列长度，然后并记录一下序列最后一个元素的值，那么开头值就是最后一个元素值加上序列长度减一。然后我们再遍历一遍原序列求出数组下标。 复杂度 时间复杂度 代码 #include<bits/stdc++.h> using namespace std; const int maxn = 2e5+5; int a[maxn]; map<int,int> mp; int m...

题意 有一个函数，等于各个位上的数字阶乘的乘积。例如。现在给你中的，请你求一个最大的，中不含有，使得。 题解 由于是各个位上的阶乘的乘积。实际上个位数的阶乘可以继续拆解为几个数的阶乘的乘积即有： f(1)=1! f(2)=2! f(3)=3! f(4)=1*2*3*4=1*2*3*1*2*1*2=3!*2!*2! f(5)=5! f(6)=1*2*3*4*5*6=1*2*3*4*5*1*2*3=5!*3! f(7)=7! f(8)=1*2*3*4*5*6*7*8=1*2*3*4*5*6*7*1*2*1*2*1*2=7!*2!*2!*2! f(9)=1*2*3*4*5*6*7*8*9=1*2*3...

题意 给你一个串，但串中有个时会变为，求最后串不变化时，一共会进行多少次这样的变化。 题解 可以发现的是，这个串最终会变为这样的形式。并且在总的变化时，的个数并没有减少。这相当于是将前面都移到之后，变化次数就是移动次数。考虑这样的形式，假设这里有个，那么考虑依次将移动到之后，对于第一个他移动只需要次，变为，也就是的个数变为了，那么对于第二个，移动时需要两次，但是的个数会变为个，那么可以发现总的移动次数就为。所以我们一次一次进行操作找00\cdots 01012^n-1$。这部分可以利用快速幂进行求解。 复杂度 时间复杂度为 代码 #include <bits/stdc++.h> u...

题意 给你两个小写字母字符串和，可以删除中的最短连续子串，使得删后的串是的子序列，求删除后的，若无解输出 题解 由于从串中删去一段子串使得其为的子序列，所以结果的串肯定是由的某个前缀和后缀拼接而成的。 那么可以这样考虑，例如的前缀作为子序列在串前缀所在的位置，例如这个记为数组，，。这里的中的表示串中的下标，也就是串所能还含有的子序列长度是前缀的多少位。同理我们可以得到后缀，这里的含义是所包含的子序列长度是串后缀的多少位。那么如何利用这两个数组来求得最短要删除的子串呢。对于其实就是要删除的子串的长度。我们可以多存两位表示只留后缀，表示只留前缀。由于要求是删除最短的子串，表示当前遍历的点，那么就能...

题意 给你一个只由构成的字符串，定义完美串为，该串上的每个字符都要属于串上的某个回文串的一部分，例如,。现在给你串，求其所有的子串中有多少个完美串。 题解 一个字符串的子串数量有个。若要正着去求解有多少个子串是完美串，是比较困难的，但是我们可以反着来，用总的子串减去不合法的串，就是答案了。什么样的串是不完美的呢，例如，就算是以对称两边的个数不同他仍是完美串。反而，这种，这四种类型的串都不是完美串，所以我们只用从前往后找一遍这两种串的个数，以及从后往前找一遍个数，总的子串减去这两种类型的不完美串即可，但是若处理时需要注意这种串可能会被多减去一次，我们需要在最后加回去。且数据需要开 复杂度 时间复...