专栏首页落影的专栏程序员进阶之算法练习(四十七)

程序员进阶之算法练习(四十七)

正文

题目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看起来是动态规划,其实就是排序后进行选择。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

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; 每次只能移动一个点,每秒只...

    落影

扫码关注云+社区

领取腾讯云代金券