7-1 电话聊天狂人 (25 分)
给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。
输入格式:
输入首先给出正整数N（≤10
5
），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。
输出格式:
在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。
输入样例:
4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832
结尾无空行
输出样例:
13588625832 3
结尾无空行
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int cmp(const void *a,const void *b)
{
return *(long long *)a-*(long long *)b;
}
int main()
{
int n;
scanf("%d",&n);
n*=2;
long long *number=(long long*)malloc(sizeof(long long)*n);
for(int i=0;i<n;i++)
{
scanf("%lld",&number[i]);
}
qsort(number,n,sizeof(long long),cmp);
long long cmp1,cord=0;
int maxSum=0,times=0;
for(int j=0;j<n;j++)
{
int sum=0;
cmp1=number[j];
for(int i=j;i<n;i++)
{
if(number[i]!=cmp1)
{
break;
}
sum++;
}
if(sum>maxSum){
times=0;
maxSum=sum;
cord=number[j];
}
else if(sum==maxSum&&number[j]!=cord)
{
times++;
}
}
if(times)
printf("%lld %d %d",cord,maxSum,times+1);
else
printf("%lld %d",cord,maxSum);
return 0;
}
7-2 两个有序序列的中位数 (25 分)
已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A
0
,A
1
,⋯,A
N−1
的中位数指A
(N−1)/2
的值,即第⌊(N+1)/2⌋个数（A
0
为第1个数）。
输入格式:
输入分三行。第一行给出序列的公共长度N（0<N≤100000），随后每行输入一个序列的信息，即N个非降序排列的整数。数字用空格间隔。
输出格式:
在一行中输出两个输入序列的并集序列的中位数。
输入样例1:
5
1 3 5 7 9
2 3 4 5 6
结尾无空行
输出样例1:
4
结尾无空行
输入样例2:
6
-100 -10 1 1 1 1
-50 0 2 3 4 5
输出样例2:
1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int comp(const void *a,const void *b)
{
return *(int*)b-*(int*)a;
}
int main()
{
int i;
int n;
int a[1000001];
scanf("%d",&n);
for(i=0;i<n*2;i++)
{
scanf("%d",&a[i]);
}
qsort(a,n*2,sizeof(a[0]),comp);
printf("%d\n",a[n]);
return 0;
}
7-3 词频统计 (30 分)
请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频最大的前10%的单词。
所谓“单词”，是指由不超过80个单词字符组成的连续字符串，但长度超过15的单词将只截取保留前15个单词字符。而合法的“单词字符”为大小写字母、数字和下划线，其它字符均认为是单词分隔符。
输入格式:
输入给出一段非空文本，最后以符号#结尾。输入保证存在至少10个不同的单词。
输出格式:
在第一行中输出文本中所有不同单词的个数。注意“单词”不区分英文大小写，例如“PAT”和“pat”被认为是同一个单词。
随后按照词频递减的顺序，按照词频:单词的格式输出词频最大的前10%的单词。若有并列，则按递增字典序输出。
输入样例：
This is a test.
The word “this” is the word with the highest frequency.
Longlonglonglongword should be cut off, so is considered as the same as longlonglonglonee. But this_8 is different than this, and this, and this…#
this line should be ignored.
结尾无空行
输出样例：（注意：虽然单词the也出现了4次，但因为我们只要输出前10%（即23个单词中的前2个）单词，而按照字母序，the排第3位，所以不输出。）
23
5:this
4:is
结尾无空行
感谢武汉理工大学的郭小兵老师修正测试数据！
#include <bits/stdc++.h>
using namespace std;
using psi = pair<string, int>;
map<string, int> mp;
vector<psi> a;
bool cmp(psi x, psi y)
{
if (x.second == y.second)
return x.first < y.first;
return x.second > y.second;
}
int main()
{
char c;
string s;
while (~scanf("%c", &c))
{
if ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') || (c >= 'A' && c <= 'Z') || (c == '_'))
{
if (c >= 'A' && c <= 'Z')
c += 32;
if (s.length() < 15)
s += c;
}
else if (c == '#' || s.length() > 0)
{
mp[s]++;
s.clear();
if (c == '#')
break;
}
}
for (auto i : mp)
{
if (i.first.length() > 0)
a.push_back(i);
}
sort(a.begin(), a.end(), cmp);
int cnt = a.size() * 0.1;
cout << a.size() << endl;
for (int i = 0; i < cnt; i++)
cout << a[i].second << ":" << a[i].first << "\n";
return 0;
}
7-4 集合相似度 (25 分)
给定两个整数集合，它们的相似度定义为：N
c
/N
t
×100%。其中N
c
是两个集合都有的不相等整数的个数，N
t
是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。
输入格式：
输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤10
4
），是集合中元素的个数；然后跟M个[0,10
9
]区间内的整数。
之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。
输出格式：
对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。
输入样例：
3
3 99 87 101
4 87 101 5 87
7 99 101 18 5 135 18 99
2
1 2
1 3
结尾无空行
输出样例：
50.00%
33.33%
结尾无空行
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
long long a[55][10005];
int cnt,sum;
void slove(long long a[],long long n,long long b[],long long m)
{
int i=1,j=1;
while(i<=n&&j<=m)
{
if(b[j]<a[i])
{
sum++;
j++;
}
else if(a[i]<b[j])
{
sum++;
i++;
}
else if(a[i]==b[j])
{
sum++;
cnt++;
i++;
j++;
}
}
if(i<=n) sum+=n-i+1;
if(j<=m) sum+=m-j+1;
}
int main()
{
int n,k,x,y;
long long i,j;
scanf("%d",&n);
int sum1;
for(i=1;i<=n;i++)
{
sum1=0;
scanf("%lld",&a[i][0]);
for(j=1;j<=a[i][0];j++)
{
scanf("%lld",&a[i][j]);
}
sort(a[i]+1,a[i]+1+a[i][0]);
for(j=1;j<a[i][0];j++)
{
if(a[i][j]==a[i][j+1])
{
a[i][j]=1e10;
sum1++;
}
}
sort(a[i]+1,a[i]+1+a[i][0]);
a[i][0]-=sum1;
}
scanf("%d",&k);
while(k--)
{
scanf("%d %d",&x,&y);
cnt=sum=0;
slove(a[x],a[x][0],a[y],a[y][0]);
double ans=cnt*1.0/sum;
printf("%.2lf%c\n",ans*100,'%');
}
return 0;
}
7-5 悄悄关注 (25 分)
新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。
输入格式：
输入首先在第一行给出某用户的关注列表，格式如下：
人数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;
string s;
set<string> st;
map<string, int> mp;
vector<string> a;
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> s;
st.insert(s);
}
int m;
cin >> m;
int sum = 0; //点赞总次数
for (int i = 0; i < m; i++)
{
int x;
cin >> s;
scanf("%d", &x);
sum += x;
mp[s] = x;
}
double ave = 1.0 * sum / m; //平均点赞次数
for (auto i : mp)
{
string name = i.first;
int cnt = i.second;
if (i.second > ave && st.find(name) == st.end())
a.push_back(name);
}
if (a.empty())
printf("Bing Mei You");
else
{
sort(a.begin(), a.end());
for (auto i : a)
cout << i << endl;
}
return 0;
}
7-6 单身狗 (25 分)
“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。
输入格式：
输入第一行给出一个正整数 N（≤50000），是已知夫妻/伴侣的对数；随后 N 行，每行给出一对夫妻/伴侣——为方便起见，每人对应一个 ID 号，为 5 位数字（从 00000 到 99999），ID 间以空格分隔；之后给出一个正整数 M（≤10000），为参加派对的总人数；随后一行给出这 M 位客人的 ID，以空格分隔。题目保证无人重婚或脚踩两条船。
输出格式：
首先第一行输出落单客人的总人数；随后第二行按 ID 递增顺序列出落单的客人。ID 间用 1 个空格分隔，行的首尾不得有多余空格。
输入样例：
3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333
结尾无空行
输出样例：
5
10000 23333 44444 55555 88888
结尾无空行
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 100000
int main()
{
int arr[100000]={0};
int n,x,y;
scanf("%d",&n);
while(n--)
{
scanf("%d%d",&x,&y);
arr[x]=y+1;
arr[y]=x+1;
}
scanf("%d",&n);
int res=0;
while(n--)
{
scanf("%d",&x);
if(arr[x]==0)
{
arr[x]=-1;
res++;
}
else
{
if(arr[arr[x]-1]==(x+1))
{
arr[x]=-1;
res++;
}
else{
arr[arr[x]-1]=-2;
arr[x]=-2;
res--;
}
}
}
int f=0;
printf("%d\n",res);
for(int i=0;i<MAX;i++)
{
if(arr[i]==-1)
{
if(f)
printf(" ");
printf("%05d",i);
f=1;
}
}
return 0;
}
7-7 词典 (15 分)
你刚从滑铁卢搬到了一个大城市，这里的人们讲一种难以理解的外语方言。幸运的是，你有一本字典来帮助你理解它们。
输入格式:
输入第一行是正整数N和M,后面是N行字典条目（最多10000条），然后是M行要翻译的外语单词（最多10000个）。每一个字典条目都包含一个英语单词，后面跟着一个空格和一个外语单词。 输入中的每个单词都由最多10个小写字母组成。
输出格式:
输出翻译后的英文单词，每行一个单词。非词典中的外来词汇输出“eh”。
输入样例:
5 3
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay
atcay
ittenkay
oopslay
输出样例:
cat
eh
loops
#include <bits/stdc++.h>
using namespace std;
int main()
{
map<string, string> mp;
int n, m;
scanf("%d %d", &n, &m);
while (n--)
{
string a, b;
cin >> a >> b;
mp[b] = a;
}
while (m--)
{
string s;
cin >> s;
if (!mp.count(s))
printf("eh\n");
else
cout << mp[s] << endl;
}
return 0;
}
7-8 中序遍历树并判断是否为二叉搜索树 (20 分)
对给定的有N个节点（N>=0）的二叉树，给出中序遍历序列，并判断是否为二叉搜索树。
题目保证二叉树不超过200个节点，节点数值在整型int范围内且各不相同。
输入格式:
第一行是一个非负整数N，表示有N个节点
第二行是一个整数k，是树根的元素值
接下来有N-1行，每行是一个新节点，格式为 r d e 三个整数，
r表示该节点的父节点元素值（保证父节点存在）；d是方向，0表示该节点为父节点的左儿子，1表示右儿子；e是该节点的元素值
输出格式:
首先输出二叉树的中序遍历序列，每个元素占一行。对于空树，不输出任何内容。
然后如果给定的树是二叉搜索树，输出Yes 否则输出No
对于图片中的二叉树：
3
20
20 0 10
20 1 25
结尾无空行
输出样例:
10
20
25
Yes
结尾无空行
#include<stdio.h>
#include<stdlib.h>
typedef struct node* BinTree;
struct node{
int Data;
BinTree lchild,rchild;
};
int a[400];
int m=0;
//初始化
BinTree CreatTree(){
BinTree T=(BinTree)malloc(sizeof(struct node));
T->Data=NULL;
T->lchild=NULL;
T->rchild=NULL;
return T;
}
//查找
BinTree Find(BinTree T,int r){
if(!T){
return NULL;
}
if(T->Data==r){
return T;
}else{
BinTree temp;
temp=Find(T->lchild,r);
if(!temp){
return Find(T->rchild,r);
}
return temp;
}
}
//插入
void Insert(BinTree father,int d,int e){
BinTree tree=CreatTree();
tree->Data=e;
if(d==0){
father->lchild=tree;
}else{
father->rchild=tree;
}
}
//中序输出
void InOrderTraverse(BinTree T){
if(T==NULL){
return ;
}else{
InOrderTraverse(T->lchild);
printf("%d\n",T->Data);
a[m]=T->Data;
m=m+1;
InOrderTraverse(T->rchild);
}
}
int main(){
int n,i;
scanf("%d",&n);
if(n==0){
printf("Yes");
return 0;
}
BinTree T=CreatTree();
for(i=0;i<n;i++){
int r,d,e,k;
if(i==0){
scanf("%d",&k);
T->Data=k;
}else{
scanf("%d %d %d",&r,&d,&e);
BinTree father=Find(T,r);
Insert(father,d,e);
}
}
InOrderTraverse( T) ;
int flag=1;
int min=a[0];
for(i=1;i<m;i++){
if(min<a[i]){
flag=1;
min=a[i];
}else{
flag=0;
break;
}
}
if(flag==1){
printf("Yes");
}else{
printf("No");
}
return 0;
}