最小改正字符数
给定一个由0和1的字符串和该字符串中某个区间左边界和右边界，要求求出将该区间字符串变成01间隔（例如101、010）的字符串需要改动的最小字符数。
给定输入第一行是n，表示区间数，第二行是该字符串s，接下来n行是左边界l和右边界r。
题目中n满足 1 <= n <= 10^5
1 <= s.length() <= 10^5
1 <= l ,r <= 10^5
这道题开始直接自己构造一个等长度符合条件1开头的字符串，和一个0开头的字符串，逐个比较不同字符的个数，后来超时了。这题复杂度O(n * n)确实会超时。考试过程中也没想到前缀和。考完才想起来。这里记录一下正确解法。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
string s;
cin >> s;
int l, r;
string s1 = "";
string s2 = "";
for (int i = 0; i < s.length(); i++) {
if (i % 2 == 0) s1 += "1";
else s1 += "0";
}
for (int i = 0; i < s.length(); i++) {
if (i % 2 == 0) s1 += "0";
else s2 += "1";
}
vector<int> d1(s.length() + 1, 0);
vector<int> d2(s.length() + 1, 0);
for (int i = 1; i <= s.length(); i++) {
d1[i] = d1[i - 1] + abs(s1[i - 1] - s[i - 1]);
d2[i] = d2[i - 1] + abs(s2[i - 1] - s[i - 1]);
}
while (n--) {
cin >> l >> r;
int res = min(d1[r + 1] - d1[l], d2[r + 1] - d1[l]);
cout << res << endl;
}
return 0;
}符合条件的不相邻结点数
有一棵树，有n个节点，构成一个图。要求求出不相邻节点相乘是偶数的方案数。
输入第一行是n，表示节点个数。后面是n- 1行，每行用u和v表示相邻节点序号数。
其中 1<= n <= 10^5
1 <= u <= 10^5
1 <= v <= 10^5
请给出符合条件的方案数
这题一开始用邻接矩阵 + map统计来做，爆内存了，确实二维矩阵这个规模下会爆。同样也是当时没想起来。考完后意识到也许可以map<int, vector>作为记录子节点的成员结构来实现。
代码如下：
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
map<int, vector<int>> mymap_vec;
int u, v;
for (int i = 0; i < n - 1; i++) {
cin >> u >> v;
mymap_vec[u].push_back(v);
mymap_vec[v].push_back(u);
}
int num = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0 && mymap_vec[i].size() > 0) {
num += (n - mymap_vec[i].size());
}
else {
int sum = (n - 1) / 2 + 1;
for (int j = 0; j < mymap_vec[i].size(); j++) {
if (mymap_vec[i][j] % 2 == 0) sum--;
}
num += sum;
}
}
cout << num / 2 << endl;
return 0;
}完美数组
这题是用的回溯。其实应该是写出来了，当时测试用例其实有点问题的。
给定一个数组，要求求出该数组所有非空子序列中满足完美数组要求的个数。其中完美数组是指该数组中奇数有奇数个，偶数有偶数个。
输入n表示数组元素个数，下面一行输入n个元素表示数组元素a[i]（0，...，n-1）
n满足 1 <= n <= 10^5
a[i] 满足 1 <= a[i] <= 10^5
其实就是个回溯法组合问题，涉及到去重。而回溯法简单来说就是一种依靠递归进行的暴力枚举。每次挑出当前数组中一个值放入path路径数组，并进行递归，递归结束后返回到该处位置时又从path路径数组中去除该元素，如果是字符串则需要一开始保存，后面再赋值回去。这是递归逻辑。循环结束条件是path数组长度满足要求或者满足其他条件，将其值放入记录答案的数组即可。当记录数组访问下标的变量显示到达边界时也要进行处理。
去重逻辑首先要求排序，排完序后相同的值就在相邻位置了，由于在这样的情况下，该值有可能会产生的结果都由这些数中第一个数递归下去存储完了，因此后续需要将下标i移到最后一个该元素相同值位置处，并再借由循环中i++移到下一个不等于该值的元素处进行下一轮判断即可。
看代码直观些，代码如下：
#include <iostream>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int num = 0;
vector<int> path;
void backtracking(vector<int>& nums, int index, int size, int n1, int n2) {
if (path.size() == size) {
if (n1 % 2 == 1 && n2 % 2 == 0) num++;
num %= (1000000000 + 7);
return;
}
if (index == nums.size()) return;
for (int i = index; i < nums.size(); i++) {
path.push_back(nums[i]);
if (nums[i] % 2 == 0)
backtracking(nums, i + 1, size, n1, n2 + 1);
else backtracking(nums, i + 1, size, n1 + 1, n2);
while (i + 1 < nums.size() && nums[i + 1] == nums[i]) i++;
path.pop_back();
}
}
int main() {
int n;
cin >> n;
vector<int> nums;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
nums.push_back(x);
}
sort(nums.begin(), nums.end());
for (int i = 1; i < nums.size(); i++) {
backtracking(nums, 0, i, 0, 0);
}
cout << num << endl;
return 0;
}算法训练营第二十七天 | 组合问题
一样的回溯法，稍微改动下即可。
class Solution {
private:
vector<int> path;
vector<vector<int>> res;
void backtracking(int n, int index, int k) {
if (path.size() == k) {
res.push_back(path);
return;
}
if (index == n + 1) return;
for (int i = index; i <= n; i++) {
path.push_back(i);
backtracking(n, i + 1, k);
path.pop_back();
}
}
public:
vector<vector<int>> combine(int n, int k) {
backtracking(n, 1, k);
return res;
}
};