Kick Start 2020C

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

拖到了D轮结束才写C轮的总结,发现当时的思路现在都有点想不起来了,只好对着自己的代码回顾了一遍。

1. Countdown

题目: 给一个数组A[N]和k,找到k,k-1,…,2,1子数组的数量。

热身题,从左往右扫描,遇到值为k的时候,就往右看能不能一直数到1

2. Stable Wall

题目: 想要砌一堵由字母砌成的墙,每个字母在下面的有字母时才能被放上,一次需要把一类的字母都放上,问这堵墙是否可以被砌成。如下面这个可以以通过E-D-C-B-A的顺序砌成:

AAABBCCDDE
AABBCCDDEE
AABBCCDDEE

当时读了好久的都没明白题意,理解后其实就是简单的拓扑排序题。上面的字母依赖于下面的字母,根据此建立有向图,然后根据依赖关系进行拓扑排序即可。注意上下字母一样的时候就不需要对自己加边了。

void solve(){
    int R, C;
    string ret;
    cin >> R >> C;
    vector<string> s(R);
    for(int i=0; i<R; i++) cin >> s[i];

    vector<int> in_count(26, 0);
    vector<unordered_set<int>> outs(26);
    unordered_set<int> all_chars;

    // 建边
    for(int i=1; i<R; i++){
        for (int j=0; j<C; j++){
            if(s[i][j]-'A' != s[i-1][j]-'A')
                outs[s[i][j]-'A'].insert(s[i-1][j]-'A');
        }
    }
    for(string str: s)
        for(char c: str) all_chars.insert(c-'A');
    // 计算每个定点的入度
    for(auto out: outs){
        for(auto c: out) in_count[c]++;
    }
    // 拓扑排序
    queue<int> nodes;
    for(char c: all_chars){
        if(in_count[c]==0) nodes.push(c);
    }
    while(!nodes.empty()){
        char c = nodes.front();
        ret += ('A'+c);
        nodes.pop();
        for(char out: outs[c]){
            if(--in_count[out]==0) nodes.push(out);
        }
    }

    if (ret.size() == all_chars.size()) cout<<ret;
    else cout<<"-1";
    cout<<endl;
}

3. Perfect Subarray

题目: 给一个数组A[N],-100<=Ai<=100,N<=100000,求子数组和为完全平方数的个数。如数组1 2 2中,复合条件的子数组为12 2,所以个数是2。

想法思路:要求子数组和,可以计算sum数组,sum[i]=A1+A2+...+Ai,那么i到j的子数组和就等于sum[j]-sum[i-1],这是常见的用法。此时可以对N^2个子数组和判断是否为完全平方数。

但是这种方法复杂度达不到要求,而且-100<=Ai<=100的条件并没有用到。可以用常见的一个思路,把子数组的一端固定住,看有什么规律,例如看以Ai为开头的子数组中,有多少子数组的和是完全平方数,也就是sum[j]-sum[i]中多少是完全平方数,也即在{sum[i+1],…,sum[N]}中有多少个等于sum[i]+k*k。

所以可以试探不同的k(从1到足够大),然后判断{sum[i+1],…,sum[N]}中sum[i]+k*k的个数,这样做的原因是有-100<=Ai<=100条件,所以sum[j]-sum[i] <= 100*(j-i),差值不会太大,导致要尝试的k在sqrt(N*100)的量级,对每个i都要尝试这么多,所以复杂度只有 \(O(N\sqrt{N*100}) \)。

程序的思路为:初始ans=0,从i从N-1遍历到1,维护max_right=max{sum[i+1],…sum[N]},以及用map记录右边每个sum出现的次数。对于每个i,查找sum[i]+k*k在map中的次数,加在ans上即可:

int A[100010], S[100010];
int N;

