八段第八课字符串算法总结
A T恤分配
解法
这道题好像是到二分图。
直接连每个人能选的码数，然后二分图模板即可。
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 2000;
int h[N],e[N],ne[N],idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
string s;
int x,a[22];
string sz[22];
int k[6][22];
map<char,int> mp;
int pi[N];
bool m[N];
bool find(int u)
{
for(int i=h[u];i!=-1;i=ne[i])
{
if(!m[e[i]])
{
m[e[i]]=1;
if(pi[e[i]]==0 || find(pi[e[i]]))
{
pi[e[i]]=u;
pi[u]=e[i];
return true;
}
}
}
return false;
}
int main()
{
mp['S']=1;
mp['M']=2;
mp['L']=3;
mp['X']=4;
mp['T']=5;
cin>>s>>x;
int sum=0;
for(int i=1;i<=x;i++) cin>>sz[i];
int cnt=x;
for(int i=1;i<=5;i++)
{
cin>>a[i];sum+=a[i];
for(int j=1;j<=a[i];j++) k[i][j]=++cnt;
}
if(sum<x)
{
puts("NO");
return 0;
}
memset(h,-1,sizeof h);
for(int i=1;i<=x;i++)
{
for(int j=mp[sz[i][0]];j<=mp[sz[i][1]];j++)
{
for(int l=1;l<=a[j];l++) add(i,k[j][l]),add(k[j][l],i);
}
}
cin>>s;
int ans=0;
for(int i=1;i<=x;i++)
{
memset(m,false,sizeof m);
if(find(i)) ans++;
}
if(ans<x) puts("NO");
else puts("YES");
}
|
B 单词博弈
解法
我们可以构建一棵 $trie$ 树，然后从叶子节点开始，假设当前已经选到了当前节点，轮到先手走，看是否有必胜，必败策略。
假设先手有必败和必胜策略，先手就可以一直败以保持自己的先手地位，然后再最后一局赢。
假设先手只有必胜策略，那么先手和后手一直会调换位置，就看局数是否为奇数。
否则一定是后手赢。
代码
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 1000010;
int trie[N][26],idx=1;
int ts[N],w[N],l[N];
void insert()
{
string s;
cin>>s;
int t=s.size();
int p=0;
for(int i=0;i<t;i++)
{
if(trie[p][s[i]-'a']==0)
{
ts[p]=1;
trie[p][s[i]-'a']=idx;
idx++;
}
p=trie[p][s[i]-'a'];
}
}
int n;
int dfs1(int u)
{
if(!ts[u]) return w[u]=0;
for(int i=0;i<26;i++)
{
if(trie[u][i] && !dfs1(trie[u][i])) return w[u]=1;
}
return w[u]=0;
}
int dfs2(int u)
{
if(!ts[u]) return l[u]=1;
for(int i=0;i<26;i++)
{
if(trie[u][i] && !dfs2(trie[u][i])) return l[u]=1;
}
return l[u]=0;
}
int k;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) insert();
dfs1(0);
dfs2(0);
if(l[0] && w[0]) puts("First");
else if(w[0] && k&1) puts("First");
else puts("Second");
}
|
F 三个好朋友
解法
首先讲讲字符串哈希。
我们可以把整个字符串变成一个 $p$ 进制的数，比如 AAB ，那么他的哈希值就是 $A \times p^2 + A\times p^1 + B\times p^0$。
而假设我们要求字符串 $l-r$ 范围内的值：
首先，$h_l$ 的值的位数和 $h_r$ 的位数不相等，所以我们需要将其乘上 $p^{r-l+1}$，这就好比说前面的字符串假设为十进制，哈希值为 $123$，而后面的哈希值为 $123456$，那么我们需要先给前面的成上 $10^3$，将其变成 $123000$，再与后面相减得到 $456$，就得到了我们要求的那段区间。
那么回到这道题，我们可以直接枚举加入的字符可能的位置，然后通过以上公式求出剩下的两半哈希值是否相等就行了。
代码
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
| #include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2000010;
const int p = 99;
int h[N];
char s[N];
int pw[N];
int n;
int get_hash(int l,int r)
{
return h[r]-h[l-1]*(pw[r-l+1]);
}
map<int,int> mp;
signed main()
{
scanf("%s",s+1);
pw[0]=1;
n=strlen(s+1);
if(n%2==0)
{
puts("NOT POSSIBLE");
return 0;
}
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*p;
for(int i=1;i<=n;i++) h[i]=h[i-1]*p+s[i];
int cnt=0;
int l=0,r=0;
for(int i=1;i<=n;i++)
{
if(i==n/2+1)
{
if(get_hash(1,n/2)==get_hash(n/2+1,n)) 那么两遍均匀分成两半
{
mp[get_hash(n/2+1,n)]++;
if(mp[get_hash(n/2+1,n)]==1) cnt++;
l=1,r=n/2;
}
}
else if(i<=n/2)
{
if(get_hash(1,i-1)*pw[n/2+1-i]+get_hash(i+1,n/2+1)==get_hash(n/2+2,n))
{
mp[get_hash(n/2+2,n)]++;
if(mp[get_hash(n/2+2,n)]==1) cnt++;
l=n/2+2,r=n;
}
}
else if(i>n/2+1)
{
if(get_hash(1,n/2)==get_hash(n/2+1,i-1)*pw[n-i]+get_hash(i+1,n))
{
mp[get_hash(1,n/2)]++;
if(mp[get_hash(1,n/2)]==1) cnt++;
l=1,r=n/2;
}
}
}
if(cnt==0) puts("NOT POSSIBLE");
else if(cnt>1) puts("NOT UNIQUE");
else for(int i=l;i<=r;i++) cout<<s[i];
}
|
