关于本题正解
查看原帖
关于本题正解
1053122
shy_lihui楼主2024/8/29 15:42

通过长逝,暴力不用任何优化也就是O(n4)O(n^4)的复杂度可以得到20pts,然后我尝试了哈希表的做法如下

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;
struct node
{
	int x,y;
};
int n,m;
unordered_map<int,vector<node>>mp;
int main()
{
	
	cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			int num;
			cin>>num;
			mp[num].push_back({i,j});
		}
	}
	int ans=0;
	for(const auto &p:mp)
	{
		const auto &v=p.second;
		for(int i=0;i<v.size();i++)
		{
			for(int j=i+1;j<v.size();j++)
			{
				int x1=v[i].x,y1=v[i].y;
				int x2=v[j].x,y2=v[j].y;
				if(abs(x1-x2)==abs(y1-y2)&&abs(x1-x2)>0)
				{
					ans++;
				}
			}
		}
	}
	cout<<ans*2;
	return 0;
}

但很明显这个复杂度是O(n3)O(n^3)只能得到40pts,各位dalao能不能优化一下

2024/8/29 15:42
加载中...