程序员进阶之算法练习（四十七）

正文

题目1

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；

```    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

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

```    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

Examples input 3 5 abc xaybz output 2 2 3 样例解释：可以把abc变成a??（适配ayb），这样需要变第2、3个字符； 先输出最少变的次数，再输出具体的位置。

```    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

Examples input 4 5 1 3 4 1 2 5 5 6 1 1 2 4 output 5

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;```

0 条评论

• 程序员进阶之算法练习（十七）

前言 正文6道题目来自leetcode––为求职为生的编程网站，目的是工作闲暇之时锤炼代码功底。 如何从这篇文章受益？ 先看题目大意，对照Example的样...

• 程序员进阶之算法练习（四十四）

题目链接 题目大意： 给出整数x，求两个整数a和b，满足： ???(?,?)+???(?,?)=? . GCD是最大公约数； LCM是最小公约数；

• 程序员进阶之算法练习（十四）

前言 坚持做算法练习对开发的好处是抽象能力变强，拿到一个需求能很快对其进行抽象，然后再用学过的设计模式相关知识进行整理，最后用代码实现。 最大的好处在于：对...

• 程序员进阶之算法练习（二十七）

前言 日常练习，保持思考。 正文 1.Parallelogram is Back 题目链接 题目大意： 给出平行四边形的三个点(x[i], y[i])，求出...

• 程序员进阶之算法练习（二十四）

前言 已经有三个月未更新算法文章，大厂工作环境是步步紧逼的，使得所有的人越来越忙碌。余下的学习时间，要用于技术预研、知识面开阔、底层原理理解等等，慢慢算法只能占...

• 程序员进阶之算法练习（四十二）

题目链接 题目大意： n个学生参加测试，一共有m道题，每道题的答案可能是(A, B, C, D , E)中的一个； m道题分别有?1,?2,…,??，共m...

• 程序员进阶之算法练习（四十五）

每个路口的机动车道有三个方向，分别是左转、直行、右转，同时路口有一条人行道； 每行输入有四个数字l，s，r，p，分别表示左转、直行、右转、人行道的交通信号灯是...

• 程序员进阶之算法练习（四十一）

题目链接 题目大意： 有一个由数字0、1组成的字符串，长度为n； 现在需要将其切分成若干段，要求每一段0和1的数量是不相同的。 比如说1, 101, 0...

• 程序员进阶之算法练习（四十）Codeforces

题目链接 题目大意： 在一维坐标轴上有三个点，坐标是a、b、c； 现在需要移动这三个点的位置，使得三个点之间两两间隔大于d； 每次只能移动一个点，每秒只...