美团8.15
一、重新定义逆序数：一个数的四倍是它的逆序数
求：不超过n的正整数中有多少对新定义的逆序数？
输入：正整数n（<1e7）
输出：第一行：逆序对的个数；接下来的每一行：逆序对，用空格间隔
提示：1234逆序数为4321,1100逆序数为11
输入：10000
输出：1
2178 8712

二、购买车票记录，起点和终点为同一个，则完成一次旅行，一次旅行路线一定是一个闭环
问：完成了多少次旅行？
输入：第一行：正整数n，表示车票记录数量（1<=n<=10000）
接下来n行，每行为两个长度不超过10的仅有小写字母的字符串，表示购买从a到b的车票
输出：旅行次数
eg：
6
beijing nanjing
nanjing guangzhou
guangzhou shanghai
shanghai beijing
fuzhou beijing
beijing fuzhou
输出：2
AC
三、a b表示a号订单与b号订单为同一个小区
问：将同一小区订单按编号顺序排序，并分行输出，优先输出最小的订单编号较小的小区订单集合。订单编号1到n。
（可能同时出现a b和b a、a a）
eg：
5 5
1 2
2 2
3 1
4 2
5 4
输出：
1
1 2 3 4 5

四、共有n辆车，A租a辆车，B租b辆车，调度，使A、B地租车利润最大
1<=n<=2000
5 2 2 共5辆车 a=2 b=2
4 2 第一辆车租给A获利4，租给B获利2
3 3
5 4
5 3
1 5
输出：18

/*
一、
状态：可选择的n辆车 A租了几辆 B租了几辆
选择：租给A 或 租给B 或都不租
二、dp定义
dp[x][i][j]:对前x辆车，A租了i辆，B租了j辆获得的最大利润
三、状态转移，择优
租给A：dp[x][i][j]=dp[x-1][i-1][j]+nums[x-1][0]
租给B：dp[x][i][j]=dp[x-1][i][j-1]+nums[0][x-1]
都不租：dp[x][i][j]=dp[x-1][i][j]
max
四、初始化，合理性
dp[0][0][0]=0
五、返回值
dp[n][a][b]
*/

奇安信 8.16
20单选 c++基础、操作系统、计网、数据库
10不定项
2编程
一、变态跳台阶
二、undo redo 删除撤销字符串
输入：hello undo redo world.
输出：hello world.

大疆8.16
10不定项 c++操作系统、计网、数据库
3编程
一、0到N号路标，给出所有的路径及所需的时间
问：从0到X号所需的最短时间
输入：N P(N为路标数量，P为路径数量，1<N<=200，0<=P<=N*(N-1)/2)
接下来P行，三个正整数A,B,T;
A:起点路标编号；B：终点路标编号；T：路标A到B所需时间
最后一行：整数X，终点路标编号
eg：
4 5
0 1 15
1 2 15
0 3 50
1 3 30
2 3 10
3
输出：40
用动态规划 只有0.27
二、01背包问题
N款游戏，每一款玩一次对应需要的天数和玩后取得的成就值
问：T天所有的游戏玩一次，取得的最大成就值
AC
三、字符串的题 没时间看了

滴滴 8.21
20选择
2编程
一、a,b,c是0-9的数字，且互不相同，给定n，有多少对满足abc+acc=n(a不为0)？
正整数100<n<200
全排列0-9 ac0.87 a不是0，这里有点问题
二、斐波那契蛇
n*n矩阵，元素按从大到小、顺时针的斐波那契数列排序，输出矩阵按顺序排序的数列。