1 //枚举左上、右下顶点 时间复杂度O(n^2*m^2) 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long LL; //LL是已经定义好的long long 5 int main(){ 6 int n,m; 7 LL squ=0,rec=0;//squ统计正方形个数,rec统计长方形个数 8 cin>>n>>m; 9 for(int x1=0;x1<n;x1++) 10 for(int y1=0;y1<m;y1++) 11 for(int x2=x1+1;x2<=n;x2++) 12 for(int y2=y1+1;y2<=m;y2++) //四层循环不TLE才怪 13 if (x2-x1 == y2-y1)squ++; 14 else rec++; 15 cout<<squ<<" "<<rec<<endl; 16 return 0; 17 }
1 //枚举一个点构成的所有矩形,统计结果除4 时间复杂度O(n*m) 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long LL; //LL是已经定义好的long long 5 int main(){ 6 int n,m; 7 LL squ=0,rec=0; 8 cin>>n>>m; 9 for(int x=0;x<=n;x++) 10 for(int y=0;y<=m;y++){ 11 LL tmp=min(x,y)+min(n-x,y)+min(x,m-y)+min(n-x,m-y);//对角线的正方形枚举方式 12 squ+=tmp; 13 rec+=n*m-tmp; 14 } 15 cout<<squ/4<<" "<<rec/4<<endl;//四个顶点算了四次,所以要除4输出 16 return 0; 17 }
还能不能更快呢?
1 //枚举右下角顶点 时间复杂度O(n*m) 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long LL; 5 int main(){ 6 int n,m; 7 LL squ=0,rec=0; 8 cin>>n>>m; 9 for(int x=0;x<=n;x++) 10 for(int y=0;y<=m;y++){ 11 LL tmp=min(x,y); 12 squ+=tmp; 13 rec+=x*y-tmp; 14 } 15 cout<<squ<<" "<<rec<<endl; 16 return 0; 17 }
1 //枚举两条边 时间复杂度O(n*m) 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long LL; 5 int main(){ 6 int n,m; 7 LL squ=0,rec=0; 8 cin>>n>>m; 9 for(int a=1;a<=n;a++) 10 for(int b=1;b<=m;b++) 11 if(a==b) 12 squ+=(n-a+1)*(m-b+1); 13 else 14 rec+=(n-a+1)*(m-b+1); 15 cout<<squ<<" "<<rec<<endl; 16 return 0; 17 }
1 //枚举一条边 时间复杂度:O(n) 2 #include<bits/stdc++.h> 3 using namespace std; 4 typedef long long LL; 5 int main(){ 6 int n,m; 7 LL squ=0,rec=0; 8 cin>>n>>m; 9 for(int a=1;a<=min(n,m);a++) 10 squ+=(n-a+1)*(m-a+1); 11 rec=(n+1)*n*(m+1)*m/4-squ; 12 cout<<squ<<" "<<rec<<endl; 13 return 0; 14 }
转载自: https://www.cnblogs.com/zhangqixun/p/17078440.html