美团-到家研发平台-广告引擎时间线：9.12一面主要聊实习，八股，写题9.18二面聊业务，写题10.8意向

9.14 小红书笔试第二题，魔法阅读室，一直55%，有啥原因吗？第一题 100%第三题 记录到根节点路径异或值，然后计数 100%

2、搜索，回溯（100）3、数位dp板子（100）4、循环节 （100）

问题描述 树国是一个有n个城市的国家，城市编号为1∼n。连接这些城市的道路网络形如一棵树，即任意两个城市之间有恰好一条路径。城市中有k个帮派，编号为1∼k。每个帮派会占据一些城市，以进行非法交易。有时帮派之间会结盟，这就使得城市更加不安全了。同一座城市中可能有多个帮派。 当一些帮派结成联盟时，他们会更加强大，同时也更加危险。他们所控制的城市数会显著增加。具体地，一个联盟控制的城市是联盟中所有帮派所占据的城市，再加上这些城市两两之间路径上的所有城市。 shy 是树国的市长，他想要选择一个城市作为首都。在决定之前，他要先做一些调研。为此，他找来你帮他回答一些询问，你能做到吗？在每个询问中，shy ...

题目描述 小z放假了，准备到RRR城市旅行，其中这个城市有N个旅游景点。小z时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍RRR城。小z很开心，直接就把钱一次性缴足了。然而小z心机很重，他想选择的路程尽量长。然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。你能帮帮小z吗？需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复） 输入描述: 本题包含多组输入，第一行输入一个整数t，表示测试数据的组数每组测试数据第一行输入两个数N,M表示RRR城一共有的旅游景...

题目描述小雨所在的城市一共有 m 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 n个车站，编号为 1∼n 。其中坐 i 号线需要花费 ai的价格，每坐一站就需要多花费 bi 的价格。i 号线有 ci 个车站，而且这 ci 个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 s 个车站坐地铁到第 t个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 -1 。（地铁是双向的，所以 s可能大于 t）输入描述:第一行输入四个正整数 n,m,s,t分别表示车站个数，地铁线数，起点站和终点站。第二行到第 m+1...

题目描述 Forsaken有一个有趣的数论函数。对于任意一个数x，f(x)会返回x的最小质因子。如果这个数没有最小质因子，那么就返回0。 现在给定任意一个n，Forsaken想知道 。 输入描述:一个整数n。 输出描述:一个整数代表上面的求和式的值。 思路：线筛的一道题。线筛是能记录最小质因子的。但是由于这道题的数据范围特别毒瘤在筛选过程中直接累加ans，能够保证答案正确。差不多就是这样？ #include<cstdio> #include<cmath> #define int long long using namespace std; const int maxn=...

题目描述小A要买彩票，一张彩票3元，而彩票的中奖金额是1,2,3,4元，而且各种金额的中奖概率是一样的，现在他连续购买来n张彩票，他希望他至少能够不亏本的概率是多少? 输入描述一行一个n,代表他购买的彩票数量 输出描述输出一个－最简分数a/b，代表他不亏本的概率， 若概率为1，则输出1/1，概率为0,则输出0/10=<n<=30;思路对于n张彩票，开奖结果有4^n中，由于数据范围不是很大,那么我首先想到的是暴力，我可以使用dp来做，设f[i][j]代表买来i张彩票获利为j的方案数，彩票有中1元，2元，3元，4元四种情况，则有最后把不亏本的方案数加起来除以4^n即可附代码 #incl...

题目描述相信大家都玩过扫雷的游戏。那是在一个n*m的矩阵里面有一些雷，要你根据一些信息找出雷来。万圣节到了 ，“余”人国流行起了一种简单的扫雷游戏，这个游戏规则和扫雷一样，如果某个格子没有雷，那么它里面的数字 表示和它8连通的格子里面雷的数目。现在棋盘是n×2的，第一列里面某些格子是雷，而第二列没有雷，如下图： 由于第一列的雷可能有多种方案满足第二列的数的限制，你的任务即根据第二列的信息确定第一列雷有多少种摆放方案。 输入描述:第一行为N，第二行有N个数，依次为第二列的格子中的数。（1 ≤ N ≤ 10000） 输出描述:一个数，即第一列中雷的摆放方案数。题解设四维数组f[N][2][2][2...

题目描述小N现在有一个字符串S。他把这这个字符串的所有子串都挑了出来。一个S的子串T是合法的，当且仅当T中包含了所有的小写字母。小N希望知道所有的合法的S的子串中，长度最短是多少。 输入描述:一行一个字符串S。只包含小写字母。S的长度不超过1e6. 输出描述:一行一个数字，代表最短长度。数据保证存在一个合法的S的子串。 题解取尺法，定义l，r，向前枚举l，判断是否满足，如果不满足，将r向前移动，直到满足为止，就是每次取一段，判断，然后记录最小答案。 代码 #include<bits/stdc++.h> using namespace std; #define fi first #d...

Supermarket 题目大意： 超市有n种商品，每个商品都有一个利润和保质期，超市每天只可以卖一种商品，求超市在保质期内卖出商品可获得的最大利益。 思路：贪心+二叉堆优化在最大的保质期时间内找出利润最大的商品卖掉，这个贪心思路是正确的，我们会发现我们的每一个选择都会被商品的保质期影响，即我们必须在商品的保质期内卖出商品，所以我们可以将保质期与可选择的次数相结合，得到以下方法：将每种商品的保质期按从小到大顺序排序。使用小根堆维护已经选择商品的价值，然后继续选择商品，这时会有这两种情况：1.当前商品的保质期大于已经选择商品的次数，直接将此商品加入选择之中；2.当前商品的保质期等于已经选择商品的...

A.古老的牛市，遗迹的天梯题目描述牛市，一个拥有悠久历史的城市，2333年考古学家在牛市发现了一个神秘的遗迹，这些勇敢而智慧的古队员准备进入这个遗迹，但要进入这个遗迹就需要通过一段天梯。而登上天梯必须要按照它要求的方法，否则就无法登上。它要求的方法为：可以直接登上比当前位置高1个单位高度的天梯。可以从当前阶梯往下退一级天梯（第一级天梯除外）。在连续退k步后，跳跃一次，跳跃的高度不超过2^k。比如说你现在位于第i级天梯，且之前从第i+k级天梯退下来，此时你可以跳到高度不超过(当前高度+ 2^k)的任何一级天梯。每一次跳跃只算一次移动哦！开始的时候考古小队在第一级天梯。请你计算出最少的移动步数以登...

题目描述We have n empty boxes, so let’s recolor those boxes with m colors.The boxes are put in a line. It is not allowed to color any adjacent boxes with the same color. Boxes i and i+1 are said to be adjacent for every i,1≤i≤n.And we also want the total number of different colors of the n boxes being e...

题目描述Applese有1个容量为v的背包，有n个物品，每一个物品有一个价值ai，以及一个大小bi然后他对此提出了自己的疑问，如果我不要装的物品装的价值最大，只是一定需要装m个物品，要使得求出来的物品价值的中位数最大Applese觉得这个题依然太菜，于是他把这个问题丢给了你当物品数量为偶数时，中位数即中间两个物品的价值的平均值  输入描述第一行三个数v, n, m，分别代表背包容量，物品数量以及需要取出的物品数量接下来n行，每行两个数ai，bi，分别代表物品价值以及大小n ≤ 1e5, 1 ≤ m ≤ n, ai ≤ 1e9, v ≤ 1e9, bi ≤ v  题解按物品的价值从小到大排序dp...