刷题tips

# 判断奇偶
x % 2 == 1  ->  (x&1) == 1

x = x & (x-1)  清零最低位的1
x&-x  得到最低位的1
x&~x  => 0

* 回溯算法
 *
 result = []
 def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
    return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择
 *
 */
/***
 二分查找
int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

 */
/**
 * 滑动窗口
 *
 int left = 0, right = 0;

 while (right < s.size()) {
     window.add(s[right]);
     right++;

     while (valid) {
         window.remove(s[left]);
         left++;
        //中间有跳跃一定要把结果删掉
     }
 }
 
单调栈： 查找每个数左侧第一个比它小的数
 单调队列： 滑动窗口中的最值

public class Solution {
    int n,W;
    int[] w,v;

    int[] dp;
    // 0 1 背包
    void solve1() {
        for (int i =  0; i < n ; i++) {
            for (int j = W; j >= w[i] ; j--) {

                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        System.out.println(dp[W]);
    }

    // 完全背包

    void solve2() {
        int m = 0;
        for (int i =  0; i < n ; i++) {
            for (int j = w[i]; j <= m ; j++) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        System.out.println(dp[W]);
    }


    // 多重背包
    void solve3() {

        int s = 0, m = 0;
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= 0; j--) {
                for (int k = 1; k <= s && k * w[i] <= j ; k++) {
                    dp[j] = Math.max(dp[j], dp[j - k * w[i] ] + k * v[i] );
                }
            }
        }
        System.out.println(dp[m]);
    }
}

一般ACM或者笔试题的时间限制是1秒或2秒。
在这种情况下，C++代码中的操作次数控制在 107107 为最佳。

下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：

n≤30n≤30, 指数级别, dfs+剪枝，状态压缩dp
n≤100n≤100 => O(n3)O(n3)，floyd，dp
n≤1000n≤1000 => O(n2)O(n2)，O(n2logn)O(n2logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
n≤10000n≤10000 => O(n∗n√)O(n∗n)，块状链表、分块、莫队
n≤100000n≤100000 => O(nlogn)O(nlogn) => 各种sort，线段树、树状数组、set/map、heap、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分
n≤1000000n≤1000000 => O(n)O(n), 以及常数较小的 O(nlogn)O(nlogn) 算法 => hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn)O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
n≤10000000n≤10000000 => O(n)O(n)，双指针扫描、kmp、AC自动机、线性筛素数
n≤109n≤109 => O(n√)O(n)，判断质数
n≤1018n≤1018 => O(logn)O(logn)，最大公约数，快速幂
n≤101000n≤101000 => O((logn)2)O((logn)2)，高精度加减乘除
n≤10100000n≤10100000 => O(logn×loglogn)O(logn×loglogn)，高精度加减、FFT/NTT