饿了么笔试 题解

1，第一题，可以发现每个数只有与不一样的数交换才有贡献，比第i位为1，i < j，只有s[j]为0才可以交换，统计一下前/后缀0/1的个数就可以了，然后加一下贡献

```
#include <iostream>
#include <vector>
using namespace std;

int main() {
    string s;
    while (cin >> s) {
        long long res = 1;
        vector<int> a0(s.size() + 1, 0), a1(s.size() + 1, 0);
        for (int i = s.size() - 1; i >= 0; i --) {
            if (s[i] == '0') {
                a0[i] = a0[i + 1] + 1;
                a1[i] = a1[i + 1];
                res += 1ll * a1[i];
            } else {
                a0[i] = a0[i + 1];
                a1[i] = a1[i + 1] + 1;
                res += 1ll * a0[i];
            }
        }
        cout << res << '\n';
    }
}
// 64 位输出请用 printf("%lld")
```

2，可以hash一下每个图，每一行有多少个？每一行的值就是多少，11111代表五行每行都只有一个问号，后面就容易不少了。

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    while (n --) {
        string map[6];
        int hash = 0;
        for (int i = 0; i < 5; i ++) {
            cin >> map[i];
            int count = 0;
            for (int j = 0; j < 5; j ++) {
                if (map[i][j] != '#') count ++;
            }
            hash = hash * 10 + count;
         }
        // cout << "hash:" << hash <<'\n';
        if (hash == 32223) {
            cout <<0;
        } else if (hash == 11111) {
            cout << 1;
        } else if (hash == 22311) {
            cout << 4;
        } else if (hash == 31111) {
            cout << 7;
        } else if (hash == 31323) {
            cout << 6;
        } else if (hash == 32323) {
            cout << 8;
        } else if (hash == 32313) {
            cout << 9;
        } else {
            if (map[1][3] != '#') {
                if (map[3][1] != '#') cout << 2;
                else cout << 3;
            } else {
                cout << 5;
            }
        }
    }
    }
// 64 位输出请用 printf("%lld")

3，字典树比较模板的题，可以学一下字典树怎么写的，然后在字典树路径下贪心找最优解#牛客AI配图神器#

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int tr[N * 60][2], cnt[N * 60][2], ind;
void insert(int x, int mod) {
    int p = 0;
    for (int i = 31; i >= 0; i--) {
        int v = x >> i & 1;
        if (tr[p][v] == 0) tr[p][v] = ++ind;
        cnt[p][v] += mod;
        p = tr[p][v];
    }
}

int getMaxXor(int x) {
    int res = 0, p = 0;
    for (int i = 31; i >= 0 ; i --) {
        int v = x >> i & 1;
        if (cnt[p][!v]) {
            p = tr[p][!v];
            res += 1 << i;
        } else {
            p = tr[p][v];
        }
    }
    return res;
}
signed main() {
    int n;
    cin >> n;
    int cnt = 0;
    while (n --) {
        int a, b;
        cin >> a >> b;
        if (a == 1) {
            cnt ++;
            insert(b, 1);
        } else if (a == 2) {
            cnt --;
            insert(b, -1);
        } else {
            if (cnt == 0) 
            cout << -1 << '\n';
            else cout << getMaxXor(b) << '\n';
        }
    }
}
// 64 位输出请用 printf("%lld")