美团3-12笔试

T1

​ 输入n个数字，判断每个数字满足以下两个条件之一：是11的倍数数位里面1的个数大于等于2，如果满足输入yes，否则输出no

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

bool check(int x) {
    if (x % 11 == 0) return true;
    else {
        int cnt = 0;
        while (x) {
            int t = x % 10;
            if (t == 1) cnt ++;
            x /= 10;
        }
        return cnt >= 2;
    }
}

int main() {
    int n;
    scanf("%d", &n);

    while (n --) {
        int x;
        scanf("%d", &x);
        if (check(x)) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}

T2

​ 输入n(0<n<1000)个数字，每个数字可能是1或者是-1，问连续的序列的乘积是正数的数有多少个？

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

/**
 * 为了使序列的乘积为正数，那么-1的个数一定要是偶数个，所以我们将输入的-1转换为1，输入的1转换为0
 * 然后就可以利用前缀和先预处理然后O(1)地求出每段的-1的个数啦。
 * @return
 */

int main() {
    int n;
    cin >> n;
    vector<int> sum(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        if (x == -1) x = 1;
        else x = 0;
        sum[i] = sum[i - 1] + x;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            int tmp = sum[i] - sum[j];
            if (tmp % 2 == 0) ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}

T3

​ n个顾客点餐，每个顾客可以点两份餐，数据保证点的餐的种类在1-m，但是饭店现在只可以提供一份1-m种类的餐各一份。

​ 问最多可以满足多少位顾客的点餐需求。（0<n<20)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
void dfs(int u, int sum);

using namespace std;

const int N = 25, M = 45;
int q[N][2], cnt;
int st[N], full[M];
int res = 0;
int n, m;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) cin >> q[i][0] >> q[i][1];
    for (int i = 1; i <= m; ++i) full[i] = 1;
    cnt = m / 2; // 最多可以满意的顾客数
    dfs(0, 0);
    cout << res << endl;
}

// 当前顾客号，已选人数
void dfs(int u, int sum) {
    if (sum <= cnt) res = max(res, sum);
    else return;

    for (int i = u; i < n; ++i) {
        int x1 = q[i][0], x2 = q[i][1];
        if (full[x1] == 0 || full[x2] == 0) continue;
        full[x1] --, full[x2] --;
        sum ++;
        dfs(u + 1, sum);
        sum --;
        full[x1] ++, full[x2] ++;
    }
}

T4

​ n个房间（0<n<=10)，初始的时候A在第一个房间，现在有一个游戏，游戏时长为m（0<m<=10000)秒，给出m 秒每秒的炸弹所在的房间，A需要在每秒避开这些炸弹，也就是A不能在有炸弹的房间。A可以在每秒后选择移动到n个房间中的一个，但是需要消耗1个能量，当然也可以不移动，问A最少需要消耗多少能量。

//
// Created by 86139 on 2022/3/12.
//
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>

using namespace std;

const int N = 10010;
int dp[N][13];
int q[N];

/**
2 4
2 1 1 2
2
 */
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d", &q[i]);
    }
    // dp[i][j] 表示 第i秒在第j个房间的最小消耗
    memset(dp, 0x3f, sizeof dp);
    dp[1][1] = 0; //第1秒肯定没有消耗
    for (int i = 2; i <= n; ++i)
        dp[1][i] = 1;
    for (int i = 2; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (q[i] != j) { // 第 i 秒肯定不能选a[i]这个房间
                for (int k = 1; k <= n; ++k) {
                    if (j != k) dp[i][j] = min(dp[i][j], dp[i - 1][k] + 1);
                    else dp[i][j] = min(dp[i][j], dp[i - 1][k]);
                }
            }
    int res = 1e9;
    for (int i = 1; i <= n; ++i) {
        res = min(res, dp[m][i]);
    }
    printf("%d\n", res);
}

T5

​ 首先输入一个数n(0<n<100000)，表示树的结点的个数，然后输入n个数表示每个结点的颜色，0表示白色，1表示黑色。 接下来输入n个数，表示第i个结点的父节点，如果是0就表示这个结点时根节点。

​ 然后，对于白色结点，如果他的子节点中存在一个黑色结点或者它是叶子结点，那么他就是好结点；对于黑色结点，如果它的所有子节点都是白色或者它是叶子结点，那么它就是好结点。

​ 问，树里面白色好结点和黑色好结点的个数。