暴力做法：最暴力的做法是dfs枚举每个数是否被选取，然后枚举质数，看是否存在X个不同的质数可以整除选取的所有数。但这样dfs的复杂度是2^S.size()复杂度太高，即使加上剪枝也很难通过 正解：首先我们转换一下题意，要求存在至少X个质数可以整除未被删除的所有数，等价于GCD(剩下的所有数)存在至少X个不同的质因数。那么我们可以用筛法预处理出1~10^6中每个数有多少个不同的质数，然后枚举每个可行的GCD。首先可以用cnt[i]记录数组中一共有多少个数i，那么当枚举GCD为g时，最终保留的数为cnt[g] + cnt[2 * g] + cnt[3 * g] + ... + cnt[10^6 d...

解法：考虑到原来的每一块肉最多被切成两块肉，那么原来的第一块肉只有以下两种可能：1、它是切完之后的第一块肉2、它被切成了两块肉，那么它的大小是切完之后前两块肉的和只需要依次判断这两种情况是否可能即可。 bool isOk(vector <int> &A, int x) { int cur = 0; while (cur < A.size()) { if (A[cur] == x) { cur++; } else if (cur + 1 < A.size() && A[cur] + A[cur + 1] == x) { cur += 2; } el...

做法1：枚举每一种可能的分割方案，得到前面和后面两个子串，判断这两个子串是不是都是回文串 bool isOk(string S) { for (int i = 0; i < S.size(); i++) { if (S[i] != S[S.size() - 1 - i]) { return false; } } return true; } int CountDoublePalindromeString(string S) { int n = S.size(); int ans = 0; for (int i = 0; i <= n; i++) { ans += (isOk(S.s...

暴力做法：首先我们转换一下题意，要求存在至少X个质数可以整除A[l]~A[r]之间的所有数，等价于GCD(A[l], A[l + 1], A[l + 2], ..., A[r])存在至少X个不同的质因数。因此我们可以暴力枚举所有可能的数对(l, r)，然后求出GCD(A[l], A[l + 1], A[l + 2], ..., A[r])，并对其进行质因数分解，如果存在至少X个不同的质因数，说明这是一个合法的数对。那么我们最后只需记录下所有合法的数对并排序，找到第K长的数对即可。 int GetKthLength(vector<int>& A, int X, int K) ...

暴力解法：最暴力的做法是DFS枚举素数累加，但复杂度太大根据哥德巴赫猜想，我们知道答案最大为3，因此可以先判断N本身是不是素数，然后暴力判断是否可以分解成两个素数的和，如果不行的话答案就是3。 bool IsPrime(int N) { if (N < 2) { return false; } for (int i = 2; i * i <= N; i++) { if (N % i == 0) { return false; } } return true; } int MinPrimeSum(int N) { if (IsPrime(N)) { return 1; } for (...

暴力解法：枚举所有可能的X1和X2，然后计算替换之后的答案，从所有可能的答案中选取最小值复杂度O(26 * 26 * N)  /** * 计算最少的距离 * @param S1 string字符串 第一个字符串 * @param S2 string字符串 第二个字符串 * @return int整型 */ int GetMinDistance(string S1, string S2) { int ans = 1e9; for (char c = 'a'; c <= 'z'; c++) { for (char d = 'a'; d <= 'z'; d++) { int dist =...

暴力解法：枚举l, r，计算区间和，统计有多少对符合条件的l, r int countLR(vector<int> &a, vector<int> &b) { int n = a.size(); int ans = 0; for (int l = 0; l < n; l++) { for (int r = l; r < n; r++) { int s = 0; for (int i = l; i <= r; i++) { s += a[i]; } ans += (s == b[l] + b[r]); } } return ans; }正...