2016 百度之星资格赛(Astar Round 1)

最近不知道要刷什么题,刚好看到前几天的“百度之星”资格赛,便跑去做完了。

本文是2016年“百度之星”资格赛(Astar Round 1)所有题目的解题报告。

Problem A

题目大意

给定一个大字符串。有 $N$ 次询问,每次询问子串 $[L,R]$ 的哈希值 $H(s)$。
一个字符串的哈希值定义为:$H(s)=\prod_{i=1}^{i\leq len(s)}(s_{i}-28)\ (mod\ 9973)$。
$(1 \le N \le 1000$,$1 \le len(string) \le 10^5$,$1 \le L,R \le len(string))$

解题思路

预处理前缀+乘法逆元

何谓乘法逆元?简单来讲,就是可以将除法取模转化为乘法:
$(X \div Y)(mod\ P) = (X \times Y^{p-2})(mod\ P)$(当且仅当$P$为素数)

知道这个再预处理下前缀就做完了。

解题代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MOD = 9973;

char s[MAXN];
int H[MAXN];

int fast_pow(int x, int n)
{

int res = 1;
while( n ) {
if( n & 1 ) res = res * x % MOD;
x = x * x % MOD;
n >>= 1;
}
return res;
}
int main()
{

int n;
while( ~scanf("%d", &n) ) {
scanf("%s", s + 1);
int len = strlen(s + 1);
H[0] = 1;
for( int i = 1; i <= len; ++ i ) {
H[i] = ((H[i - 1] * (s[i] - 28)) % MOD + MOD) % MOD;
}
int a, b;
while( n-- ) {
scanf("%d %d", &a, &b);
printf("%d\n", H[b] * fast_pow(H[a - 1], MOD - 2) % MOD);
}
}

return 0;
}


Problem B

题目大意

给定一个全1序列。你可以合并任意相邻的两个1(只能是1),从而形成一个新的序列$(11->2)$,请计算根据以上方法,可以构成多少种不同的序列。题目输入一个 $N$,代表全1序列的长度,要求输出所能形成的新序列的数量。
$(1 \le N \le 200)$

解题思路

递推+大数

设 $dp[i]$ 表示长度为 $i$ 的全1序列所能形成的新序列的数量。

很容易算出 $dp[i] = dp[i - 1] + dp[i - 2]$。由于 $N$ 较大,本题需要用到大数。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.*;
import java.math.*;

public class Main {
final static int MAXN = 200 + 10;
public static void main(String[] args) {
BigInteger[] f = new BigInteger[MAXN];
f[1] = BigInteger.ONE;
f[2] = BigInteger.valueOf(2);
for( int i = 3; i < MAXN; ++ i ) {
f[i] = f[i - 1].add(f[i - 2]);
}
Scanner cin = new Scanner(System.in);
while( cin.hasNext() ) {
int n = cin.nextInt();
System.out.println(f[n]);
}
cin.close();
}
};


Problem C

题目大意

度熊手上有一本神奇的字典,你可以在它里面做如下三个操作:

  • $insert$ : 往神奇字典中插入一个单词
  • $delete$ : 在神奇字典中删除所有前缀等于给定字符串的单词
  • $search$ : 查询是否在神奇字典中有一个字符串的前缀等于给定的字符串

现共有 $N$ 次操作,题目要求对于每一个 $search$ 操作,如果在度熊的字典中存在给定的字符串为前缀的单词,则输出 $Yes$ 否则输出 $No$。
$(1 \le N \le 10^5)$

解题思路

字典树

理解题意后不难想到要用字典树,然后一开始对 $delete$ 操作我的想法是只让该点的儿子数组清空,这样对于 $search$ 操作由于其无法从该点继续往下走来实现删除功能。然而这样是有问题的,考虑这样几组操作:

3
insert helloworld
delete hellow
search hello

若按刚才所说只让该点的儿子数组清空,那么对于 $seach$ 操作将会输出 $Yes$,因为字典树可以走到 $o$ 结点,但是事实上从 $o$ 点出发的单词已经不存在了。因此可以在每个结点记录从该点出发的单词数量,维护下就可以了。

解题代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MAXM = 26 + 10;

