Problem 1: Lexicographical String Matching

Solution

1. Since the problem involves lexicographical order, a trie data structure is suitable.
2. To find the solution, use a greedy approach. Determine if the string ending at the current node is the answer. If not, continue to traverse to one of the child nodes. The process is illustrated in the following steps.
3. The time complexity is ( \mathcal{O}(\sum |w|) ).

Code

View Code

#include <bits/stdc++.h>
using namespace std;
const int maxw = 1e6 + 10;
int nextNode[maxw][26], countNodes, size[maxw], total[maxw];
int n, k, root;
char str[maxw];

void buildTrie() {
    int currentNode = root;
    int length = strlen(str + 1);
    total[currentNode]++;
    for (int i = 1; i <= length; i++) {
        int charIndex = str[i] - 'a';
        if (!nextNode[currentNode][charIndex]) nextNode[currentNode][charIndex] = ++countNodes;
        total[currentNode = nextNode[currentNode][charIndex]]++;
    }
    size[currentNode]++;
}

void solveProblem() {
    scanf("%d%d", &n, &k);
    root = ++countNodes;
    for (int i = 1; i <= n; i++) {
        scanf("%s", str + 1);
        buildTrie();
    }
    int currentNode = root;
    while (true) {
        int t = size[currentNode];
        for (int i = 0; i < 26; i++)
            if (total[nextNode[currentNode][i]]) t++;
        if (t >= k) {
            if (currentNode == root) printf("EMPTY\n");
            return;
        }
        for (int i = 0; i < 26; i++) {
            if (total[nextNode[currentNode][i]] == 0) continue;
            t += -1 + total[nextNode[currentNode][i]];
            if (t >= k) {
                k -= (t - total[nextNode[currentNode][i]]);
                printf("%c", 'a' + i);
                currentNode = nextNode[currentNode][i];
                break;
            }
        }
    }
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) solveProblem();
    return 0;
}

Problem 2: Optimal Housing Arrangement

Solution

1. According to the problem, all people need to be assigned housing. Each person's contribution is either (a) or (b), and adjacent people can be arranged without affecting the result.
2. Sort the people by (b - a) and iterate through possible breakpoints. For each breakpoint, place people before the breakpoint together and those after the breakpoint in separate houses. The sequence length incerases as the breakpiont decreases. If the length exceeds (m), stop the iteration. When (i = 2), everyone is separated, so the lower bound for (i) is 3. Handle the case where everyone is separated separately.
3. When (n = 1), the above method does not apply (since there are no neighbors). This case needs to be handled separately.
4. The time complexity is ( \mathcal{O}(n \log n) ).

Code

View Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e5 + 100;
int n, m;
struct Person {
    int a, b;
} people[maxn];

bool compare(const Person &a, const Person &b) {
    return (a.b - a.a) < (b.b - b.a);
}

ll sumB[maxn], sumA[maxn];

void solveProblem() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &people[i].a, &people[i].b);
    if (n == 1) {
        int maxA = 0;
        for (int i = 1; i <= n; i++)
            maxA = max(people[i].b, maxA);
        printf("%d\n", maxA);
        return;
    }
    sort(people + 1, people + n + 1, compare);
    for (int i = 1; i <= n; i++) {
        sumA[i] = sumA[i - 1] + people[i].a;
        sumB[i] = sumB[i - 1] + people[i].b;
    }
    ll ans = sumA[n];
    for (int i = n; i >= 3; i--) {
        if (i - 1 + 2 * (n - i + 1) > m) break;
        ans = max(ans, sumA[i - 1] + sumB[n] - sumB[i - 1]);
    }
    if (2 * n - 1 <= m) ans = max(ans, sumB[n]);
    printf("%lld\n", ans);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) solveProblem();
    return 0;
}

Problem 3: Maximizing Profit from Buying and Selling

Solution 1

1. Use a greedy approach to buy the cheapest and sell at the highest price. Implement this using two pointers.
2. The time complexity is ( \mathcal{O}(n \log n) ).

Code 1

View Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 10;
int n;
struct Item {
    int buy, sell;
} items[maxn];

bool compareItems(const Item &a, const Item &b) {
    return a.buy < b.buy;
}

void solveProblem() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &items[i].buy, &items[i].sell);
    sort(items + 1, items + n + 1, compareItems);
    ll profit = 0;
    int left = 1, right = n;
    while (left < right) {
        int num = min(items[left].sell, items[right].sell);
        profit += 1LL * num * (items[right].buy - items[left].buy);
        items[left].sell -= num;
        items[right].sell -= num;
        if (items[left].sell == 0) left++;
        if (items[right].sell == 0) right--;
    }
    printf("%lld\n", profit);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) solveProblem();
    return 0;
}

Solution 2

1. Use a greedy approach. Sort the items by price and use binary search to find the smallest non-negative difference between the number of sold and bought items. Adjust the final profit by removing any excess sold items that do not have corresponding buys.
2. Two common mistakes:

• Setting the minimum value of l to 1, which ignores the possibility that the first item's frequency might be greater than the sum of all subsequent frequencies.
• Assuming that there must be a state where the number of bought items equals the number of sold items, which is not always true.

Code 2

View Code

#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int maxn = 1e5 + 10;
int n;
struct Item {
    int buy, sell;
} items[maxn];

bool compareItems(const Item &a, const Item &b) {
    return a.buy < b.buy;
}

ll sum[maxn], sumi[maxn];

void solveProblem() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &items[i].buy, &items[i].sell);
    sort(items + 1, items + n + 1, compareItems);
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + items[i].sell;
        sumi[i] = sumi[i - 1] + items[i].buy * items[i].sell;
    }
    int l = 0, r = n, idx = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (sum[mid] <= sum[n] - sum[mid])
            idx = mid, l = mid + 1;
        else r = mid - 1;
    }
    l = 0, r = items[idx + 1].sell; int num = -1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (sum[idx] + mid <= sum[n] - sum[idx] - mid)
            num = mid, l = mid + 1;
        else r = mid - 1;
    }
    ll profit;
    ll total = sum[n] - sum[idx] - num - (sum[idx] + num);
    profit = sumi[n] - sumi[idx + 1] + items[idx + 1].buy * (items[idx + 1].sell - num - total);
    profit -= sumi[idx] + items[idx + 1].buy * num;
    printf("%lld\n", profit);
}

int main() {
    int t;
    scanf("%lld", &t);
    while (t--) solveProblem();
    return 0;
}