long solve(){
    long ret = 0;
    cin >> N;
    S[0] = 0;
    for(int i=0; i<N; i++){
        cin >> A[i];
        S[i+1] = A[i] + S[i];
    }
    unordered_map<int, int> sums;
    int maxv = S[N];
    sums[S[N]] ++;
    for(int i=N-1; i>=0; i--){
        int maxd = maxv - S[i];
        for(int j=0; j*j<=maxd; j++){
            int target = j*j + S[i];
            if(sums.find(target) != sums.end()){
                ret += sums[target];
            }
        }
        maxv = max(maxv, S[i]);
        sums[S[i]] ++;
    }

    return ret;
}

这道题出的很灵性,在普通的情景上加上-100<=Ai<=100的条件,就促成了更好的解法。其中的解题思路和很多题一样:找到更好的分解与组合的方式。例如,由于有N*N个子数组,不能分解为一个一个地判断是否复合要求,所以需要分批判断,才能达到更优的复杂度。对于子数组问题,分批就是,将起点相同或者终点相同的子数组划分到一起,然后一起判断,这是常见的套路。

4. Candies

题目: 给一个数组A[N],定义求和的方式为 \( A_l -2A_{l+1} + 3A_{l+2} - 4A_{l+3} + 5A_{l+4} … \) ,求l到r的和,中间可以更新数组的值,更新和求和的数量L<=100000。

多次更新与多次查询,基本是线段树没跑了,复杂度应为O(Llog(N))。这道题的子数组求和操作,也可以分解为前缀和相减,找两个例子试一下就能推导出来。

#define fi first
#define se second

#define isOdd(x) ((unsigned)(x)&1u)

const int n = 200010;
int N, Q;

struct node{
    long ms, ps;
}nodes[n*4];

int A[n];

void build(long i, long l, long r){
    if(l == r){
        nodes[i].ms = isOdd(l)? l*A[l]: -l*A[l];
        nodes[i].ps = isOdd(l)? A[l]: -A[l];
        return;
    }

    long mid = (l + r)/2;
    build(i*2, l, mid);
    build(i*2+1, mid+1, r);
    nodes[i].ms = nodes[i*2].ms + nodes[i*2+1].ms;
    nodes[i].ps = nodes[i*2].ps + nodes[i*2+1].ps;
}

void update(long i, long l, long r, long target){
    if(l == r){
        nodes[i].ms = isOdd(l)? l*A[l]: -l*A[l];
        nodes[i].ps = isOdd(l)? A[l]: -A[l];
    }
    else{
        long mid = (l+r)/2;
        if(target<=mid) update(i*2, l, mid, target);
        else update(i*2+1, mid+1, r, target);
        nodes[i].ms = nodes[i*2].ms + nodes[i*2+1].ms;
        nodes[i].ps = nodes[i*2].ps + nodes[i*2+1].ps;
    }
}

pair<long, long> query(long i, long l, long r, long ql, long qr){
    if(ql <=l && qr >=r) return {nodes[i].ms, nodes[i].ps};

    long mid = (l+r)/2, m=0, p=0;
    if(mid>=ql){
        auto pair = query(i*2, l, mid, ql, qr);
        m += pair.fi; p += pair.se;
    }
    if(mid+1<=qr){
        auto pair = query(i*2+1, mid+1, r, ql, qr);
        m += pair.fi; p += pair.se;
    }
    return {m, p};
}

long solve(){
    long ret = 0;
    cin >> N >> Q;

    for(int i=1; i<=N; i++) cin >> A[i];
    build(1, 1, N);

    char c;
    int l, r;
    for(int i=0; i<Q; i++){
        cin >> c;
        cin >> l >> r;
        if(c=='Q'){
            auto pair = query(1, 1, N, l, r);
            long sum = pair.fi - (l-1)*pair.se;
            sum = isOdd(l)? sum: -sum;
            ret += sum;
        }
        else{
            A[l] = r;
            update(1, 1, N, l);
        }
    }

    return ret;
}

由于当时时间不太足够,也好久没写线段树了,所以就当时只能暴力过test1了。写的过程中正负数和奇偶很容易弄错,还好当时赶在最后一分钟提交代码,时间结束后才跑出来,顺利过test1,非常刺激。