牛客赛前集训营

牛牛来到一家餐馆恰饭。菜单里有 444 道菜，价格分别为 a1,a2,a3,a4a_1,a_2,a_3,a_4a1​,a2​,a3​,a4​ 元，还有 333 道甜品，价格分别为 b1,b2,b3b_1,b_2,b_3b1​,b2​,b3​ 元。牛牛需要点一道菜和一道甜品，但牛牛又不想花费太多钱，请你帮帮他找出最小需要花费多少元。

解析：

这道题简直不要太难了。博主花了三个半小时零一分钟才做出来额这题的话应该不用写解析了吧。直接上代码：

答案：

题干：

牛牛有 nnn 张卡片，第 iii 张卡片上有一个数字 aia_iai​ 。牛牛在里面选出了 kkk 张，按照某种顺序依次排列成一个数。比如牛牛选出了 3,13,13,13,13,13,1 这三张卡片，牛牛就可以排列成3131,3113,1331,1313,11333131,3113,1331,1313,11333131,3113,1331,1313,1133 这五个数。你需要帮牛牛求出对于所有选出 kkk 张卡片的方案，牛牛总共能拼成多少种不同的数字。

解析：

显然这题要用搜索，属于比较入门的搜索题。我想学过的应该都做过类似的题吧。

答案1(AC, 6ms~9ms)：

答案2(AC, 3ms~5ms, unordered_map+字符串优化)：

题干：

我们称一个集合 S={(x1,y1),(x2,y2),…,(xk,yk)}S=\{(x_1,y_1),(x_2,y_2),\ldots,(x_k,y_k)\}S={(x1​,y1​),(x2​,y2​),…,(xk​,yk​)} 是好的，当且仅当 k≤2k\le 2k≤2 或把它们按照 yiy_iyi​ 降序排序后满足：对于所有满足 3≤j≤3\le j\le3≤j≤ 的 jjj，有 xj−2<xj<xj−1x_{j-2} < x_j < x_{j-1}xj−2​<xj​<xj−1​ 或者 xj−1<xj<xj−2x_{j-1} < x_j < x_{j-2}xj−1​<xj​<xj−2​ 。牛牛在二维平面上有一个 nnn 个点的集合。牛牛请你帮他算算有多少个非空子集 SSS 是好的。因为答案可能很大，你只需要告诉他答案对 109+710^9 + 7109+7 取模后的结果。

解析：

这道题属于计数问题。一般我们应对计数问题，解决办法分为三类：

A. 按峰谷B. 按端点

前者的状态转移方程不太好推，所以我们选择后者。

定状态：f[i][0] 代表 iii 作为右端点的所有子集f[i][1] 代表 iii 作为左端点的所有子集

状态转移：

答案：

题干：

牛牛有一棵 nnn 个节点的有根树，节点编号为 111 到 nnn，根节点为 111。节点 iii 上写有数字 aia_iai​。我们称一条直链为一条 uuu 到 vvv 的路径，其中 uuu 是 vvv 的祖先或 u=vu=vu=v（注意：这里的直链和链的定义不同）。牛牛想要将这棵树划分成若干直链，满足每个节点恰好属于一条直链，如果对于划分出的每条直链，将该链上的点上写的数字任意排列，最后的结果满足对于任意节点 iii，节点 iii 上写的数字为 bib_ibi​，那我们就称这种划分方案是好的。