Home > Old Blog Posts > USACO 1.4.3 Arithmetic Progressions

USACO 1.4.3 Arithmetic Progressions


最简单的方法就是枚举a和b,但超时会超的很惨烈,于是开始优化,最直接的思路就是缩小枚举的范围,由此:

int tmp2=(M*M)<<1,tmp=(int)(tmp2/(N-1));
for(a=0;a<=tmp2;a++)
for(b=1;b<=tmp&&a<=tmp2-b*(N-1);b++)

优化仅仅靠这三行就足够AC。

但其实还有一个很强大的优化,就是直接枚举公差,不过我没用。

代码:

/*
ID: dementr1
PROG: ariprog
LANG: C++
*/
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin(“ariprog.in”);
ofstream fout(“ariprog.out”);
bool A[125001]={false};
int number[100000],print[10000][2],
num,N,M,ans=0;

void swap(int *a, int *b)
{
int x=*a;
*a=*b;
*b=x;
}
int partition(int A[][2],int left, int right)
{
int i=(left+right)/2,j;
swap(&A[i][0],&A[right][0]);
swap(&A[i][1],&A[right][1]);
i=left-1;
for(j=left;j<right;j++)
{
if(A[j][1]<A[right][1]||(A[j][1]==A[right][1]&&A[j][0]<A[right][0]))
{
i++;
swap(&A[i][0],&A[j][0]);
swap(&A[i][1],&A[j][1]);
}
}
i++;
swap(&A[i][0],&A[right][0]);
swap(&A[i][1],&A[right][1]);
return i;
}
void quicksort(int A[][2], int left, int right)
{
int i;
if(left<right)
{
i=partition(A,left,right);
quicksort(A,left,i-1);
quicksort(A,i+1,right);
}
}
void init()
{
fin>>N>>M;
}
void create()
{
int i,j;
for(i=0;i<=M;i++)
for(j=0;j<=i;j++)
A[i*i+j*j]=true;
}
void work()
{
int b,a,k,i;
int tmp2=(M*M)<<1,tmp=(int)(tmp2/(N-1));

for(a=0;a<=tmp2;a++)
{
for(b=1;b<=tmp&&a<=tmp2-b*(N-1);b++)
{
bool flag=true;
for(i=0;i<N;i++)
if(!A[a+b*i])
{
flag=false;
break;
}
if(flag)
{
print[ans][0]=a;
print[ans++][1]=b;
}
}
}
}
int main()
{
init();
create();
work();
quicksort(print,0,ans-1);
for(int i=0;i<ans;i++)
{
if(i==0||print[i][0]!=print[i-1][0]||print[i][1]!=print[i-1][1]) fout<<print[i][0]<<” “<<print[i][1]<<endl;
}
if(ans==0) fout<<“NONE”<<endl;
return 0;
}

Categories: Old Blog Posts
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: