首页 > 试题广场 > 完美对
[编程题]完美对
  • 热度指数:600 时间限制:C/C++ 5秒,其他语言10秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
个物品,每个物品有个属性,第件物品的第个属性用一个正整数表示记为,两个不同的物品被称为是完美对的当且仅当,求完美对的个数。

输入描述:
第一行两个数字

接下来行,第个数字表示



输出描述:
一行一个数字表示答案
示例1

输入

5 3
2 11 21
19 10 1
20 11 1
6 15 24
18 27 36

输出

3
容易观察得到两个元素是完美对,它们的K个属性的差分为相反数,差分之和也为相反数。
因此,用哈希法存储元素下标,用K个属性的差分之和作为哈希值。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int a[100005][11];
int n,k;
vector<int>head[2005];
bool check(int x,int y)
{
    int sum=a[x][1]+a[y][1];
    for(int i=2;i<=k;i++)
        if(a[x][i]+a[y][i]!=sum)
        return false;
    return true;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int i,j,ans=0;
    cin>>n>>k;
    for(i=1;i<=n;i++)
        for(j=1;j<=k;j++)
        cin>>a[i][j];
    for(i=1;i<=n;i++)
    {
        int sum=0;
        for(j=2;j<=k;j++)
            sum+=a[i][j]-a[i][j-1];
        for(j=0;j<head[-sum+1000].size();j++)
            if(check(i,head[-sum+1000][j]))
                ans++;
        head[sum+1000].push_back(i);
    }
    cout<<ans;
    return 0;
}

发表于 2021-05-07 10:09:29 回复(4)
这题是个映射问题
两个数组a, b互为完美对的充分必要条件是:对于任意的i,j,有ai+bi=aj+bj
这等价于:ai-aj=-(bi-bj)
可以证明,上述命题等价于:
两个数组a, b互为完美对的充分必要条件是:对于任意不越界的i,i-1,有a[i]-a[i-1]=b[i]-b[i-1]

这个命题转换的目的是,将两个数组间的比较问题转换为了一个数组的自己的属性问题。如果我们将数组a所有相邻两数的差值求出来,并转换为一个字符串,那么与这个字符串“相反”的数组就是它的完美对,“相反”指字符串中数字相同,正负号相反。
注意属性值全相等的特殊情况。

思路明确之后代码就好写了:
class Solution {
private:
	int n, k;
	int allSameNum = 0;
	//<code:形如+1-2+3,code对应的物品个数>
	unordered_map<string, int> memo;
	string getAntiCode(const string &s) {
		string r;
		for (char c : s) {
			if (c == '+')
				r += '-';
			else if (c == '-')
				r += '+';
			else
				r += c;
		}
		return r;
	}
public:
	Solution() {
		cin >> n >> k;
		int temp, last;
		for (int i = 0; i < n; i++)
		{
			string code;
			bool allSame = true;
			for (int j = 0; j < k; j++)
			{
				cin >> temp;
				if (j == 0)
					last = temp;
				else {
					if (temp != last)
						allSame = false;
					if (temp - last > 0)
						code += '+';
					code += to_string(temp - last);
					last = temp;
				}
			}
			if (allSame)
				allSameNum += 1;
			else if (memo.count(code))
				++memo[code];
			else
				memo[code] = 1;
		}
	}
	void solve() {
		int r = 0;
		for (const auto &m : memo) {
			string antiCode = getAntiCode(m.first);
			if (memo.count(antiCode))
				r += m.second * memo[antiCode];
		}
		r /= 2;
		r += allSameNum * (allSameNum - 1) / 2;
		cout << r << endl;
	}
};


int main()
{
	ios::sync_with_stdio(false);
	Solution s;
	s.solve();
	return 0;
}


编辑于 2021-05-31 16:35:03 回复(0)
我真傻,我居然花了这么久的时间优化求交集的过程,没想到一个哈希就解决了。。。
def count(n, k, a_list):
    cnt = 0
    delta_map = dict()
    for i in range(n):
        delta_list = []
        for m in range(k-1):
            delta_list.append(a_list[i][m+1] - a_list[i][0])
        p_str = ' '.join([str(j) for j in delta_list])
        n_str = ' '.join([str(-j) for j in delta_list])
        if delta_map.get(n_str):
            cnt += delta_map.get(n_str)
        if delta_map.get(p_str):
            delta_map[p_str] += 1
        else:
            delta_map[p_str] = 1
    return cnt

编辑于 2021-04-28 14:49:05 回复(0)

热门推荐

通过挑战的用户