Trie全WA求调
  • 板块P5149 会议座位
  • 楼主qfpjm
  • 当前回复0
  • 已保存回复0
  • 发布时间2021/8/13 09:34
  • 上次更新2023/11/4 10:50:34
查看原帖
Trie全WA求调
342868
qfpjm楼主2021/8/13 09:34
#include <bits/stdc++.h>

using namespace std;

class TrieNode 
{
public:
	map<char, TrieNode* > childrens;
    string word;
	bool is_word = false;
	int leftl, leftr;
};

class Trie
{
public:
    TrieNode* root = new TrieNode;
    void add(string word, int s, int e)
	{
        TrieNode* p = root;
        for (int i = 0 ; i < word.size() ; i ++)
        {
            map<char, TrieNode* >::iterator it;
            it = p ->childrens.find(word[i]);
            if (it == p ->childrens.end())
            {
                p ->childrens[word[i]] = new TrieNode;
            }
            p = p ->childrens[word[i]];
        }
        p ->is_word = true;
        p ->word = word;
        p ->leftl = s;
        p ->leftr = e;
    }
    int find(string word, int s, int e, string str[])
    {
        TrieNode* p = root;
        for (int i = 0 ; i < word.size() ; i ++)
        {
            p = p ->childrens[word[i]];
        }
        map<string, int> vis;
        for (int i = s ; i <= e ; i ++)
        {
        	vis[str[i]] ++;
		}
        for (int i = p ->leftl ; i <= p ->leftr ; i ++)
        {
        	vis[str[i]] ++;
		}
		map<string, int> :: reverse_iterator iter;
		int cnt = 0;
		for(iter = vis.rbegin() ; iter != vis.rend() ; iter++)
		{
          	if (iter ->second != 2)
          	{
          		cnt ++;
			}
     	}
    	return cnt;
    }
};

int n, m, ans;
string str[100005];

int main()
{
    cin >> n;
    Trie trie;
    for (int i = 1 ; i <= n ; i ++)
    {
        cin >> str[i];
    }
    for (int i = 1 ; i <= n ; i ++)
    {
        trie.add(str[i], 1, i - 1);
	}
    for (int i = 1 ; i <= n ; i ++)
    {
        string s;
        cin >> s;
        ans += trie.find(s, 1, i - 1, str);
    }
    cout << ans;
    return 0;
}
2021/8/13 09:34
加载中...