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 }

View Code