Областная олимпиада по информатике 2019 год

Задача E. Меж двух миров

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Алан живет в мире под номером $A$. Нурдаулет живет в мире под номером $B$. В мире $A$, если одна строка является префиксом другой, то они считаются одинаковыми. У Нурдаулета есть $n$ строк, он хочет узнать количество неупорядоченных пар $i, j$ таких, что Алану они покажется одинаковыми. Помогите Нурдаулету с задачей. Обозначим $|s|$ как длину строки $s$. Строка $s$ является префиксом строки $t$, если $|s| <= |t|$ и строка $s$ равна строке, образованной из первых $|s|$ символов строки $t$.

Формат входного файла

В первой строке дается единственное число $n (1 <= n <= 100000)$ — количество строк. В следующих $n$ строках дается по одной строке $s_i$. Гарантируется, что суммарная длина строк не превышает $500000$.

Формат выходного файла

Выведите единственное число — ответ на задачу.

Система оценки

В 40 процентах тестов $n <= 100$. В 20 процентах тестов, длины всех строк равны.

Пример:

Вход

3
ab
abc
ab

Ответ

3

( Alan Amanov )

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

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

#include <bits/stdc++.h>
#define ll long long
#define N 100010
#define pb push_back
#define si size()
#define fi first
#define se second

using namespace std;

const int inf = 2e9;
const int modw = 1e9 + 7;

map<string, int> ans;
map<string, int> rv;

string a[N];

bool cp(string a, string b)
{
	int asize = a.si;
	int bsize = b.si;
	if(asize > bsize)
		return false;
	if(bsize > asize)
		return true;
	else
	{
		for(int i = 0; i < asize; i++)
		{
			if(a[i] > b[i])
				return false;
			if(b[i] > a[i])
				return true;
		}
	}
	return false;
}

int main()
{
	int n;
	cin >> n;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n, cp);
	for(int i = 0; i < n; i++)
	{
		string t = "";
		t += a[i][0];
		for(int j = 1; j < a[i].si; j++)
		{
			if(ans.find(t) != ans.end())
				ans[t]++;
			t += a[i][j];
			//cout << t << endl;
		}
		if(ans.find(a[i]) == ans.end())
		{
			ans[a[i]] = 0;
			rv[a[i]] = 1;
		}
		else
		{
			rv[a[i]]++;
		}
	}
	ll otv = 0;
	for(map<string, int>::iterator it = ans.begin(); it != ans.end(); it++)
	{
		otv += (it->se) * (rv.find(it->fi))->se;
	}
	//cout << endl;
	for(map<string, int>::iterator it = rv.begin(); it != rv.end(); it++)
	{
		int temp = (it->se);
		otv += (temp * (temp - 1)) / 2;
	}
	cout << otv;
}

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

with open('input') as file:

    inner, data = file.readlines(), list()

    for line in inner: data.append(line.split('\n')[0])

    data, sc, out = sorted(data), dict(), list()

    for num in range(1, len(data)):

        for i in range(0, len(data[num])+1):

            if data[num][0:i] == data[num][0:i] and data[num][0:i] != '':

                prefix = data[num][0:i]

                if prefix in sc.keys(): sc.update({prefix: int(sc[prefix] + 1)})

                else: sc.update({prefix: 1})

    with open('output', 'w') as file: file.write(str(max(sc.values())))

    

Вот решение с помощью бора тупое но работает

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

#include <bits/stdc++.h>
using namespace std;
  
#define F first
#define S second 
#define mp make_pair
#define pb push_back
#define pf push_front
#define speed_up ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define debug cerr << "OK\n";
#define ub upper_bound
#define lb lower_bound
#define treap_pair pair<treap*, treap*>
  
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef set <int> si;
typedef set <ll> sll;
typedef multiset <int> msi;
typedef multiset <ll> msll;
typedef map <int, int> mi;
typedef map <ll, ll> mll;
  
const int N = 1e5 + 2;
const int M = 1e5 + 2;
const int mod = 1e9 + 7;
const int inf = 1e9;
const ll INF = 1e16;
  
void data() {
    #ifdef PC
        freopen("main.in", "r", stdin);
        freopen("main.out", "w", stdout);
    #endif
}
  
template <typename T>
void scerr(T nums) {
    for (auto it : nums)
        cerr << it << " | ";
    cerr << "\n";
}

int n, k, ans = 0;
string s[N];

struct trie {
	trie *nxt[26];
	int end, sum;
	trie() {
		for (int i = 0; i < 26; ++i)
			nxt[i] = nullptr;
		end = 0;
		sum = 0;
	}
} *t = new trie();

void add(string s) {
	trie *cnt = t;
	for (int i = 0; i < sz(s); ++i) {
		if (cnt->nxt[s[i] - 'a'] == nullptr)
			cnt->nxt[s[i] - 'a'] = new trie();
		cnt = cnt->nxt[s[i] - 'a'];
	}
	cnt->end++;
}

void cnt(string s) {
	trie *cnt = t;
	int sum = 0;
	for (int i = 0; i < sz(s); ++i) {
		sum += cnt->end;
		if (cnt->nxt[s[i] - 'a'] != nullptr)
			cnt = cnt->nxt[s[i] - 'a'];
	}
	cnt->sum = sum;
}

