[笔试题]9月21日网易笔试ak

近期太忙了，好多AK的笔试都没发出来，今天做了个网易，感觉难度挺大的，和uu们分享一下

T1 （100%）

购买物品，可以在A超市买，也可以在B超市买，B超市限制只能买连续的一段。 最大子串问题。

        int[] sub = new int[n];
        for(int i = 0; i < n; i++){
            sub[i] = a[i] - b[i];
        }

        int l = 0, r = 0;// 选l不选r
        int cl = 0, cr = 0;
        long ans = 0, cur = 0;

        for(int i = 0; i < n; i++){
            if(cur + sub[i] > 0){
                cur += sub[i];
                cr = i+1;
            }else{
                cur = 0;
                cl = i+1;
            }
            if(ans < cur){
                ans = cur;
                l = cl;
                r = cr;
            }
        }
        long res = suma;
        for(int i = l; i < r; i++){
            res -= a[i];
            res += b[i];
        }

T2 （100%）

最少的跳跃次数。 做最少次的公交车。

        Arrays.sort(c, 
        (int[] a, int[] b)->{return a[0] == b[0] ? a[1] - b[1] : a[0] - b[0] ;});
        int ind = 0, res = 0, tag = 0;
        PriorityQueue<Integer> q = 
        new PriorityQueue<Integer>((a, b)->{return b-a;});
        if(x == y){
            System.out.println(0);
        }else if(c[0][0] > x) {
            System.out.println(-1);
        }else{
            while(ind < m){
                while(ind < m && c[ind][0] <= x){
                    q.add(c[ind++][1]);
                }
                if(q.isEmpty() || q.peek() == x){
                    break;
                }
                x = q.peek();
                res++;
                if(x >= y) break;
            }
            if(x < y) System.out.println(-1);
            else System.out.println(res);
        }

T3（100%）

连线问题，咋都是源。。。

        int[][] dp = new int[na+1][nb+1];
        for(int i = 1; i <= na; i++){
            for(int j = 1; j <= nb; j++){
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                if(a[i-1] == b[j-1]){
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);
                }
            }
        }

T4 （100%）

这题有意思了，花了我40分钟左右。

有n行m列的人，分三组，前后左右相邻人不在同一组。

n <= 5, m <= 1000, 共三组。

看范围，暴力肯定TLE，又懒得写dp，只能dfs + cache的亚子试试。

cache的key如何设置？

取决于影响当前以及后续操作的因素。首先是从上往下，从左往右，依次填人，那么影响当前位置的就是上面的人和左面的人。我们记录状态，但是下一次又是左面下面的人，所以要记录一整列的分组状态，其次还要记录当前填到那里了。

所以就是 5个1-3的数字，一个1-5的row，一个1-1000的col。

状态压缩刚刚好够用，所以这个数据范围是精心设计的。

用ll，大致：row + col + tag（tag是10位bit）

然后有趣的是，我们左侧和上方的人刚好是第一个和最后一个tag的bit部分，就用起来很方便了。

贴一些核心代码：

void findChu(int ctal, int cur, ll ctag){ // 先枚举第一列
    if(cur == ctal) {
        chu.push_back(ctag);
        return ;
    }
    for(int i = 1; i <= 3; i++){
        if(i != (ctag % 4)) findChu(ctal, cur + 1, (ctag << 2) | i);
    }
}

int findRow(ll tag){return (7 & (tag >> 28));}
int findCnt(ll tag){return (((1 << 10) - 1) & (tag >> 16));}

bool check(int ci, ll tag){ // 检查能不能放
    int crow = findRow(tag), ccnt = findCnt(tag);
    if(crow == 0){
        int xi = (3 & (tag >> (2 * (row - 1))));
        if(ci != xi) return true;
        else return false;
    }else{
        int xi1 = (3 & tag);
        int xi2 = (3 & (tag >> (2 * (row - 1))));
        if(ci != xi1 && ci != xi2) return true;
        else return false;
    }
}

ll dfs(ll tag){
    if(mp.find(tag) != mp.end()) return mp[tag];
    ll ans = 0;
    int crow = findRow(tag), ccnt = findCnt(tag);
    if(crow == 0 && ccnt == cnt - 1) return 1;//填满
    int nrow = (crow == (row - 1)) ? 0 : crow + 1;
    int ncnt = (crow == (row - 1)) ? ccnt + 1 : ccnt;
    for(int i = 1; i <= 3; i++){
        if(check(i, tag)) {
            ll ntag = ((ll) nrow << 28) | ((ll) ncnt << 16) | 
            (((tag << 2) | i) & ((1 << (2 * row)) - 1));
            ans = (ans + dfs(ntag)) % mod;
        }
    }
    return mp[tag] = ans;
}

int main() {
    cin >> row >> cnt;
    findChu(row, 0, 0);
    for(int i = 0; i < chu.size(); i++) res = (res + dfs(chu[i])) % mod;
    cout << res;
    return 0;
}