1. 知识点总结
卡在了图树结构上🤣，订正过真不应该啊哈哈
2. 分题题解
2.1 General Palindromic Number
回文判别+进制转换，属于大一C++基础，没有难度和坑
需要注意的是转换后每个位保存在vector中，因为radix的值比较大，超过36了
#include<bits/stdc++.h>
using namespace std;
int num,radix;
vector<int>ans;
int len;
void change(int num,int index){
while(num){
ans.push_back(num%index);
num/=index;
}
return;
}
bool isPalindromic(){
len=ans.size();
for(int i=0;i<len/2;i++){
if(ans[i]!=ans[len-i-1]){
return false;
}
}
return true;
}
int main(){
scanf("%d%d",&num,&radix);
change(num,radix);
if(isPalindromic()){
printf("Yes\n");
}else{
printf("No\n");
}
for(int i=len-1;i>=0;i--){
if(i!=len-1){
printf(" ");
}
printf("%d",ans[i]);
}
return 0;
}
2.2 Tree Traversals
根据后序遍历和中序遍历得到树结构再层序输出：
属于数据结构基础题，也是板子题
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>pos;
vector<int>in;
struct node{
int val;
node* left=NULL;
node* right=NULL;
};
node* build(int posL,int posR,int inL,int inR){
if(posL>posR||inL>inR){
return NULL;
}
int k;
int val=pos[posR];
for(int i=inL;i<=inR;i++){
if(in[i]==val){
k=i;
break;
}
}
int Left_len=k-inL;
node*root=new node;
root->val=val;
root->left=build(posL,posL+Left_len-1,inL,k-1);
root->right=build(posL+Left_len,posR-1,k+1,inR);
return root;
}
void levelTravel(node* root){
queue<node*>q;
q.push(root);
bool flag=false;
while(!q.empty()){
node* top=q.front();
q.pop();
if(!flag){
flag=true;
}else{
printf(" ");
}
printf("%d",top->val);
if(top->left!=NULL){
q.push(top->left);
}
if(top->right!=NULL){
q.push(top->right);
}
}
return ;
}
int main(){
scanf("%d",&n);
pos.resize(n);
in.resize(n);
for(int i=0;i<n;i++){
scanf("%d",&pos[i]);
}
for(int i=0;i<n;i++){
scanf("%d",&in[i]);
}
node* root=build(0,n-1,0,n-1);
levelTravel(root);
return 0;
}
2.3 Deepest Root
订正过又忘了……超时＋错误
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> >graph;
vector<bool>vis;
int cnt=0;
int n;
int u,v;
int max_level=-1;
set<int>ans;
void dfs(int id,int level){
vis[id]=true;
for(int i=0;i<graph[id].size();i++){
if(!vis[graph[id][i]]){
dfs(graph[id][i],level+1);
}
}
return;
}
void dfs2(int id,int level,int root){
vis[id]=true;
bool flag=false;
for(int i=0;i<graph[id].size();i++){
if(!vis[graph[id][i]]){
dfs2(graph[id][i],level+1,root);
flag=true;
}
}
if(!flag){
if(level>max_level){
max_level=level;
ans.clear();
ans.insert(root);
}else if(level==max_level){
ans.insert(root);
}
}
return;
}
int main(){
scanf("%d",&n);
graph.resize(n+1);
vis.resize(n+1);
for(int i=0;i<n-1;i++){
scanf("%d%d",&u,&v);
graph[u].push_back(v);
graph[v].push_back(u);
}
fill(vis.begin(),vis.end(),false);
for(int i=1;i<=n;i++){
if(!vis[i]){
cnt++;
dfs(i,0);
}
}
if(cnt!=1){
printf("Error: %d components",cnt);
}else{
for(int i=1;i<=n;i++){
if(graph[i].size()==1){
fill(vis.begin(),vis.end(),false);
dfs2(i,0,i);
}
}
for(set<int>::iterator it=ans.begin();it!=ans.end();it++){
printf("%d\n",*it);
}
}
return 0;
}
2.4 Digital Library
结构体的简单应用，同时复习了find+vector写法;难度不敌前一题
#include<bits/stdc++.h>
using namespace std;
struct Book{
string id;
string title;
string author;
vector<string>keywords;
string publisher;
string date;
};
int n,m;
int op;
string temp;
string query;
vector<Book>books;
string str;
bool cmp(Book a,Book b){
return a.id<b.id;
}
int main(){
scanf("%d",&n);
books.resize(n);
getchar();
for(int i=0;i<n;i++){
getline(cin,books[i].id);
getline(cin,books[i].title);
getline(cin,books[i].author);
getline(cin,str);
temp="";
str+=" ";
for(int k=0;k<str.length();k++){
if(str[k]==' '){
if(temp!=""){
books[i].keywords.push_back(temp);
temp="";
}
}else{
temp+=str[k];
}
}
getline(cin,books[i].publisher);
getline(cin,books[i].date);
}
scanf("%d",&m);
sort(books.begin(),books.end(),cmp);
bool flag=false;
for(int i=0;i<m;i++){
scanf("%d: ",&op);
getline(cin,str);
flag=false;
printf("%d: ",op);
cout<<str<<"\n";
if(op==1){
for(int i=0;i<n;i++){
if(books[i].title==str){
flag=true;
cout<<books[i].id<<"\n";
}
}
}else if(op==2){
for(int i=0;i<n;i++){
if(books[i].author==str){
flag=true;
cout<<books[i].id<<"\n";
}
}
}else if(op==3){
for(int i=0;i<n;i++){
if(find(books[i].keywords.begin(),books[i].keywords.end(),str)!=books[i].keywords.end()){
flag=true;
cout<<books[i].id<<"\n";
}
}
}else if(op==4){
for(int i=0;i<n;i++){
if(books[i].publisher==str){
flag=true;
cout<<books[i].id<<"\n";
}
}
}else{
for(int i=0;i<n;i++){
if(books[i].date==str){
flag=true;
cout<<books[i].id<<"\n";
}
}
}
if(!flag){
cout<<"Not Found\n";
}
}
return 0;
}
|