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

发布(235) 评论刷题

2020-12-24 11:38

北京师范大学 C++

python一些trick(2020.12.24)

今天早上看了一篇讲python黑魔法的博客做一下学习笔记记录 trick: 连接多个列表 >>> a = [1,2] >>> b = [3,4] >>> c = [5,6] >>> >>> sum((a,b,c), []) [1, 2, 3, 4, 5, 6] \作为续行符 >>> a = 'talk is cheap,'\ ... 'show me the code.' >>> >>> print(a) talk is cheap,show ...

课余学习(*^▽^*)

0 点赞评论收藏

分享

2020-12-23 15:17

北京师范大学 C++

牛客练习赛73 ABCD题解

补题原则 ABCD四题比赛时通过人数均超过40其中ABC题较水，用来练习python语法D用来锻炼自己的思维 A.招生 简单模拟题，考察排序，注意分数不能小于0python的排序函数 ，如果只调用 并不会把 的元素排序需要执行 另外第m大可以用 得到 Code n, m, p = map(int, input().split()) a = [] for i in range(n): x, y = map(int, input().split()) a.append(x * 0.85 + y * 0.15) a = sorted(a) #print(a[-m]) ans = int...

0 点赞评论收藏

分享

2020-12-22 16:52

北京师范大学 C++

Codeforces Round #686 (Div. 3) E Number of Simple Paths 题解

Description 题目链接给顶一个n个顶点、n条边的图，统计图内简单路径的数量。 Solution 数据很有特点， 个顶点并且具有 条边。如果是 条边的话显然是一棵树。树上简单路径如何计算呢? 假设当前树的节点有 个，显然是 现在多了一条边，可以看成是多棵树相互独立，中间是一个环，如下图：由红圈中三个子树构成，分别拥有节点个数为3、3、3对于每个子树我们统计节点数 ，可以计算贡献那么剩下的就是如何统计节点了，类似于拓扑排序，每次把度为1的点都放到队列里，慢慢删边即可。时间复杂度 Code #include<bits/stdc++.h> using namespace...

0 点赞评论收藏

分享

2020-12-22 14:48

已编辑

北京师范大学 C++

Python 爬虫学习和实例(2020.12.22)

