Kick Start 2019D

KickStart是谷歌的线上笔试,每年会举办数轮,通过KickStart可以拿到工作面试名额。KickStart的有一定难度,但是又没有用到复杂的数据结构,是比较好的笔试筛选题。之前的题解在这里:

最近忙着实习,好久没刷过题了,熟练度下降很多,加上比赛中遇到了状况,排名直接扑街。。。

1. Record Breaker

题目: 给一个数组A[N],第i项是一个突破,当A[i]>max{A[1],A[2],…,A[i-1]}且A[i]>A[i+1](i是最后一项时这个条件可以不考虑),求突破的个数。

签到题,给把第N+1项补为-1,然后从1到N遍历计数就行。

2. Alien Piano

题目: 给一个整数数组A[N],将它改写为B[N],B[i]里只能从1、2、3、4里选,并且若A[i+1]>A[i],则B[i+1]>B[i];若A[i+1]=A[i],则B[i+1]=B[i];若A[i+1]<A[i],则B[i+1]<B[i]。为了改写成功,可能需要违反这个规则,求最少违反的规则数量。

这种问题是序列状态选择问题:对于序列中的每一项,有4种状态可以选择,且每一项的选择只和前一项有关,目标求最优解。这种问题,是应用动态规划的经典场景,维特比算法就是有名的例子。

int dp[10010][4];

int solve(){
    int N;
    cin >> N;
    for(int i=0; i<4; i++) dp[0][i] = 0;
    int last, curr;
    cin >> last;

    for(int i=1; i<N; i++){
        cin >> curr;
        for(int j=0; j<4; j++){
            dp[i][j] = INT_MAX;

            for(int k=0; k<4; k++){
                int d = (curr-last)*(j-k);
                if(d>0) dp[i][j] = min(dp[i][j], dp[i-1][k]);
                else if(d<0) dp[i][j] = min(dp[i][j], dp[i-1][k]+1);
                else{
                    if(curr==last && j==k) dp[i][j] = min(dp[i][j], dp[i-1][k]);
                    else dp[i][j] = min(dp[i][j], dp[i-1][k]+1);
                }
            }
        }
        last = curr;
    }

    int ret = INT_MAX;
    for(int i=0; i<4;i++) ret = min(ret, dp[N-1][i]);
    return ret;
}

这道题还可以用贪心法来解:原数组中,波峰都填4,波谷都填1,如果中间连续上升或下降的太多,不得不违反规则,也贪心地来违反。附上参考答案的图,非常直观了:

from google

附上参考答案的Python代码,写的很漂亮:

def solve():
  k = input()
  a = map(int, raw_input().split())
  # Filter out repeated notes.
  a = [a[i] for i in xrange(0, k) if i == 0 or a[i - 1] != a[i]]
  upCount = 0
  downCount = 0
  violations = 0
  for i in xrange(1, len(a)):
    if a[i] > a[i - 1]:
      upCount += 1
      downCount = 0
    else:
      downCount += 1
      upCount = 0
    if upCount > 3 or downCount > 3:
      violations += 1
      upCount = downCount = 0
  return violations

3. Beauty of tree

题目: 给一个树,节点数为N,N<100000,小红在树上随机选一个节点,然后向上每隔A个节点涂上红色(包括此节点),直到树根;小蓝在树上随机选一个节点,然后向上每隔B个节点涂上蓝色(包括此节点),直到树根。一个节点只要被一个人涂上颜色就算被选中了,求选中的节点数的期望。

选中节点数的期望=SUM{每个节点至少被涂色一次的概率},对于一个节点a,P(被至少涂色一次) = P(被小红涂色) + P(被小蓝涂色) - P(被小红涂色) * P(被小蓝涂色),这个等式成立是因为小红和小蓝的选择是独立的。

所以这个问题就分解为,求每个节点被小红涂色的概率,每个节点被小蓝涂色的概率。如何求呢?一个节点被小红涂色的概率,等于小红在每个节点都选一次,然后次节点被涂色的次数再除以N。而一个节点被涂色,要么它本身被选择,要么是因为它的A层子节点被涂过色,即对于一个节点,被小红涂色次数 = 1 + SUM{该节点的A层子节点被涂色的次数}。

所以可以用动态规划求解,先求叶子节点被选择的次数,然后再不断迭代到树根去。这就需要使用dfs了,dfs时维护一个从根节点到当前节点的路径,当本节点被涂的次数计算完后,更新它的A层父节点的次数就可以,直到树根。表述比较复杂,直接看代码更清晰:

void dfs(long long curr, vector<vector<long long>>&childs, vector<long long>&path, vector<long>&cnt, long long step){
    cnt[curr] ++;
    path.push_back(curr);
    for(long long child: childs[curr]){
        dfs(child, childs, path, cnt, step);
    }
    path.pop_back();
    long long n = path.size();
    long long remote = n - step;
    if(remote >=0 ) cnt[path[remote]] += cnt[curr];
}


double solve(){
    long long N, A, B;
    cin >> N >> A >> B;
    vector<long> cntA(N+1, 0), cntB(N+1, 0);

    vector<vector<long long>> childs(N+1, vector<long long>());
    long long parent;
    for(long long i=2; i<=N; i++){
        cin>>parent;
        childs[parent].push_back(i);
    }

    vector<long long> path;
    dfs(1, childs, path, cntA, A);
    dfs(1, childs, path, cntB, B);

    long ret = 0;
    for(long long i=1; i<=N; i++){
        ret += cntA[i]*N + cntB[i]*N - cntA[i]*cntB[i];
    }

    return (double)ret/(double)(N*N);
}

这道题个人觉得出得很好(虽然我没做出来),需要先推导概率计算,然后想到DP的思路,最后还要结合dfs来进行DP。虽然代码量不大,但是需要三种思想,比较考验思维。有点遗憾的是,由于输出的是浮点数,答案对精度的判定有问题,我答题时使用cout << ans;这样输出总是WA,然而改成printf("%lf", ans);这种就可以PASS,可能是四舍五入之类的有细微影响。

4. Locked Doors

题目: N个房间在一排,两个房间隔着一道门,每个门都有一个开启的困难程度,小红最开是在一个房间s中,每次选择左右两边门中最容易开启的一扇门来开,随后进入房间,问在第k次开门后她在哪个房间中?也就是给(s, k)求位置,这样的查询很多最多为100000个。

这么多查询,十有八九也是用线段树,关键是如何转化。

说一下我的一个思路:考虑最困难的那扇门,将所有房间分隔为左右两部分,如果小红最开始在左侧,那么她肯定是把左侧的所有门开完了,才进入右侧。所以,如果左侧的门的数量小于k,那么她最终的位置肯定在左侧,如果大于k,那么她最终的位置肯定在右侧。这样划分出范围后,再继续求此范围内的最困难的那扇门,继续这样此步骤直到区间只有一扇门就是小红的位置。为了查询区间内最困难的门,可以使用线段树,总共的复杂度应该是O((Q(logN)^2),但是此方法不稳定,在最坏的情况下会退化到QNlogN。

参考一位同学的博客,使用二分加线段树可以求解。思路为:小红总共开了k-1扇门,设左边开了a扇门,那么右边就开了k-1-a扇门,可以用二分法求解这个a——如果左边多开了一扇门,那么这扇门肯定比面还没开的那扇门大,即左右两边是不平衡的。