struct Trie {
int cnt, sz[MAXN * 30][MAXM], num[MAXN * 30];
void init() {
cnt = 0;
memset(sz[0], 0, sizeof(sz[0]));
memset(num, 0, sizeof(num));
}

void insert(char *s) {
int len = strlen(s), now = 0;
for( int i = 0; i < len; ++ i ) {
if( !sz[now][s[i] - 'a'] ) {
sz[now][s[i] - 'a'] = ++cnt;
memset(sz[cnt], 0, sizeof(sz[cnt]));
}
num[now]++;
now = sz[now][s[i] - 'a'];
}
num[now]++;
}

void del(char *s) {
int len = strlen(s), now = 0;
for( int i = 0; i < len; ++ i ) {
if( !sz[now][s[i] - 'a'] ) return ;
now = sz[now][s[i] - 'a'];
}
memset(sz[now], 0, sizeof(sz[now]));
int m = num[now];
num[now] = 0;
now = 0;
for( int i = 0; i < len; ++ i ) {
num[now] -= m;
now = sz[now][s[i] - 'a'];
}
}

bool search(char *s) {
int len = strlen(s), now = 0;
for( int i = 0; i < len; ++ i ) {
if( !sz[now][s[i] - 'a'] ) return false;
now = sz[now][s[i] - 'a'];
}
return num[now];
}
} T;
int main()
{

int n;
while( ~scanf("%d", &n) ) {
char op[10], s[50];
T.init();
for( int i = 0; i < n; ++ i ) {
scanf("%s %s", op, s);
if( op[0] == 'i' ) {
T.insert(s);
}
else if( op[0] == 'd' ) {
T.del(s);
}
else if( op[0] == 's' ) {
printf("%s\n", T.search(s) ? "Yes" : "No");
}
}
}
return 0;
}


Problem D

题目大意

题目规定字符串的所有全排列属于同个字符串。现给定 $N$ 个字符串,对于每个字符串输出前面出现过多少个相同的字符串。
$(1 \le N \le 10^5)$

解题思路

map / hash

将每个字符串按字典序排序再哈希一下,统计次数就可以了。

解题代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

map<string, int> mp;

int main()
{

int n;
while( ~scanf("%d", &n) ) {
mp.clear();
char s[50];
for( int i = 0; i < n; ++ i ) {
scanf("%s", s);
sort(s, s + strlen(s));
printf("%d\n", mp[s]);
mp[s]++;
}
}
return 0;
}


Problem E

题目大意

给定 $N$ 个条件,条件可能是一个『简单条件』或者是一个『复合条件』。简单条件由『变量』、『比较符』和『运算数』组成,其中『变量』是用小写字符表示的一串字符(不同变量数量不会超过30个),『运算数』仅为整数,『运算符』包括:<、>、<=、>=、==。若干个『简单条件』中间通过英文逗号组成一个『复合条件』,各『简单条件』之间是逻辑与的关系。

题目要求对于第 $i$ 个条件,输出其与前 $i−1$ 个条件是否存在交集非空的情况。如果不存在交集非空的其他条件,输出一行字符串:『unique』。否则按照从小到大的顺序输出与其存在非空交集的条件的编号。
$(1 \le N \le 1000)$

解题思路

逻辑题(?)。

个人感觉本题的难度主要是要看懂题目…题目的交集为空指的是两个条件相互矛盾。明白题意之后稍微理一下关系其实是很好写的。且题目 $N$ 只有 $1000$,不同变量的数量也不会超过30个,直接暴力 $O(N^2)$ 就可以了: 对于每个条件先看其本身是否矛盾,若不矛盾则存储该条件中所有变量的范围,然后与前面的条件 $check$ 下。

解题代码

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
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e3 + 10;
const int INF = 0x3f3f3f3f;

int m, ans[MAXN];
map<string, int> mp;

struct Con {
int L[MAXN], R[MAXN];
bool isValid;

void init() {
for( int i = 1; i <= 30; ++ i ) {
L[i] = -INF;
R[i] = +INF;
}
isValid = true;
}

void insert(char *s, char *op, int num) {
if( !isValid ) return ;
if( !mp[s] ) mp[s] = ++m;
if( op[0] == '>' ) {
if( op[1] == 0 ) L[mp[s]] = max(num + 1, L[mp[s]]);
else L[mp[s]] = max(num, L[mp[s]]);
}
else if( op[0] == '=' ) {
if( L[mp[s]] > num || R[mp[s]] < num ) isValid = false;
L[mp[s]] = R[mp[s]] = num;
}
else {
if( op[1] == 0 ) R[mp[s]] = min(num - 1, R[mp[s]]);
else R[mp[s]] = min(num, R[mp[s]]);
}
if( L[mp[s]] > R[mp[s]] ) isValid = false;
}

} G[MAXN];

int main()
{

int n;
scanf("%d", &n);
for( int i = 0; i < n; ++ i ) {
G[i].init();
char s[30], op[10];
int num;
scanf(" %[a-z] %[>=<] %d", s, op, &num);
G[i].insert(s, op, num);
while( scanf(" , %[a-z] %[>=<] %d", s, op, &num) > 0 ) {
G[i].insert(s, op, num);
}
if( !G[i].isValid ) {
puts("unique");
continue;
}
int cnt = 0;
for( int j = 0; j < i; ++ j ) {
if( !G[j].isValid ) continue;
bool isUnite = true;
for( int k = 1; k <= 30; ++ k ) {
if( G[i].L[k] > G[j].R[k] || G[i].R[k] < G[j].L[k] ) isUnite = false;
}
if( isUnite ) ans[cnt++] = j + 1;
}
for( int j = 0; j < cnt; ++ j ) {
printf("%d%c", ans[j], " \n"[j == cnt - 1]);
}
if( !cnt ) puts("unique");
}
return 0;
}
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!