题解
L2-016 愿天下有情人都是失散多年的兄妹
呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？
输入格式：
输入第一行给出一个正整数N（2 ≤ N ≤10
4
），随后N行，每行按以下格式给出一个人的信息：
本人ID 性别 父亲ID 母亲ID
其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。
接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。
注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。
输出格式：
对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出Never Mind；如果是异性并且关系出了五服，输出Yes；如果异性关系未出五服，输出No。
输入样例：
24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011
输出样例：
Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No
#include<bits/stdc++.h>
using namespace std;
const int inf=1e5+5;
vector<int>vec[inf];
bool vis[inf];
char sex[inf];
bool flag;
void Dfs(int x,int num)
{
if(num>=5)
return;
for(int i=0;i<vec[x].size();i++)
{
if(!vis[vec[x][i]])
{
vis[vec[x][i]]=1;
Dfs(vec[x][i],num+1);
}
else
flag=1;
}
}
int main()
{
int T;
cin>>T;
while(T--)
{
int t,fa,ma;
char ch;
scanf("%d ",&t);
sex[t]=getchar();
scanf(" %d %d",&fa,&ma);
if(fa!=-1)
{
vec[t].push_back(fa);
sex[fa]='M';
}
if(ma!=-1)
{
vec[t].push_back(ma);
sex[ma]='F';
}
}
cin>>T;
while(T--)
{
int x,y;
scanf("%d %d",&x,&y);
if(sex[x]==sex[y])
cout<<"Never Mind"<<endl;
else
{
memset(vis,0,sizeof(vis));
vis[x]=1;
vis[y]=1;
flag=0;
Dfs(x,1);
Dfs(y,1);
if(flag)
cout<<"No"<<endl;
else
cout<<"Yes"<<endl;
}
}
}
L2-017 人以群分
社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。
输入格式：
输入第一行给出一个正整数N（2≤N≤10
5
）。随后一行给出N个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过2
31
。
输出格式：
按下列格式输出：
Outgoing #: N1
Introverted #: N2
Diff = N3
其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。
输入样例1：
10
23 8 10 99 46 2333 46 1 666 555
输出样例1：
Outgoing #: 5
Introverted #: 5
Diff = 3611
输入样例2：
13
110 79 218 69 3721 100 29 135 2 6 13 5188 85
输出样例2：
Outgoing #: 7
Introverted #: 6
Diff = 9359
#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
int sum1=0,cnt1=0;
int sum2=0,cnt2=0;
for(int i=0;i<n/2;i++)
{
sum1+=a[i];
cnt1++;
}
for(int i=n/2;i<n;i++)
{
sum2+=a[i];
cnt2++;
}
printf("Outgoing #: %d\n",cnt2);
printf("Introverted #: %d\n",cnt1);
printf("Diff = %d",sum2-sum1);
}
L2-018 多项式A除以B
这仍然是一道关于A/B的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R，其中R的阶数必须小于B的阶数。
输入格式：
输入分两行，每行给出一个非零多项式，先给出A，再给出B。每行的格式如下：
N e[1] c[1] … e[N] c[N]
其中N是该多项式非零项的个数，e[i]是第i个非零项的指数，c[i]是第i个非零项的系数。各项按照指数递减的顺序给出，保证所有指数是各不相同的非负整数，所有系数是非零整数，所有整数在整型范围内。
输出格式：
分两行先后输出商和余，输出格式与输入格式相同，输出的系数保留小数点后1位。同行数字间以1个空格分隔，行首尾不得有多余空格。注意：零多项式是一个特殊多项式，对应输出为0 0 0.0。但非零多项式不能输出零系数（包括舍入后为0.0）的项。在样例中，余多项式其实有常数项-1/27，但因其舍入后为0.0，故不输出。
输入样例：
4 4 1 2 -3 1 -1 0 -1
3 2 3 1 -2 0 1
输出样例：
3 2 0.3 1 0.2 0 -1.0
1 1 -3.1
#include<bits/stdc++.h>
using namespace std;
double c1[100005],c2[100005],c3[100005];
int f(double a[],int e)
{
int ret=0;
for(int i=e;i>=0;i--)
{
if(fabs(a[i])>=0.05)
ret++;
}
return ret;
}
void solve(double a[],int e)
{
cout<<f(a,e);
if(f(a,e)==0)
cout<<" 0 0.0";
else
{
for(int i=e;i>=0;i--)
{
if(fabs(a[i])>=0.05)
printf(" %d %.1lf",i,a[i]);
}
}
cout<<endl;
}
int main()
{
int n;
while(cin>>n)
{
int maxe1,maxe2;
for(int i=0;i<n;i++)
{
int e;
double c;
cin>>e>>c;
if(i==0)
{
maxe1=e;
}
c1[e]=c;
}
int m;
cin>>m;
for(int i=0;i<m;i++)
{
int e;
double c;
cin>>e>>c;
if(i==0)
{
maxe2=e;
}
c2[e]=c;
}
int d=maxe1-maxe2;
while(maxe2<=maxe1)
{
double v=c1[maxe1]/c2[maxe2];
c3[maxe1-maxe2]=v;
for(int i=maxe1,j=maxe2;i>=0&&j>=0;j--,i--)
{
c1[i]-=c2[j]*v;
}
while(fabs(c1[maxe1])<0.05)
maxe1--;
}
solve(c3,d);
solve(c1,maxe1);
}
system("pause");
return 0;
}
L2-019 悄悄关注
新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。
输入格式：
输入首先在第一行给出某用户的关注列表，格式如下：
人数N 用户1 用户2 …… 用户N
其中N是不超过5000的正整数，每个用户i（i=1, …, N）是被其关注的用户的ID，是长度为4位的由数字和英文字母组成的字符串，各项间以空格分隔。
之后给出该用户点赞的信息：首先给出一个不超过10000的正整数M，随后M行，每行给出一个被其点赞的用户ID和对该用户的点赞次数（不超过1000），以空格分隔。注意：用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户，在点赞信息中也没有重复用户。
输出格式：
我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人，很可能是其悄悄关注的人。根据这个假设，请你按用户ID字母序的升序输出可能是其悄悄关注的人，每行1个ID。如果其实并没有这样的人，则输出“Bing Mei You”。
输入样例1：
10 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao
8
Magi 50
Pota 30
LLao 3
Ammy 48
Dave 15
GAO3 31
Zoro 1
Cath 60
输出样例1：
Ammy
Cath
Pota
输入样例2：
11 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao Pota
7
Magi 50
Pota 30
LLao 48
Ammy 3
Dave 15
GAO3 31
Zoro 29
输出样例2：
Bing Mei You
#include<bits/stdc++.h>
using namespace std;
struct node
{
string name;
int cnt;
}stu[10001];
bool cmp(node a,node b)
{
return a.name<b.name;
}
int main()
{
string s;
map<string,bool>mp;
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s;
mp[s]=1;
}
int m;
cin>>m;
double sum=0;
for(int i=1;i<=m;i++)
{
cin>>stu[i].name>>stu[i].cnt;
sum+=stu[i].cnt;
}
sum/=m*1.0;
int count=0;
sort(stu,stu+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(stu[i].cnt>sum&&mp[stu[i].name]!=1)
{
cout<<stu[i].name<<endl;
count++;
}
}
if(count==0)
cout<<"Bing Mei You";
}
写在最后
🍁🍁🍁好啦，本文的内容就到此结束啦，我们下期再见哦！另外在祝各位小伙伴们要天天开心哦！
🍂🍂🍂如果你觉得本文对你有帮助的话，还请不要吝惜您的三连哦！您的支持就是我创作的最大动力！！爱你们💕💕💕