上篇文章中,我们介绍了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的测试还是需要熟练掌握数据结构和算法的知识的。希望大家通过此文能够有所收获!

扫码联系船长