山东省第九届acm大学程序设计竞赛山师选拔赛第二场
(声明：标题是自己取的，如果有语法错误的话与他人无关)
—————————————————————–分割线—————————————————————–
Problem A. Alice and Bob(NimK博弈)
题意：
有N堆石子，每次可以取1~M堆中的任意多个石子，最后无石子可取的那个失败。Alice先手，问谁会赢。
思路：
NimK博弈裸题，结论是当且仅当每一位二进制位上的数%(m+1)都是0的时候，先手必败，否则先手必胜。见识++。
原理留坑待补。
Mycode：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
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int tem, tot;
int u[MAX][55];
int t, res, a, b, n, m;
int main()
{
scanf("%d",&t);
for(int cas = 1; cas <= t; ++cas)
{
memset(u, 0, sizeof(u));
scanf("%d%d",&n,&m);
for(int i = 0; i < n; ++i)
{
scanf("%d",&tem);
tot = 0;
while(tem)
{
u[i][tot++] = tem & 1;
tem >>= 1;
}
}
bool flag = true;
for(int j = 0; j < 32; ++j)
{
int yy = 0;
for(int i = 0; i < n; ++i)
{
yy += u[i][j];
}
if(yy % (m+1))
{
flag = false;
break;
}
}
printf("Case #%d: ", cas);
puts(flag ? "Bob" : "Alice");
}
return 0;
}
Problem B. SOS(基础)
题意：
已知gcd(a, c) = b， 给出a和b求满足条件的最小的不等于b的c。
思路：
对式子变形得，gcd(a/b, c/b) = 1， 即求最小的与a/b互质的数。
(之前做过一道一模一样的题SDNU-1132: 最大公约数改，枚举答案也能水过啦)
Mycode：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
using namespace std;
typedef long long LL;
const int MAX = 1e6+7;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int t, res, a, b;
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
int main()
{
scanf("%d",&t);
for(int cas = 1; cas <= t; ++cas)
{
scanf("%d%d",&a,&b);
a /= b;
for(int i = 2; ; ++i)
{
if(gcd(a, i) == 1)
{
res = i;
break;
}
}
printf("Case #%d: %d\n", cas, res * b);
}
return 0;
}
Problem C. Boooooooo(规律)
题意：
给出一个数N，找出最小的大于等于N的整数pp，其中pp满足存在整数hh使得2hh(hh + 1) = pp(pp + 1)。
思路：
打表找规律。(找不出来怎么办？GG呗)
Mycode：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
using namespace std;
typedef long long LL;
int t;
long long n, res;
long long a[30] = {3,20};
int main()
{
for(int i = 2; i < 25; ++i)
{
a[i] = 6 * a[i-1] - a[i-2] + 2;
//cout << a[i] << endl;
}
scanf("%d",&t);
for(int cas = 1; cas <= t; ++cas)
{
scanf("%lld", &n);
for(int i = 0; ; ++i)
{
if(a[i] >= n)
{
printf("Case #%d: %lld\n", cas, a[i]);
break;
}
}
}
return 0;
}
Problem D. XC’s pot(期望)
题目原型：
LightOJ-1027: A Dangerous Maze
Problem E. SDNU ACM/ICPC TEAM(拓扑排序)
题意不清，不如做这个吧：HDU-4857: 逃生
Problem F. The Avengers(最小生成树)
队友补了，目前不想补。
Problem G. play the guitar(大数)
题意：
Calculate $n^k$ and change all 7,8,9 to 1,2,3(7 to 1, 8 to 2, 9 to 3).
思路：
开上Java直接做。
Mycode：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
28import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scanner = new Scanner(System.in);
int n, m;
BigInteger res;
String s;
while(scanner.hasNext())
{
n = scanner.nextInt();
m = scanner.nextInt();
res = BigInteger.valueOf(1);
for(int i = 1; i <= m; ++i)
{
res = res.multiply(BigInteger.valueOf(n));
}
s = res.toString();
s = s.replace('7','1');
s = s.replace('8','2');
s = s.replace('9','3');
System.out.println(s);
}
}
}
Problem H. The chord(最长公共子串)
题意：
所有和弦中，伟大的歌手LHM只会其中的部分和弦，给出一个包含很多和弦的吉他谱，问LMH能弹奏的连续的最长的一段乐曲包含多少和弦。
思路：
先将不同字符串转换，然后计算转换后的两个串的最长公共子串(套后缀数组的模板)。
(转换时当然想到map，然而套各种模板都会超时，因此只好写个100+行的函数来转换。这个题目的idea还是不错的。)
Mycode：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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
using namespace std;
const int N = 200000 + 10, INF = 0x3f3f3f3f;
const char trans[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r'};
int sa[N], height[N], rnk[N], wa[N], wb[N], c[N];
char str[N], S[N];
int s[N], Q;
bool cmp(int *r, int a, int b, int l)
{
return r[a] == r[b] && r[a+l] == r[b+l];
}
void Rsort(int *x, int *y, int n, int m)
{
for(int i = 0; i < m; i++)
c[i] = 0;
for(int i = 0; i < n; i++)
c[x[y[i]]]++;
for(int i = 1; i < m; i++)
c[i] += c[i-1];
for(int i = n-1; i >= 0; i--)
sa[--c[x[y[i]]]] = y[i];
}
void da(int *s, int n, int m)
{
int *x = wa, *y = wb;
for(int i = 0; i < n; i++)
x[i] = s[i], y[i] = i;
Rsort(x, y, n, m);
for(int j = 1, p = 1; p < n; j *= 2, m = p)
{
p = 0;
for(int i = n-j; i < n; i++)
y[p++] = i;
for(int i = 0; i < n; i++)
if(sa[i] >= j)
y[p++] = sa[i] - j;
Rsort(x, y, n, m);
swap(x, y);
p = 1;
x[sa[0]] = 0;
for(int i = 1; i < n; i++)
x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1 : p++;
}
}
void get_height(int *s, int n)
{
int i, j, k = 0;
for(i = 0; i <= n; i++)
rnk[sa[i]] = i;
for(i = 0; i < n; height[rnk[i++]] = k)
for(k ? --k : 0, j = sa[rnk[i]-1]; s[i+k] == s[j+k]; k++);
}
int change(int L)
{
int res = 0;
for(int i = 0; i < L; ++i)
{
if(str[i] == 'A')
{
if(str[i+1] == '7')
{
s[res++] = trans[1];
++i;
}
else if(str[i+1] == 'm')
{
s[res++] = trans[2];
++i;
}
else if(str[i+1] == 's')
{
s[res++] = trans[3];
i += 4;
}
else
s[res++] = trans[0];
}
else if(str[i] == 'B')
{
if(str[i+1] == '7')
s[res++] = trans[4];
else
s[res++] = trans[5];
++i;
}
else if(str[i] == 'C')
{
if(str[i+1] == '7')
{
s[res++] = trans[7];
++i;
}
else
s[res++] = trans[6];
}
else if(str[i] == 'D')
{
if(str[i+1] == '7')
{
s[res++] = trans[9];
++i;
}
else if(str[i+1] == 'm')
{
if(str[i+2] == '7')
{
s[res++] = trans[10];
i += 2;
}
else
{
s[res++] = trans[11];
i++;
}
}
else
s[res++] = trans[8];
}
else if(str[i] == 'E')
{
if(str[i+1] == 'm')
{
s[res++] = trans[13];
++i;
}
else
s[res++] = trans[12];
}
else if(str[i] == 'F')
{
if(str[i+1] == 'm')
{
s[res++] = trans[14];
i += 4;
}
else
s[res++] = trans[15];
}
else if(str[i] == 'G')
{
if(str[i+1] == '7')
{
s[res++] = trans[16];
i++;
}
else
s[res++] = trans[17];
}
else
{
Q = res;
s[res++] = '$';
}
}
return res;
}
int main()
{
while(~scanf("%s", str))
{
int len = strlen(str);
str[len] = '$';
scanf("%s", str + 1 + len);
len = strlen(str);
len = change(len);
s[len] = 0;
int len_1 = Q;
da(s, len + 1, 130);//第二个参数，即长度比原数组大一，因为在末尾补了一个极小值，故+1
get_height(s, len);//此处传入原长度
int ans = 0;
for(int i = 1; i <= len; i++)//height[1]~height[len]，因为sa[0]是以极小值为起点的后缀，然后sa[1]~sa[len]，故height[1]~height[len]
if(height[i] > ans && ((sa[i-1]<len_1 && sa[i]>len_1) || (sa[i-1]>len_1 && sa[i]<len_1)))
ans = height[i];
printf("%d\n", ans);
}
return 0;
}
Problem I. Alice and Bob II(记忆化搜索)
题意：
N堆石子，Alice先手，每次两人都可以从石子的两端取任意一堆，问Alice最多能取多少石子。
思路：
我觉得题目中这句they both smart不应该有，不然给出的正解讲不通。去掉这句话的话就是看Alice能取的石子最大值了。使Alice取最多即每次Alice往多了取，Bob往小了取。最多100堆，枚举每个状态的话肯定不能完成。采取记忆化搜索可以保留左右位置为l、r时的最优解，大大减少时间复杂度，任务完成。
Mycode：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
using namespace std;
typedef long long LL;
const int MAX = 105;
int a[MAX];
int n, res, t;
int dp[MAX][MAX];
int DFS(int l, int r, bool flag)
{
if(dp[l][r])
return dp[l][r];
int res = 0;
if(flag)
{
if(l == r)
return a[l];
res = max(DFS(l+1, r, !flag) + a[l], DFS(l, r-1, !flag) + a[r]);
}
else
{
if(l == r)
return 0;
res = min(DFS(l+1, r, !flag), DFS(l, r-1, !flag));
}
dp[l][r] = res;
return res;
}
int main()
{
scanf("%d",&t);
for(int cas = 1; cas <= t; ++cas)
{
scanf("%d",&n);
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; ++i)
scanf("%d",&a[i]);
int ans = DFS(1, n, true);
printf("Case #%d: %d\n", cas, ans);
}
return 0;
}
