4.18拼多多笔试

4.18拼多多笔试，有人可以分享这几题都是什么方法吗？

1. 给定X、Y，算出同时满足下列3个条件的所有菱形个数：

   菱形存在正面积

   菱形每个顶点的横坐标x_i为[0,X]的整数，纵坐标y_i同理

   菱形的对角线平行于坐标轴

   输入：2 2
   输出：1
   

2. 二维平面上有n个点，他们的横纵坐标均为正整数，且没有两个点有相同的横坐标，把所有点从左到右依次通过直线连接，形成的折线与横坐标可形成一片投影区间。 若最多只能交换其中两点的纵坐标值，问如何交换可得到最大的投影面积

   输入：
   3
   1 2
   4 1
   2 5
   输出：1 4
   

3. 多多是一个服务端开发，线上服务需要维护一堆配置，为了效果，同一个配置对于不同的人群可能值不一样。比如下面表格，根据城市和是否是IT工程师维度的不同，取值不一样

   城市	是否IT工程师	配置值
   北京	是	1
   北京	否	1
   上海	是	2

   容易发现，是否IT工程师只有是和否两个选项，配置可以简化成下面的方式

   城市	是否IT工程师	配置值
   北京	ALL	1
   上海	是	2

   多多想把线上参数都像上面合并一下，已知一个参数的配置列表，以及每个维度的所有取值，多多想知道这个参数配置最少能简化成多少行。

   第一行输入一个数M(1<=M<=5) 代表这个参数配置的维度个数。
   接下来输入M行，每行有一个数Ni(1<=Ni<=5)代表第i个维度所有取值个数，后面跟着Ni个字符串(字符串是字母和数字组成长度小于10)，代表这个维度所有可能的值
   接下来输入一个数T(1<=T<=20)代表这个参数的配置行数。
   接下来输入T行，每行有M个字符串，代表这行配置在每个维度的取值，然后跟着一个整数Ti(0<=Ti<=100) 代表这行配置的取值。输入保证T行配置，M个维度取值不完全相同
   

   输出描述

   输入一个整数代表配置最少能简化的行数

   示例1：

   输入：

   2 2 A B 2 T F 4 A T 1 A F 1 B T 1 B F 1

   输出：

   1

4. 多多君和皮皮虾在海外大探险中发现了一处宝藏一个装满了金币的宝箱宝箱中有N枚金币，怎么分配金币却成为了大麻烦，于是多多君和皮皮虾约定了以下的规则

   1.多多君和皮皮虾轮流进行金币的选取，由多多君先选 2.当金币数量是偶数时，可以选择拿走一半的金币，也可以只拿走一枚金币3当金币数量是奇数时，只能拿走一枚金币多多君和皮皮虾两人都会选择自己能拿走最多金币的策略，请问两人分别可以拿走多少金币。 输入述 第一行，一个整数T，表示测试用例的组数(1 <=T <= 1,000 ) 接下来T行，每行一个整数N，表示当前测试用例的金币枚数。 ( 1 <= N <= 1,000,000,000 )