sunrise__sunrise - 个人主页动态 - 牛客网

发布(392) 评论刷题收藏

2020-06-08 18:23

中国海洋大学 C++

并查集+map #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(vv) (vv).begin(), (vv).end() #define endl "...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-08 14:54

已编辑

中国海洋大学 C++

题意 有一天教授有了n个虫子，m个***关系，并且给出全部的关系，问是否存在同性恋的关系。）当然是有的阿！ 解题思路 方法比较多，可以用 2 * n的并查集，去用不带权的方法去做，雨巨讲了3个关系的，这个比较简单我就用另外一种方法把，用的带权的并查集。另外开一个数组）好像可以看出来空间没有节约哎……），代表自己和父节点的关系。0代表同性，1代表异性，注意这个是在路径压缩的前提中去判断得。所以每次如果查到两只虫子是同一个树中，再去判断这两个虫子是不是一个性别即可。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimi...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-08 11:24

中国海洋大学 C++

程序自动分析

离散化+并查集 关系的化就是并查集处理，但是数据规模很大，下标到了1e9，所以开不下那么大的并查集数组，那么怎么办，离散化去搞。我们不需要知道每个数具体多大，只需要知道相对大小，找到这个数就行了。别用set，常数很大，就用快排+去重。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespace std; #define js...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-10 14:56

已编辑

中国海洋大学 C++

优先队列+二分 题目需要找到中位数最大，那么我们直接按照价值升序排序，再把体重升序排序。从头把m对半分开，求前m最小和后m最小，如果是奇数最终加上当前这位的体积比v小于等于，直接这一位的价值就是答案。如果是偶数，这个会复杂一点，因为你无法保证某一次价值大的体重小，但是可以发现，我们是求中间两个取平均，我们已经对这个物品先按价值升序排序，那么我们就在这个合理的区间中可以发现，如果存在符合V的区间，显然我们希望这个区间越靠后面越高兴，所以我们要接一个二分去寻找合理的最大值。代码写的比较玄乎，码了注释。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") ...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-08 08:37

中国海洋大学 C++

并查集 测谎话，并查集的基础作用，我们开个3 * n的数组，每n个元素看成是同类，其余跨种族。 我们把输入的x和y进行找种族，如果存在冲突+1即可，雨巨也教的比较明白了，白嫖课大家可以去康康吖。 安利一波江大佬的带权并查集不用开3 * n的空间，保存n的大小，对3取模。传送门 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using na...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2021-04-26 17:53

已编辑

中国海洋大学 C++

Operating System

堆/优先队列 这个题目写起来不难，题目读起来是真的困难，出题人根本没把题目意思交代清楚……观摩大佬AC代码之后，看的有点懵，反正给出的数，需要求一下下一次出现的位置，可以用2个数组，也可以用umap去离散记录。我就不展开了。其余的就是贪心的思路了，按下一次出现优先降序排序，最大的那个最先出队，如果出现时间相同，按照输入的数据升序排序，可看代码用了pair自带的二元组，第一元素先升序，第二元素再升序。关于最先出队C++的优先队列即可满足。 #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_s...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-07 18:48

中国海洋大学 C++

前缀和+STL 前缀和应该挺简单不用我说吧，C++中一个STL叫upper_bound()查找在一个左闭右开的区间中第一个大于x的迭代器位置，记住不带等号！！带等号的是lower_bound()！！！迭代器减掉起始下标就是距离了。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespace std; #define js ...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-07 18:43

中国海洋大学 C++

Monthly Expense

二分 题目意思，给出最大k个球，问每个球重量一样最小可能需要多大才可以把这n个东西都放进去。很容易发现的二分思路，check函数也挺好写的，直接看代码应该挺容易理解，基础二分题。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <cstdio> #include <algorithm> #include <vector> #include <cs...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-07 18:38

中国海洋大学 C++

Monthly Expense

二分 挺容易发现的二分思路，单调性比较明显，而且check函数直接把大于等于答案的累加进去，求解判断下就可以了。注意特判个k=1，就行了。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <cstdio> #include <algorithm> #include <vector> #include <cstring> #include ...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-07 18:32

中国海洋大学 C++

Chocolate Eating

二分 首先假设已经求解到的ans代表合理的最大幸福的，我们显然希望找到一个吃巧克力的方式让他比当前ans更大，否则只能更小。符合二分性质。而且二分的check函数设计直接把吃过的sum每天减半如果不够了再吃一个新的巧克力，看最后会不会超过n即可 最后调用一次check求道合理的最大幸福度的安排方法。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h&g...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-07 18:23

中国海洋大学 C++

[SCOI2010]传送带

三分 雨巨点名的三分题……本菜鸡还是不太懂，观摩其他大佬的代码终于有点理解。我们先三分出从A点到AB中的某个点X，作为出发点，然后，再三分出从X到CD的某个点Y，再从Y直接到D，这样，我们就可以求出最小的值了。路径的话，存在4条路，分别代表走不走传送带。不走AB带就直接走到B，不走CD带就直接从x走到D，直接码三分的板子就行了，向量求起来有点复杂，要仔细。精度问题，建议double的直接循环100或者1000次，看题目规模去改，别搞超时了。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-07 18:09

中国海洋大学 C++

聪明的质监员

二分+前缀和 求解最小值，观察题目给出的判断条件，W随着变大时，区间中符合要求的会减少，同时所有，所以也随着变小，求得Y也是递减，可以得知W和Y是满足二分的关系。在求解每一个时，运用到前缀和的思想O(1)实现。 总的时间复杂度 Code #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespace std; #define ...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-07 17:15

中国海洋大学 C++

[SHOI2017]期末考试

三分 带两个约束条件，如果你数学好约分化简合并之后就是个抛物线，要求最顶点（拐点）直接三分答案即可，注意check函数的写法，而且C++写的注意爆了ll，可以使用__int128保险一点，我试了下ull也过了。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespace std; #define js ios::sync_w...

牛客算法竞赛入门课

0 点赞评论收藏

分享

2020-06-07 09:59

已编辑

中国海洋大学 C++

第十七届浙大城市学院程序设计竞赛（同步赛）

A、Sumo and Keyboard-Cat 直接遍历整个字符串康康多少个地方进行了大小写转换，初始状态为大写，注意一下就过了，签到题。 #pragma GCC target("avx,sse2,sse3,sse4,popcnt") #pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math") #include <bits/stdc++.h> using namespace std; #define js ios::sync_with_stdio(false);cin.tie(0); cout.ti...

0 点赞评论收藏

分享

2020-06-06 10:45

已编辑

中国海洋大学 C++

第三届中国计量大学ACM程序设计竞赛个人赛（同步赛）-Python

时间关系只写了一点题目，手机码的A和N……手残党的失败，并且只用了Python N、Yet Another Hanoi Problem 看不太懂英文题，但是看图片以及样例大概猜到是指定移动规则的哈诺塔。应该是只能移动到相邻位置，不能跨柱子移动。 找到公式以及通项公式 T = int(input()) for i in range(T): n = int(input()) print(pow(3,n,1000000007)-1) A、Arithmetic Problems 减号代表乘法，除号代表加法，加号代表除法，乘号代表减法，如果除了0，特判出来。 计算表达式，符号作用被...

0 点赞评论收藏

分享

创作者周榜

更多

关注他的用户也关注了：

牛客网
牛客企业服务