KickStart 2018 Round A题解

Even Digits

题目链接

题目大意

给定一个数字n,找到相邻最近的所有元素由偶数构成的数字,如22099,则为22088。

思路

题目比较简单,找到一个比它大的数a及一个比它小的数b,比较差值即可。
其中,b可以通过找到最高元素为奇数的位,将其减1,并将之后所有低位全部赋值为8完成。
a则可以通过找到最高元素为奇数的位,将其加1,并将之后所有低位全部赋值为0完成,需要特别注意进位。
求解a的过程有一个优化点:如果需要进位(首个奇数位是9),(a-n) 一定大于 (n-b)。因为对于首字母为9的k位数,(a-n)一定大于(10^k+1),而(n-b)则不会大于(10^k+1)。

代码

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
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>

#define ull unsigned long long

using namespace std;

const int MAXN = 20;

ull toNumber(char *str) {
ull res = 0;
for (int i = strlen(str)-1; i >= 0; --i) {
res = res * 10 + (str[i] - '0');
}
return res;
}

char * toStr(ull n) {
char *str = new char[MAXN];
for (int i = 0; i < MAXN; ++i) str[i] = '0';
int len = 0;
while (n != 0) {
str[len++] = (n % 10) + '0';
n /= 10;
}
str[len] = '\0';
return str;
}

char * getLower(char *num) {
int len = strlen(num) - 1;
for (; len >= 0; --len) {
if ((num[len] - '0') & 1) {
num[len--]--;
break;
}
}
while (len >= 0) num[len--] = '8';
return num;
}

char *getUpper(char *num) {
// 有优化点,首位为9时可以直接返回INT_MAX
int p = strlen(num) - 1;
for (; p >= 0; --p) {
if ((num[p] - '0') & 1) {
for (int i = 0; i < p; ++i) num[i] = '0';
if (num[p] == '9') {
num[p]++;
num[p+1]++;
num[p+2] = '\0';
return getUpper(num);
}
num[p]++;
break;
}
}
return num;
}

ull solve(ull n) {
ull a = toNumber(getLower(toStr(n)));
ull b = toNumber(getUpper(toStr(n)));
return min(n-a, b-n);
}

int main(int argc, const char * argv[]) {

int T;
ull n;
scanf("%d", &T);
for (int kase = 1; kase <= T; ++kase) {
scanf("%ld", &n);
printf("Case #%d: %llu\n", kase, solve(n));
}

return 0;
}

Lucky Dip

题目链接

题目大意

袋子中有N个物品,每个物品值Vi元,现在选手从中取一个物品,共有k次放回机会。尽可能取出商品价值最大,求该数学期望。

思路

考虑一种放回策略,使得物品价值的期望最大,则可以考虑如下方案:
当本次取出商品价值大于之前几次期望时,保留,否则放回重新取。
即K次循环,每次将商品价格排序后,依据上次的数学期望划分成两部分,价格低于期望的使用期望价格(放回),高于的部分用于更新本次期望(保留)。
状态转移方程:exp[i] = (smaller_count * exp[i-1] + sum_of_larger) / N;
预先排序便于二分,并计算前缀和。

代码

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
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>

#define ll long long

using namespace std;

const int MAXN = 2e4+10;
int V[MAXN];

double solve(int N, int K) {
sort(V, V+N);
ll *sum = new ll[N+1];
sum[N] = 0;
for (int i = N-1; i >= 0; --i)
sum[i] = sum[i+1] + V[i];
double *exp = new double[K+1];
exp[0] = (double) sum[0] / N;
for (int i = 1; i <= K; ++i) {
int larger = upper_bound(V, V+N, exp[i-1]) - V;
exp[i] = (larger * exp[i-1] + sum[larger]) / N;
}
return exp[K];
}

int main(int argc, const char * argv[]) {
int T, N, K;

scanf("%d", &T);
for (int kase = 1; kase <= T; ++kase) {
scanf("%d %d", &N, &K);
for (int i = 0; i < N; ++i) {
scanf("%d", &V[i]);
}
printf("Case #%d: %.6lf\n", kase, solve(N, K));
}
return 0;
}

Scrambled Words

题目链接

题目大意

研表究明,汉字序顺并不定一影阅响读。事证实明了当你看这完句话之后才发字现都乱是的。
根据这一现象,Scrmable博士将一个单词的首尾字母保持不变,中间字母任意乱序,生成的单词成为Scrmable Word,现在我们认为原单词和Scrmable单词一样可以阅读。
现在给定一个字符串和一个单词数组,求单词数组中有多少个单词出现在字符串中(原单词和Scrmable单词均可)。

思路

首尾不变,中间字母顺序任意,则可以通过将单词哈希来匹配,哈希依据字母表中每个字母出现的次数。
统计每个单词的长度,遍历所有存在的单词长度,从头到尾依次枚举区间,当区间单词哈希存在匹配时则存在Scrmabled或Original Word,匹配后移除匹配的单词。

代码

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
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>

#define ll long long
#define ull unsigned long long

using namespace std;

const int HASH_SEED = 123;
const int MAXN = 1e5+10;
const int MAXM = 1e6+10;

int T, L, N, A, B, C, D;
char S1, S2;
char S[MAXM];
int numSeed[MAXM];
int alpha[26];

ull getHash(char start, char end, int alpha[]) {
ull res = start * HASH_SEED + end;
for (int i = 0; i < 26; ++i) {
res = res * HASH_SEED + alpha[i];
}
return res;
}

int solve() {
unordered_map<ull, int> hash;
int lenArr[MAXN];
char tmpStr[MAXN];
int totLen = 0;

scanf("%d", &L);
for (int i = 0; i < L; ++i) {
scanf("%s", tmpStr);
int len = strlen(tmpStr);
memset(alpha, 0, sizeof(alpha));
for (int j = 1; j < len-1; ++j)
alpha[tmpStr[j] - 'a']++;
hash[getHash(tmpStr[0], tmpStr[len-1], alpha)]++;
lenArr[totLen++] = len;
}
sort(lenArr, lenArr+totLen);
totLen = unique(lenArr, lenArr+totLen) - lenArr;
getchar();
scanf("%c %c %d %d %d %d %d", &S1, &S2, &N, &A, &B, &C, &D);

numSeed[0] = S[0] = S1;
numSeed[1] = S[1] = S2;
for (int i = 2; i < N; ++i) {
numSeed[i] = ((ll) A * numSeed[i-1] + (ll) B * numSeed[i-2] + (ll) C) % (ll) D;
S[i] = (char) (numSeed[i] % 26 + 97);
}
S[N] = '\0';

int res = 0;
ull substrHash;
for (int i = 0; i < totLen; ++i) {
int len = lenArr[i];
if (len > N) continue;
memset(alpha, 0, sizeof(alpha));
for (int j = 1; j < len-1; ++j)
alpha[S[j] - 'a']++;
substrHash = getHash(S[0], S[len-1], alpha);
if (hash.count(substrHash)) {
res += hash[substrHash];
hash.erase(substrHash);
}
for (int j = len; j < N; ++j) {
++alpha[S[j - 1] -'a'];
--alpha[S[j - len + 1] - 'a'];
substrHash = getHash(S[j-len+1], S[j], alpha);
if (hash.count(substrHash)) {
res += hash[substrHash];
hash.erase(substrHash);
}
}
}
return res;
}

int main(int argc, const char * argv[]) {
scanf("%d", &T);
for (int kase = 1; kase <= T; ++kase) {
printf("Case #%d: %d\n", kase, solve());
}
return 0;
}