上篇文章中，我们介绍了Kick Start中一道简单的交互式问题——Number Gussing作为入门引导，这是2019年的Round A中的问题，相信大家对于题目已经有了一定的了解。接下来的这篇文章我们将会介绍一下2018年Round A的三道题，希望大家通过文章能够熟悉Kick Start的题目。
2018年Round A中包含三道题目，分别为23分，29分和48分，总分达到51分即可通过比赛。下面详细介绍每道题目。
Problem A: Even Didits
题目描述
已知一个正整数N，每次对数字进行加一或者减一，使得数字N的十进制中不存在奇数，求最少要操作多少次。
示例：
42=>0 11=>3 1=>1 2018=>2
数据集及得分
小数据的取值范围为1<=N<=10^5，分值为8分，大数据集的取值范围为1<=N<=10^16，分值为15分。
答题思路
对于小数据集我们就用简单的暴力解法即可通过，即每次对数字进行加一或者减一，判断操作后的数字是否已经符合要求。示例代码如下：
public static int getAns(int N){
for(int i=0;;i++){
if(check(N-i) || check(N+i)){
return i;
}
}
}
public static boolean check(int i){
int x;
while (i > 0){
x = i % 10;
i = i / 10;
if(x % 2 == 1){
return false;
}
}
return true;
}
然而大数据集的范围为1<=N<=10^16，显然采用上述算法对于大数据集而言会超时。所以，我们需要再重新分析一下。对于一个正整数N，我们要将它变为没有奇数的形式其实并不需要依次加一或减一，我们可以直接构造出来，那么构造的结果与正整数N的差的绝对值即为运算步骤。所以问题就在于如何构造这样一个数。
因为有加减两种运算，所以我们可以构造出两个数，一个是利用加运算求得的比正整数N大的最小数，一个是利用减运算求得的比正整数N小的最大数。
那么对于比正整数N小的最大数的构造很简单，就从正整数N左端开始找奇数，遇到奇数将其减1，然后将之后的所有数位置8即可，如示例：
2234424=>2228888 12422886=>08888888 246202=>246202
对于比正整数N大的最小数的构造也类似，就从正整数N左端开始找奇数，遇到奇数将其加1，然后将之后的所有数位置0即可.需要注意的是，当奇数为9时，需要进位，但是不能进1位（因为会破环奇数位之前的偶数性质），对于之前的数字全是8的还需要增加数位，如示例：
2234424=>2240000 12422886=>20000000 20470=>20480 4249231=>4260000 4289231=>4400000 8889231=>20000000
示例代码如下：
public static long getPre(long n){
int cnt = 0;
int num[] = new int[20];
do{
num[cnt++] = (int)n%10;
n = n / 10;
}while (n > 0);
for(int i=cnt-1; i>=0; i--){
if(num[i] % 2 == 1){
num[i] --;
for(int j=i-1; j>=0; j--){
num[j] = 8;
}
break;
}
}
long ans = 0;
for(int i=cnt-1; i>=0; i--){
ans = ans * 10 + num[i];
}
return ans;
}
public static long getNext(long n){
int cnt = 0;
int num[] = new int[20];
do{
num[cnt++] = (int)n % 10;
n /= 10;
}while (n > 0);
num[cnt++] = 0;
for(int i=cnt-1; i>=0; i--){
if(num[i] % 2 == 1){
if(num[i] == 9){
int j = i+1;
while (num[j] == 8) j++;
num[j] += 2;
while ((--j) >= 0){
num[j] = 0;
}
}
else{
num[i]++;
for(int j=i-1; j>=0; j--){
num[j] = 0;
}
}
break;
}
}
long ans = 0;
for(int i=cnt-1; i>=0; i--){
ans = ans * 10 + num[i];
}
return ans;
}
Problem B: Lucky Dip
题目描述
背包中有n个物品，每个物品i有其对应的价值Vi。你每次从背包中随机取一个物品（取到每个物品的概率相同），取出后你有k次机会可以选择放回该物品或者留下该物品，但最后一次你必须留下该物品。希望你想出一个最优的策略来最大化取出的商品的价值，商品的价值的期望是多少？
示例：
4 0 1 2 3 4 =>2.500000 3 1 1 10 1 =>6.000000 3 15 80000 80000 80000 =>80000.000000 1 1 10 =>10.000000 5 3 16 11 7 4 1 =>12.358400
数据集及得分
小数据集的取值范围是0<=K<=1，分值是10分，大数据集取值范围是0<=K<=5*10^4，分值是19分。
答题思路
定义一个数组E[k]来表示物品放回k次的最优期望值。那么显然E[0]的值为sum(Vi)/N（因为不可放回，所以直接求均值）。那么为了保证价值最高，你的放回策略应该为：
– 当你得到物品价值>=E[k-1]时，保留
– 否则将其放回。
这样我们就得到了一个E的递推公式：E[k] = (E[k-1] * (背包中比E[k-1]价值小的物品个数) + (背包中比E[k-1]价值大的物品价值总数)) / n
对于题目还可以进行一定的优化：比如对背包中的物品按价值排序，计算取最大x个物品的价值总和，利用二分查找求背包中比价值v小的物品的个数。
代码示例如下：
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i=0; i<t; i++){
List ls = new ArrayList();
int n = sc.nextInt();
int k = sc.nextInt();
for(int j=0; j<n; j++){
ls.add(sc.nextInt());
}
int a[] = new int[ls.size()];
for(int j=0; j=0; j--){
sum[j] = sum[j+1] + a[j];
}
dp[0] = (double)sum[0] / n;
for(int j=1; j<=k; j++){
int cnt = upperBound(a,n,dp[j-1]);
dp[j] = (cnt * dp[j-1] + sum[cnt]) / n;
}
System.out.println("Case #" + (i+1) + ": " + dp[k]);
}
}
public static int upperBound(int[] array, int length, double value) {
int low = 0;
int high = length;
while (low = array[mid]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
Problem C: Scrambled Words
题目描述
统计已知字符串S中出现的每个单词的个数L，不同于其他题目的点在于统计的单词不仅是单词原型，单词的变体也统计在该原型的数目中（单词变体是指首尾字母相同，但其他位置的字母可以是任何顺序的）。
数据集及得分
小数据集S的长度取值范围为2<=N<=1000，L的取值范围为1<=L<=1000，分值为18分，大数据集S的长度取值范围为2<=N<=10^6，L的取值范围为1<=L<=20000，分值为30分。
答题思路
利用数组来表示字母出现的频率，用哈希来统计相同长度的单词。
char str[100010];
int X[100010];
const int SEED = 13331;
//把数组变成unsigned long long类型，后面只需要判断unsigned long long是否相等
unsigned long long getHash(char start, char end, int num[]){
unsigned long long ret = start * SEED + end;
for(int i=0; i<26; i++){
ret = ret * SEED + num[i];
}
return ret;
}
char dict[100010];
unsigned long long dictHash[20010];
int num[26];
int Len[20010];
int main(){
int T;
int icase = 0;
scanf("%d", %T);
while(T--){
icase ++;
int L;
scanf("%d", &L);
int totLen = 0;
for(int i=0; i<L; i++){
scanf("%s", dict);
int len = strlen(dict);
memset(num, 0, sizeof(num));
for(int j=1; j> str[0];
cin >> str[1];
scanf("%d%d%d%d%d",&N,&A,&B,&C,&D);
X[0] = str[0];
X[1] = str[1];
for(int i=2; i<N; i++){
X[i] = ((long long)A * X[i-1] + (long long)B * i);
str[i] = (char)(97 + X[i] % 26);
}
str[N] = 0;
//把相同长度的merge到一起
sort(Len, Len + totLen);
totLen = unique(Len, Len + totLen) - Len;
unorderer_map mp;
for(int i=0; i<L; i++){
mp[dictHash[i]] ++;
}
int ans = 0;
//按长度的数组去枚举目标的串
for(int j=0; j N)
continue;
memset(num, 0, sizeof(num));
for(int i=1; i<len-1; i++){
num[str[i] - 'a']++;
}
//目标值的哈希值如果相同，则删掉
unsigned long long tmp1 = getHash(str[0], str[len-1], num);
if(mp.count(tmp1)){
ans += mp[tmp1];
mp.erase(tmp1);
}
for(int i=lenl i<N; i++){
num[str[i-1] - 'a']++;
num[str[i-len+1] - 'a']--;
unsigned long long tmp = getHash(str[i-len+1], str[len-1], num);
if(mp.count(tmp)){
ans += mp[tmp];
mp.erase(tmp);
}
}
}
printf("Case #%d: %d\n",icase, ans);
}
return 0;
总结
A题是一道比较简单的题目，只要使用贪心算法进行构造或者二分查找即可解决。B题属于中等难度的算法题目，需要找到递推的公式，利用动态规划来进行求解，可以使用二分查找来进行优化。C题相对较难，是一道字符串的问题，可以维护一个字母出现频率的数组或者哈希来进行优化，为了通过大数据集也需要进行一定的优化。总的来说，想要达到51分通过Kick Start的测试还是需要熟练掌握数据结构和算法的知识的。希望大家通过此文能够有所收获！