首页 > 代码库 > Arithmetic Progressions
Arithmetic Progressions
链接
分析:首先预处理数据集,然后将数据集排序,我们对于当前位置,去搜索是否存在满足条件的等差数列即可,之前一直TLE,完全是map的锅,太慢了
1 #include "iostream" 2 #include "cstdio" 3 #include "cstring" 4 #include "map" 5 #include "algorithm" 6 #include "vector" 7 using namespace std; 8 const int maxn=2e5; 9 struct Node{ 10 int x,y; 11 }; 12 int mp[maxn]; 13 vector<int> h; 14 vector<Node> p; 15 int n,m,len; 16 bool cmp(Node a,Node b){ 17 if(a.y==b.y){ 18 return a.x<b.x; 19 } 20 return a.y<b.y; 21 } 22 int main() 23 { 24 cin>>n>>m; 25 for(int i=0;i<=m;i++){ 26 for(int j=i;j<=m;j++){ 27 int num=i*i+j*j; 28 if(!mp[num]){ 29 mp[num]=1; 30 h.push_back(num); 31 } 32 } 33 } 34 sort(h.begin(),h.end()); 35 len=h.size(); 36 int cnt=0; 37 for(int i=0;i<len-n+1;i++){ 38 for(int j=i+1;j<len-n+2;j++){ 39 int cha=h[j]-h[i]; 40 int flag=0; 41 if(h[i]+(n-1)*cha>h[len-1]) break; 42 for(int k=1;k<=n-2;k++){ 43 if(h[i]+(k+1)*cha>h[len-1]){ 44 flag=2; break; 45 } 46 if(!mp[h[j]+k*cha]){ 47 flag=1; break; 48 } 49 } 50 if(flag==2) break; 51 if(!flag){ 52 cnt++; 53 Node tt; 54 tt.x=h[i],tt.y=cha; 55 p.push_back(tt); 56 } 57 } 58 } 59 if(cnt==0){ 60 cout<<"NONE"<<endl; 61 }else{ 62 sort(p.begin(),p.end(),cmp); 63 //cout<<cnt<<endl; 64 for(int i=0;i<p.size();i++) 65 cout<<p[i].x<<" "<<p[i].y<<endl; 66 } 67 return 0; 68 }
Arithmetic Progressions
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。