Bernard5

题解

作业(2) 学习笔记(17) 技术教程(45) 期末应试(57) 未归档(17) 赛后分析(7) 题集(15)

/ 注册

全部文章 / 题解（共132篇）

环形纸牌均分问题贪心来自专栏

本题是一道非常经典的贪心问题。我们可以规定方向，进行单向传递，可以传递负数张纸牌，即为逆向抽取。规定每个人向左传递张纸牌。表示第个人向第个人传递的纸牌数量。最终每个人手中的纸牌数量是题目所求是指的可能的最小值。问题转化成「货仓选址问题」：给定数轴上的n个点，找出一个到它们的距离之和尽量...

贪心思维

2021-03-06

12 971

Berland Crossword 思维题来自专栏

给定矩阵大小，最顶上一行有多少黑格，最右一列有多少黑格，最下一行有多少黑格，最左一列有多少黑格。问是否存在这样的矩阵。 #include <bits/stdc++.h> #define sc(x) scanf("%d", &(x)) #define nxt (i + 1) % ...

2021-03-03

0 589

牛牛与比赛颁奖离散化差分来自专栏

本题其实是一道非常基础的离散化+差分的板子题。 #include <bits/stdc++.h> #define sc(x) scanf("%d", &(x)) #define pr(x) printf("%d ", (x)) #define rep(i, l, r) for (...

差分前缀和

2021-02-16

0 781

牛牛想要成为hacker 三角形思维构造来自专栏

本题很容易想到用斐波那契数列构建，但是fib很快就会超过1e9，数据项并不够。所以：不可能找不到三角形，只能推迟，但无法阻止时间复杂度提示 >>> from math import log2 >>> log2(100000) 16.60964047443...

构造思维

2021-02-16

1 624

牛牛与交换排序 deque 模拟来自专栏

简单分析后可知第一次操作必然使最小的、不在其位的数让它归位那么长度就已经固定了那么接下来要做的就是模拟，看能否完成排序即可可以用deque双端队列模拟，也可以用平衡树 #include <bits/stdc++.h> #define sc(x) scanf("%d", &am...

模拟思维

2021-02-16

1 632

牛牛的“质因数” 筛法 DFS 来自专栏

埃筛做法首先什么是埃筛： #include <stdio.h> #include <string.h> const int N = 100 + 8; int isPrime[N]; void sieve() { memset(isPrime, -1, sizeof ...

筛法数论

2021-02-16

2 734

牛牛与整除分块来自专栏

时化简可得于是以为界，在左边或者右边找对应的位置即可。 #include <bits/stdc++.h> #define sc(x) scanf("%lld", &(x)) #define pr(x) printf("%lld\n", (x)) #define rep(i, ...

数论数学整数分块

2021-02-08

1 553

点一成零并查集组合数学来自专栏

前置知识：简单并查集、简单逆元、简单组合数学本题数据量很小于是可以暴力合并，我这里是用dfs的，这样并查集就不用重复路径压缩了。用并查集维护，新加进来的数也可以实时合并或增加集合。答案其实就是每个集合里面的点数累乘，最后乘一个集合数量的全排列即可。详细来说就是：把所有相邻的1合并到同一集...

并查集组合数学

2021-02-02

6 736

幂塔个位数欧拉降幂来自专栏

本题可以找规律，但这里采用欧拉降幂的做法：欧拉降幂的前置知识是欧拉函数简单来说欧拉降幂其实就是一个公式表示同余，表示p的欧拉函数大数交给Python def phi(x): if x == 10: return 4 if x == 4: ret...

数学欧拉降幂

2021-02-02

5 600

红与蓝 DFS 染色来自专栏

叶子节点之与父亲有边相连，所以叶子节点必然与父亲同色。而父亲节点已经和叶子节点同色，所以叶子节点必然与爷爷节点异色。爷爷的颜色确定后，如果爷爷还与一条边相连，那么标记爷爷的相邻点颜色也确定。对于任何一条路径，可以这样递归上去。所以统计同色（友）信息然后再跑一边DFS染色即可 #include...

DFS 思维

2021-02-02

7 847