Σελίδα 2 από 2
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Δημοσιεύτηκε: Σάβ Απρ 03, 2021 3:12 pm
από switch
Ανιιξε την εφαρμογη zoom, για join id κανεις copy paste το id και σου εβγαλε invalid?
Βαλε αυτο για id
https://ucph-ku.zoom.us/j/62298579631?p ... RQZitYZz09
Copy link address πρεπει να κανεις, οχι copy text
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Δημοσιεύτηκε: Σάβ Απρ 03, 2021 3:14 pm
από giorgosk
ακριβώς έτσι τα έκανα και νγάζει invalid
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Δημοσιεύτηκε: Σάβ Απρ 03, 2021 11:07 pm
από Marilenatsiop
Καλησπέρα σας!
Παρακάτω βρίσκονται οι κώδικες για τις λύσεις που παρουσιάσαμε στην κλήση.
Η αναπαράσταση του binary tree γίνεται με έναν διπλό πίνακα : node[1002][2] και η DFS υλοποιείται αναδρομικά.
- Spoiler: show
-
ΛΥΣΗ Ο(Ν+Μ)
⋒ Σε αυτήν την λύση, ξεκινώ απο δύο roots που διασχίζουν ταυτόχρονα το
tree, όταν το root1 κινείται left το root2 κινείται right και αντίστροφα, οπότε το root1
είναι αντικατοπρικο του root2 (και αντίστροφα) και αυτή την πληροφορία την αποθηκεύω
στον πίνακα mirror.
Κώδικας: Επιλογή όλων
//ΛΥΣΗ Ο(Ν+Μ)
#include <iostream>
using namespace std;
int n,m,q,a,b;
int node[1002][2];
int mirror[1002];
char c;
int L=0,R=1;
void dfs(int root1,int root2){
if(root1==0 or root2==0){
return;
}
mirror[root1]=root2;
mirror[root2]=root1;
dfs(node[root1][L],node[root2][R]);
dfs(node[root1][R],node[root2][L]);
}
int main()
{
cin>>n>>m;
for(int i=1; i<n; i++){
cin>>a>>b>>c;
if(c=='L'){
node[a][L]=b;
}else{
node[a][R]=b;
}
}
for(int i=0; i<m; i++){
cin>>q;
if(mirror[q]==0){
cout<<"-1"<<'\n';
}else{
cout<<mirror[q]<<'\n';
}
}
return 0;
}
⋒ Σε αυτήν την λύση έχω πάλι 2 roots που τρέχουν ταυτόχρονα το tree, το root1 διασχίζει το left sub tree και το root2 το right sub tree με την dfs. Πρώτα διασχίζω τα external nodes και μετά τα internal nodes και αν κάποιο root βρεί το value, επιστρέφω το αντίθετο root.
Κώδικας: Επιλογή όλων
//ΛΥΣΗ Ο(Ν*Μ)
#include <iostream>
using namespace std;
int n,m,a,b,q;
char c;
int node[1002][2];
int L=0,R=1;
int dfs(int value, int root1, int root2){
if(root1==0 or root2==0){
return -1;
}
if(root1==value){
return root2;
}
if(root2==value){
return root1;
}
int ans=dfs(value,node[root1][L],node[root2][R]);
if(ans>0){
return ans;
}
return dfs(value,node[root1][R],node[root2][L]);
}
int main(){
cin>>n>>m;
for(int i=1; i<n; i++){
cin>>a>>b>>c;
if(c=='L'){
node[a][L]=b;
}else{
node[a][R]=b;
}
}
for(int i=0; i<m; i++){
cin>>q;
cout<<dfs(q,1,1)<<'\n';
}
return 0;
}
⋒ Σε αυτήν την λύση έχω μόνο ένα root, το οποίο τρεχει ολο το tree μέχρι να βρει το value και αποθηκεύω τον "δρόμο" του σε έναν πίνακα path. Μετά διαβαζω τον πίνακα path αντίστροφα , δηλαδή όποτε βλέπω right , το root παει left και το αντίστροφο.
Κώδικας: Επιλογή όλων
//ΛΥΣΗ Ο(Ν*Μ)
#include <iostream>
using namespace std;
int n,m,a,b,q;
char c;
int node[1002][2];
const int L=0,R=1;
char path[1002];
bool dfs1(int value, int root, int height){
if(root==0){
return false;
}
if(root==value){
path[height]=0;
return true;
}
path[height]='L';
if(dfs1(value,node[root][L],height+1)>0){
return true;
}
path[height]='R';
if(dfs1(value,node[root][R],height+1)>0){
return true;
}
return false;
}
int dfs2(int root,int height){
if(root==0){
return -1;
}
if(path[height]=='\0'){
return root;
}
if(path[height]=='L'){
dfs2(node[root][R],height+1);
}if(path[height]=='R'){
dfs2(node[root][L],height+1);
}
}
int main(){
cin>>n>>m;
for(int i=1; i<n; i++){
cin>>a>>b>>c;
if(c=='L'){
node[a][L]=b;
}else{
node[a][R]=b;
}
}
for(int i=0; i<m; i++){
cin>>q;
dfs1(q,1,0);
cout<<dfs2(1,0)<<'\n';
}
return 0;
}
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Δημοσιεύτηκε: Πέμ Απρ 22, 2021 9:31 pm
από Κηπουρίδης
Ορίστε και η παρουσίαση που μας έκανε η Μαριλένα. Να σημειώσω ότι λόγω τεχνικών προβλημάτων η Μαριλένα μου ζήτησε να την ανεβάσω εγώ ακριβώς μετά την κλήση.
Η αργοπορία είναι καθαρά δικό μου λάθος, ζητώ συγγνώμη.
https://www.file.io/download/231AJr2Ls7Mh
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Δημοσιεύτηκε: Παρ Απρ 23, 2021 8:36 am
από radaiosm7
Υπάρχει ένα πρόβλημα με το αρχείο οπότε θα ανέβει ξανά σήμερα.
Re: Μηνιαία Πρόκληση: Μάρτιος 2021
Δημοσιεύτηκε: Σάβ Απρ 24, 2021 3:39 pm
από Κηπουρίδης