白给怪 - 个人主页动态

2020-06-08 12:27

题目链接：https://codeforces.com/problemset/problem/559/B分析：比赛的时候以为是一道比较难的字符串题，用python交了一次递归的做法，结果runtime error了，可能是代码有问题。后来结束以后看别人的代码，才发现暴力的按照题目的分治递归就能过了。也不是那么难，比赛的时候没有去好好的多试试几次，可惜了。 #include <iostream> #include <cstdio>      //定义输入／输出函数 #include <stack>      //STL 堆栈容器 #include <ma...

0 点赞评论收藏

2020-06-06 10:36

中国科学技术大学算法工程师

幸运数字Ⅱ

题目链接：https://ac.nowcoder.com/acm/problem/15291分析：由于这道题的l 和 r的上线都很接近于int上限，觉得类型转换比较烦，所以索性把所有数据都声明为long long了在1e10里面的幸运数字个数为 2+2^2+2^3+2^4+...+2^10 数量级大概2的11次左右，很小。所以我们是可以大表存下所有1e10以内的幸运数的，当然最后还要加一个4444444444，否则r=1e10，就找不到大于1e10的幸运数了。之后对于这个幸运数数组从小到大排序，用二分去查找l和r在其中的相对位置（当然用lower_bound和upper_bound）然后对...

0 点赞评论收藏

2020-06-05 11:14

中国科学技术大学算法工程师

走出迷宫

题目链接：https://ac.nowcoder.com/acm/problem/14572分析：很简单的dfs题目，当然也可以用bfs题，对于这类题是都行得通的，因为只要能走到终点就行。下面给出的是dfs的做法，“无脑走全图”。细节和终点看代码和注释吧！ #include<iostream> #include<algorithm> #include<queue> #include<string> #include<cstdio> #include<cstring> #include<queue> #inclu...

0 点赞评论收藏

2020-06-04 15:17

中国科学技术大学算法工程师

建筑抢修

题目链接：https://ac.nowcoder.com/acm/problem/20154思路：首先将每栋建筑按照截至时间排序，当然你可以用结构体排序，或者定义二维数组，二位向量啥的，但是在这里，用pair会比较简单，pair 默认对first升序（若相等，对second 升序），这样可以避免写cmp函数或者重载运算符＜。但是要注意把截止时间放在first 把花费时间放在second接着呢 我们把从截止时间早的开始 把凡是能修的就修，能修指 now（现在的时间点）+修理所需要的时间<=截止时间然后我们把修理时间放到一个优先队列（大根堆）里面这样队列里面放的就都是我们修过的建筑的修理时间...

0 点赞评论收藏

2020-06-04 13:12

中国科学技术大学算法工程师

2020-06-04

在牛客打卡5天，今天也很努力鸭！

0 点赞评论收藏

2020-06-03 19:42

中国科学技术大学算法工程师

程序自动分析（不会写也能ac小技巧）

题目链接：https://ac.nowcoder.com/acm/problem/17881首先看到这道题，最简单的想法就是对于每一对相等的i，j通过并查集来建立联系，然后再去判断不相等的i，j是否有相等关系，有则不成立，没有就成立。但是一看i和j的数据范围，头晕了。这么大的数据？？？？？那怎么办呢？ 离散化嘛？（可是好烦啊，真的好烦啊，好复杂）今天从毛毛雨学姐那学了一招。诈胡AC掉这道题。对于1000000000数量级的i和j 我们将它，mod上一个较大，但是又没那么大的数。比如mod上1e6+7 这样所有的i和j就强行缩小到我们可以接受的1e6 数量级了，再对这个范围进行并查集，应该就...

0 点赞评论收藏

2020-06-03 15:49

中国科学技术大学算法工程师

关押罪犯

题目链接：https://ac.nowcoder.com/acm/problem/16591分析：因为市长只看最大影响力，所以我们将影响力从大到小排序，尽可能的去将会发生大影响的冲突避免（即将两个人分到两个监狱里面）下面解释一句话，敌人的敌人是朋友————假如 a和b会产生冲突，由于我们是将数组按照影响力从大到小排序的，所以我们要去尽可能避免a和b发生冲突，将a和b分到两个监狱去，这时候假如又告知你，b和c会产生冲突，那么为了避免b和c的冲突，你很自然的会把c放到和a一个监狱里。把a和c放到一个监狱里，就形成了类似敌人的敌人是朋友的观念。但是如果他下文在告诉你a和c会发生矛盾，那么这个a和c的...

