USACO 1.4 Arithmetic Progressions

用一个bool数组标记一下,然后暴力....最长3秒多,题目要求5秒以内即可。

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

using namespace std;

ifstream fin(
"ariprog.in");
ofstream fout(
"ariprog.out");

#ifdef _DEBUG
#define out cout
#define in cin
#else
#define out fout
#define in fin
#endif

bool mark[250*250*2+1];

void solve()
{
    
int n,m;
    
in>>n>>m;

    memset(mark,
0,sizeof(mark));

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

    
int max = m*m*2+1;

    vector
<int>v;
    v.reserve(max);

    
for(int i=0;i<max;++i)
        
if(mark[i])
            v.push_back(i);


    
int size = v.size();

    
int max_len = (v[size-1]-v[0])/(n-1);

    
bool find = false;

    
for(int len=1;len<=max_len;len++){
        
for(int i=0;i<size;++i){
            
int cnt = n-1;
            
int t =v[i];
            
while(cnt){
                t
+=len;
                
if(t>v[size-1])
                    
break;
                
if(!mark[t])
                    
break;
                cnt
--;
            }

            
if(cnt==0){
                find 
= true;
                
out<<v[i]<<' '<<len<<endl;
            }
        }
    }

    
if(!find)
        
out<<"NONE"<<endl;
}

int main(int argc,char *argv[])
{
  solve();
  
return 0;
}



posted on 2009-06-10 23:25 YZY 阅读(1321) 评论(3)  编辑 收藏 引用 所属分类: AlgorithmUSACO

评论

# re: USACO 1.4 Arithmetic Progressions[未登录] 2009-06-11 10:37 megax

做题也能上瘾啊~~~
我给你来点实际的.写个字符串倒序查找吧.kmp, bm啊,能用的你都用上.  回复  更多评论   

# re: USACO 1.4 Arithmetic Progressions 2011-01-26 12:02 aaa

貌似你3s多的话不用C++就TLE了。。。
呵呵  回复  更多评论   

# re: USACO 1.4 Arithmetic Progressions 2011-01-26 12:04 aaa

其实可以再优化的
你要再开一个整型数组
枚举首项的时候就直接从这个数组里面取
会快很多  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2011年1月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