数据结构与算法复习：第三十六弹
依旧是查漏补缺为主题~
昨天去迎新结果一个下午都呆在帐篷里，算起来三年迎新每一次都阴差阳错地参加了，感觉还是很有意义der(不过因为是下午场的原因，基本上见不到新生了，于是唠嗑中度过😃)
这两天都在订正之前光顾着刷题但是没有订正的部分，因为一开始写了前面的十几道，后来模拟是从后往前刷的，再回头看前面的一些错误觉得：很哇塞了😅，有一些确实是比较难，也有一些就是当时考虑不周导致测试点卡住，
修复的bug:1015，1009,1021
没有完全修复的bug：1010（24/25）
1. 1015 Reversible Primes
A reversible prime in any number system is a prime whose “reverse” in that number system is also a prime. For example in the decimal system 73 is a reversible prime because its reverse 37 is also a prime.
Now given any two positive integers N (<105) and D (1<D≤10), you are supposed to tell if N is a reversible prime with radix D.
Input Specification:
The input file consists of several test cases. Each case occupies a line which contains two integers N and D. The input is finished by a negative N.
Output Specification:
For each test case, print in one line Yes if N is a reversible prime with radix D, or No if not.
Sample Input:
73 10
23 2
23 10
-2
Sample Output:
Yes
Yes
No
分析
首先判断输入的N是否是正素数，满足条件后再判断在指定D位下的逆转后的N是否还是素数，这个逆转后的数字转换成十进制可以在逆转的过程中就实现，代码如下：
#include<bits/stdc++.h>
using namespace std;
int N,D;
bool isPrime(int x){
if(x<=1){
return false;
}
if(x==2||x==3||x==5||x==7){
return true;
}
for(int i=2;i*i<=x;i++){
if(x%i==0){
return false;
}
}
return true;
}
int convert(int N,int D){
int ans=0;
//printf("%d",N);
while(N){
ans=ans*D+N%D;
N/=D;
}
//printf("-%d\n",ans);
return ans;
}
int main(){
while(scanf("%d",&N)&&N>=0){
scanf("%d",&D);
if(isPrime(N)&&isPrime(convert(N,D))){
printf("Yes\n");
}else{
printf("No\n");
}
}
return 0;
}
2. 1009 Product of Polynomials
This time, you are supposed to find A×B where A and B are two polynomials.
Input Specification:
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:
K N1 a**N1 N2 a**N2 … N**K aNK
where K is the number of nonzero terms in the polynomial, N**i and aNi (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10, 0≤N**K<⋯<N2<N1≤1000.
Output Specification:
For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.
Sample Input:
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output:
3 3 3.6 2 6.0 1 1.6
题目分析
一开始写的时候用了Map来避免重复访问0的问题，但是问题在于在多项式乘法个过程中，加和过程会导致产生0的情况，在这种情况下需要用erase删除后之前统计的对应的指数
#include<bits/stdc++.h>
using namespace std;
//多项式乘法
const int maxn=1001;
struct Poly{
map<int,double>mp;
int K;
};
Poly A,B,C;
int ep;double co;
int main(){
//输入A
scanf("%d",&A.K);
for(int i=0;i<A.K;i++){
scanf("%d%lf",&ep,&co);
A.mp[ep]=co;
}
//输入B
scanf("%d",&B.K);
for(int i=0;i<B.K;i++){
scanf("%d%lf",&ep,&co);
B.mp[ep]=co;
}
//计算乘法
for(map<int,double>::iterator ait=A.mp.begin();ait!=A.mp.end();ait++){
for(map<int,double>::iterator bit=B.mp.begin();bit!=B.mp.end();bit++){
co=ait->second*bit->second;
ep=ait->first+bit->first;
if(co==0){
continue;
}
if(C.mp.find(-ep)==C.mp.end()){
C.mp[-ep]=co;
}else{
C.mp[-ep]+=co;
if(C.mp[-ep]==0){
C.mp.erase(-ep);
}
}
}
}
//输出
printf("%d",C.mp.size());
for(map<int,double>::iterator cit=C.mp.begin();cit!=C.mp.end();cit++){
printf(" %d %.1f",-cit->first,cit->second);
}
return 0;
}
3. 1010 Radix
Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number.
Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given.
Input Specification:
Each input file contains one test case. Each case occupies a line which contains 4 positive integers:
N1 N2 tag radix
Here N1 and N2 each has no more than 10 digits. A digit is less than its radix and is chosen from the set { 0-9, a-z } where 0-9 represent the decimal numbers 0-9, and a-z represent the decimal numbers 10-35. The last number radix is the radix of N1 if tag is 1, or of N2 if tag is 2.
Output Specification:
For each test case, print in one line the radix of the other number so that the equation N1 = N2 is true. If the equation is impossible, print Impossible. If the solution is not unique, output the smallest possible radix.
Sample Input 1:
6 110 1 10
Sample Output 1:
2
Sample Input 2:
1 ab 1 2
题目分析
首先得到给定radix的数字对应的十进制数，然后再逐个计算从2到100radix中哪一个使得另一个数字对应的十进制数等于第一个数字
订正思路主要是radix必须保证原始N2中每一个数字都要小于radix，否则停止计算直接返回false
订正后得分从19变成24，主要是第七个测试点的问题，看了题解说是需要用二分……emmmm好吧，分就分
24分代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
string N1,N2;
ull n1=0;
int tag,radix;
bool flag=true;
bool ok(int radix){
ull a=1,n2=0;
for(int i=N2.length()-1;i>=0;i--){
if(N2[i]<='9'&&N2[i]>='0'){
if(N2[i]-'0'>=radix){
return false;
}
n2=n2+(N2[i]-'0')*a;
}else{
if(N2[i]-'a'+10>=radix){
return false;
}
n2=n2+(N2[i]-'a'+10)*a;
}
a*=radix;
}
// cout<<radix<<":"<<n2<<"\n";
if(n2>n1){
flag=false;
}
if(n2==n1){
return true;
}else{
return false;
}
}
int main(){
cin>>N1>>N2>>tag>>radix;
if(tag==2){
swap(N1,N2);
}
//N1的十进制的值
ull a=1;
for(int i=N1.length()-1;i>=0;i--){
if(N1[i]<='9'&&N1[i]>='0'){
n1=n1+(N1[i]-'0')*a;
if(N1[i]-'0'>=radix){
printf("Impossible");
return 0;
}
}else{
if(N1[i]-'a'+10>=radix){
printf("Impossible");
return 0;
}
n1=n1+(N1[i]-'a'+10)*a;
}
a*=radix;
}
// cout<<"原本的数字："<<n1<<"\n";
for(int i=2;i<=100000;i++){
if(ok(i)){
printf("%d",i);
return 0;
}
if(!flag){
break;
}
}
printf("Impossible");
return 0;
}
二分代码如下【参考链接】
4. 1021 Deepest Root
A graph which is connected and acyclic can be considered a tree. The height of the tree depends on the selected root. Now you are supposed to find the root that results in a highest tree. Such a root is called the deepest root.
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤104) which is the number of nodes, and hence the nodes are numbered from 1 to N. Then N−1 lines follow, each describes an edge by given the two adjacent nodes’ numbers.
Output Specification:
For each test case, print each of the deepest roots in a line. If such a root is not unique, print them in increasing order of their numbers. In case that the given graph is not a tree, print Error: K components where K is the number of connected components in the graph.
Sample Input 1:
5
1 2
1 3
1 4
2 5
Sample Output 1:
3
4
5
Sample Input 2:
5
1 3
1 4
2 5
3 4
Sample Output 2:
Error: 2 components
本题是求连通图的个数+树的直径求解
首先dfs判断连通图个数，大于1的则Error，在DFS过程中找出任意起点开始的最大深度导向的结点，存入ans数组中，之后同样的DFS过程对ans中任一结点操作得到新的ans数组，两次ans数组的并集即为答案。
至于为什么两次DFS就可以得到答案，是有证明der,这里不列了，记住就好~
代码如下：
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> >graph;
vector<bool>vis;
int N,v1,v2,cnt=0;
int max_deep=1;
vector<int>ans;
void dfs(int x,int deep){
deep++;
vis[x]=true;
bool flag=false;
for(int i=0;i<graph[x].size();i++){
if(!vis[graph[x][i]]){
dfs(graph[x][i],deep);
flag=true;
}
}
if(!flag){
if(deep>max_deep){
max_deep=deep;
ans.clear();
ans.push_back(x);
}else if(deep==max_deep){
ans.push_back(x);
}
}
}
int main(){
scanf("%d",&N);
graph.resize(N+1);
vis.resize(N+1,false);
for(int i=0;i<N-1;i++){
scanf("%d%d",&v1,&v2);
graph[v1].push_back(v2);
graph[v2].push_back(v1);
}
for(int i=1;i<=N;i++){
if(!vis[i]){
cnt++;
dfs(i,0);
}
}
if(cnt>1){
printf("Error: %d components",cnt);
}else{
set<int>res;
for(int i=0;i<ans.size();i++){
res.insert(ans[i]);
}
int x=ans[0];
ans.clear();
fill(vis.begin(),vis.end(),false);
dfs(x,0);
for(int i=0;i<ans.size();i++){
res.insert(ans[i]);
}
for(set<int>::iterator it=res.begin();it!=res.end();it++){
printf("%d\n",*it);
}
}
return 0;
}