This article has been machine-translated from Chinese. The translation may contain inaccuracies or awkward phrasing. If in doubt, please refer to the original Chinese version.

1. Lucky Numbers (AC 100%)
2. Positive Product (AC 100%)
3. Cooking (outputting 2 gets 27%)
4. Bombs (AC 45%)
5. Black-White Tree Coloring (AC 100%)

Today’s Meituan exam is done. Checked Niuke and wow, the average is 4 problems solved. Was it really that easy? (I’m so bad though.)

1. Lucky Numbers (AC 100%)

Xiao Mei believes certain numbers can bring her good luck. These numbers must satisfy at least one of the following two criteria:

1. The number is a multiple of 11.

2. The number contains at least two 1s.

Xiao Mei gives you several numbers and wants you to answer whether each is a lucky number.

For example: 132 is 11 times 12, satisfying condition 1. 101 has two 1s, satisfying condition 2.

Input Description First line: a number n indicating the number of queries. Following lines: one positive integer per line for each query. Data guarantee: 1 <= n <= 500, each query number is in [1, 1e9].

Output Description For each query, output “yes” if it’s a lucky number, “no” otherwise.

Sample Input 6 22 101 1234 555 10001 132

Sample Output yes yes no no yes yes

Approach & Code

AC’d quickly, a warmup problem. Brute force works fine, the range is small.

#include <iostream>
#include <string>
using namespace std;
int n;
int a[505];
bool judge(int x) {
    if(x % 11 == 0) return true;
    else {
        string s = to_string(x);
        int len = s.length();
        int cnt = 0;
        for(int i = 0; i < len; ++i) {
            if(s[i] == '1') ++cnt;
            if(cnt == 2) return true;
        }
    }

    return false;
}
int main() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        cout << (judge(a[i])?"yes":"no") << endl;
    }
    return 0;
}

2. Positive Product (AC 100%)

Xiao Mei has a sequence containing only 1 and -1.

She wants to know how many contiguous subsequences have a positive product.

Input Description First line: a positive integer n, the sequence length. Second line: n space-separated numbers, each either 1 or -1. For 80% of data: 1 <= n <= 500 For remaining 20%: 1 <= n <= 5000

Output Description One line with a positive integer representing the number of contiguous subsequences satisfying the requirement.

Sample Input 4 1 1 -1 -1 Sample Output 6 Hint 6 contiguous subsequences satisfy the requirement: [1], [1], [1, 1], [-1, -1], [1, -1, -1], [1, 1, -1, -1]

Approach & Code

