这道题目学到的是,如果是bool类型的判断,亲你还是用数组,加上初始化来得容易一些啊,然后判断是否是Bisquare的时候脑子抽筋,没有直接根据index去判断,导致一开始总是超时。但是值得鼓励的是自己的思路还是正确的,昨天关于数组的想法并没有及时记录或者实现。
下面是最终代码:
/* ID: bbsunch2 PROG: ariprog LANG: C++ */ #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<queue> #include<map> #include<set> #include<cmath> #include<algorithm> #include<fstream> using namespace std; const long M_MAX=250; int N,M; bool bNumIsBisquare[(M_MAX)*(M_MAX)*2+1]; int calculate_bisquares(const int upperBound){ for(int i = 0; i <= M; i++){ for(int j = 0; j <= M; j++){ bNumIsBisquare[i*i+j*j] = true; } } } bool arithmetic_progression(const int i, const int j){ for(int k =0; k < N; k++){ if(!bNumIsBisquare[i+k*j]) return false; } return true; } int main(){ ofstream fout("ariprog.out"); ifstream fin("ariprog.in"); fin >> N; fin >> M; int squareM = M*M; int upperBound = 2* squareM+1; bool found = false; memset(bNumIsBisquare, false, sizeof(bNumIsBisquare)); calculate_bisquares(upperBound); map<int, vector<int> > difference__firstNumbers; for(int i = 0; i < upperBound; i++){ for(int j = 1; j < upperBound; j++){ if (i + (N-1)*j > upperBound) break; if( arithmetic_progression(i,j)){ found = true; if(difference__firstNumbers.find(j) == difference__firstNumbers.end()){ vector<int> tempVector; tempVector.push_back(i); difference__firstNumbers.insert(pair<int, vector<int> > (j, tempVector)); }else{ difference__firstNumbers[j].push_back(i); } } } } if(!found){ fout << "NONE" << endl; return 0; } for(map<int, vector<int> >::iterator it = difference__firstNumbers.begin(); it != difference__firstNumbers.end(); it++){ int difference = it->first; vector<int> firstNumbers = it->second; sort(firstNumbers.begin(), firstNumbers.end()); for(int i = 0; i < firstNumbers.size(); i++){ cout << firstNumbers[i] << " " << difference << endl; fout << firstNumbers[i] << " " << difference << endl; } } return 0; }
相关推荐
USACO所有题目的题解 NOCOW整理版
USACO题解+代码+翻译,好东西,超级齐全,对大家帮助不小,特别是现在nocow挂了
Usaco总结&题解 一位大牛写的Usaco的总结,并有所有题的题解,推荐!!
USACO教程,包含USACO全部英文原题,题解(NOCOW整理版),翻译,教程,代码,测试数据。
我的USACO题解和程序
USACO月赛题解1
USACO题解(NOCOW整理版).doc
USACO1.4~2.3C语言题解 绝对能通过
丰富的USACO1.1--2.3.4的所有题解
usaco解题报告,就是usaco.training.gateway上面的题目全解
非常详细的题解,个人觉得很好,帮助非常大。nocow关闭后不太好找资源了。
USACO题解及中文译题1.1.1-2.4.5 题目为TXT格式文档,代码为C++语言所编写
非常详细的题解,比较全的,个人觉得刷题者可以入手,帮助非常大。
非常详细的题解,比较全的,个人觉得刷题者可以入手,帮助非常大。
非常详细的题解,个人觉得比较全的,刷题者可以入手,帮助会非常大。
usaco全部题解。 网址:blog.csdn.net/jiangshibiao
usaco的某道题的题解
里面有usaco前几节的程序和代码,欢迎使用,希望对你有所帮主。
数据结构机考所参考的USACO网站所有题目的解题思路,资源比较稀有!
usaco Chapter2 usaco 第二章 题解