首先我作为一个蒟蒻,拿到字符串题,首先看看能不能无脑哈希

然后于是我们就发现了一个绝妙的做法:暴力枚举每个字符串能够转换成的字符串

于是我们就获得了$O(N * 8^4)$的优秀复杂度

显然会T飞QwQ

我们考虑再这个基础上进行优化

我们会发现如果我们$O(8^4)$枚举的话,其中有一大部分枚举出来的状态都是重复的

那么我们思考:这其中有多少个状态是有用的呢

首先我们假设我们将$s_a, s_b$交换,$s_c, s_d$互换($a,b,c,d\in [1, 8] $, $a \neq b \neq c \neq d$)同时我们令$a < b $ 且 $c < d$

那么我们会发现最终只有$C_8^4 * 3$种可能是可行的

所以我们只需要把这些预处理出来,那么我们在后面枚举的时候只需要在这些状态中取就行了

最终复杂度$O(N * C_8^4 * 3 * 8)$,(最后的8是Hash的复杂度)佐以优秀的常数便可AC此题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
// Sooke bless me.
// LJC00118 bless me.
#include<bits/stdc++.h>

using namespace std;

#define INF 2147483647
#define ll long long

int Inp(){
char c = getchar();
register int Neg = 1;
while(c < '0' || c > '9'){
if(c == '-')
Neg = -1;
c = getchar();
}
register int Sum = 0;
while(c >= '0' && c <= '9'){
Sum = ((Sum << 3) + (Sum << 1)) + c - '0';
c = getchar();
}
return Neg * Sum;
}

string s[10010];
bool Used[20];

bool cg[10000000];

inline int Hash(string s){
int Sum = 0;
for(int i = 0; i < 8; i++){
Sum <<= 2;
switch(s[i]){
case 'A':{
Sum += 1;
break;
}
case 'C':{
Sum += 2;
break;
}
case 'T':{
Sum += 3;
break;
}
}
}
return Sum;
}

int Hsh[10000];
int sa[1010];
int sb[1010];
int C_swap;

int main(){
register int n = Inp();
for(register int i = 1; i <= n; i++)
cin >> s[i], Hsh[i] = Hash(s[i]);
for(register int j1 = 0; j1 < 8; j1++){
Used[j1] = true;
for(register int j2 = j1 + 1; j2 < 8; j2++){
if(Used[j2])
continue;
Used[j2] = true;
sa[++C_swap] = j1;
sb[C_swap] = j2;
Used[j2] = false;
}
Used[j1] = false;
}
register int Ans = 0;
for(register int i = 1; i <= n; i++){

for(int j = 1; j <= C_swap; j++)
for(int u = j + 1; u <= C_swap; u++){
if(sa[j] == sa[u] || sb[j] == sb[u] || sa[j] == sb[u] || sb[j] == sa[u])
continue;
string s2 = s[i];
swap(s2[sa[j]], s2[sb[j]]);
swap(s2[sa[u]], s2[sb[u]]);
cg[Hash(s2)] = true;
}
for(register int j = i + 1; j <= n; j++)
if(cg[Hsh[j]])
Ans++, cg[Hsh[j]] = false;
}
printf("%d", Ans);
}

 评论