【CCCC】L2-028 秀恩爱分得快 (25分)，模拟题

problem

L2-028 秀恩爱分得快 (25分)
古人云：秀恩爱，分得快。

互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？

输入格式：
输入在第一行给出 2 个正整数：N（不超过1000，为总人数——简单起见，我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的负号表示女性）和 M（不超过1000，为照片总数）。随后 M 行，每行给出一张照片的信息，格式如下：

K P[1] … P[K]
其中 K（≤ 500）是该照片中出现的人数，P[1] ~ P[K] 就是这些人的编号。最后一行给出一对异性情侣的编号 A 和 B。同行数字以空格分隔。题目保证每个人只有一个性别，并且不会在同一张照片里出现多次。

输出格式：
首先输出 A PA，其中 PA 是与 A 最亲密的异性。如果 PA 不唯一，则按他们编号的绝对值递增输出；然后类似地输出 B PB。但如果 A 和 B 正是彼此亲密度最高的一对，则只输出他们的编号，无论是否还有其他人并列。

输入样例 1：
10 4
4 -1 2 -3 4
4 2 -3 -5 -6
3 2 4 -5
3 -6 0 2
-3 2
输出样例 1：
-3 2
2 -5
2 -6
输入样例 2：
4 4
4 -1 2 -3 0
2 0 -3
2 2 -3
2 -1 2
-3 2
输出样例 2：
-3 2

• 给出n个人，求一对cp最亲密的异性是谁
• 给出m张照片，每张上的k个人两两亲密度+=1/k

solution

• 枚举照片，如果出现了cp，累加他们和其他异性的亲密度，排序输出。
• 对于0和-0，把他们转换为1000以上（大于范围就行）
• BUG了一次，只有15分，改不动了，重新写一遍

//AC
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a, int b){
  if(abs(a)==1000)return true;
  if(abs(b)==1000)return false;
  return abs(a)<abs(b);
}
int main(){
  //input
  int n, m, sex[1010]={0};
  cin>>n>>m;
  vector<vector<int>>photo(m);
  for(int i = 0; i < m; i++){
    int k;  cin>>k;
    for(int j = 0; j < k; j++){
      string s;  cin>>s;
      if(s=="0")s="1000";
      if(s=="-0")s="-1000";
      int tmp = stoi(s);
      photo[i].push_back(tmp);
      sex[abs(tmp)] = tmp;
    }
  }
  int cp[3];
  for(int i = 1; i <= 2; i++){
    string s;  cin>>s;
    if(s=="0")s="1000";
    if(s=="-0")s="-1000";
    cp[i] = stoi(s);
  }
  //Search Photo
  double love[1010] = {0};
  for(int c = 1; c <= 2; c++){
    for(int i = 0; i < m; i++){
      //Find CP
      int ok = 0;
      for(int j = 0; j < photo[i].size(); j++){
        if(photo[i][j]==cp[c]){
          ok = 1;
          break;
        }
      }
      //Add Love
      if(ok){
        for(int j = 0; j < photo[i].size(); j++){
          if(cp[c]*photo[i][j]<0){
            love[abs(photo[i][j])] += 1.0/photo[i].size();
          }
        }
      }
    }
  }
  //Count maxlove
  double maxx[3] = {0};
  vector<vector<int> >ans(3);
  for(int c = 1; c <= 2; c++){
    for(int i = 1; i <= 1000; i++){
      if(cp[c]*sex[i]<0){
        if(love[i]>maxx[c]){
          maxx[c] = love[i];
          ans[c].clear();
          ans[c].push_back(sex[i]);
        }else if(love[i]==maxx[c]){
          ans[c].push_back(sex[i]);
        }
      }
    }
  }
  //cout<<ans[1].size()<<" "<<ans[2].size()<<endl;
  //output
  if(maxx[1]==love[abs(cp[2])] && maxx[2]==love[abs(cp[1])]){
    string s1 = to_string(cp[1]), s2 = to_string(cp[2]);
    if(cp[1]==1000)s1="0";
    if(cp[1]==-1000)s1="-0";
    if(cp[2]==1000)s2="0";
    if(cp[2]==-1000)s2="-0";
    cout<<s1<<" "<<s2<<endl;
    return 0;
  }
  for(int c = 1; c <= 2; c++){
    sort(ans[c].begin(), ans[c].end(),cmp);
    for(int i = 0; i < ans[c].size(); i++){
      string s1 = to_string(cp[c]), s2 = to_string(ans[c][i]);
      if(cp[c]==1000)s1 = "0";
      if(cp[c]==-1000)s1 = "-0";
      if(ans[c][i]==1000)s2 = "0";
      if(ans[c][i]==-1000)s2 = "-0";
      cout<<s1<<" "<<s2<<endl;
    }
  }
  return 0;
}

