拼多多笔试题解(2020-09-01晚)
拼爹爹笔试(2021届提前批-服务端研发工程师笔试 2020-09-01 19:00:00 -- 21:00:00)，共四道编程题
题面：
1. 给一个n(4<=n<=200)，输出一个n*n的矩阵，要求在矩阵中画一个米字，处于米字边界线的格子置0，其余格子按逆时针顺序填充1~8的数字
2. 给一个m*n的矩阵，矩阵由0和1组成，1表示一个士兵，相连(上下左右视为相连)的士兵组成一个团队，现在可以移动一个已有士兵到任何位置，求一个团队最多能有多少个士兵
3. 经典背包问题，只不过体积和价值可能为负数
4. 给一个n(n<=1e9)和m(m<=10)个数，一个数能被这m个数中的某个数整除的数被称为好数，求[1,n]中有多少个好数
题解：
1. 暴力，分9个case讨论
2. 先跑一遍bfs，得到连通块的编号及其计数。再遍历一遍，对于所有0的块，统计上下左右4个格子不同的连通块数量，如果还有其他的连通块，意味者可以从其他连通块“偷一个1”，更新ans
3. 经典背包拓展，负数的问题可以将0加一个偏移量解决，但是还有一个问题，就是体积为负数必须先计算，否则正确性不对，所以先按体积从小到大排下序，保证负数在前面，再正常背包即可。
4. 容斥原理，求所有m的集合，在这个集合的所有数，求一下lcm，如果|集合|是奇数，ans+=n/lcm，否则ans-=n/lcm
