Project Euler problem 61
2024-10-19 04:25:26
题意很明了。
然后我大概的做法就是暴搜了
先把每个几边形数中四位数的处理出来。
然后我就DFS回溯着找就行了。
比较简单吧。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
vector<int>g[7], v[7][10000];
int vis[7];
void get_three()
{
for(int i = 1; ; i++)
{
int x = i * (i + 1) / 2;
if(x >= 10000) break;
if(x >= 1000) g[0].push_back(x);
}
}
void get_four()
{
for(int i = 1; ; i++)
{
int x = i * i;
if(x >= 10000) break;
if(x >= 1000) g[1].push_back(x);
}
}
void get_five()
{
for(int i = 1; ; i++)
{
int x = i * (3 * i - 1) / 2;
if(x >= 10000) break;
if(x >= 1000) g[2].push_back(x);
}
}
void get_six()
{
for(int i = 1; ; i++)
{
int x = i * (2 * i - 1);
if(x >= 10000) break;
if(x >= 1000) g[3].push_back(x);
}
}
void get_seven()
{
for(int i = 1; ; i++)
{
int x = i * (i * 5 - 3) / 2;
if(x >= 10000) break;
if(x >= 1000) g[4].push_back(x);
}
}
void get_eight()
{
for(int i = 1; ; i++)
{
int x = i * (3 * i - 2);
if(x >= 10000) break;
if(x >= 1000) g[5].push_back(x);
}
}
int a[7];
int ans;
int flag;
void dfs(int deep)
{
if(flag) return;
if(deep == 6)
{
if(a[5] % 100 == a[0] / 100)
{
flag = 1;
printf("%d\n", a[0] + a[1] + a[2] + a[3] + a[4] + a[5]);
return;
}
}
for(int i = 0; i < 6; i++)
{
if(!vis[i])
{
for(int j = 0; j < g[i].size(); j++)
{
int y = g[i][j];
if(!deep || y / 100 == a[deep - 1] % 100)
{
vis[i] = 1;
a[deep] = y;
dfs(deep + 1);
vis[i] = 0;
}
}
}
}
}
int main()
{
get_three();
get_four();
get_five();
get_six();
get_seven();
get_eight();
dfs(0);
return 0;
}
最新文章
- [LeetCode] Sentence Screen Fitting 调整屏幕上的句子
- happypack 原理解析
- Intent 转向
- ARM菜鸟:JLINK与JTAG的区别
- 纯手工全删除域内最后一个EXCHANGE--How to Manually Uninstall Last Exchange 2010 Server from Organization
- 2014-08-04 BBS主页页面的设计
- 利用mapreduce清洗日志内存不足问题
- 简陋的 ASP.NET CORE 单页Web应用程序“框架”
- Fitnesse - Slim Tables
- Python内置函数(54)——callable
- 剑指Offer——乐视笔试题+知识点总结
- java的finalize方法使用
- 树莓派(Raspberry Pi)使用Shell编写的极简Service
- Python 练习:三级菜单选择城市(二)
- 我学到的新知识之——Lotus Notes闪退如何修复
- LinkedHashMap结构get和put源码流程简析及LRU应用
- java.net.NoRouteToHostException
- 像素 转换 px dp
- js 下拉加载
- Centos7 安装netcat