//WA
#include<bits/stdc++.h>
using namespace std;
bool cmp(pair<int,double>a , pair<int,double> b){
  if(a.second!=b.second)return a.second>b.second;
  return a.first<b.first;
}
int main(){
  //input
  int n, m;
  cin>>n>>m;
  vector<vector<int> >photo(m+1);
  for(int i = 1; i <= m; i++){
    int k;  cin>>k;
    for(int j = 1; j <= k; j++){
      string x;  cin>>x;
      if(x=="0")x = "1000";
      if(x=="-0")x = "-1000";
      photo[i].push_back(stoi(x));
    }
  }
  int cp[3];
  for(int i = 1; i <= 2; i++){
    string x;   cin>>x;
    if(x=="0")x = "1000";
    if(x=="-0")x = "-1000";
    cp[i] = stoi(x);
  }
  //solve
  double love[3][1050];
  memset(love,0,sizeof(love));
  for(int i = 1; i <= m; i++){
    for(int c = 1; c <= 2; c++){
      //Find CP
      int ok = 0;
      for(int j = 0; j < photo[i].size(); j++){
        if(photo[i][j]==cp[c]){
          ok = 1; break;
        }
      }
      //Add love
      if(ok){
        //cout<<i<<"\n";
        for(int j = 0; j < photo[i].size(); j++){
          if(cp[c]*photo[i][j]<0){
            love[c][abs(photo[i][j])] += 1.0/photo[i].size();
          }
        }
      }
    }
  }
  vector<pair<int,double> >ans[3];
  for(int i = 1; i <= 1000; i++){
    for(int c = 1; c <= 2; c++){
      if(love[c][i]>0){
        ans[c].push_back(make_pair(i,love[c][i]));
      }
    }
  }
  sort(ans[1].begin(),ans[1].end(),cmp);
  sort(ans[2].begin(),ans[2].end(),cmp);
  //output
  //for(int i = 0; i < ans[2].size(); i++)
  //  cout<<ans[2][i].first<<" "<<ans[2][i].second<<"\n";
  if(abs(ans[1][0].second-love[1][abs(cp[2])])<0.02 && abs(ans[2][0].second-love[2][abs(cp[1])])<0.02){
    string s1 = to_string(cp[1]), s2 = to_string(cp[2]);
    if(cp[1]==1000)s1="0";
    if(cp[1]==-1000)s1="-0";
    if(cp[2]==1000)s2="0";
    if(cp[2]==-1000)s2="-0";
    cout<<s1<<" "<<s2<<endl;
    return 0;
  }
  for(int c = 1; c <= 2; c++){
    for(int i = 0; i < ans[c].size(); i++){
      if(ans[c][i].second==ans[c][0].second){
        int t = cp[c], tt = -abs(cp[c]*ans[c][i].first)/cp[c];
        string ts = to_string(t), tts = to_string(tt);
        if(t==1000)ts="0";
        if(t==-1000)ts="-0";
        if(tt==1000)tts="0";
        if(tt==-1000)tts="-0";
        cout<<ts<<" "<<tts<<endl;
      }
    }
  }
  return 0;
}