void cnt1(string s) {
	trie *cnt = t;
	for (int i = 0; i < sz(s); ++i) {
		if (cnt->nxt[s[i] - 'a'] != nullptr)
			cnt = cnt->nxt[s[i] - 'a'];
	}
	ans += cnt->sum;
	ans += cnt->end - 1;
	cnt->end--;
}


int main() {
    data();
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		cin >> s[i];
		add(s[i]);
	}
	for (int i = 1; i <= n; ++i) {
		cnt(s[i]);
	}
	for (int i = 1; i <= n; ++i) {
		cnt1(s[i]);

	}
	printf("%d", ans);	
}       
  
/*
    Timus: 288481RF
    CodeForces: fractal
*/

Решение Бором с удалениями и сортировкой.

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

#include <bits/stdc++.h>
#define ll int
#define pb push_back
#define f first
#define s second
#define pill pair<ll,ll>
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const ll N = 2e5 ;

struct node{
    node *anc[26];
    ll ends;
    node(){
        for(int i = 0 ; i < 26 ; i++)
            anc[i] = nullptr;
        ends = 0;
    }
} *root = new node(); 

void add(string a){
    node *v = root;
    for(int i = 0 ; i < a.size() ; i++){
        ll c = a[i] - 'a';
        if(v -> anc[c] == nullptr)
            v -> anc[c] = new node();
        v =  v -> anc[c];
    }
    (v -> ends)++;
}
string dl;
 
void del(node *v = root, node *an = root , ll cur = 0){
    if(dl.size() != cur)
        del(v -> anc[dl[cur] - 'a'] , v , cur + 1);
    if(cur == 0)
        return;
    if(cur == dl.size())
        (v -> ends)--;
    for(int i = 0 ; i < 26 ; i++)
        if(v -> anc[i] != nullptr)
            return;
    if(v -> ends)
        return;
    an -> anc[dl[cur - 1] - 'a'] = nullptr;
}
 
string a,b;
ll n,f = 0;
void dfs(string p){
    node v = root;
    for(int i = 0 ; i < p.size() ; i++){
        ll c = p[i] - 'a';
        v = v -> anc[c];
        f += v -> ends;
    }
}


int main() {
    speed;
    cin >> n;
    string arr[n];
    for(int i = 0 ; i < n ; i++){
        cin >> arr[i];
        add(arr[i]);
    }
    sort(arr,arr + n);
    for(int i = n - 1; i >= 0; i--){
        dfs(arr[i]);
        dl = arr[i];
        del();
    }
    cout << f - n << "\n";
}

Решение бором

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

 
#include <bits/stdc++.h>
#define speed                   \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
#define oprecision    \
  cout.precision(30); \
  cerr.precision(7);
#define ll long long
#define ld long double
#define ss string
#define pii pair<int, int>
#define pll pair<ll, ll>
#define forn(n) for (int i = 1; i <= n; i++)
#define forlr(l, r) \
  for (int i = l; (l > r ? i >= r : i <= r); (l > r ? i-- : i++))
#define pb push_back
#define pc builtin_popcount
#define pcll builtin_popcountll
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
using namespace std;
int n, ans;
ss x[500005];
struct trie {
  trie *nxt[26];
  int end, sum;
  trie() {
    for (int i = 0; i < 26; i++) nxt[i] = nullptr;
    end = sum = 0;
  }
} *t = new trie();
void add(ss s) {
  trie *cnt = t;
  for (int i = 0; i < s.size(); i++) {
    int go = s[i] - 'a';
    if (cnt->nxt[go] == nullptr) cnt->nxt[go] = new trie();
    cnt = cnt->nxt[go];
  }
  cnt->end++;
}
void cnt(ss s) {
  trie *cnt = t;
  int sum = 0;
  for (int i = 0; i < s.size(); i++) {
    int go = s[i] - 'a';
    sum += cnt->end;
    cnt = cnt->nxt[go];
  }
  cnt->sum = sum;
}
void find(ss s) {
  trie *cnt = t;
  for (int i = 0; i < s.size(); i++) {
    int go = s[i] - 'a';
    cnt = cnt->nxt[go];
  }
  ans += cnt->sum + (--cnt->end);
}
int main() {
  speed;
  oprecision;
  // code
  cin >> n;
  forn(n) cin >> x[i], add(x[i]);
  forn(n) cnt(x[i]);
  forn(n) find(x[i]);
  cout << ans;
  // endl
#ifndef ONLINE_JUDGE
  cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

DELETED

Решение без бора

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

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>
using vvi = vt< vt<int> >

const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60), p = 31;
const double eps = 1e-6;

void solve () {
	int n;
	cin >> n;
	vt<string> s(n);
	for (string &i: s) cin >> i;
	sort(all(s));
	int ans = 0;
	map<string, int> used;
	for (string x: s) {
		string h = "";
		for (int i = 0; i < sz(x); i++) h += x[i], ans += used[h];
		used[x]++;
	}
	cout << ans;
	cout << '\n';
}

bool testcases = 0;
                  
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve();
    }
}