题目
这个l2-4题也太离谱了，感觉太恶心人了。也可能是我学艺不精。
l1-7 谷歌的招聘。
坑点: 要用n-k而不是s.size()-k，我感觉很不能理解，n是给定的字符串长度，但是题干说的就是给定长度为n的字符串啊，这怎么能wa，我理解不了。
l2-4秀恩爱，分得快
题意: 给定n个人，编号0-n-1，如果一个数是负数代表是女，否则代表男。有m个照片，在照片中任意两个异性之间的亲密度会+1/k，k为照片中有几个人。给定st和ed，如果他俩是彼此亲密度最高的异性(或之一)，输出他俩，否则依次输出二者所有亲密度最高的异性(按编号绝对值大小升序排列)。
思路: 看着其实不复杂，n才1000，拿数组维护一下或者用map都可。
但是这个题我感觉很恶心人。
- 有-0和0，要用字符串输入。这一点我着实没想到
- 有可能st和ed在照片中根本不出现
- 但是最后还是wa，一直wa，不知道为啥。敲了三遍，浪费了一晚上时间。后来看到题解的数据，-0我按0输出了，那个也要特判。和-0输入要特判一样，很烦。什么鬼题。
时间复杂度: O(能过)
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10;
int n,m,k,T;
int st,ed;
vector<int> va[N];
int to[N];
double a[N][N];
void print(int x)
{
if(x==0&&!to[x]) {printf("-0");return;}
if(!to[x]) x *= -1;
printf("%d",x);
}
int input()
{
string s; cin>>s;
int x = stoi(s);
if(s[0] == '-') x *= -1;
else to[x] = 1;
return x;
}
void solve()
{
cin>>n>>m;
for(int i=0;i<m;++i)
{
int num; cin>>num;
while(num--)
{
va[i].push_back(input());
}
}
st = input(); ed = input();
// cout<<st<<" "<<ed<<endl;
for(int i=0;i<m;++i)
{
auto iter1 = find(va[i].begin(),va[i].end(),st);
auto iter2 = find(va[i].begin(),va[i].end(),ed);
for(int j=0;j<va[i].size();++j)
{
int t = va[i][j];
if(iter1 != va[i].end() && t != st)
{
a[st][t] += (1.0/va[i].size());
}
if(iter2 != va[i].end() && t != ed)
{
a[ed][t] += (1.0/va[i].size());
}
}
}
double mx1 = 0,mx2 = 0;
for(int i=0;i<n;++i)
{
if(to[i]+to[st]==1) mx1 = max(mx1,a[st][i]);
if(to[i]+to[ed]==1) mx2 = max(mx2,a[ed][i]);
}
if(a[st][ed] == mx1 && a[ed][st] == mx2)
{
print(st),printf(" "),print(ed);
}
else
{
for(int i=0;i<n;++i)
if(to[i]+to[st] ==1 && a[st][i] == mx1)
print(st),printf(" "),print(i),printf("\n");
for(int i=0;i<n;++i)
if(to[i]+to[ed] ==1 && a[ed][i] == mx2)
print(ed),printf(" "),print(i),printf("\n");
}
}
signed main(void)
{
// ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
solve();
return 0;
}
