https://www.lintcode.com/problem/maximum-subarray/description
关键点：因为数据是连续的 即累加值如果小于当前值 则直接切到当前值重新开始为最优 期间res是最优值。

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: A integer indicate the sum of max subarray
     */
    public int maxSubArray(int[] nums) {
        int res = nums[0], tmp = nums[0];
        for(int i = 1; i<nums.length; i++){
            if(tmp + nums[i] < nums[i]){
                tmp = nums[i];
            }else{
                tmp += nums[i];
            }
            res = Math.max(res, tmp);
        }
        return res;
    }
}

https://www.lintcode.com/problem/recover-rotated-sorted-array/description
因为是旋转的排序数组 那么我们只需要三步就能还原回来 首先找到把数组分为两部分顺序的数组，然后分别左右两边reverse则就会变成逆序数组 再reverse一次即可。

public class Solution {
    /**
     * @param nums: An integer array
     * @return: nothing
     */
    public void reverse(List<Integer> nums, int start, int end){
        for(int i = start; i<=start + (end-start)/2; i++){
            int tmp = nums.get(end - i + start);
            nums.set(end - i + start, nums.get(i));
            nums.set(i, tmp);
        }
    }
    public void recoverRotatedSortedArray(List<Integer> nums) {
        for(int i = 0; i < nums.size() - 1; i++){
            if(nums.get(i) <= nums.get(i+1)){
                continue;
            }
            reverse(nums, 0, i);
            reverse(nums, i+1, nums.size() - 1);
            reverse(nums, 0, nums.size()-1);
            break;
        }
    }
}

双重二分 下标为0处理比较恶心。https://www.lintcode.com/problem/search-a-2d-matrix/description

public class Solution {
    /**
     * @param matrix: matrix, a list of lists of integers
     * @param target: An integer
     * @return: a boolean, indicate whether matrix contains target
     */
    private boolean solve(int[] matrix, int target){
        int left = 0, right = matrix.length - 1;
        while(left < right){
            int mid = left + (right - left) / 2;
            if(matrix[mid] > target){
                right = mid - 1;
            }else if(matrix[mid] < target){
                left = mid + 1;
            }else{
                right = mid;
            }
        }
        return matrix[left] == target;
    }
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix == null || matrix.length == 0){
            return false;
        }
        int left = 0, right = matrix.length - 1;
        while(left + 1 < right){
            int mid = left + (right - left) / 2;
            System.out.println(mid);
            if(matrix[mid][0] > target){
                right = mid;
            }else if(matrix[mid][0] < target){
                left = mid;
            }else{
                return true;
            }
        }
        if(target >= matrix[right][0]){
            left = right;
        }
        return solve(matrix[left], target);
    }
}

https://www.lintcode.com/problem/trailing-zeros/description
末尾0的个数就是指这个数总共有几个10因子，而10又能表示成2和5的乘积。假设m=n!，那么m中2的因子个数肯定大于5的因子个数，所以m中5的因子个数即是所要求结果；

显然n除以5可得到1~n中包含有一个因子5的个数，但是，1~n中有的数可以被5整除好几次，所以必须将这个数再除以5，得到1~n中包含有两个因子5的个数，依次循环进行累加即可得到全部5的因子个数；

地址:https://www.luogu.org/problemnew/show/SP3377
关键点：与普通并查集不同的是要一个rel数组来维护 在merge 和 find 里进行维护rel
在find里 因为路径压缩，x并不能直接知道他与路径压缩的根节点的关系 所以他得跟他回溯过来的原来的父节点比较关系
rel[x] = (rel[x] + rel[f[x]]) % 2;
merge中 因为无法直接知道b跟a的直接关系 得用x,y来推算出b与a的关系。

#include <set>
#include <iostream>
#include <cstring>
using namespace std;
int rel[1000005],f[1000005],t,n,m;
bool flag;
int find(int x){
    if(f[x] == x)return f[x];
    int p = find(f[x]);
    rel[x] = (rel[x] + rel[f[x]]) % 2;
    f[x] = p;
    return f[x];
}
void merge(int x, int y){
    int a = find(x);
    int b = find(y);
    if(a == b){
        if(rel[x] == rel[y]){
            flag = true;
        }
        return;
    }
    f[b] = a;
    rel[b] = (rel[x] - rel[y] + 1) % 2;
}

int main() {
    scanf("%d", &t);
    for(int k = 1; k<=t; k++){
        flag = false;
        memset(rel, 0, sizeof(rel));
        memset(f, 0, sizeof(f));
        n = 0, m = 0;
        scanf("%d %d", &n, &m);
        for(int i = 1; i<=n; i++){
            f[i] = i;
        }
        for(int i = 1; i<=m; i++){
            int a,b;
            scanf("%d %d", &a, &b);
            merge(a, b);
        }
        printf("Scenario #%d:\n", k);
        if(flag)printf("Suspicious bugs found!\n");
        else printf("No suspicious bugs found!\n");
    }
}