SDUT PTA 查找表

7-1 电话聊天狂人

给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。

输入格式:

输入首先给出正整数N（≤105），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。

输出格式:

在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。

输入样例:

4
13005711862 13588625832
13505711862 13088625832
13588625832 18087925832
15005713862 13588625832

输出样例:

13588625832 3

#include
using namespace std;
typedef map msi;
int main()
{msi mp;msi::iterator it;int n, maxn = -1;string maxnn;cin >> n;while(n--){string a, b;cin >> a >> b;mp[a]++;mp[b]++;if(mp[a] > maxn){maxn = mp[a];maxnn = a;}if(mp[b] > maxn){maxn = mp[b];maxnn = b;}}int cnt = 0;for(it = mp.begin(); it!= mp.end(); it++){if(it->second == maxn){cnt++;}}if(cnt == 1) cout << maxnn << " " << maxn << endl;else{for(it = mp.begin(); it != mp.end(); it++){if(it->second == maxn){cout << it->first << " " << maxn << " " << cnt;break;}}}return 0;
}

7-2 两个有序序列的中位数

已知有两个等长的非降序序列S1, S2, 设计函数求S1与S2并集的中位数。有序序列A0​,A1​,⋯,AN−1​的中位数指A(N−1)/2​的值,即第⌊(N+1)/2⌋个数（A0​为第1个数）。

输入格式:

输入分三行。第一行给出序列的公共长度N（0

输出格式:

在一行中输出两个输入序列的并集序列的中位数。

输入样例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
using namespace std;const int N = 1e5 + 10;
int a[N * 2];
int main()
{int n;cin >> n;for(int i = 0; i < n * 2; i++){cin >> a[i];}sort(a, a + 2 * n);cout << a[n-1];return 0;
}

7-3 词频统计

