7-1 Sexy primes(20分)
Sexy primes are pairs of primes of the form (p, p+6), so-named since “sex” is the Latin word for “six”. (Quoted from http://mathworld.wolfram.com/SexyPrimes.html)
Now given an integer, you are supposed to tell if it is a sexy prime.
Input Specification:
Each input file contains one test case. Each case gives a positive integer N (≤10$^8$).
Output Specification:
For each case, print in a line Yes if N is a sexy prime, then print in the next line the other sexy prime paired with N (if the answer is not unique, output the smaller number). Or if N is not a sexy prime, print No instead, then print in the next line the smallest sexy prime which is larger than N.
Sample Input 1:
47
Sample Output 1:
Yes
41
Sample Input 2:
21
Sample Output 2:
No
23
题意:如果p是质数,p + 6也是质数的话,那么就称这两个数是Sexy primes,现在给出一个数,判断是否是Sexy primes,如果是,则输出Yes
,并输出与其配对的另一个数,如果有多个配对,则输出最小的那个。如果不是的话,输出No,再输出大于这个数的最小Sexy primes
思路:质数,枚举
看不懂题目是硬伤,一开始我还以为两个数需要满足在(p, p + 6)
内是两个仅有的素数,吓得我素数筛都差点掏出来了,一看范围10e8
算了
pair 成对的
要特别注意,对于数p,不仅要和p + 6比较,还要和p - 6比较,因为是成对关系
这样就能很好得解释为什么会有多个配对关系,就是往前配对和往后配对
搞清楚了这些,代码直接信手拈来,O(sqrt(n))
判断质数,随便枚举都可
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
bool is_prime(int x)
{
if(x < 2)
return false;
for (int i = 2; i <= x / i; i ++ )
if(x % i == 0)
return false;
return true;
}
int main()
{
int x;
cin >> x;
if(is_prime(x) && is_prime(x - 6))
{
cout << "Yes" << endl << x - 6 << endl;
}
else if(is_prime(x) && is_prime(x + 6))
{
cout << "Yes" << endl << x + 6 << endl;
}
else
{
cout << "No" << endl;
for (int i = x; ; i ++ )
{
if(is_prime(i) && (is_prime(i - 6) || is_prime(i + 6)))
{
cout << i << endl;
break;
}
}
}
return 0;
}
7-2 Anniversary(25分)
Zhejiang University is about to celebrate her 122th anniversary in 2019. To prepare for the celebration, the alumni association (校友会) has gathered the ID’s of all her alumni. Now your job is to write a program to count the number of alumni among all the people who come to the celebration.
Input Specification:
Each input file contains one test case. For each case, the first part is about the information of all the alumni. Given in the first line is a positive integer N (≤10$^5$). Then N lines follow, each contains an ID number of an alumnus. An ID number is a string of 18 digits or the letter X. It is guaranteed that all the ID’s are distinct.
The next part gives the information of all the people who come to the celebration. Again given in the first line is a positive integer M (≤10$^5$). Then M lines follow, each contains an ID number of a guest. It is guaranteed that all the ID’s are distinct.
Output Specification:
First print in a line the number of alumni among all the people who come to the celebration. Then in the second line, print the ID of the oldest alumnus – notice that the 7th - 14th digits of the ID gives one’s birth date. If no alumnus comes, output the ID of the oldest guest instead. It is guaranteed that such an alumnus or guest is unique.
Sample Input:
5
372928196906118710
610481197806202213
440684198612150417
13072819571002001X
150702193604190912
6
530125197901260019
150702193604190912
220221196701020034
610481197806202213
440684198612150417
370205198709275042
Sample Output:
3
150702193604190912
题意:给出校友会的人的id,再给出与会者id,问与会者里有多少个校友会成员,如果个数不为零,则输出参加校庆的校友会成员年纪最大的,如果为零,则输出与会者年纪最大的,id就是身份证号码,第7-14位是出生日期
思路:哈希,字符串处理,模拟
这道题倒是一眼就看懂了,做法也比较简单,unordered_set
存下所有校友会成员,然后对于每个与会成员都查询依次,查询的复杂度是O(1)
的,所以不会超时,每次都更新一下年纪最大的id,substr(6,8)
,从第6位开始取8位出来,出生日期直接根据字符串比较即可,不难证明出生日期较前的对应的字符串字典序也较小,前提是都是不足位补好零的
恶心的是我没看到个数为零,也要输出年纪最大的与会者id,还好又看了一边题目
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>
using namespace std;
unordered_set<string> s;
int n, m;
string str;
int main()
{
cin >> n;
while (n -- )
{
cin >> str;
s.insert(str);
}
cin >> m;
int cnt = 0;
string ans = "", ans1 = "";
while (m -- )
{
cin >> str;
if(s.count(str))
{
cnt++;
if(ans == "" || ans.substr(6, 8) > str.substr(6, 8))
ans = str;
}
else
{
if(ans1 == "" || ans1.substr(6, 8) > str.substr(6, 8))
ans1 = str;
}
}
if(cnt)
cout << cnt << endl << ans << endl;
else
cout << 0 << endl << ans1 << endl;
return 0;
}
7-3 Telefraud Detection(25分)
Telefraud(电信诈骗) remains a common and persistent problem in our society. In some cases, unsuspecting victims lose their entire life savings. To stop this crime, you are supposed to write a program to detect those suspects from a huge amount of phone call records.
A person must be detected as a suspect if he/she makes more than K short phone calls to different people everyday, but no more than 20% of these people would call back. And more, if two suspects are calling each other, we say they might belong to the same gang. A makes a short phone call to B means that the total duration of the calls from A to B is no more than 5 minutes.
Input Specification:
Each input file contains one test case. For each case, the first line gives 3 positive integers K (≤500, the threshold(阈值) of the amount of short phone calls), N (≤10&^3&, the number of different phone numbers), and M (≤10$^5$, the number of phone call records). Then M lines of one day’s records are given, each in the format:
caller receiver duration
where caller and receiver are numbered from 1 to N, and duration is no more than 1440 minutes in a day.
Output Specification:
Print in each line all the detected suspects in a gang, in ascending order of their numbers. The gangs are printed in ascending order of their first members. The numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.
If no one is detected, output None instead.
Sample Input 1:
5 15 31
1 4 2
1 5 2
1 5 4
1 7 5
1 8 3
1 9 1
1 6 5
1 15 2
1 15 5
3 2 2
3 5 15
3 13 1
3 12 1
3 14 1
3 10 2
3 11 5
5 2 1
5 3 10
5 1 1
5 7 2
5 6 1
5 13 4
5 15 1
11 10 5
12 14 1
6 1 1
6 9 2
6 10 5
6 11 2
6 12 1
6 13 1
Sample Output 1:
3 5
6
Note: In sample 1, although 1 had 9 records, but there were 7 distinct receivers, among which 5 and 15 both had conversations lasted more than 5 minutes in total. Hence 1 had made 5 short phone calls and didn’t exceed the threshold 5, and therefore is not a suspect.
Sample Input 2:
5 7 8
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
2 1 1
3 1 1
Sample Output 2:
None
题意:给出m条a给b打了c分钟的通话记录,要求找出哪些人是骗子。成为骗子的条件是,在这一天内给超过k个不同的人进行了短通话(所有a给b打的通话时长不超过5分钟),并且这些人只有不超过20%的人回拨了电话。如果两个人都是骗子,并且两个人都互相打过电话,就认为这两个骗子是一个组织的。最后输出各个组织里的人,组织内部按照id升序,组织输出顺序按照每个组织第一个人的id升序排列。如果一个组织都没有,则输出None
思路:建图,枚举,模拟,并查集
在没看到total duration
之前,我是邻接表建图,有点东西,细节拉满
如果是总时长的话,那必然是邻接矩阵建图,这样很方便得能过找到任意两个人的通话时间
还有一个细节就是each other
,就是说两个骗子需要互相都给对方打才认为是一个组织的
真是有点东西啊
直接模拟题意,标记好骗子,然后枚举任意两个骗子看是否能过合并,能够合并则合并,合并时把二者较小值作为父节点,随后用set
找出所有父节点,再遍历set
找出所有相同组织的成员,这里就已经保证了组织外部是有序的,组织内部也是有序的(set保证外部,顺序枚举保证内部),每个组织用vector
来存,答案数组是vector
嵌套vector
,最后判断答案数组的size
即可
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <set>
using namespace std;
const int N = 1010;
bool st[N];
int k, m, n, G[N][N], f[N];
void init()
{
for (int i = 0; i < N; i ++ )
f[i] = i;
}
int find(int x)
{
return f[x] = f[x] == x ? x : find(f[x]);
}
void merge(int x, int y)
{
int fx = find(x), fy = find(y);
if(fx > fy)
swap(fx, fy);
f[fy] = fx;
}
int main()
{
init();
cin >> k >> n >> m;
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
G[a][b] += c;
}
for(int i = 1; i <= n; i++)
{
unordered_set<int> s;
for(int j = 1; j <= n; j++)
{
if(G[i][j] && G[i][j] <= 5)
s.insert(j);
}
if(s.size() > k)
{
int cnt = 0;
for(auto &x : s)
{
if(G[x][i])
cnt++;
}
if(cnt <= (double)s.size() * 0.2)
st[i] = true;
}
}
for(int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j ++ )
{
if(st[i] && st[j] && G[i][j] && G[j][i])
merge(i, j);
}
}
set<int> s;
for(int i = 1; i <= n; i++)
{
if(st[i])
s.insert(f[i]);
}
vector<vector<int>> ans;
for(auto &x : s)
{
vector<int> t;
for (int i = 1; i <= n; i ++ )
if(st[i] && f[i] == x)
t.push_back(i);
ans.push_back(t);
}
if(ans.size())
{
for(auto &v : ans)
{
for (int i = 0; i < v.size(); i ++ )
cout << v[i] << (i == v.size() - 1 ? '\n' : ' ');
}
}
else
cout << "None" << endl;
return 0;
}
7-4 Structure of a Binary Tree(30分)
Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.
Now given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:
A is the root
A and B are siblings
A is the parent of B
A is the left child of B
A is the right child of B
A and B are on the same level
It is a full tree
Note:
Two nodes are on the same level, means that they have the same depth.
A full binary tree is a tree in which every node other than the leaves has two children.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are no more than 10&^3&and are separated by a space.
Then another positive integer M (≤30) is given, followed by M lines of statements. It is guaranteed that both A and B in the statements are in the tree.
Output Specification:
For each statement, print in a line Yes if it is correct, or No if not.
Sample Input:
9
16 7 11 32 28 2 23 8 15
16 23 7 32 11 2 28 15 8
7
15 is the root
8 and 2 are siblings
32 is the parent of 11
23 is the left child of 16
28 is the right child of 2
7 and 11 are on the same level
It is a full tree
Sample Output:
Yes
No
Yes
No
Yes
Yes
Yes
题意:给出一颗二叉树的后序遍历和中序遍历,要求重建二叉树并且判断m条语句的正确与否,比如说判断根节点,左右儿子,兄弟,父节点,是否再同一层以及是否为”满”二叉树,所有节点的权值是各不相同的正数,并且不超过1000
思路:树的遍历,重建二叉树,字符串处理
看到这个结构就知道这题稳了,做过两道类似的好像,二叉搜索树的结构和完全二叉树的结构应该是,都是一个类型的,给出遍历序列,重建二叉树之后,给定一些语句根据二叉树结构来判断正确与否
注意到每个节点的权值互不相同,所以我们可以直接通过节点的权值去映射其其他信息
比如节点的左右儿子,父节点,深度,并且这些信息都是可以在建树的时候完成赋值
最后坑的就是这个”满”二叉树的定义
看完这里加了引号你就知道并不是传统意义上的满二叉树了,如果是的话那就是每一层都是满的,只需要记录下最大层数和总结点个数比较一下就行
但是这里我们看Note
,里面给出了”满”二叉树的定义,它只是保留了每个节点要么左右儿子都有,要么都没有,换句话来说就是这棵树没有一度点,这个也可以在建树的时候完成赋值,只要建树过程中有一度点存在,就给变量赋值成false
这个字符串,读入一行(记得吸收掉读入行数的回车),然后根据不同语句的特定词进入到不同的语句情况,用sscanf
就行反向读入,从字符串读取输入并完成变量赋值
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <cmath>
using namespace std;
const int N = 1010;
int n, m;
bool isFull = true;
int in[N], post[N];
int l[N], r[N], deep[N], p[N], cnt;
unordered_map<int, int> mp;
int build(int il, int ir, int pl, int pr, int deepth, int parent)
{
int root = post[pr];
int k = mp[root];
p[root] = parent;
deep[root] = deepth;
if(il < k)
l[root] = build(il, k - 1, pl , pl + (k - 1 - il), deepth + 1, root);
if(k < ir)
r[root] = build(k + 1, ir, pl + (k - 1 - il) + 1, pr - 1, deepth + 1, root);
if(l[root] + r[root] != 0 && l[root] * r[root] == 0)
isFull = false;
return root;
}
void judge(int x, int y)
{
cout << (x == y ? "Yes" : "No") << endl;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
cin >> post[i];
for (int i = 0; i < n; i ++ )
{
cin >> in[i];
mp[in[i]] = i;
}
build(0, n - 1, 0, n - 1, 1, -1);
cin >> m;
getchar();
while (m -- )
{
int x, y;
string str;
getline(cin, str);
if(str.find("root") != -1)
{
sscanf(str.c_str(), "%d is the root", &x);
judge(deep[x], 1);
}
else if(str.find("siblings") != -1)
{
sscanf(str.c_str(), "%d and %d are siblings", &x, &y);
judge(p[x], p[y]);
}
else if(str.find("parent") != -1)
{
sscanf(str.c_str(), "%d is the parent of %d", &x, &y);
judge(x, p[y]);
}
else if(str.find("left") != -1)
{
sscanf(str.c_str(), "%d is the left child of %d", &x, &y);
judge(x, l[y]);
}
else if(str.find("right") != -1)
{
sscanf(str.c_str(), "%d is the right child of %d", &x, &y);
judge(x, r[y]);
}
else if(str.find("level") != -1)
{
sscanf(str.c_str(), "%d and %d are on the same level", &x, &y);
judge(deep[x], deep[y]);
}
else
{
judge(isFull, true);
}
}
return 0;
}