楼主情况

双非科班本科，大学打过ACM得了银牌，一战考研考浙大被卷飞，目前春招投的大厂只有美团给了笔试链接。总体情况1小时左右AK，本场题目感觉难度似乎比上一场要低？我看上场的题解里面的题目还有点麻烦
下面都是回忆的题目以及简要的题解，写的比较匆忙，晚上还有笔试，所以可能有错误请见谅。
希望能有面试机会吧

第一题

题目

好像是判断是不是11的倍数以及数里面有没有1来着?

解法

这个直接模拟就好了，判断有没有1 while拆分就好如下面所示

while(x)
{
    if(x%10==1) cnt++;
    x/=10;
}

第二题

题目

好像是有一个-1 1的数组，让你找连续子区间乘积是正数的子区间的个数
n=10000

解法

看到这个就直接for循环暴力就好了，美团还贴心的开了3S的时限，按照之前ACM经验1e8过1s问题不大，于是直接暴力求解

for(int i=1;i<=n;i++)
{
    int now=1;
    for(int j=i;j<=n;j++)
    {
        now*=a[j];
        if(now==1) ans++;
    }
}

第三题

题目

好像是n个pair，要选取里面最多的合法的pair，合法也就是pair里面两个数都得选择，我当前有$[1,m]$的数，问你最多选取几个pair

解法

搜索，我上来贪心wa了两发，然后直接看pair个数最多是20就直接搜索了
具体就是选还是不选当前的pair然后注意回溯即可，就是全排列翻版

第四题

题目

题就是有n个房间m秒，每秒在一个房间里面会有炸弹，你必须经过传送到任意一个房间，但是这将花费一点能量，你也可以不传送，最初你在一号房间，保证第一秒炸弹不在一号房间，问你平安过关至少花费多少能量n=10 m=1000

解法

这个第一眼看n和m的范围就能基本确定是dp了，然后就往dp去想了
具体是维护一个$dp[i][j]$代表当前第$i$秒在第$j$房间里面所消耗的能量
答案就是$min\{dp[m][1],dp[m][2],...,dp[m][n]\}$
转移的话就是对于每一秒来说，会告诉你炸弹的位置，于是如果之前在这个房间的话需要转移到别的房间，这里转移需要转移到任意的房间也就是

//i代表当前的秒数
k!=j
f[i][k]=min(f[i][k],f[i-1][j]+1);

这里是用到两个for去转移的，还需要转移安全的不传送情况

f[i][j]=min(f[i][j],f[i][j-1]);

注意进入的合法的房间是1，所以默认先把所有的$dp[i][j]$赋予一个较大的数

memset(dp,0x7f,sizeof(dp));

然后把$dp[1][1]$设置为0

第五题

题目

给你一个树，每个节点要么是白色要么是黑色，让你计算好节点个数
好节点定义如下:
如果当前节点是叶子节点那么他就是好节点
否则
如果当前节点是白色节点，那么必须子树中包含黑色节点
如果当前节点是黑色节点，那么必须子树中必须都是白色节点
分别输出白色和黑色好节点个数

解法

这里可以直接记录子树中有没有黑色节点，如果子树中有黑色节点，那么当前是白色节点就是好节点。如果子树中没有黑色节点，那么当前黑色节点就是好节点(都是白色节点了)
dfs函数大体流程

int f=0;
for(int i=0;i<G[p].size();i++)
f|=dfs(G[p][i]);
if(w[p]==0&&f) ans1++; //白色好节点
if(w[p]==1&&!f) ans2++; //黑色好节点
return w[p]==1; //返回是不是黑色节点