2017网易校招编程题-笔记

对网易有一种莫名的执着,然而感觉这次笔试又跪了

1. 独立的小易

小易为了向他的父母表现他已经长大独立了,他决定搬出去自己居住一段时间。一个人生活增加了许多花费: 小易每天必须吃一个水果并且需要每天支付x元的房屋租金。当前小易手中已经有f个水果和d元钱,小易也能去商店购买一些水果,商店每个水果售卖p元。小易为了表现他独立生活的能力,希望能独立生活的时间越长越好,小易希望你来帮他计算一下他最多能独立生活多少天。
输入描述：
输入包括一行,四个整数x, f, d, p(1 ≤ x,f,d,p ≤ 2 * 10^9),以空格分割
输出描述：
输出一个整数, 表示小易最多能独立生活多少天。

难得遇到一个送分题…

while True:
    try:
        str = raw_input()
        x, f, d, p = [int(x) for x in str.split()]
        ans = 0
        if x * f >= d:
            print int(d/ x)
        else:
            d -= (x * f)
            print f + int(d/(p+x))
    except EOFError:
        break

2. 堆棋子

小易将n个棋子摆放在一张无限大的棋盘上。第i个棋子放在第x[i]行y[i]列。同一个格子允许放置多个棋子。每一次操作小易可以把一个棋子拿起并将其移动到原格子的上、下、左、右的任意一个格子中。小易想知道要让棋盘上出现有一个格子中至少有i(1 ≤ i ≤ n)个棋子所需要的最少操作次数.
输入描述：
输入包括三行,第一行一个整数n(1 ≤ n ≤ 50),表示棋子的个数
第二行为n个棋子的横坐标xi
第三行为n个棋子的纵坐标yi
输出描述：
输出n个整数,第i个表示棋盘上有一个格子至少有i个棋子所需要的操作数,以空格分割。行末无空格
如样例所示:
对于1个棋子: 不需要操作
对于2个棋子: 将前两个棋子放在(1, 1)中
对于3个棋子: 将前三个棋子放在(2, 1)中
对于4个棋子: 将所有棋子都放在(3, 1)中

假设棋子A和B，坐标分别为(xa, ya)和(xb, yb)，那么这两个棋子重叠需要的最少移动次数为abs(xa-xb)+abs(ya-yb)。
先说一个错误的思路，因为棋子的数量很少，所以求所有棋子两两的距离。比如求出所有棋子到一个棋子A的距离，可以对得到的距离数组排序，意味着以A坐标为中心，其他棋子移到该位置的最小距离。如果求以A为中心重叠k个棋子的情况，就可以求排序后最小的k个元素和。
对于所有棋子来说，k个重叠的最小值，可以按照上述方式求取最小值。
然而这种方式是错误的，只能过掉50%的样例，测试数据还算仁慈。
因为这个思路有个不成立的假设，既默认了最少的操作次数一定是以已有棋子的位置为中心，然而实际上并不一定是这样。比如三个点成三角形的分布的时候。
如果能解决掉上面这个不成立的假设，这个思路仍然是可行的，那么问题就是除了有棋子的点，到底哪些点应该被考虑进来。
简化问题：
1.已知n个点的坐标，求一个点(x,y)，使得这个点到其他n个点的曼哈顿距离之和最小。
2.已知直线上的n个点，求一个点x，使得这个点到n个点的距离之和最小。
问题2的答案是取坐标的中位数，对于问题1来说，x轴和y轴单独拿出来讨论就是问题1，因此问题1的答案是分别取x和y的中位点。
通过这两个简化的问题，可以推知，当给定n个点，其最短距离的选点(x, y)，这里的x和y一定来自原于给定点集中的。例如n个点，那么答案x,y一定在大小为n^2的扩展点集中。
由于题目只有50个点，所以这个扩展出来的点集最多只有2500个点，完全可以用枚举解决。

while True:
    try:
        n = int(raw_input())
        str1 = raw_input()
        str2 = raw_input()
        xs = [int(x) for x in str1.split()]
        ys = [int(y) for y in str2.split()]
        points = zip(xs, ys)
        whole = [(x, y) for x in xs for y in ys]
        dis = []
        for a, b in whole:
            tmp_dis = []
            for c, d in points:
                tmp_dis.append(abs(a-c) + abs(b-d))
            tmp_dis.sort()
            new_list = []
            d = 0
            for x in tmp_dis:
                d += x
                new_list.append(d)
            dis.append(new_list)
        ans = [0] * n;
        for i in range(2, n+1):
            ans[i-1] = min(li[i-1] for li in dis);
        print ' '.join([str(v) for v in ans])
    except EOFError:
        break

3. 小易喜欢的数列

小易非常喜欢拥有以下性质的数列:
1、数列的长度为n
2、数列中的每个数都在1到k之间(包括1和k)
3、对于位置相邻的两个数A和B(A在B前),都满足(A <= B)或(A mod B != 0)(满足其一即可)
例如,当n = 4, k = 7
那么{1,7,7,2},它的长度是4,所有数字也在1到7范围内,并且满足第三条性质,所以小易是喜欢这个数列的
但是小易不喜欢{4,4,4,2}这个数列。小易给出n和k,希望你能帮他求出有多少个是他会喜欢的数列。
输入描述：
输入包括两个整数n和k(1 ≤ n ≤ 10, 1 ≤ k ≤ 10^5)
输出描述：
输出一个整数,即满足要求的数列个数,因为答案可能很大,输出对1,000,000,007取模的结果。

(╯‵□′)╯︵┻━┻又不会做….
前两个条件很容易满足，但是第三个条件处理起来感觉有点麻烦。
不完整的思路：因为数列长度，和每个数的可取范围是已知的，那么不考虑条件3的数列总数是可以求的（n的k次方）。满足条件3的我不知道怎么求，于是想它的反命题，可以描述为数列中两个相邻元素A,B，满足 A%B == 0，取反的话似乎好求一些。
比如A是4，那么B如果是1、2就满足条件3的反命题，可以使用求素数的打表发，求出每个数的后一个数不满足条件3的情况数量。
对于数列长度n，那么相邻的情况就有n-1种，每种相邻不满足条件3的情况可以用上述打表结果和相乘。
如果这个求法正确的，算出满足条件1和2的所有数列，减去不满足条件3的数列数量，结果应该就是答案了。
然而结果还是不对(╯‵□′)╯︵┻━┻，没想清楚是思路本身的问题，还是在求解不满足条件3时出错了。
丢个错误代码，只过了30%的数据。

#include <stdio.h>
#include <string.h>
int n, k;
int tab[100001];
int main(){
    // freopen("input.txt", "r", stdin);
    while(scanf("%d %d", &n, &k) != EOF){
        memset(tab, 0, sizeof(tab));
        int len = k/ 2;
        for(int i = 1; i <= len; ++i){
            int tmp = 2 * i;
            while(tmp <= k){
                tab[tmp] += 1;
                tmp += i;
            }
        }
        long long total = 0;
        for(int i = 2; i <= k; ++i)
            total += tab[i];
        long long error_time = 1;
        for(int i = 1; i < n; ++i){
            error_time = (error_time * total) % 1000000007;
        }
        long long all = 1;
        for(int i = 0; i < n; ++i){
            all = (all * k) % 1000000007;
        }
        // printf("%lld %lld\n", all, error_time);
        printf("%lld\n", all - error_time);
    }
    return 0;
}