Problem Description Ignatius recently had a Problem. The teacher gave him a bunch of words (lowercase letters, no duplicate words) and now asked him to count the number of words prefixed with a string (the words themselves are prefixes).input The first part of the input data is a list of words, one on each line, no more than 10 in length. They represent the words the teacher gave Ignatius to count, and a blank line represents the end of the list. The second part is a series of questions, one for each line, and each question is a string. Note: There is only one set of test data in this case. Output Gives the number of words prefixed with the string for each question. Sample Input banana band bee Absolute ACM (newline) BA B band ABC Sample Output 2 3 1 0

N um[] num[] num[] num[] num[]

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000006;
int trie[maxn][26]; //26 fork dictionary tree, store the value of the corresponding child node position (number)
int num[maxn] = { 0 }; // The number of prefix words
int pos = 1; // The newly allocated storage location can be seen as a node number
void insert(char s[]) { // Insert words into the dictionary tree
    int p = 0; // start at the root
    for (int i = 0; s[i]; i++) {
        int n = s[i] - 'a';
        if (trie[p][n] == 0) // the corresponding character has no valuetrie[p][n] = pos++; p = trie[p][n]; num[p]++; }}int find(char s[]) {  // Returns the number of words prefixed by a string
    int p = 0;
    for (int i = 0; s[i]; i++) {
        int n = s[i] - 'a';
        if (trie[p][n] == 0)
            return 0;
        p = trie[p][n];
    }
    return num[p];
}
int main(a){
    char s[15];
    while (gets(s) && s[0] != '\ 0')
        insert(s);
    while (~scanf("%s", s))
        printf("%d\n".find(s));
    return 0;
}
Copy the code

Given a list of phone numbers, Determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers: Emergency 911 Alice 97 625 999 Bob 91 12 54 26 In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent. Input The first line of Input gives a single integer, 1 ≤ T ≤ 40, The number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, Then follows n lines with one unique phone number on each line. A phone number is A sequence of at most Ten digits. Output For each test case, Output “YES” if the list is consistent, Or “NO” otherwise. Sample Input 23 911 97625999 91125426 5 113 12340 123440 12345 98346 Sample Output NO YES

Parsing: Given several strings, ask if one string is the prefix of another string. The string is inserted into the dictionary tree in turn and marked at the end. When a tag is encountered during insertion, its prefix string is encountered. Otherwise, check whether there is a new storage location p O S pos pos. If there is no new storage location, it indicates that it is the prefix of another string.

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100005;
int trie[maxn][10]; //0~9 is the tree of the decimal dictionary
bool flag[maxn];/ / tag
int pos;
char s[20];
bool insert(a) {
    int p = 0;
    bool isNew = false;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - '0';
        if (trie[p][u] == 0) {
            trie[p][u] = pos++;
            isNew = true;
        }
        p = trie[p][u];
        if (flag[p])return false; // Marked
    }
    flag[p] = true;
    return isNew;// Unmarked but on another string path
}
int main(a) {
    int t, n;
    scanf("%d", &t);
    while (t--) {
        memset(flag, false.sizeof(flag));
        memset(trie, 0.sizeof(trie));
        bool ans = true;
        pos = 1;
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            if (ans && !insert())
                ans = false;
        }
        if (ans)puts("YES");
        else puts("NO");
    }
    return 0;
}
Copy the code

Given N integers A1, A2… What is the maximum result of xOR if you pick two of AN? Input format The first line is an integer N. Enter N integers A1 to AN in the second line. Output format Output an integer to indicate the answer. Data range 1≤N≤105, 0≤Ai<231 Input example: 31 23 Output example: 3

Analysis: find the maximum xOR value, build a binary dictionary tree (01), convert the number into binary, from high to high, make the decision to make the path as different as possible (different xor value is 1), traverse the output optimal solution.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100005;
int trie[maxn * 100] [2], num[maxn * 100];
int a[maxn], pos = 1;
void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        if (trie[p][u] == 0)
            trie[p][u] = pos++;
        p = trie[p][u];
    }
    num[p] = x;// The end marks the value of the path
}
int find(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        if (trie[p][!u])p = trie[p][!u];// There is another way to go
        else p = trie[p][u];// If you can't go, go the same
    }
    return num[p] ^ x;
}
int main(a) {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        insert(a[i]);
    }
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans = max(ans, find(a[i]));
    cout << ans << "\n";
    return 0;
}
Copy the code

Problem Description John is a manager of a CPU chip factory, the factory produces lots of chips everyday. To manage large amounts of products, every processor has a serial number. More specifically, the factory produces n chips today, the i-th chip produced this day has a serial number si. At the end of the day, he packages all the chips produced this day, and send it to wholesalers. More specially, he writes a checksum number on the package, this checksum is defined as below: Maxi, J, K (SI + SJ)⊕ SK which I, J, K are three different integers between 1 and N. and ⊕ is symbol of bitwise xor. Can you help John calculate the checksum number of today? Input The first line of input contains an integer T indicating the total number of test cases. The first line of each The test case is an integer N, indicating the number of chips produced today. The next line has n integers S1, S2,… ,sn, separated with single space, 1≤T≤1000 3≤n≤1000 0≤si≤109 There are at most 10 testcases with N >100 Output For each test case, please output an integer indicating the checksum number in a line. Sample Input 2 3 1 2 3 3 100 200 300 Sample Output 6 400

Analysis: Given a sequence s, s, s, ask to find three distinct I,j,k I,j,k I,j,k, Make (s + s [I] [j]) (s + s [j] [I]) (s + s [j] [I]) xor s [k] s [k] s [k] the value of the maximum. I,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j,j Then query s[I]+ S [j] s[I]+ S [j] s[I]+ S [j] s[I]+ S [j], is also the decision to make the path as different as possible, update the optimal solution, and then backtrack to insert deleted S [I], s[j] s[I], S [j] s[I], S [j] s[j], s[j] s[I], S [j]. C nt[] CNT [] CNT [] CNT [] CNT [] CNT [] CNT []

#include<bits/stdc++.h>
using namespace std;
const int maxn = 40004;
int trie[maxn][2], cnt[maxn], num[maxn];
int pos, k, a[1003];
void insert(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        if (trie[p][u] == 0)
            trie[p][u] = pos++;
        p = trie[p][u];
        cnt[p]++;   // Record the path
    }
    num[p] = x;
}
void del(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        p = trie[p][u];
        cnt[p]--;   // The corresponding path --}}int find(int x) {
    int p = 0;
    for (int i = 30; i >= 0; i--) {
        int u = x >> i & 1;
        // Trie [p][! U] is not empty, but its path has been deleted
        // We should use CNT
        if (cnt[trie[p][!u]])p = trie[p][!u];// Take the other route first
        else p = trie[p][u];
    }
    return num[p] ^ x;
}
int main(a) {
    int t, n;
    cin >> t;
    while (t--) {
        memset(cnt, 0.sizeof(cnt));
        memset(num, 0.sizeof(num));
        memset(trie, 0.sizeof(trie));
        pos = 1;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];    // Insert into the dictionary tree
            insert(a[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) / / traverse the ij
            for (int j = i + 1; j < n; j++) {
                del(a[i]);  / / remove the ij
                del(a[j]);
                ans = max(ans, find(a[i] + a[j]));
                insert(a[i]); // Insert ij traceback
                insert(a[j]);
            }
        cout << ans << "\n";
    }
    return 0;
}
Copy the code

Original is not easy, please do not reprint (this is not rich visits add insult to injury) blogger home page: blog.csdn.net/qq_45034708 If the article is helpful to you, remember to focus on the likes collection ❤