算法日记

网易互娱笔试5/28

第二题：

有一款游戏名叫《永远的明日之都》，这款游戏以[1-7]天为一个轮回，

n <= 10 ^ 9

n <= m <= 7 * n

输入一个n，表示游戏进行的总天数，输入一个m，表示玩家达成的结局数

输出，结局的所有天数构成中各个 i [1-7]出现的最大次数

输入样例

2 10

输出样例

0
0
1
1
2
1
1

解释：在10天内达成两个结局的情况有且仅有 3+7，4+6，5+5，6+4，3+7，其中天数i = 5最多出现两次，天数3最多出现一次，依次类推

题目分析：

​ 本题我没有理解清晰题意，直到交卷，我也没理解好题目的输出，我抽象的模型是有面额为1-7的硬币，可以选取n枚硬币，求出选取的硬币总和为m的所有组合，推断用dp来推导，思维到这里开始卡壳，因为dp并不能很好的求出目标组合的各个组合选取的硬币的种类，之后暂时放弃了这道题，去做了下一道题…

​ 做任何题目之前，要有观察数据范围的习惯，本题的数据范围 1 <= n <= 10 ^ 9 且 n <= m <= 7 * n ，这种数据范围根本不能使用数组来存储，也就是不能使用常规的二分，dp等

​ 本题目其实可以抽象为一个数学问题，如果有n次选择机会，设置i的选择次数最大为x，x <= n，x * i + m % i = m，x = (m - m % i) / i，0 <= m % i < i ，

所以x的范围，(m - i + 1) / i <= x <= min(n, m / i ) , 且 n - x <= m - i * x <= 7 * (n - x)(余数需要满足的范围)，

推出，*当 i != 1的时候，x <= (m - n) / (i - 1) 且当i != 7的时候，x <= (7 n - m) / 7 - i

所以可以给出计算的代码

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        for (int i = 1; i <= 7; i++) {
            System.out.println(calculate(n, m, i));
        }
    }

    public static int calculate(int n, int m, int i) {
        int res = Math.min(n, m / i);
        if (i != 1) res = Math.min(res, (m - n) / (i - 1));
        if (i != 7) res = Math.min(res, (7 * n - m) / (7 - i));
        return res;
    }
}

第三题

两个点 (x1, y1) 和 (x2, y2)，曼哈顿距离 = |x1 - x2| + |y1 - y2|

​ 本题会给出一个地图，使用char[][]数组来表示，其中#表示障碍物，障碍物不能走，S表示起点，T表示屠夫，.表示空地，$表示发电机，题目输入m, n, k 表示一个 m行n列的矩阵，其中k表示距离屠夫曼哈顿距离<= k 的格子不能走，要求，求出从起点S出发到达终点E且至少有5台发电机的最短路径，如果找不到，返回-1，

输入样例，

5 5 1
#S$..
$$..$
.#.T.
.$..E
$#...

输出样例

14
解释：正确路径是 (0,1) -> (0,2) -> (1, 2) -> (1, 1) -> (1, 0) -> (2, 0) -> (3, 0) -> (4, 0) -> (3, 0) -> (3,1) -> (3,2) -> (4,2) -> (4,3) -> (4,4) -> (3, 4)

牡蛎/(ㄒoㄒ)/~~

确实写不出来，就等之后我变厉害了在回来写吧

如何根据数据范围来判断大致的时间复杂度？

数据范围 算法时间复杂度 可选择算法
n ≤ 30 指数级别的算法 暴力搜索、dfs+减枝、状态压缩dp
n ≤ 100 O(n^3) floyd，dp
n ≤ 1000 O(n^2)，O(n^2logn) dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
n ≤ 10000 O(nsqrt{n}) 块状链表、分块、莫队
n ≤ 100000 O(nlogn) 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、spfa、求凸包、求半平面交、二分
n≤1000000 O(n)，常数小的O(nlogn) hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn)O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa
n≤10000000 O(n) 双指针扫描、kmp、AC自动机、线性筛素数
n≤10^9 O(sqrt(n)) 判断质数
n≤10^18 O((sqrt(n))^2) 最大公约数，快速幂
n≤10^10 O(logn*loglogn) 高精度加减乘除
n≤10^100000 高精度加减、FFT/NTT