程序员进阶之算法练习(二)

前言

看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。

A

题目链接 题目大意:n个点,坐标x[i]从小到大,每个点可以选择Left或者Right的方向前进,速度v=1,求相遇的时间。 代码实现

    int right = -1;
    for (int i = 0; i < n; ++i) {
        if (str[i] == 'R') {
            right = i;
        }
        else {
            if (right != -1 && a[i] != a[right]) {
                if (ret == -1) {
                    ret = (a[i] - a[right]) / 2;
                }
                else {
                    ret = min(ret, (a[i] - a[right]) / 2);
                }
            }
        }
    }

题目解析: 对于点i,有两种碰撞情况: 1、方向是L,遇到左边的点方向是R; 2、方向是R,遇到右边的店方向是L; 假设点i和点j是碰撞的点,那么点i的情况1就是点j的情况2; 那么对于点i只考虑左边的点即可; 题目变成:对于每个点,求左边最近的方向为R 的点

B

题目链接 题目大意:n*m的棋盘上有若干点,找一个点横竖能覆盖所有点。

方法1:

代码实现

  // 假设符合的点
    for (int i = 0; i < n && OK; ++i) {
        for (int j = 0; j < m && OK; ++j) {
            Node tmp;
            tmp.x = i;
            tmp.y = j;
            nodes.insert(tmp);
        }
    }

  // 检查假设的点
    for (int i = 0; i < n && OK; ++i) {
        for (int j = 0; j < m && OK; ++j) {
            if (str[i][j] == '*') {
                set<Node>::iterator it = nodes.begin();
                while (it != nodes.end()) {
                    if (it->x == i || it->y == j) {
                        ++it;
                    }
                    else {
                        nodes.erase(it++);
                    }
                }
                if (nodes.size() == 0) {
                    OK = 0;
                }
            }
        }
    }

题目解析: 假设所有点符合,用set来存放所有的点,每遇到一个点,把不符合的去掉; 时间复杂度为O(NM*LogN),复杂度的关键在于set的构建。

方法2:

代码实现

    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            cin>>c[i][j];
            if(c[i][j]=='*'){
                k++;
                a[i]++;
                b[j]++;
            }
        }
    }
    for(i=0;i<n;i++){
        for(j=0;j<m;j++) {
            s=a[i]+b[j];
            if(c[i][j]=='*'){
                s--;
            }
            if(s==k) {
                cout<<"YES"<<endl<<i+1<<" "<<j+1;
                return 0;
            }
        }
    }

题目解析: 假设某一点符合,求这一个点覆盖的点数是否包括其他所有需要覆盖的点; 事先统计每行每列对应的点数,求点覆盖点数时通过每行每列的值可以较快计算出来。 时间复杂度为O(NM)。

C

题目链接 题目大意:有n天,每天有四种可能,如下。问最少能休息几天。 1、on this day the gym is closed and the contest is not carried out; 2、on this day the gym is closed and the contest is carried out; 3、on this day the gym is open and the contest is not carried out; 4、on this day the gym is open and the contest is carried out. 不能连续两天比赛,也不能连续两天锻炼。

代码实现

    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        d[i][0] = min(min(d[i - 1][0] + 1, d[i - 1][1] + 1), d[i - 1][2] + 1);
        if (k == 0) {
            d[i][1] = d[i][2] = N;
        }
        if (k == 1) { // can to contest
            d[i][1] = min(d[i - 1][2], d[i - 1][0]);
            d[i][2] = N;
        }
        if (k == 2) { // can to gym
            d[i][1] = N;
            d[i][2] = min(d[i - 1][1], d[i - 1][0]);
        }
        if (k == 3) {
            d[i][1] = min(d[i - 1][2], d[i - 1][0]);
            d[i][2] = min(d[i - 1][1], d[i - 1][0]);
        }
    }
    
    cout << min(min(d[n][0], d[n][1]), d[n][2]) << endl;

题目解析: 典型的动态规划。 d[i][j]表示第i天,状态为j时的最小休息天数。 j = 0表示都不去; j = 1表示去contest; j = 2表示去gym;

这样j = 0可以由前面三种状态转换过来; j = 1只能由0和2转换; j = 2只能由1和2转换;

然后动态规划一遍得最优解。

D

题目链接 题目大意:n个点,每个点对应的a[i]表示第i个点的parent节点,问使其变成一棵树,最少需要修改多少条边,并且把所有值输出。 代码实现

lld find(lld x) {
    lld ret = f[x];
    if (ret != x) {
        ret = find(ret);
    }
    return f[x] = ret;
}


int main() {
    for (int i = 1; i <= n; ++i) {
        if (i != root) {
            lld x = find(i);
            lld y = find(a[i]);
            if (x == y) {
                ++ans;
                if (!root) {
                    root = x;
                }
                a[i] = root;
            }
            else {
                f[x] = f[y];
            }
            
        }
    }
}

题目解析: n个点,n条边。如果是树必然是一条边指向自己,其余n-1条边没有环。(有且仅有一个环) 那么假设有一个根节点root,当出现环的时候,直接将环某个点指向root即可; 需要修改的数量=环的数量 - 1。

总结

两个关键词:动态规划(C题)、并查集(D题)。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

7828:最大公约数与最小公倍数

7828:最大公约数与最小公倍数 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 两个正整数的最大公约数是G,最小公倍数是...

47680
来自专栏Python中文社区

Python文档精要研读系列:hash函数

hash(object) Return the hash value of the object (if it has one). Hash values ar...

266100
来自专栏跟着阿笨一起玩NET

浅谈UML中类之间的五种关系及其在代码中的表现形式

类有很多种提炼角度,需要根据系统地目标、业务的场景,选取合适的角度对事物进行归纳。

18020
来自专栏落影的专栏

程序员进阶之算法练习(二十九)

29420
来自专栏开发 & 算法杂谈

凸包问题之GrahamScan解法

当沿着Convex hull逆时针漫游时,总是向左转在极坐标系下按照极角大小排列,然后逆时针方向漫游点集,去除非Convex hull顶点(非左 转点)。

10940
来自专栏C/C++基础

认识UML类关系——依赖、关联、聚合、组合、泛化

在学习面向对象设计时,类关系涉及依赖、关联、聚合、组合和泛化这五种关系,耦合度依次递增。关于耦合度,可以简单地理解为当一个类发生变更时,对其他类造成的影响程度,...

18820
来自专栏tkokof 的技术,小趣及杂念

HGE系列之五 管中窥豹(基础类别)

继上次我们编写了那个小程序之后,想必大家对于HGE的认识都有了进一步的提高,那么现在,我想则是时候来一番“管中窥豹”,睹一睹HGE的源码实现了 :)而相应的源...

10610
来自专栏数据结构与算法

牛客NOIP提高组(二)题解

好难啊,$30$分的枚举颜色dp应该比较好想把,$f[i][j]$表示第$i$个位置,填了$j$个颜色,然后先枚举一下$1$的颜色,前缀和优化一下,$O(n a...

11410
来自专栏漫漫深度学习路

pytorch学习笔记(九):PyTorch结构介绍

PyTorch结构介绍 对PyTorch架构的粗浅理解,不能保证完全正确,但是希望可以从更高层次上对PyTorch上有个整体把握。水平有限,如有错误,欢迎指错,...

33560
来自专栏CDA数据分析师

资源 | 23种Pandas核心操作,你需要过一遍吗?

Pandas 是基于 NumPy 构建的库,在数据处理方面可以把它理解为 NumPy 加强版,同时 Pandas 也是一项开源项目。它基于 Cython,因此读...

9820

扫码关注云+社区

领取腾讯云代金券