请编写程序，对一段英文文本，统计其中所有不同单词的个数，以及词频最大的前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
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
typedef pairpls;
vectorvec;
mapmp;
bool cmp(pls a, pls b){if(a.first == b.first){return a.second < b.second;}else return a.first > b.first;
}
int main()
{char s;string str = "";while(~scanf("%c", &s) && s != '#'){// 必须这样输入呢if(s >= 'A' && s <= 'Z'){s += 32;}if(s >= 'a' && s <= 'z' || s >= '0' && s <= '9' || s == '_'){if(str.size() < 15) str += s;}else {if(str.size() > 0){mp[str]++, str.clear();}}}for(auto it : mp){vec.push_back({it.second, it.first});// vector和pls必须对应起来}sort(vec.begin(), vec.end(), cmp);cout << mp.size() << endl;for(int i = 0; i < mp.size() / 10; i++){cout << vec[i].first << ":" << vec[i].second << endl;}return 0;
}

7-4 集合相似度

给定两个整数集合，它们的相似度定义为：Nc​/Nt​×100%。其中Nc​是两个集合都有的不相等整数的个数，Nt​是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式：

输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤104），是集合中元素的个数；然后跟M个[0,109]区间内的整数。

之后一行给出一个正整数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
using namespace std;
const int N = 55;
const int INF = 0x3f3f3f3f;
sets[N];
int main()
{int n;cin >> n;for(int i = 1; i <= n; i++){int m;cin >> m;while(m--){int x;cin >> x;s[i].insert(x);}}int k;cin >> k;while(k--){int num = 0;int a, b;cin >> a >> b;for(auto it : s[a]){if(s[b].find(it) != s[b].end()){num++;// 重复的}}int tot = s[a].size() + s[b].size() - num;double ans = 1.0 * num / tot;printf("%.2lf%%\n", ans * 100);}return 0;
}

7-5 悄悄关注

新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。

输入格式：

输入首先在第一行给出某用户的关注列表，格式如下：

人数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
using namespace std;
const int N = 5e3 + 10;
const int INF = 0x3f3f3f3f;
typedef pairpsi;
vectorvec;
vectorans;
int cnt;
mapmp;int main()
{int n;cin >> n;for(int i = 0; i < n; i++){string str;cin >> str;mp[str] = 1;}int m;cin >> m;int sum = 0;for(int i = 0; i < m; i++){string name;int like;cin >> name >> like;vec.push_back({name, like});sum += like;}int ave = sum / m;for(auto it : vec){if(it.second > ave && mp[it.first] == 0){ans.push_back(it.first);cnt++;}}if(cnt == 0) cout << "Bing Mei You" << endl;else{sort(ans.begin(), ans.end());for(auto it : ans){cout << it << endl;}}return 0;
}

7-6 单身狗

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。

输入格式：

输入第一行给出一个正整数 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
using namespace std;
const int N = 5e3 + 10;
const int INF = 0x3f3f3f3f;
vectorvec;
vectorans;
mapmpi;
mapmps;
// 少两分T_T
int main()
{int n;cin >> n;while(n--){string hus, wife;cin >> hus >> wife;mps[hus] = wife;mps[wife] = hus;mpi[hus] = 1;mpi[wife] = 1;}int m;cin >> m;while(m--){string id;cin >> id;vec.push_back(id);mpi[id]++;}for(auto it : vec){if(mpi[it] == 2 && mpi[mps[it]] == 2){continue;}ans.push_back(it);}sort(ans.begin(), ans.end());cout << ans.size() << endl;int num = ans.size();for(int i = 0; i < num; i++){if(i == num - 1) cout << ans[i] << endl;else cout << ans[i] << " ";}return 0;
}

7-7 词典

你刚从滑铁卢搬到了一个大城市，这里的人们讲一种难以理解的外语方言。幸运的是，你有一本字典来帮助你理解它们。

输入格式:

输入第一行是正整数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
using namespace std;
const int N = 5e3 + 10;
const int INF = 0x3f3f3f3f;
mapmps;
mapmpi;
int main()
{int n, m;cin >> n>> m;while(n--){string w1, w2;cin >> w1 >> w2;mps[w2] = w1;mpi[w2] = 1;}while(m--){string word;cin >> word;if(mpi[word] == 0){cout << "eh" << endl;}else{cout << mps[word] << endl;}}return 0;
}

7-8 这是二叉搜索树吗？

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，

• 其左子树中所有结点的键值小于该结点的键值；
• 其右子树中所有结点的键值大于等于该结点的键值；
• 其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N（≤1000）。随后一行给出 N 个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES ，然后在下一行输出该树后序遍历的结果。数字间有 1 个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

输入样例 1：

7
8 6 5 7 10 8 11

输出样例 1：

YES
5 7 6 8 11 10 8

输入样例 2：

7
8 10 11 8 6 7 5

输出样例 2：

YES
11 8 10 7 5 6 8

输入样例 3：

7
8 6 8 5 10 9 11

输出样例 3：

NO

#include
using namespace std;
const int N = 1e3 + 10;
int pre[N];
int f = 1;
vector post;
void dfs(int l, int r){if(l > r) return ;int ll = l + 1, rr = r;if(f){// 正常二叉排序树while(ll <= r && pre[ll] < pre[l]){ll++;}while(rr > l && pre[rr] >= pre[l]){rr--;}}else{// 镜像二叉排序树while(ll <= r && pre[ll] >= pre[l]){ll++;}while(rr > l && pre[rr] < pre[l]){rr--;}}// 最终ll和rr挨着，并且ll在rr右边if(ll - rr != 1){// 若不是上述关系,就不是一棵二叉排序树return ;}dfs(l + 1, rr);// 左子树  此时的ll和rr已经不是原来的数值了dfs(ll, r);// 右子树post.push_back(pre[l]);
}
int main()
{int n;cin >> n;for(int i = 0; i < n; i++){cin >> pre[i];}dfs(0, n - 1);if(post.size() != n){f = 0;post.clear();dfs(0, n - 1);}if(post.size() != n){cout << "NO" << endl;}else{cout << "YES" << endl;cout << post[0];for(int i = 1; i < post.size(); i++){cout << " " << post[i];}cout << endl;}return 0;
}

7-9 二叉搜索树

对于一个无穷的满二叉排序树（如图），节点的编号是1,2,3，…。对于一棵树根为X的子树，沿着左节点一直往下到最后一层，可以获得该子树编号最小的节点；沿着右节点一直往下到最后一层，可以获得该子树编号最大的节点。现在给出的问题是“在一棵树根为X的子树中，节点的最小编号和最大编号是什么？”。请你给出答案。

输入格式:

输入的第一行给出测试用例的数目，一个整数N。在后面的N行中，每行给出一个整数X（1<=X<=231-1），表示子树树根的编号。

输出格式:

输出N行，第i行给出第i个问题的答案。

输入样例:

2
8
10

输出样例:

1 15
9 11

#include
using namespace std;int main()
{int n;cin >> n;while(n--){int x;cin >> x;int t = x;int b = 1;while(x % 2 == 0){x /= 2;b *= 2;}b--;cout << t - b << " " << t + b << endl;}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！