0 点赞评论收藏

2020-06-02 20:37

中国科学技术大学算法工程师

任意点

题目链接：https://ac.nowcoder.com/acm/problem/15808说到这道题，就介绍一道及其相似的题目--- 加边无向图（链接：https://ac.nowcoder.com/acm/problem/14685）任意点这道题是很明显的一道并查集的题目，用一个复杂度为O（logn）的遍历所有点，然后判断他们的横坐标是否相同，或者纵坐标是否相同，相同就归为一类中，最后去求有多少个独立的点区域，然后输出个数减1（因为n个区域只需要n-1个点就可以连通）。并查集常用的merge操作和find操作就不谈了，注意点和详情直接看代码和注释。 #include<iostream...

0 点赞评论收藏

2020-06-02 20:09

中国科学技术大学算法工程师

加边的无向图

题目链接：https://ac.nowcoder.com/acm/problem/14685看题目好像是图论？ 不存在的 ，吓唬你一下而已。这就是简单的并查集，用到的也是并查集最常规的find 和merge（合并） 操作而已在并查集基础上我用了集合，将各个不同的区域网放入了集合中，可能用不着set，但是用了更清楚，更好理解。话不多说，细节和详情看代码，注释写的很清楚哦！ #include<iostream> #include<algorithm> #include<queue> #include<string> #include<cstdi...

0 点赞评论收藏

2020-06-02 19:48

中国科学技术大学算法工程师

经商

题目链接：https://ac.nowcoder.com/acm/problem/14545思路：用并查集将关系网捋清楚，筛选出小d关系网内的人。然后后续问题就是01背包问题了，即代价C内，如何交际才能使价值最大。并查集所用的就是两个最基础的find 和merge 操作，就不必多说了。01背包也是最简单的dp问题了 。话不多说，贴代码，很多细节在注释中。 #include<iostream> #include<algorithm> #include<queue> #include<string> #include<cstdio> #i...

0 点赞评论收藏

2020-06-02 17:13

中国科学技术大学算法工程师

食物链

题目链接：https://ac.nowcoder.com/acm/problem/16884刚看到这道题的时候听懵逼的，只能看出来是并查集，但觉得要加上权值做法很复杂 ，后来听毛毛雨姐姐讲完课以后顿悟了，只要将n的数量级开三倍，来表示三个层次就能解决问题，简化了不少。思路：将数组开3倍大，a表示自身的一层（即a类），a+n表示被a吃掉的一类，a+2n表示能吃a的一类。判断一个语句是否为真，则只要判断它的反例是否成立。如 1 A B，表示A 和B 是一类的 那么只要判断A和B+n或者A和b+2n是不是一类的 如果是，说明这句话是假话，否则就是真话。并查集的基本操作merge（归并） 和find ...

0 点赞评论收藏

2020-06-02 14:07

中国科学技术大学算法工程师

Cut

题目地址：https://ac.nowcoder.com/acm/problem/14291思路：这道题是一道很明显的贪心题目，要使得代价最大，肯定是每次切割将最小的切掉，这样后续更大的数，在计算代价的时候会被多次累加，从而达到最大的目的。所以做法就是： 先排序，然后每次将最小的元素分割掉，这样总代价就相当于为什么要减去a[n]，最后只剩两个元素时只要分割一次，所以最大的一个元素只会被计算到n-1次。下面是代码： #include <iostream> #include <cstdio>      //定义输入／输出函数 #include <stack>  ...

0 点赞评论收藏

2020-06-01 19:38

中国科学技术大学算法工程师

2020-06-01

在牛客打卡4天，今天也很努力鸭！

0 点赞评论收藏

2020-05-18 19:29

中国科学技术大学算法工程师

2020-05-18

在牛客打卡3天，今天也很努力鸭！

0 点赞评论收藏

2020-05-15 17:49

中国科学技术大学算法工程师

2020-05-15

在牛客打卡2天，今天也很努力鸭！

0 点赞评论收藏

关注他的用户也关注了：