Областная олимпиада по информатике, 2008 год, 9-10-11 классы

Задача A. Hello world

Комментарий/решение

показать/скрыть код

 #include <iostream>
 #include <algorithm>
 #include <vector>
 #include <cmath>
 #include <string>
 #include <set>
 #include <map>
 #include <unordered_map>
 #include <iomanip>
 #include <stack>
 #include <queue>
 #include <deque>
using namespace std;
struct node{
    node *next[26];
    long long strings;
    node(){
        for(long long i=0;i<26;i++){
            next[i]=nullptr;
        }
        strings=0;
    }
};
node *root=new node();
void add(const string& s){
    node *cur_v=root;
    for(long long i = 0;i < s.size();i++){
        char c = s[i];
        if(cur_v->next[c-'a'] == nullptr){
            cur_v->next[c-'a'] = new node();
        }
        cur_v = cur_v->next[c-'a'];
    }
    cur_v->strings++;
}
long long ans;
void calc(long long prev, node *v = root){
    if(v->strings>0){
        ans+=(v->strings*prev);
        ans+=(v->strings*(v->strings-1))/2;
    }
    for(long long i = 0;i <26 ;i++){
        if(v->next[i]!=nullptr){
            calc(prev+(v->strings),v->next[i]);
        }
    }
}
int main(){
    long long n;
    cin>>n;
    for(long long i=0;i<n;i++){
        string s;
        cin>>s;
        add(s);
    }
    calc(0);
    cout<<ans;
}

показать/скрыть код

 #include <iostream>
 #include <algorithm>
 #include <vector>
 #include <cmath>
 #include <string>
 #include <set>
 #include <map>
 #include <unordered_map>
 #include <iomanip>
 #include <stack>
 #include <queue>
 #include <deque>
using namespace std;
struct node{
    node *next[26];
    long long strings;
    node(){
        for(long long i=0;i<26;i++){
            next[i]=nullptr;
        }
        strings=0;
    }
};
node *root=new node();
void add(const string& s){
    node *cur_v=root;
    for(long long i = 0;i < s.size();i++){
        char c = s[i];
        if(cur_v->next[c-'a'] == nullptr){
            cur_v->next[c-'a'] = new node();
        }
        cur_v = cur_v->next[c-'a'];
    }
    cur_v->strings++;
}
long long ans;
void calc(long long prev, node *v = root){
    if(v->strings>0){
        ans+=(v->strings*prev);
        ans+=(v->strings*(v->strings-1))/2;
    }
    for(long long i = 0;i <26 ;i++){
        if(v->next[i]!=nullptr){
            calc(prev+(v->strings),v->next[i]);
        }
    }
}
int main(){
    long long n;
    cin>>n;
    for(long long i=0;i<n;i++){
        string s;
        cin>>s;
        add(s);
    }
    calc(0);
    cout<<ans;
}