首先我作为一个蒟蒻，拿到字符串题，首先看看能不能无脑哈希
然后于是我们就发现了一个绝妙的做法：暴力枚举每个字符串能够转换成的字符串
于是我们就获得了O(N∗84)的优秀复杂度
显然会T飞QwQ
我们考虑再这个基础上进行优化
我们会发现如果我们O(84)枚举的话，其中有一大部分枚举出来的状态都是重复的
那么我们思考：这其中有多少个状态是有用的呢
首先我们假设我们将sa,sb交换，sc,sd互换（$a,b,c,d\in [1, 8] $, a=b=c=d）同时我们令$a < b $ 且 c<d
那么我们会发现最终只有C84∗3种可能是可行的
所以我们只需要把这些预处理出来，那么我们在后面枚举的时候只需要在这些状态中取就行了
最终复杂度O(N∗C84∗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
|
#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);
}
|
