7-1 Forever(20分)
“Forever number” is a positive integer A with K digits, satisfying the following constrains:
the sum of all the digits of A is m;
the sum of all the digits of A+1 is n; and
the greatest common divisor of m and n is a prime number which is greater than 2.
Now you are supposed to find these forever numbers.
Input Specification:
Each input file contains one test case. For each test case, the first line contains a positive integer N (≤5). Then N lines follow, each gives a pair of K (3<K<10) and m (1<m<90), of which the meanings are given in the problem description.
Output Specification:
For each pair of K and m, first print in a line Case X, where X is the case index (starts from 1). Then print n and A in the following line. The numbers must be separated by a space. If the solution is not unique, output in the ascending order of n. If still not unique, output in the ascending order of A. If there is no solution, output No Solution.
Sample Input:
2
6 45
7 80
Sample Output:
Case 1
10 189999
10 279999
10 369999
10 459999
10 549999
10 639999
10 729999
10 819999
10 909999
Case 2
No Solution
题意:
给定一个k和一个m,求一个k位数a,a的各位数之和是m,a+1的各位数之和为n,并且m和n的最大公约数大于2并且是个质数,要求输出符合条件的n和a,先按照n升序,n相同按照a升序输出,如果无解输出No Solution
分析:
dfs,剪枝,构造,素数,约数
思路:
一开始直接暴力15分,完美收获超时
可以看下为什么超时,极限情况每次k都是9,遍历所有的九位数,需要计算约1e10
,那超时就不奇怪了
我们看下有什么性质可以用上,各位和这个性质可以用上
因为在遍历的时候,大部分情况都是各位之和是不等于m的,所以才造成极大的时间消耗
我们能不能根据各位之和构造一个k位数,这样就可以极大程度上避免无效的枚举
我们可以通过dfs
去构造,每次选取每个位上的数字,要注意这里构造出来的数一定要是正数,所以说我们在枚举第一位的时候不能是零,并且如果不用上各位之和这个条件,我们通过dfs
构造时间复杂度和直接遍历相差无几
那么怎么用呢,一个很简单的剪枝就是,如果在枚举过程中当前数的各位和已经超过m,那么再构造下去一定不能够找到答案的,还有就是如果当前各位和恰好等于m,但位数不足k或者大于k,这样也是不行的
但通过这两个剪枝我们仍然还是会超时,我们可以看下我们最先枚举出来的数字是什么(这里是每位数字按照从0-9枚举的),我们根据样例举例,需要构造一个6位数,各位和是45,我们最先枚举出来的就是100000,100001,100002……这些数字确实是六位数,但是我们会发现各位和距离45相差了十万八千里,我们能否为其加上一个剪枝呢
答案是可以的,比如我们枚举到10xxxx
时(xxxx代表还未枚举),我们可以尝试,如果把还未枚举出的数字全填上最大的9,能否凑出来45呢,如109999,各位和是37,可以看到即使全填上最大数字也不能凑够45,说明我们之前枚举的数字太小了,我们接着往下枚举是必然不可能凑出来答案的,所以说我们直接返回,不往下进行枚举了
通过如上方法进行剪枝,最大数据也仅需5ms
就能顺利通过(时限3000ms)
考试卡了很久因为没看到题目要求最大公约数还要满足是质数的条件,果然第一道题必考素数
排序输出的话直接用pair
就行了,自定义排序都省了
2021/09/10 18:56
还可以用上a,b两数的最大公约数大于2这个条件,可以断定最后一位一定是9。
因为如果不是9,就无法进位,那么b == a + 1,此时最大公约数一定是1,不可能大于2
2022/02/20 00:54
更新代码用上最后一位必定是9这个条件
时间来到3ms
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> PII;
int k, m;
vector<PII> res;
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 get_sum(int x)
{
int res = 0;
while(x)
{
res += x % 10;
x /= 10;
}
return res;
}
// u 当前第几位
// sum 当前和
// x 当前数
void dfs(int u, int sum, int x)
{
if(sum >= m || sum + 9 * (k - u + 1) < m)
return ;
if(u == k)
{
if(sum + 9 == m)
{
x = x * 10 + 9;
int n = get_sum(x + 1), num = __gcd(n, m);
if(is_prime(num) && num > 2)
res.push_back({n, x});
}
return ;
}
for(int i = 0; i < 10; i++)
{
if(u == 1 && i == 0)
continue;
dfs(u + 1, sum + i, x * 10 + i);
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> k >> m;
res.clear();
dfs(1, 0, 0);
cout << "Case " << i << endl;
if(res.size())
{
sort(res.begin(), res.end());
for(auto [a, b] : res)
cout << a << ' ' << b << endl;
}
else
puts("No Solution");
}
return 0;
}
7-2 Merging Linked Lists(25分)
Given two singly linked lists $L_1$ $=$ $a_1$ $\rightarrow$ $a_2$ $\rightarrow$ ···· $\rightarrow$ $a_{n-1}$ $\rightarrow$ $a_n$ and $L_2$ $=$ $b_1$ $\rightarrow$ $b_2$ $\rightarrow$ ···· $\rightarrow$ $b_{m-1}$ $\rightarrow$ $b_m$
. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a $a_1$ $\rightarrow$ $a_2$ $\rightarrow$ $b_m$ $\rightarrow$ $a_3$ $\rightarrow$ $a_4$ $\rightarrow$ $b_{m-1}$ ···· For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.
Input Specification:
Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of $L_1$ and $L_2$, plus a positive N (≤$10^5$) which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is a positive integer no more than $10^5$, and Next is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.
Output Specification:
For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.
Sample Input:
00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1
Sample Output:
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1
题意:给出两条链表,一条比另一条的两倍还要长,要求把短的逆序后,组成一条每两个长的再连上一个短的链表
思路:模拟,链表
又是一道老链表题了,每次的输出输出都差不多,但每次需要模拟问题有一些不一样
由于节点的地址不会超过$10^5$,所以我们可以直接通过地址去映射data
和next
,组成的链表就是用数组存的一系列节点的地址,一个循环就可以串起一个链表
值得注意的是,题目描述里,l1是长链表,但是举的例子里,l2又变成了长链表,说明哪个是长链表是不确定的,需要我们自己判断(默认l1是长链表能够得到22分),其实如果默认处理l1为长链表,发现l2比l1长,直接交换一下就行,或者是if判断写两遍相似的组合代码
注意在组合两个链表的时候,一定要先判断有没有越界,防止段错误
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int h1, h2, m;
int datas[N], ne[N];
int main()
{
cin >> h1 >> h2 >> m;
while (m -- )
{
int adress, d, next;
cin >> adress >> d >> next;
datas[adress] = d, ne[adress] = next;
}
vector<int> l1, l2;
while(h1 != -1)
{
l1.push_back(h1);
h1 = ne[h1];
}
while(h2 != -1)
{
l2.push_back(h2);
h2 = ne[h2];
}
if(l2.size() > l1.size()) //并没有说哪个链表是长的
swap(l1, l2);
reverse(l2.begin(), l2.end());
vector<int> all;
for(int i = 0, j = 0; i < l1.size();)
{
all.push_back(l1[i++]);
if(i < l1.size())
all.push_back(l1[i++]);
if(j < l2.size())
all.push_back(l2[j++]);
}
for (int i = 0; i + 1 < all.size(); i ++ )
printf("%05d %d %05d\n", all[i], datas[all[i]], all[i + 1]);
if(all.size())
printf("%05d %d -1\n", all.back(), datas[all.back()]);
return 0;
}
7-3 Postfix Expression(25分)
Given a syntax tree (binary), you are supposed to output the corresponding postfix expression, with parentheses reflecting the precedences of the operators.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (≤ 20) which is the total number of nodes in the syntax tree. Then N lines follow, each gives the information of a node (the i-th line corresponds to the i-th node) in the format:
data left_child right_child
where data is a string of no more than 10 characters, left_child and right_child are the indices of this node’s left and right children, respectively. The nodes are indexed from 1 to N. The NULL link is represented by −1. The figures 1 and 2 correspond to the samples 1 and 2, respectively.
$\qquad$$\qquad$$\qquad$Figure 1 $\qquad$$\qquad$$\qquad$$\qquad$$\qquad$$\qquad$ Figure 2
Output Specification:
For each case, print in a line the postfix expression, with parentheses reflecting the precedences of the operators.There must be no space between any symbols.
Sample Input 1:
8
* 8 7
a -1 -1
* 4 1
+ 2 5
b -1 -1
d -1 -1
- -1 6
c -1 -1
Sample Output 1:
(((a)(b)+)((c)(-(d))*)*)
Sample Input 2:
8
2.35 -1 -1
* 6 1
- -1 4
% 7 8
+ 2 3
a -1 -1
str -1 -1
871 -1 -1
Sample Output 2:
(((a)(2.35)*)(-((str)(871)%))+)
思路:给定每个节点左右儿子,要求输出其后缀表达式并为其添加括号
题意:树的遍历,模拟
其实这道题看懂题意才是最难的,一开始我以为直接后序遍历输出就是了,括号也就是每个节点都加上,但是交上去只得了1分,仔细观察才发现与样例的区别
比如说第一个样例的”-“号,正常的后序遍历,这个”-“号应该出现在c和d之后的,但是它却出现在了c和d之间??
因为是这样的,”+”号和”-“号不仅可以表示二元运算符的加号和减号,也可以用作单元运算符,表示正号和负号,如果一个运算符它只有右儿子,左儿子为空的话,说明这个运算符是单元运算符,所以说出现在c和d之间的”-“号代表-d
所以我们需要特殊处理这种情况,此时需要把二者作为整体,-和d,所以应该先遍历根节点,输出-,再遍历右子树
其余情况正常后序遍历即可
代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 25;
int n;
int l[N], r[N];
bool isChild[N];
string datas[N];
void post(int u)
{
if(u == -1)
return ;
cout << "(";
if(l[u] == -1 && r[u] != -1) //处理+-号为单元操作符的情况
{
cout << datas[u];
post(r[u]);
}
else
{
post(l[u]);
post(r[u]);
cout << datas[u];
}
cout << ")";
return ;
}
int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ )
{
cin >> datas[i] >> l[i] >> r[i];
if(l[i] != -1)
isChild[l[i]] = true;
if(r[i] != -1)
isChild[r[i]] = true;
}
int root = 1;
while(isChild[root])
root++;
post(root);
return 0;
}
7-4 Dijkstra Sequence(30分)
Dijkstra’s algorithm is one of the very famous greedy algorithms. It is used for solving the single source shortest path problem which gives the shortest paths from one particular source vertex to all the other vertices of the given graph. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.
In this algorithm, a set contains vertices included in shortest path tree is maintained. During each step, we find one vertex which is not yet included and has a minimum distance from the source, and collect it into the set. Hence step by step an ordered sequence of vertices, let’s call it Dijkstra sequence, is generated by Dijkstra’s algorithm.
On the other hand, for a given graph, there could be more than one Dijkstra sequence. For example, both { 5, 1, 3, 4, 2 } and { 5, 3, 1, 2, 4 } are Dijkstra sequences for the graph, where 5 is the source. Your job is to check whether a given sequence is Dijkstra sequence or not.
Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers $N_v$(≤$10^3$) and $N_e$(≤$10^5$), which are the total numbers of vertices and edges, respectively. Hence the vertices are numbered from 1 to $N_v$.
Then $N_e$lines follow, each describes an edge by giving the indices of the vertices at the two ends, followed by a positive integer weight (≤100) of the edge. It is guaranteed that the given graph is connected.
Finally the number of queries, K, is given as a positive integer no larger than 100, followed by K lines of sequences, each contains a permutationof the $N_v$vertices. It is assumed that the first vertex is the source for each sequence.
All the inputs in a line are separated by a space.
Output Specification:
For each of the K sequences, print in a line Yes if it is a Dijkstra sequence, or No if not.
Sample Input:
5 7
1 2 2
1 5 1
2 3 1
2 4 1
2 5 2
3 5 1
3 4 1
4
5 1 3 4 2
5 3 1 2 4
2 3 4 5 1
3 2 1 5 4
Sample Output:
Yes
Yes
Yes
No
题意:给定一无向图,再给出m个顶点序列,要求判断这些序列是否是合法的dijkstra
的顶点选择序列
题意:模拟,dijkstra
感觉这题是最直接最简单的题目了,感觉是个趋势,很多题目都是判别是否合法
直接模拟即可,注意每个序列第一个给出的顶点就是起点(并不是每次都起点为1)
其次我们每次取出来的最小距离的顶点,我们都和给出的顶点判断,如果二者对应的距离起点的距离相等,那么我们就选择给出的那个顶点,反正必然不是合法的情况,如果能够正常执行完整个dijkstra
算法,那么就是合法的顶点序列
点数小于$10^3$,直接用邻接矩阵存图即可,计算次数是100次dijkstra($10^6$),到达了$10^8$,时间2s足以,极限数据是489ms,如果对时间不放心还可以用堆优化版的dijkstra
代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1010;
int n, m, k;
int G[N][N], dist[N];
bool vis[N];
bool dijkstra(vector<int> &path)
{
memset(vis, 0, sizeof vis);
memset(dist, 0x3f, sizeof dist);
dist[path[0]] = 0;
int k = 0;
while(true)
{
int t = -1;
for (int i = 1; i <= n; i ++ )
if(!vis[i] && (t == -1 || (dist[t] > dist[i])))
t = i;
if(t == -1)
break;
if(dist[t] != dist[path[k]])
return false;
t = path[k++];
vis[t] = true;
for (int i = 1; i <= n; i ++ )
dist[i] = min(dist[i], dist[t] + G[t][i]);
}
return true;
}
int main()
{
memset(G, 0x3f, sizeof G);
cin >> n >> m;
while (m -- )
{
int a, b, c;
cin >> a >> b >> c;
G[a][b] = G[b][a] = min(G[a][b], c);
}
cin >> k;
while(k--)
{
vector<int> path(n);
for (int i = 0; i < n; i ++ )
cin >> path[i];
cout << (dijkstra(path) ? "Yes" : "No") << endl;
}
return 0;
}