Charfole's Blog

蓝桥杯踩坑题

发表于 更新于 分类于 Valine：
本文字数： 1.6k 阅读时长 ≈ 1 分钟

前言

今天又是一年一度的蓝桥（baoli）杯大赛，小 J 同学经过了两年的参赛，对于前三题秉承着能 baoli 就不要思考的出发点来做题，结果他今天在第三题填空题用暴力法踩坑了，比赛中卡了一小时居然还没做出来。睡了一觉下午清醒之后，用三分钟想到了一个简单的做法，写下了这篇博文。

题面

想不起完整的题目了，下面大概复述一下。

小明是个富二代，家里仓库非常大，里面常常装满了他网购来的各种好东西。有一天，他刚学完 C++，想算一算自己家仓库的长宽高（都是整数）最多可以有多少种组合，但他想了好久也没想出来，你能帮帮他吗？

比如仓库的体积为 4，那么就有 1×4×1，1×1×4，4×1×1，1×2×2，2×1×2，2×2×1 这六种放法，下面要求的是当体积为 2021041820210418 的情况下，共有几种放法。

心路历程

这个非常直白也没有什么难度的题为什么卡了我那么久？ 大概还是因为自己一开始想的太过简单吧，因为太久没练算法题，当时一看到是个没有时间限制的填空题，就想着直接三重循环开干了。后来发现不太对，十六位数的三重循环算一天也未必算得完，后来断断续续又加了一些约束条件，比如：只用两个循环，最后一个数用除法来确定；第一层循环中的 $i$ 只遍历到 $\sqrt{N}$ ，第二层循环中的 $j$ 只遍历到 $\sqrt{N/i}$并且用 gcd 判断是否为互质的数，但，这些小伎俩在十六位数面前都是徒劳。十六位数面前只有使用 $O(\sqrt{N})$ 的算法才可以在短时间内得到解，当时在最后时间内明白了这一点后，再去想其他方法时间已经不太够了。

直到下午一觉睡醒，才突然醒悟，最常见的 $O(\sqrt{N})$ 算法不就是找因子数算法吗，大一就学过了，果然还是太久没有做题，并且在比赛的时候从一个错的方向进行思考，然后坑越踩越深，想回头也比较困难了。

虽然题解真的比较简单，但还是在下面写一下留个记录吧。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cmath>
#define ll long long

ll factor[10005];//因子数组 

using namespace std;
int main()
{
	//cin\cout 输入输出加速 
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int cnt=0;
	int ans=0;
	ll N;
	//2021041820210418 仓库体积大小 
	cin >> N;
	for(int i=1;i<=sqrt(N);i++)
	{
		if(N%i==0)
		{
			factor[cnt++] = i;
			if(N/i != i)
			{
				factor[cnt++] = N/i;
			}	
		}
	}
	//三重循环遍历所有因子组合（也挺暴力的其实） 
	for(int i=0;i<cnt;i++)
	for(int j=0;j<cnt;j++)
	{
		// 在第二个循环里判断一下，不符合的因子可以跳过 
		if(factor[i]*factor[j]>N)
		{
			continue;
		}
		for(int k=0;k<cnt;k++)
		{	
			if(factor[i] * factor[j] * factor[k] == N)
			{
				ans++;
			}
		}	
	}
	cout << ans << endl;
	return 0;
}

总结

今年蓝桥杯的题整体难度上升了不少，填空题已经开始考图论题目了，稍微简单一点的填空题也没有以前好做了，甚至在大题第二题还涉及了比较少见的博弈论内容，总体来说题目可以说是更有区分度了吧。