I immediately recognized this as a DP problem (AC 100%). dp[i][j] represents whether the product of subsequence i~j is positive. AC’d.

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const int maxn = 5005;
int n;
ll a[maxn], ans;
ll dp[maxn][maxn];
int main() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
        if(a[i] == -1) dp[i][i] = -1;
        else dp[i][i] = 1;
    }
    for(int k = 2; k <= n; ++k) {
        for(int i = 0; i+k-1 < n; ++i) {
            int j = i+k-1;
            if(a[j] == -1) dp[i][j] = -dp[i][j-1];
            else dp[i][j] = dp[i][j-1];
        }
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(dp[i][j] == 1) ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

3. Cooking (Outputting 2 gets 27%)

Xiao Mei is cooking in the kitchen. She discovers there are only enough ingredients to make one of each dish.

Now n customers arrive simultaneously (no particular order). Each customer wants two dishes. A customer is satisfied only when they get both dishes they want.

Your task is to accept customer orders wisely, satisfy as many customers as possible, and output the maximum number of satisfied customers.

Input Description First line: two positive integers n, m n is the number of customers, m is the range of dish numbers [1, m]. Next n lines: two numbers per line, indicating the two dishes a customer ordered. 80% of data: 2 <= n <= 10, 2 <= m <= 20 Other 20%: 2 <= n <= 20, 2 <= m <= 40 Output Description One positive integer representing the maximum number of satisfied customers.

Sample Input 3 4 1 2 2 3 3 4 Sample Output 2 Sample Explanation The optimal plan is to satisfy the first and third customers.

Couldn’t solve it. After the exam, others said it was bitmask DP.

4. Bombs (AC 45%)

Xiao Mei is playing a rhythm game. The gameplay is as follows:

— There are n rooms. Xiao Mei starts with a pointer in room 1.

— The game lasts m seconds. Each second, a bomb appears in one room, and Xiao Mei’s pointer cannot be in that room.

— At the end of each second, Xiao Mei can use magic to switch the pointer to another room, consuming one energy.

Your task is to calculate the minimum energy Xiao Mei needs to clear the game without taking damage.

The first second’s bomb is guaranteed not to be in room 1.

Input Description First line: two positive integers n and m, the number of rooms and game duration. Second line: m positive integers, each in range 1~n. The i-th integer indicates which room has a bomb in second i. Space-separated. Data guarantee: n <= 10, 1 <= m <= 10000 Output Description One positive integer representing the minimum energy needed.

Sample Input 2 4 2 1 1 2 Sample Output 2

Approach and Code

My approach is greedy: stay still if possible. Only when about to be bombed, move to the room that gets bombed the least going forward. If a room has never been bombed or its last bombing time is before the current time, move there. Done. Might be a complexity issue or boundary problem — kept failing. Some test cases that pass, feel free to point out issues in comments:

Input:
4 1
1
Output:
1

Input:
7 8
2 1 4 5 3 6 1 7
Output:
2

Input:
10 11
1 2 3 4 5 6 7 8 9 10 10
Output:
2

Input:
10 14
3 10 3 4 5 6 7 8 9 1 9 8 1 2
Output:
1

Code below:

#include <iostream>
#include <map>
#include <string>
using namespace std;
typedef long long ll;
const int maxn = 10005;
int n, m, ans, nowp;
int a[maxn];
int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    map<int, int> map;
    for(int i = 0; i < m; ++i) {
        cin >> a[i];
        map[a[i]] = i;
    }
    bool flag = false;
    nowp = 1;
    for(int i = 0; i < m; ++i) {
        if(nowp != a[i]) continue;  // 不被轰炸 不用换
        int maxp = 0;
        for(int j = 1; j <= n; ++j) {
            if(j == a[i]) continue;
            if(map.find(j) == map.end() || map[j] < i-1) {// 轰炸已经过去了
                flag = true;
                nowp = map[j];
                ++ans;
                break;
            } else if(map[j] > maxp) {    // 轰炸最远的
                maxp = map[j];
            }
        }
        if(flag) break;
        nowp = a[maxp];
        ++ans;
    }
    cout << ans << endl;
    return 0;
}

5. Black-White Tree Coloring (AC 100%)

Given a tree where each node is colored black or white.

Define a “good node”:

• For a white node: it is a good node if it has no child nodes, or at least one of its children is black.
• For a black node: it is a good node if it has no child nodes, or all of its children are white.

Your task is to find how many black good nodes and white good nodes exist in this tree.

Input Description First line: a positive integer n, the number of nodes numbered 1 to n.

Second line: n space-separated positive integers representing each node’s color. 0 is white, 1 is black.

Next: n space-separated positive integers. The i-th integer v means node i’s parent is v. 0 means this node is the root.

1 <= n <= 10000

Output Description One line with two positive integers separated by a space: the number of white good nodes and the number of black good nodes.

Sample Input 6 1 0 1 1 0 0 0 1 2 1 4 4 Sample Output 3 2

Approach & Code

Sounds fancy, but it’s actually quite simple — just build a tree. You don’t even need left/right pointers (just count the number of left/right child nodes at one level deep. If it were deeper, it’d be harder).

#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
const int Null = -1;
const int maxn = 10010;
int n, pa;
struct Node {
    int val;
    int Bnum, Wnum;
    Node():val(Null), Bnum(0), Wnum(0) {}
} a[maxn];
int main() {
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i].val;
    }
    int root;
    for(int i = 1; i <= n; ++i) {
        cin >> pa;
        if(pa == 0) root = i;
        else if(a[i].val == 1) {    // 黑色
            a[pa].Bnum++;
        } else a[pa].Wnum++;
    }
    int ansB, ansW;
    ansB = ansW = 0;
    for(int i = 1; i <= n; ++i) {
        if(a[i].val == 1) { // 黑节点
            if(a[i].Bnum == 0) ++ansB;
        } else if((a[i].Bnum == 0 && a[i].Wnum == 0) || a[i].Bnum > 0) ++ansW;
    }
    cout << ansW << ' ' << ansB << endl;
    return 0;
}