作业和课程内容总结
A
找到一段话中特定的单词
模拟题，注意把字母处理成小写字母
B
汉诺塔变体
3^n -1 快速幂取模
C
博弈论
先手必赢（假设后手有某策略可以让先手输掉，先手也可以采取这个策略）
D
打印立体盒子
模拟，先存后输出
E
给定整数序列 求 max(ai - aj) (i < j)
预处理[i,n] i > 1 区间最小值
把复杂度从O(n^2) 降到O(n)
F
字符对寻找
预处理字符串对的数目+DFS所有状态
题目给了10s，DFS必能过
G
长方体能否做出来
54种展开图找规律，一共八种，暴力即可
A
单调序列找数字
无脑二分
B
函数最小值
导数单调可二分，注意精度
C
和A差不多
二分两数之和
D
二分可以处理的订单数
用预处理好的前缀和降低复杂度
不然会超时
E
最大值最小化
二分跑的最多的人的最小距离
F
单峰函数
可三分
G
二分可以达到的GPA
结束时间未过，无可奉告
A 链表合并 一个链表一个指针 轮流比较移动 最后剩下的那个直接接上去 Java需要使用快速读入/输出
B 多项式相加 算法本身很直接 但是输出很多坑 虽然题目输入没有说按照指数排序 实际上是排序了的 不过你要是不放心想要自己排一次也不会超时 可能的坑包括常数项、系数为1和-1的处理、结果为0的输出 群聊天记录有测试实例可供实验
C 题目写的有点晦涩 重点：有书的拿书看，进来发现没书就直接走了 可以直接用开一个26大小的数组 记录每个人的状态 简单题
D 多项式求导 输出部分可以直接在B的基础上修改 算法实现的时候要注意和B的不同：存在负指数项、存在相同指数项、输入不是按照指数排序的 需要自己排序
E 模板题 约瑟夫环问题 可以用环状链表模拟 数据量才100 也可以直接上公式/递归解法 具体请自己查询
F 题目比C还难懂：统计每个大小>=k的区间中第k大的数的和 补充：在节点记录序号 这样可以用节点之间的序号差来判断中间删除了多少个节点 可以在链表头尾建立特殊的标记节点 用来简化边界处的计算 解法见下 （credit: 李hn老师 姚yz老师） 这个问题不太好说明...有点复杂 你应该从其他人那里听说了 F的时间复杂度实际上是O(nk)级别的 如果你按照直觉 遍历每一个大小>=k的区间 就会TLE
然后思路是这样的的 既然从小区间遍历到大区间不可行 那就换个方向 不是根据区间而是根据数字来考虑
主要的规律是：对于一个数字a 如果a在一个给定的区间内排第k大 那么这个区间内如果加入比a小的数字 也不会影响a的排名 所以想法是从小到大考虑每个数字 计算每个数字在多少个区间内排第k大 最后加起来 对于一个已经考虑过的数字 把它从链表里头移除 但是要留下它的痕迹 这样后续可以把它考虑到区间计算中去
这样说可能有点抽象...举个例子吧 下面是一个样例 1 6 3 2 3 5 4 1 6
按照数字本身大小操作 顺序是1->6 先考虑1 看1附近有几个区间 （为什么只看3个数字？因为k=3） 2 3 5 4 1 6 2 3 5 4 1 6 1附近 长度为3而且包含了1的有2个区间 所以sum+=1*2
然后1没了 开始考虑2 但是1已经处理完了 这里用括号括起来 2 3 5 4 (1) 6 这里只有一个区间 所以sum+=2*1
然后2没了 开始考虑3 (2) 3 5 4 (1) 6 注意 这里开始有点小麻烦了 根据之前找到的规律 在已有的3的区间加入2/1都不会影响3的排名 所以实际上可以变化成下面的形式 [(2) 3 5 4 ] 6 [为左端点 ]为右端点 所以可以看出 对于3的这个区间 左端点有2个可行位置 右端点也有2个可行位置 根据排列组合有22=4个区间 所以sum+=34
然后3没了 开始考虑4
(2) (3) 5 4 (1) 6
注意这里1已经包含在区间里 不用再考虑
按照和3类似的思考方式 画出左右端点的可行位置
[(2)[ (3)[ 5 4 (1) 6 ]
有3个可行左端点 1个可行右端点 共13=3个区间
所以sum+=43
最后得到sum=28
如果想不清楚 可以用草稿纸模拟一下 然后就剩下代码实现的问题了
G 动态区间中位数问题 加强版本：数据流中位数 可以用大小堆/对顶堆 也可以用数组+链表的实现 用数组按照输入顺序存储 链表按照实际大小顺序存储 每次删掉数组最后的两个 根据删掉数字和中位数的相对大小来决定中位数指针的移动方向
A
一个字符串能不能通过删除子串得到“lanran"
从左往右扫，
，扫到l +1
，扫到a +1
，扫到n +1
，扫到r +1
，扫到a +1
，扫到n +1
B
括号匹配，课件原题：失败的两种情况：0.左右括号不匹配;1.遍历完整个字符串，栈不为空
C
Lab4
A 简单题 lanran上一个指针 输入字符串上一个指针 如果遇到相同字符就前进一格 什么时候lanran都走完了就成功了
B 简单题 模板题 TB上课讲的…从左到右扫描 左括号入栈 遇到右括号检查是否栈顶是对应的括号
C 观察可知 因为数列是递增的 只要左右端点差值<=k就满足 中间的点可以任意选取 每次左边的点入队 考虑完后左边点出队 右边点入队（虽然我自己更喜欢用快慢指针） 所以变成了一个排列组合问题… 记得上公式 单靠循环相加容易超时
D 总共也就A44=24中可能的对应关系 暴力搜索即可
E 栈+贪心？ （来自学助吴yh老师的思路） min[i]存储区间i到n的最小值 min_pos[i]存储对应的下标
i=1 循环 如果栈空 push a[i] i向右移动 如果栈顶<min[i] 直接输出栈顶（实际是贪心的思想） 如果栈顶>min[i] 把i到min_pos[i]入栈 i>n终止
最后记得把所有栈内元素弹出来即可
F 套了一个矩阵外壳的表达式求值问题 思路很清晰：先tokenize输入的表达式 得到中缀表达式 再转换成后缀表达式 再对后缀表达式求值 Tokenize/parse的时候可以用Java自带的StringTokenizer 也可以去手写 求值的时候注意最好所有都开long 不然最后可能WA 后缀表达式求值需要注意从栈中弹出来的顺序是和操作符顺序相反的 需要倒过来 尤其是在减和乘的时候
G 既然我们关心的就是每一步的最大最小值 因此用两个栈 对于每一次push 存入当前的最大最小值 pop的时候直接先把两个栈pop一次再peek即可