程序员进阶之算法练习（四十七）
正文
题目1
题目链接 题目大意： 给出一个整数1~n的排列。 接下来有m个询问，每个询问包括 l, r, x。 (l <= x <= r) [l, r]区间内的数字会进行一次从小到大的排序，然后得到一个新的1到n的排列，问第x个数字是否等于原来的第x个数字； 每次询问之后，数组会变回初始的排列顺序；
输入数据 第一行，整数n, m (1 ≤ n, m ≤ 1e4) 第二行，n个整数的排列 接下来m行，每行有3个整数 l, r, x (1 ≤ l ≤ x ≤ r ≤ n)
输出数据 共m行，如果等于则输出Yes，如果不等于则输出No；
Examples input 5 5 5 4 3 2 1 1 5 3 1 3 1 2 4 3 4 4 4 2 5 3 output Yes No Yes Yes 样例解释： 样例第一行，按照给出区间，重新排序后的数组是[1, 2, 3, 4, 5]，第3个元素是3，输出Yes； 样例第二行，按照给出区间，重新排序后的数组是[3, 4, 5, 2, 1]，第1个元素不是1，输出No；
题目解析： 题目给出的是1~n的排列，那么有个性质1--没有重复的数字； m个询问是独立的，没有相互影响； 对于询问l, r, x，直接对[l, r]排序的复杂度是O(NlogN)，m个询问的复杂度会到NMLogN，复杂度较高；
因为要询问的是第x个数字是否改变，利用性质1，那么只需统计比a[x]小的区间数字有多少个，即可知道a[x]具体的位置坐标，再和原来的数字进行判断即可。 统计的方法是遍历区间[l, r]，复杂度为O(N)，m个询问的复杂度为N^2，可以接受。
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
while (m--) {
int l, r, x;
cin >> l >> r >> x;
int id = 0;
for (int i = l - 1; i < r; ++i) {
if (a[i] < a[x - 1]) {
++id;
}
}
if (id == x - l) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}题目2
题目链接 题目大意： n个数字排成一行，现在需要选出若干个区间，要求： 1、区间[l, r]如果包含数字x，那么所有数字x应该都在区间[l, r]内，并且区间与区间没有覆盖； 2、区间的权值等于区间内所有数字的XOR（相同数字只XOR一次）； 求选出的若干个区间，能得到的最大权值和。
输入数据 第一行，整数n (1 ≤ n ≤ 5000) 第二行，n个整数 (0 ≤ a[i] ≤ 5000) 输出数据 最大权值和；
Examples input 6 4 4 2 5 2 3 output 14 样例解释：: [4, 4] [2, 5, 2] [3] 权值和 = 4 + (2 xor 5) + 3 = 4 + 7 + 3 = 14
题目解析： 根据题目要求，我们可以知道，对于数字x有三个信息要记录，分别是最左边x的位置、最右边x的位置、x的值； 其中，最左和最右可以通过遍历统计，存到x对应的位置。
由于数字要么选，要么全部不去选，对于某一个数字x，我们可以只对最右边的位置去考虑，是否取该数字。
我们假设dp[i]表示前i个最优解，假如x=a[i]，并且i是数字x的最右边位置，那么数字x包括的区间有两种选择，选or不选。 于是有状态转移方程，那么有dp[i]= max(dp[i-1], dp[k-1]+xor(k, i) )， k是数字x的最左边区间。
接下来就是如何快速求出所有区间[k, i] 以及 对xor(k, i)求和； 容易知道,xor(k, i)遍历一遍方法即可，并且可以针对(k, i)进行缓存；
状态数有O(N^2)，转移的复杂度在预处理xor(k, i)之后是O(1)，预处理的复杂度是O(N^2);
int n;
cin >> n;
for (int i = 0; i < N; ++i) {
p[i].first = p[i].second = -1;
}
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (p[a[i]].first == -1) {
p[a[i]].first = i;
p[a[i]].second = i;
}
else {
p[a[i]].second = i;
}
}
for (int i = 1; i <= n; ++i) {
memset(vis, 0, sizeof(vis));
int sum = 0;
for (int j = i; j <= n; ++j) {
if (!vis[a[j]]) {
vis[a[j]] = 1;
sum ^= a[j];
}
buf[i][j] = sum;
}
}
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1];
if (p[a[i]].second == i) { // i是数字a[i]的最右边
int cur = i;
pair<int, int> range = p[a[i]];
while (cur > 0) {
if (p[a[cur]].second > range.second) {
break;
}
range.first = min(range.first, p[a[cur]].first);
if (cur == range.first) {
dp[i] = max(dp[i], dp[range.first - 1] + buf[range.first][range.second]);
}
--cur;
}
}
}
cout << dp[n] << endl;题目3
题目链接 题目大意： 给出两个长度为n和m的字符串a和b，有一个操作是把字符串a任意位置的字符变成字符?，字符?表示通配符，可以匹配任意字符； 问最少需要变多少次，才能把字符串a变成字符串b的子串？ 输出最少变的数量和位置；
输入数据 第一行，整数 n and m (1 ≤ n ≤ m ≤ 1000) 接下来是两行字符串a、b；
输出数据 最少变化的数量和位置；
Examples input 3 5 abc xaybz output 2 2 3 样例解释：可以把abc变成a??（适配ayb），这样需要变第2、3个字符； 先输出最少变的次数，再输出具体的位置。
题目解析： 因为题目数据范围比较下，可以直接枚举字符串a与字符串b的匹配起始位置； 再计算每次需要修改的字符个数，求出最小值。
复杂度O（N^2）；
int n, m;
cin >> n >> m;
string a, b;
cin >> a >> b;
vector<int> ans(n + 1);
for (int i = 0; i + n <= m; ++i) {
vector<int> tmp;
for (int j = 0; j < n; ++j) {
if (a[j] != b[i + j]) {
tmp.push_back(j + 1);
}
}
if (tmp.size() < ans.size()) {
ans = tmp;
}
}
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); ++i) {
cout << ans[i] << " ";
}题目4
题目链接 题目大意： 小明有n张优惠券，每张的有效时间是(l[i], r[i])，代价是cost[i]，表示从 l[i]天开始，r[i]天结束，时间长度是(r[i] - l[i] + 1)； 现在需要从n张优惠券中，选出2张优惠券，要求两张优惠券没有重叠的日期，并且两张优惠券的时间长度和刚好是x； 问，2张优惠券的最少代价和是多少。
输入数据 输入第一行是整数n和x (2 ≤ n, x ≤ 2·1e5) 接下来是n行，分别是l[i], r[i], cost[i]，表示优惠券的有效时间和代价； (1 ≤ l[i] ≤ r[i] ≤ 2e5, 1 ≤ cost[i] ≤ 1e9)
输出数据 输出是最小的代价和；
Examples input 4 5 1 3 4 1 2 5 5 6 1 1 2 4 output 5
题目解析： 先考虑简单的方法，直接for/for 枚举两个优惠券的组合，可以求出最小代价； 但这样的复杂度是O(N^2)，需要进行优化； 考虑到对于优惠券i，能和它组合的只有长度为(x - (r[i] - l[i] + 1))的优惠券； 长度的范围只有2e5，可以考虑用一个数组t来存长度为len的优惠券最小代价，这样在枚举优惠券i的时候，可以迅速得到与它配对的优惠券； 但是，题目还有另外一个限制：两个优惠券不能相交。 可以考虑，按l[i]从小到大，再按r[i]从小到大排序，这样可以保证l[i]的单调； 同时在更新l[i]的时候，需要把1到i-1的合法优惠券更新到数组t里面，因为在i合法，在i+1也是合法的；
把1到i-1的合法优惠券更新到数组t，这里有两种做法： 1、新建一个数组s，把1到i-1中的右节点（假设是r[k])，放到vector(r[k])中； 2、把1到i-1中的右节点（假设是r[k])，放到优先队列（最小堆）中，每次取出最小的更新；
这里选择做法2，实现更为清晰。
wa了很多次之后，发现一个trick，优惠券的长度会比x更长！
int n, x;
cin >> n >> x;
for (int i = 0; i < n; ++i) {
scanf("%lld%lld%lld", &node[i].first, &node[i].second, &node[i].cost);
}
sort(node, node + n);
priority_queue<Node> queue;
lld ans = llinf;
for (int i = 0; i < n; ++i) {
while (!queue.empty()) {
lld topRight = -queue.top().first;
if (topRight < node[i].first) {
lld index = queue.top().second;
lld len = node[index].len();
if(!s[len]) {
s[len] = node[index].cost;
}
else {
s[len] = min(s[len], node[index].cost);
}
queue.pop();
}
else {
break;
}
}
if (node[i].len() < x && s[x - node[i].len()] > 0) {
ans = min(ans, node[i].cost + s[x - node[i].len()]);
}
queue.push(Node(-node[i].second, i));
}
if (ans == llinf) {
ans = -1;
}
cout << ans << endl;总结
题目1可以直接暴力计算，不需要排序出来整个数组，避免无用计算； 题目2是动态规划的思想，状态的选择也只有取和不取两个可能； 题目3如果尝试去寻找匹配的策略会比较复杂，直接计算更加简单； 题目4看起来是动态规划，其实就是排序后进行选择。