codeforces 514C Watto and Mechanism (分段暴力)

codeforces 514C Watto and Mechanism (分段暴力)

题意：
给出一个包含n个单词的字典，给出m个待查询单词，如果单词在有且仅有一个字符不相同的情况下可以在字典里找到，则输出YES，否则输出NO
限制：
0 <= n,m <= 3*10^5; 总字符长度不大于6*10^5
思路：
分段暴力。
以查询单词长度为500分段：
查询单词长度<500则：采用set查询，复杂度为600*500*500=1.5*10^8
查询单词长度>500则：暴力查询，复杂度为600*600*500=1.8*10^8
在复杂度内可以实现。
其实这道题，还有trie树的做法和哈希的做法，不过哈希太看人品了。

/*codeforces 514C Watto and Mechanism
题意：
给出一个包含n个单词的字典，给出m个待查询单词，如果单词在有且仅有一个字符不相同的情况下可以在字典里找到，则输出YES，否则输出NO
限制：
0 <= n,m <= 3*10^5; 总字符长度不大于6*10^5
思路：
分段暴力。
以查询单词长度为500分段：
查询单词长度<500则：采用set查询，复杂度为600*500*500=1.5*10^8
查询单词长度>500则：暴力查询，复杂度为600*600*500=1.8*10^8
在复杂度内可以实现。
*/
#include
#include
#include
#include
#include
using namespace std; using namespace std::tr1; unordered_set
_set; unordered_set
::iterator it; int main(){ double st=clock(),en; ios_base::sync_with_stdio(false); int n,m; string str; cin>>n>>m; int maxl=0; for(int i=0;i
>str; _set.insert(str); } for(int i=0;i
>str; bool flag=false; if(str.length()>500){ for(it=_set.begin();it!=_set.end();++it){ if(it->length()==str.length()){ int cnt=0; for(int i=0;i
1) break; } } if(cnt==1){ flag=true; break; } } } } else for(int j=0;j

最后

以上就是积极猫咪最近收集整理的关于codeforces 514C Watto and Mechanism (分段暴力)的全部内容，更多相关codeforces内容请搜索靠谱客的其他文章。