3-26阿里笔试统计

第二题没来得及看，有人知道是什么吗

第一题双指针 第二题目做法复杂度爆炸，想不出来更好的： if __name__ == '__main__&(688)#39;:     n = int(input())     mat = [[0x3f3f3f3f for _ in range(n + 1)] for _ in range(n + 1)]     for i in range(n + 1):         mat[i][i] = 0     for _ in range(1, n):         a, b, c = list(map(int, input().split()))         mat[a][b] = c         mat[b][a] = c     for i in range(n + 1):         for j in range(n + 1):             for k in range(n + 1):                 if mat[i][k] + mat[k][j] < mat[i][j]:                     mat[i][j] = mat[i][k] + mat[k][j]     li_a = list(map(int, input().split()))[1:]     li_b = list(map(int, input().split()))[1:]     li_c = list(map(int, input().split()))[1:]     result = []     for a in li_a:         for b in li_b:             for c in li_c:                 result.append((mat[a][b] + mat[b][c] + mat[a][c]) / 2)     num = len(result)     print(sum(result) / num)

第一题直接以0作为分割点，作字符串切割，统计相邻两个片段的长度和取最大即可，另外处理一下全为1的字符串，居然就能A了😂

第一题Leetcode上有类似的，是一道简单题。 第二题如果有人找到类似的题的话，希望贡献一下链接。 https://leetcode-cn.com/problems/reverse-bits-lcci/

第二题应该是个n^2的算法，第一是求树的最短路径，不能直接用多源最短路径算法，那玩意儿n^3，这里求的话，（假想节点a为根结点，然后求各点深度，也就是距离了）。然后对于任意三点，a，b，c；假设最优点是T，那么其实距离和T无关，应该是ab，bc，ac的最短距离的和除以二。问题是怎么把三重循环求和拆开，变成二重循环

只A了第一道。。。。 第二道想了半天打算用暴力，没时间了。。。。。。

求题目

第一体100% if __name__ == '__main__&(688)#39;:     cse = int(input())     for _ in range(cse):         n = int(input())         li = list(map(int, input().split()))         cnt_0 = 0         cnt_1 = 0         p1 = 0         p2 = 0         result = 0         flag_all_1 = True         for e in li:             if e == 0:                 flag_all_1 = False                 break         while p1 < n:             if cnt_0 <= 1 and p2 < n:                 if li[p2] == 0:                     p2 += 1                     cnt_0 += 1                 else:                     p2 += 1                     cnt_1 += 1             else:                 if li[p1] == 0:                     cnt_0 -= 1                 else:                     cnt_1 -= 1                 p1 += 1             if cnt_1 > result:                 result = cnt_1         print(result if not flag_all_1 else result - 1)

第二题暴力。没分 n = int(input()) edges = [] matrix = [[float('inf&(835)#39;)]*n for i in range(n)] for i in range(n-1):     edge = [int(i) for i in input().split()]     matrix[edge[0]-1][edge[1]-1]=edge[2]     matrix[edge[1]-1][edge[0]-1]=edge[2] for i in range(n):     matrix[i][i] = 0 for i in range(n):     for j in range(n):         for  k in range(n):             matrix[i][j]=min(matrix[i][j],matrix[i][k]+matrix[k][j]) nodelike = [] for i in range(3):     nums = [int(i) for i in input().split()]     nodelike.append(nums[1:]) res = 0 for i in nodelike[0]:     for j in nodelike[1]:         for k in nodelike[2]:             onemin = float('inf&(835)#39;)             for z in range(n):                 onemin = min(onemin,matrix[i-1][z]+matrix[j-1][z]+matrix[k-1][z])             res += onemin print(res/(len(nodelike[0])*len(nodelike[1])*len(nodelike[2])))

第一题AC(C++): # #include <vector> # #include <iostream> # #include <algorithm> using namespace std; void readCardCount(int n, vector<int> &cardCount) {     cardCount.push_back(0);     for (int i = 0; i < n; i++) {         int card;         cin >> card;         if (card == 0) {             cardCount.push_back(0);         } else {             ++cardCount.back();         }     } } int maxCardLength(const vector<int> &cardCount) {     int theMax = cardCount[0] - 1;     for (int i = 1; i < cardCount.size(); i++) {         theMax = max(theMax, cardCount[i - 1] + cardCount[i]);     }     return theMax; } int main() {     int total_count;     cin >> total_count;     for (int i = 0; i < total_count; i++) {         int n;         cin >> n;         vector<int> cardCount;         readCardCount(n, cardCount);         cout << maxCardLength(cardCount) << endl;     } } 第二题给我干蒙了，感觉应该是DP或者贪心一类的东西，但是完全没有思路，那个4*10⁵暴力根本不可能过。

有没有第二题得分的大佬给个思路呀。

有没有大神给个第一题java的解法

真尴尬，没做过牛客，这上来还要自定义输入输出的，整了半天，然后第一题，先用dp发现不对，再用dfs，结果dfs的中间结果没保存下来，一时半会没发现，这就快没时间了。 然后一想，没有这么复杂啊，直接双指针暴力算就是了，结果写了一版双指针滑动窗口，按0分割，保存分割出来的1的长度，然后两两比较取最大，写完了突然想起来0可能有连续出现的情景，就又修改了代码，然后调试好往回粘的时候时间到了，真是cao了。 说道理，还是自己太菜了，另外也没调研牛客写题目还要自定义输入输出的，我之前都是刷leetcode的。 最后贴一下第一题的代码，也没提交，也不知道对不对，就是感觉跟吃了屎一样难受！

我第二题直接dfs构图的，然后再算每个酒店的最小，最不过时间来不及写完，有没有兄弟们和我方法一样写出来的，能过吗