花了一个早上简单学习了一下爬虫，做下记录吧 爬虫 正则表达式 foo ——————字符串“foo” ^foo ——————以“foo”开头的字符串 foo$ ——————以“foo”结尾的字符串 ^foo$ ——————“foo”开头和结尾，（只能是他自己 ） [abc]—————— a 或者b 或者c [a-z] —————— a到z之间任意字母 [^A-Z]——————除了 A-Z这些之外的字符 (gif|jpg)——————“gif”或者 “jpeg” [a-z]+—————— 一个或者多个 a到z之间任意字母 [0-9.-]—————— 0-9之间任意数字，或者 点 或者 横线 ^[a...

课余学习(*^▽^*)

0 点赞评论收藏

分享

2020-12-22 08:24

已编辑

北京师范大学 C++

【每日一题】小阳的贝壳题解

Description 链接：https://ac.nowcoder.com/acm/problem/26255来源：牛客网 小阳手中一共有 n 个贝壳，每个贝壳都有颜色，且初始第 i 个贝壳的颜色为 。现在小阳有 3 种操作： 1 l r x：给 [l,r]区间里所有贝壳的颜色值加上 x 。 2 l r：询问 [l,r]区间里所有相邻贝壳颜色值的差（取绝对值） 的最大值（若 l = r 输出 0）。 3 l r ：询问 [l,r]区间里所有贝壳颜色值的最大公约数。 Solution 前置知识:差分数组、线段树 差分数组 设原数组为 , 令 , 称 为 的差分数组。差分数组有什么好处呢?首...

Kurisu与牛客的每日...

0 点赞评论收藏

分享

2020-12-18 13:38

已编辑

北京师范大学 C++

【每日一题】Necklace 题解

Description 给一堆字母的使用次数，判断能否构成一个环，使得断环成链后能够成为回文串的节点尽可能多。 Solution 首先思考回文串的定义，显然如果有两个以上奇数存在是不可能构成回文串的。接着画个图，给出几组数据 3 2 4 2 2 2 2 2 2 3不难看出，按照我们的构造方法，答案最多只能是 如果有一个奇数，就把这个奇数放到中间处构造方法是每次放 个字母构成一个回文串，拼接到一起 Code #include<bits/stdc++.h> using namespace std; const int N = 5e5 + 5; typedef long long ...

Kurisu与牛客的每日...

0 点赞评论收藏

分享

2020-12-16 23:35

北京师范大学 C++

【每日一题】老瞎眼 pk 小鲜肉题解

Desription 链接：https://ac.nowcoder.com/acm/problem/50444来源：牛客网 老瞎眼有一个长度为 n 的数组 a,为了为难小鲜肉，他准备了 Q 次询问，每次给出 一个区间[L,R],他让小鲜肉寻 找一对 l,r 使L<=l<=r<=R 且 a[l]^a[l+1]^a[l+2]...^a[r]=0,老瞎眼只让他回答r-l+1 最小是多少，若没有符合条件的 l,r 输出”-1”。 Solution 以为是01Trie之类的操作偷偷看了happy的题解才知道是离线+线段树由原式子转化为前缀和 所以必然有 考虑遍历每个值的时候，记录上一...

Kurisu与牛客的每日...

0 点赞评论收藏

分享

2020-12-15 16:24

北京师范大学 C++

【每日一题】Superhero Battle 题解

Description n个数字一个循环，每秒经过一个数字，血量变化为 总血量为HP，问HP经过多少秒后小于等于0Codeforces Difficulty 1700 Solution 分类讨论 找最大的一个前缀和，如果这个最大的前缀和 大于HP，那么可以在一轮内完成。 再看一轮的前缀和 ，如果小于等于0，则经过多少轮血量都只会增加不会减少。 如果 先扣出来 , 随后剩余的看要经过多少轮才能结束(轮数要向上取整)，最后走一轮统计即可。 时间复杂度 Code #include<bits/stdc++.h> using namespace std; const int N =...

Kurisu与牛客的每日...

0 点赞评论收藏

分享

2020-12-15 10:52

已编辑

北京师范大学 C++

【每日一题】树形dp专题 [AHOI2009]CHECKER 题解

Description 链接：https://ac.nowcoder.com/acm/problem/19884来源：牛客网 在一个1行N列（N是奇数）的棋盘上，有K个格子是红色的。这种情况下，你有一个跳棋在最左端的格子上。你的目标是将它移动到最右边的格子，在开始移动之间，你可以在棋盘的任意空位上放棋子。在游戏开始后 你只可以随时在一个红色格子上放棋子。棋子的移动规则是：每次只可以选择一个棋子，跳过与之相邻的棋子走到后面的空格上，被它跳过的棋子被吃掉，即从棋盘上移走，如相邻棋子的另一侧有棋子，则不能跳。请回答以下两个问题：1：移动开始前至少要放多少棋子才能完成任务。2：如果要使开始前放的棋子数...

Kurisu与牛客的每日...

0 点赞评论收藏

分享

2020-12-14 20:38

已编辑

北京师范大学 C++

【每日一题】函数的魔法题解

Description 一位客人来到了此花亭，给了女服务员柚一个数学问题：我们有两个函数，F(X)函数可以让X变成（XXX+XX）mod 233。G(X)函数可以让X变成（XXX-XX）mod 233，我们可以任意的对A使用F(X),和G(X)，问最少需要多少次使用这两个函数让A变成B。 Solution 由于模数只有233，我们进行函数变换后永远只能在 的区间里面，不妨用 的方法搜索出答案，由于 会对到过的点进行记录，不会重复走点，第一次到达的位置一定是最小的，最多搜索233次。所以时间复杂度为 。 Code #include<bits/stdc++.h> using name...

Kurisu与牛客的每日...

0 点赞评论收藏

分享

2020-12-14 11:25

北京师范大学 C++

牛客小白月赛29 B 二进制题解

Description 给出一堆的按位操作运算，构造五次以内的三种按位操作——，， 使得最终结果与原来的操作相同。 Solution 时隔一个月?回来做这道当时不会做的构造题。考虑二进制上的每一位，无论他原来是 还是 ，我们只需要构造经过一系列的变换后每一位保证与原来的操作相同即可。于是只需要考虑三次操作，分别进行，， 其中操作数需要对原来的操作序列进行模拟，然后得出结果。具体方法如下：对于每一位取该位 和 经过操作序列的作用后 该位需要做一次或运算 该位需要做一次异或运算 需要做一次与运算 Code #include<bits/stdc++.h> using nam...

0 点赞评论收藏

分享

2020-12-10 11:37

已编辑

北京师范大学 C++

【每日一题】倍增专题 Smile Houset题解(floyd倍增找环)

Description 找最小的正环 Solution 用 找环, 令 是经过 条边, 从 到 的距离易得, 是中间点,时间复杂度 只需找到一个 的点即可考虑倍增优化 表示经过 条边, 从 到 的距离二进制贪心枚举, 找到最小符合条件的边数 Code #include<bits/stdc++.h> const int N = 5e5 + 5; typedef long long ll; __int32 f[15][305][305], dp[305][305], now[305][305]; int main() { std::ios::sync_wi...

Kurisu与牛客的每日...

0 点赞评论收藏

分享

2020-12-09 11:43

已编辑

北京师范大学 C++

【每日一题】A and B and Lecture Rooms 题解

Description 给出一棵树， 个询问，每次询问给出 ，需要得到有多少个点距离 相等。 Solution 分类讨论 时，每个点都可以，输出 为奇数时， 显然不存在点满足条件输出 剩余情况我们考虑结合 的特点 如果距离 相等的点在 上，如下图所示从他们的 开始的其他点都满足条件，即答案为 其中 是 往上跳 的点， 是 往上跳 的点 如果距离 相等的点不在 上，如下图所示我们选择两者中深度较大的点(), 往上跳 到 ，往上跳 到 ，答案即为 于是归纳出答案，上述两种情况分别为 Code #include<bits/stdc++.h> ...

Kurisu与牛客的每日...

0 点赞评论收藏

分享

2020-12-09 11:42

已编辑

北京师范大学 C++

【每日一题】倍增专题疫情控制题解

Description H 国有n 个城市，这 n 个城市用n-1 条双向道路相互连通构成一棵树，1 号城市是首都，也是树中的根节点。 H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。但特别要注意的是，首都是不能建立检查点的。 现在，在H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支...

Kurisu与牛客的每日...

0 点赞评论收藏

分享

2020-12-06 11:16

已编辑

北京师范大学 C++

牛客小白月赛30 题解

牛客小白月赛30 题解 A.黑白边 类似于最小生成树Kruscal算法的思想，用并查集维护当前的连通块直到放入 条边则实现了两两联通，因为要白边最少，排个序就可以了。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e6 + 5; const int mod = 1e9 + 7; struct Edge { int u, v, w; bool operator < (const Edge &s) const { retu...

lifehappy：lg yyds

0 点赞评论收藏

分享

关注他的用户也关注了：

牛客网
牛客企业服务