EOJ3652 乘法还原
题目链接
https://acm.ecnu.edu.cn/problem/3652/
题目大意
两个序列，分别是 $\{a_i\}$ 和 $\{b_i\}$，随后用这两个序列构造了一个表达式 $(x_{a_1} + … + x_{a_m})(x_{b_1} + … + x_{b_n})$。告诉你这个表达式的展开式，让你还原出这两个序列。
题目分析
对于给出的展开式中，如果有两项相同的话，说明 $a$ 和 $b$ 中都有这一项，可以直接将其加入 $a$ 和 $b$ 中。对于其他的，可使用 $DFS$ 对其进行染色，任何一个连边的都不属于同样的集合。注意有可能只有一边有未出现的项，需要单独处理。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
const int maxn = 1e5 + 5;
int n;
vector <int> a;
vector <int> b;
vector <int> ansa;
vector <int> ansb;
map <int, bool> m;
map <int, vector <int> > e;
map <int, bool> v;
int read(){
int x;
scanf("%d", &x);
return x;
}
bool check(){
if(ansa.size() != ansb.size()){
return ansa.size() > ansb.size();
}else{
for(int i=0;i<ansa.size();i++){
if(ansa[i] != ansb[i]){
return ansa[i] > ansb[i];
}
}
}
return false;
}
int addedge(int x, int y){
e[x].push_back(y);
e[y].push_back(x);
return 0;
}
int dfs(int x, int d){
int i, j;
int y;
v[x] = true;
if(d == 0){
ansa.push_back(x);
}else{
ansb.push_back(x);
}
for(i=0;i<e[x].size();i++){
y = e[x][i];
if(!v[y]){
dfs(y, !d);
}
}
return 0;
}
int main(){
int i, j;
int x, y;
int root = 0;
int cnt = 0;
n = read();
for(i=1;i<=n;i++){
x = read();
y = read();
if(x == y){
ansa.push_back(x);
ansb.push_back(y);
m[x] = true;
cnt++;
}else{
a.push_back(x);
b.push_back(y);
}
}
for(i=0;i<a.size();i++){
x = a[i];
y = b[i];
if(m[x] or m[y]){
continue;
}else{
addedge(x, y);
root = x;
}
}
if(root)dfs(root, 0);
if(ansa.size() == cnt){
for(i=0;i<a.size();i++){
x = a[i];
y = b[i];
if(!m[x]){
ansb.push_back(x);
m[x] = true;
}else if(!m[y]){
ansb.push_back(y);
m[y] = true;
}
}
}
sort(ansa.begin(), ansa.end());
sort(ansb.begin(), ansb.end());
if(check()){
swap(ansa, ansb);
}
printf("%d %d\n", ansa.size(), ansb.size());
for(i=0;i<ansa.size();i++){
printf("%d ", ansa[i]);
}
printf("\n");
for(i=0;i<ansb.size();i++){
printf("%d ", ansb[i]);
}
printf("\n");
return 0;
}