蓝桥杯冲冲冲~
回顾
🔖蓝桥杯每日练习（巧排扑克牌，质数拆分，日志统计，递增三元组，外卖店优先级）
🔖蓝桥杯每日练习（猴子分香蕉，等差数列，平方序列，倍数问题）
🔖蓝桥杯每日练习（纯质数（筛法的应用），最少砝码，灌溉）
🔖蓝桥杯每日练习（年龄巧合，纸牌三角形，取球游戏）
🚶引言
今天继续蓝桥杯每日练习~ 今天的题目前两个相对简单，最后一个用到了无向图拓扑找环的知识。拓扑找环是一个很重要的知识点，他可能不会出专门的题目，但是对很多题目来说他都是其中一个环节。我是学习算法的小菜鸡，每天一个小知识点，我们国赛见~
🚀今日题目
💓相乘
题目描述
小蓝发现，他将 1 至 1000000007 之间的不同的数与 2021 相乘后再求除以 1000000007 的余数，会得到不同的数。 小蓝想知道，能不能在 1 至 1000000007 之间找到一个数，与 2021 相乘后 再除以 1000000007 后的余数为 999999999。如果存在，请在答案中提交这个数； 如果不存在，请在答案中提交 0。
原题传送门
解题报告
根据题目模拟，把表达式写出来for就可以了。但是数字比较大，有一定的超时风险，所以我们需要一定的化简。题目求余数的过程其实可以等价为减去一个数以后正好能整除，然后这道题一个逆过程用整倍数加上余数就等得到原来的数。
x
%
y
=
=
a
<
=
=
>
(
x
?
a
)
%
y
=
=
0
x\%y==a <==> (x-a)\%y==0
x%y==a<==>(x?a)%y==0
参考代码(C++版本)
#include <iostream>
#define int long long
using namespace std;
const int flag=1e9+7;
signed main()
{
for(int k=1;;k++) {
if((k*flag+999999999)%2021==0) {
cout<<(k*flag+999999999)/2021<<endl;
break;
}
}
return 0;
}
🌟空间
🌱题目描述
小蓝准备用 256MB 的内存空间开一个数组，数组的每个元素都是 32 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB 的空间可以存储多少个 32 位二进制整数？
原题传送门
🌴解题报告
换算单位
1
M
B
=
1024
K
B
1MB=1024KB
1MB=1024KB
1
K
B
=
1024
B
1KB=1024B
1KB=1024B
1
B
=
8
b
1B=8b
1B=8b
🌵参考代码(C++版本)
#include <iostream>
using namespace std;
int main()
{
cout<<256*1024*1024/4<<endl;
return 0;
}
发现环
题目描述
小明的实验室有 N 台电脑，编号 1?N。原本这 N 台电脑之间有 N?1 条数据链接相连，恰好构成一个树形网络。在树形网络上，任意两台电脑之间有唯一的路径相连。
不过在最近一次维护网络时，管理员误操作使得某两台电脑之间增加了一条数据链接，于是网络中出现了环路。环路上的电脑由于两两之间不再是只有一条路径，使得这些电脑上的数据传输出现了 BUG。
为了恢复正常传输。小明需要找到所有在环路上的电脑，你能帮助他吗？
原题传送门
🚗解题报告
读完题以后可以发现这就是一道无向图找环的问题。对于这道题有挺多做法的，dfs、并查集……这里介绍一种经典做法：拓扑排序。
首先，什么是拓扑排序？拓扑排序一般对于有向图，满足每个顶点出现且只出现一次且若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。那么我们的做法是什么？先把入读为0的点放到队列里，作为起点。然后遍历起点能到达的点，每次遍历到就说明对于这个方向上它前面的点都遍历过了，所以入度就减一。入度减为0，就说明这个点前面的点都被遍历过了，就把他当作起点，如此循环。
无向图也可以借鉴这一做法，因为一条无向边就是两条方向相反的有向边。然后什么情况就可以说明我们找到环了？当一个点如此做完以后度数还是大于1就说明他必定是环里面的元素。为什么呢？因为环里面的点至少有两条边，并且不可能说他在某个方向前面的点全部被删去，所以他的度数始终至少为2。
参考代码(C++版本)
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e6 + 10;
int ne[N], num[N], h[N], len[N];
int idx, n;
queue<int>res;
void add(int a, int b) {
ne[idx] = h[a];
num[idx] = b;
len[b]++;
h[a] = idx++;
}
void find() {
for (int i = 1; i <= n; i++) {
if (len[i] == 1) res.push(i);
}
while (res.size()) {
int t = res.front();
res.pop();
for (int i = h[t]; i != -1; i = ne[i]) {
len[num[i]]--;
if (len[num[i]] == 1) res.push(num[i]);
}
}
}
int main() {
memset(h, -1, sizeof(h));
cin >> n;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
find();
for (int i = 1; i <= n; i++) {
if (len[i] > 1) cout << i << ' ';
}
}
|