谷歌Kick Start线上编程第二课

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

Captain QR Code

扫码联系船长

发表回复

您的电子邮箱地址不会被公开。