算法
(枚举、数据结构) $O(N\log N)$
只需在这 $N$ 个字符串中找两个字符串,它们之间只相差一个 !
,暴力做法是 $O(N^2)$
下面考虑如何优化:
我们可以开两个 std::set
,分别记为 $s$ 和 $t$,其中 $s$ 用来维护所有不带 !
的字符串,$t$ 用来维护带 !
的字符串。然后扫描一遍 $s$,检验其中每个元素加上 !
后是否在 $t$ 中。总的计算量为 $O(N\log N)$
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::set;
using std::string;
int main() {
int n;
cin >> n;
set<string> s, t;
rep(i, n) {
string a;
cin >> a;
if (a[0] == '!') t.insert(a);
else s.insert(a);
}
for (string a : s) {
if (t.count("!" + a)) {
cout << a << '\n';
return 0;
}
}
cout << "satisfiable\n";
return 0;
}