Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

USACO 1.1.4 Arithmetic Progressions

Posted on 2007-05-30 22:18 ZelluX 阅读(553) 评论(0)  编辑  收藏 所属分类: Algorithm
第一次做是用一张hash表记录的所有的数是否为所谓的bisquare,然后先枚举公差,再枚举首项,本来想这样做就不用再对结果排序了,没想到效率很低。
改为先枚举首项,再枚举第二项,然后计算公差后,速度提高不少。
另外第一次使用sort方法。
/*
PROG: ariprog
ID: 06301031
LANG: C++
*/


#include 
<iostream>
#include 
<fstream>
#include 
<vector>
#include 
<algorithm>

using namespace std;

struct Ans {
    
int start;
    
int step;
}
;

bool compareOp(const Ans& ans1, const Ans& ans2);

int main() {
    ifstream fin(
"ariprog.in");
    ofstream fout(
"ariprog.out");
    
int n, m, i, j, k;
    
bool solved = false;
    fin 
>> n >> m;

    
// generate Arithmetic Progressions sequence
    bool seq[250*250*2 + 1];    
    
for (i = 0; i <= m * m * 2; i++{
        seq[i] 
= false;
    }

    
for (i = 0; i <= m; i++{
        
for (int j = 0; j <= i; j++{
            seq[i
*+ j*j] = true;
        }

    }


    vector
<Ans> result;
    
int step;
    
for (i = 0; i <= m * m * 2; i++{
        
if (!seq[i]) {
            
continue;
        }

        
for (j = i + 1; j <= m * m * 2; j++{
            
if (!seq[j]) {
                
continue;
            }

            step 
= j - i;
            
if (i + step * (n - 1> m * m * 2{
                
break;
            }


            
bool flag = true;
            
for (k = 1; k < n; k++{
                
if (!seq[i + step * k]) {
                    flag 
= false;
                    
break;
                }

            }

            
if (flag) {
                Ans ans;
                ans.start 
= i;
                ans.step 
= step;
                result.push_back(ans);
                solved 
= true;
            }

        }

    }

    
if (!solved) {
        fout 
<< "NONE" << endl;
    }


    sort(result.begin(), result.end(), compareOp);
    vector
<Ans>::iterator iter;
    
for (iter = result.begin(); iter != result.end(); iter++{
        fout 
<< iter->start << " " << iter->step << endl;
    }

    fout.close();
    
return 0;
}


bool compareOp(const Ans& ans1, const Ans& ans2) {
    
return ans1.step < ans2.step;
}

只有注册用户登录后才能发表评论。


网站导航: