Elementary Math、

二分图匹配+离散化

#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
#include<iostream>
using namespace std;
typedef __int64 ll;
const int qq = 2505;
vector <int> adj[qq];
map<ll,int>notoint;
int N,nodes,pred[qq*3];
ll a[qq],b[qq],idtores[qq*3],res[qq];
bool mark[qq*3];
bool match(int i){	//访问左边的顶点、 
	for(int j=0; j<adj[i].size(); ++j){
		int x=adj[i][j];	//与当前有联系的右边的顶点、 
		if(mark[x])	continue;		//没判断这个又调试了一会、 
		mark[x]=true;
		if(pred[x]==-1 || match(pred[x])){
			pred[x]=i;			//右边的x顶点连边 i 、 
			return true;
		}
	}
	return false;
}
int maxmatch(){
	memset(pred, -1, sizeof(pred));
	int res=0;
	for(int i=0; i<N; ++i){
		memset(mark, false, sizeof(mark));
		if(match(i))	res++;
	}
	return res;
}
int get(ll x){		//得到的结果为键值、 
	if(!notoint.count(x)){
		notoint[x] = nodes++;	//每一个值对应一个数字进行离散化、用map记录 
		idtores[notoint[x]] = x;	//然后用这个数组还原数值、 
	}
	return notoint[x];	//返回每一个值离散化后的数字、 
}
int main(){
	cin >> N;
	nodes=0;
	for(int i=0; i<N; ++i){
		cin >> a[i] >> b[i];
		adj[i].push_back(get(a[i]+b[i]));
		adj[i].push_back(get(a[i]-b[i]));
		adj[i].push_back(get(a[i]*b[i]));
	}
//	for(int i=0; i<N; ++i)
//		for(int j=0; j<adj[i].size(); ++j)
//			printf("%d\n",adj[i][j]);
	if(maxmatch() < N)	cout << "impossible" << endl;
	else{
		for(int i=0; i<nodes; ++i)	
			if(pred[i]>=0)
				res[pred[i]]=idtores[i];
		for(int i=0; i<N; ++i){
			char ch='+';
			if(a[i]-b[i]==res[i])	ch='-';
			else if(a[i]*b[i]==res[i])	ch='*';
			cout << a[i] << " " << ch << " " << b[i] << " = " << res[i] << endl;
		}
	}
	return 0;
}