公关策划网站建设,合肥瑶海区网站建设价格,公司做网站推广的价格,邢台网约车新政策蓝桥杯大赛历届真题 - CC 大学 B 组 - 蓝桥云课 (lanqiao.cn)
题目描述 题目分析
对于此题#xff0c;首先想到了dfs进行一一找寻#xff0c;注意每次不要将重复的算进去#xff0c;故我们每次循环可以记录一个开始的位置#xff0c;下一次到这个位置时#xff0c;…蓝桥杯大赛历届真题 - CC 大学 B 组 - 蓝桥云课 (lanqiao.cn)
题目描述 题目分析
对于此题首先想到了dfs进行一一找寻注意每次不要将重复的算进去故我们每次循环可以记录一个开始的位置下一次到这个位置时这个数就不会被重复选择
没有运行出来的代码
#includebits/stdc.h
using namespace std;
typedef unsigned long long ull;
const int N 2e5 10;
ull ans, a[N];
void dfs(int n, ull start)
{if(n 3) {ull sum a[0];for(int i 1; i 3; i )sum * a[i];if(sum 2021041820210418)ans ;return;}for(ull i start; i 2021041820210418; i ){a[n] i;dfs(n 1, i);a[n] 0;}
}
int main()
{dfs(0, 1);cout ans;return 0;
}
发现数字过大运行时间过长思考如何进行优化想到这三个数都是2021041820210418的因数这三个数乘积为2021041820210418故我们可以先将2021041820210418的所有因数找出来在这些因数中进行dfs
#includebits/stdc.h
using namespace std;
const int N 2e5 10;
typedef unsigned long long ull;
ull cnt, a[N], q[N], ans;
void dfs(int dep, ull start)
{if(dep 3){ull sum q[0];for(int i 1; i 3; i )sum * q[i];if(sum 2021041820210418){ans ;}return;}for(ull i 0; i cnt; i ){q[dep] a[i];dfs(dep 1, i);q[dep] 0;}
}
int main()
{for(ull i 1; i 2021041820210418 / i; i ){if(2021041820210418 % i)continue;a[cnt ] i;if(i ! 2021041820210418 / i)a[cnt ] 2021041820210418 / i;}dfs(0, 0);cout ans;return 0;
}
得到正解2430
当然也可以一进行纯纯暴力
#includebits/stdc.h
using namespace std;
const int N 2e5 10;
typedef unsigned long long ull;
ull cnt, a[N], q[N], ans;
int main()
{for(ull i 1; i 2021041820210418 / i; i ){if(2021041820210418 % i)continue;a[cnt ] i;if(i ! 2021041820210418 / i)a[cnt ] 2021041820210418 / i;}for(int i 0; i cnt; i ){for(int j 0; j cnt; j ){for(int k 0; k cnt; k ){if(a[i] * a[j] * a[k] 2021041820210418)ans ;}}}cout ans;return 0;
}
