tries树和stl中常用的数据结构

刘汝佳的算法书中，有一些关于模拟的题目
比较典型，代码量也比较大
同时叶比较考验代码的组织能力
具体题目请参阅《算法竞赛入门经典（第二版）》 第五章
这里对一些复杂的习题予以解答

小型订单系统的设计

Exchange

设计思路：

//
//  main.cpp
//  UVA1598
//
//  Created by zhangmin chen on 2019/5/4.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;


class Order {
public:
    string cmd;
    int price, size;
    
    Order(string str, int p, int s) : cmd(str), price(p), size(s) {}
};

map<int, set<int> > buypq, sellpq;
map<int, int> buytab, selltab;
vector<Order> books;

void init() {
    //
    books.clear();
    buypq.clear();
    sellpq.clear();
    
    buytab.clear();
    selltab.clear();
}

void trade(int flag) {
    //
    // flag 0 for buy, flag 1 for sell
    // buy -> match books[sell]
    // sell -> match books[buy]
    while (!buypq.empty() && !sellpq.empty()) {
        int bidP = buypq.rbegin()->first, askP = sellpq.begin()->first;
        
        if(bidP >= askP) {
            // trade
            set<int>& bitem = buypq.rbegin()->second;
            set<int>& sitem = sellpq.begin()->second;
            
            // bitem = {id1, id2....}, sitem = {id1, id2,...}
            
            int bi = *bitem.begin(), si = *sitem.begin();
            int sz = min(books[bi].size, books[si].size);
            
            // then print trade information
            printf("TRADE %d %d\n", sz, flag ? books[bi].price : books[si].price);
            
            // trade begin
            books[bi].size -= sz; books[si].size -= sz;
            buytab[books[bi].price] -= sz; selltab[books[si].price] -= sz;
            
            if(books[bi].size == 0) bitem.erase(bi);
            if(bitem.size() == 0) buypq.erase(books[bi].price);
            
            if(books[si].size == 0) sitem.erase(si);
            if(sitem.size() == 0) sellpq.erase(books[si].price);
        } else {
            return;
        }
    }
}

void quote() {
    //
    while(buytab.size() && buytab.rbegin()->second <= 0)
        buytab.erase(buytab.rbegin()->first);
    while(selltab.size() && selltab.begin()->second <= 0)
        selltab.erase(selltab.begin()->first);
    
    printf("QUOTE ");
    if(buytab.size()) {
        // print (size, price) = (second, first)
        printf("%d %d", buytab.rbegin()->second, buytab.rbegin()->first);
    } else {
        printf("0 0");
    }
    
    cout << " - ";
    
    if(selltab.size()) {
        printf("%d %d", selltab.begin()->second, selltab.begin()->first);
    } else {
        printf("0 99999");
    }
    cout << endl;
}

int main() {
    freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    int n = 0, kase = 0;
    string cmd;
    
    while(scanf("%d", &n) == 1) {
        //
        if(kase++) cout << endl;
        
        init();
        
        int size, price;
        int id;
        for(int i = 0; i < n; i++) {
            cin >> cmd;
            if(cmd == "BUY") {
                cin >> size >> price;
                books.push_back(Order(cmd, price, size));
                
                buypq[price].insert(i);
                buytab[price] += size;
                trade(0);
            } else if(cmd == "SELL") {
                cin >> size >> price;
                books.push_back(Order(cmd, price, size));
                
                sellpq[price].insert(i);
                selltab[price] += size;
                trade(1);
            } else if(cmd == "CANCEL") {
                cin >> id; id--;
                books.push_back(Order(cmd, 0, id));
                // 0 is illegal
                
                if(books[id].cmd == "BUY") {
                    //
                    int p = books[id].price, q = books[id].size;
                    buypq[p].erase(id);
                    if(buypq[p].size() == 0) buypq.erase(p);
                    buytab[p] -= q;
                    
                    books[id].size = 0;
                    
                } else if(books[id].cmd == "SELL") {
                    //
                    int p = books[id].price, q = books[id].size;
                    sellpq[p].erase(id);
                    if(sellpq[p].size() == 0) sellpq.erase(p);
                    selltab[p] -= q;
                    
                    books[id].size = 0;
                }
            }
            
            // one cmd finished
            quote();
        }
    }
}

优先队列与面向对象思想

Use of Hospital Facilities

具体实现如下：

维护一个优先队列，先pq = priority_queue.pop()，出队的时候同时维护next进队元素的信息
then priority_queue.push(next)

//
//  main.cpp
//  UVA212
//
//  Created by zhangmin chen on 2019/5/7.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

class Room {
public:
    int beg, id;
    Room(int beg, int id) : beg(beg), id(id) {}
    
    bool operator < (const Room& rhs) const {
        if(beg != rhs.beg) return beg > rhs.beg;
        return id > rhs.id;
    }
};

// we use priority queue;
// room --> bed

class Patient {
public:
    char name[105];
    int opT, bedT;
    int id, roomID, bedID;
    int opS, opEnd;
    int bedS, bedEnd;
};

bool cmp(Patient& lhs, Patient& rhs) {
    if(lhs.opEnd != rhs.opEnd) return lhs.opEnd < rhs.opEnd;
    return lhs.roomID < rhs.roomID;
}

bool cmp2(Patient& lhs, Patient& rhs) {
    return lhs.id < rhs.id;
}

// n opRooms, m beds, H start hours
// t1 trans-time, t2 pre-opTime, t3 pre-bedTime
// k paitients

int main() {
    freopen("input.txt", "r", stdin);
    
    int n, m, H, t1, t2, t3, k;
    while(~ (scanf("%d%d%d%d%d%d%d", &n, &m, &H, &t1, &t2, &t3, &k)) ) {
        // init
        
        vector<Patient> pents(k);
        priority_queue<Room> rooms;
        vector<int> rUsed(n+1, 0);
        
        for(int i = 1; i <= n; i++) rooms.push(Room(H*60, i));
        // then we get all rooms
        
        for(int i = 0; i < k; i++) {
            Patient& p = pents[i];
            cin >> p.name >> p.opT >> p.bedT;
            p.id = i+1;
            
            // then we get each patient
            
            Room r = rooms.top(); rooms.pop();
            
            p.opS = r.beg; p.opEnd = p.opS + p.opT;
            p.bedS = p.opEnd + t1; p.bedEnd = p.bedS + p.bedT;
            
            p.roomID = r.id;
            rUsed[r.id] += p.opT;
            
            rooms.push(Room(p.opEnd + t2, r.id));
        }
        
        // we arrange op-Room for each patient
        
        sort(pents.begin(), pents.end(), cmp);
        
        // then arrange bed for each patient
        int END = 0;
        vector<int> bUsed(m+1, 0);
        vector<int> Beds(m+1, H*60);
        
        for(int i = 0; i < k; i++) {
            Patient& p = pents[i];
            int j;
            for(j = 1; j <= m; j++) {
                if(Beds[j] <= p.opEnd) break;
            }
            
            // &p: get into Beds[j];
            
            p.bedID =j;
            Beds[j] = p.bedEnd + t3;
            bUsed[j] += p.bedT;
            
            END = max(END, p.bedEnd);
        }
        
        
        // we arrange beds for each patient
        sort(pents.begin(), pents.end(), cmp2);
        
        puts(" Patient          Operating Room          Recovery Room");
        puts(" #  Name     Room#  Begin   End      Bed#  Begin    End");
        puts(" ------------------------------------------------------");
        
        for(int i = 0; i < k; i++) {
            const Patient& p = pents[i];
            printf("%2d  %-9s ", p.id, p.name);
            printf("%2d  %3d:%02d  %3d:%02d     ", p.roomID, p.opS/60, p.opS%60, p.opEnd/60, p.opEnd%60);
            printf("%2d  %3d:%02d  %3d:%02d\n", p.bedID, p.bedS/60, p.bedS%60, p.bedEnd/60, p.bedEnd%60);
        }
        printf("\n");
        
        puts("Facility Utilization");
        puts("Type  # Minutes  % Used");
        puts("-------------------------");
        
        for(int i = 1; i <= n; i++)
            printf("Room %2d %7d %7.2f\n", i, rUsed[i], rUsed[i] * 100.0 / (END - H*60));
        for(int i = 1; i <= m; i++)
            printf("Bed  %2d %7d %7.2f\n", i, bUsed[i], bUsed[i] * 100.0 / (END - H*60));
        
        printf("\n");
    }
}

Trie树

Trie树的实现

代码实现如下：

TrieST.h

//
// Created by zhangmin chen on 2019/2/12.
//

#ifndef TRIEST_TRIEST_H
#define TRIEST_TRIEST_H

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <stdexcept>
#include <cassert>
#include <algorithm>

using namespace std;

class TrieST {
private:
    class Node {
    public:
        Node() : next(256, nullptr), val(0), flag(false) {}
        ~Node() {
            for(int i = 0; i < R; i++) if(next[i])
                delete(next[i]);
        }

        int val;
        bool flag;
        vector<Node *> next;
    };

public:
    // int main() to create!
    TrieST() : n(0), root(nullptr) {}
    ~TrieST() { delete(root); }

    int get(string key) {
        if(key.empty()) throw invalid_argument("argument to get() is null");
        Node* x = get(root, key, 0);
        if(x == nullptr) throw runtime_error("Without this key");
        return x->val;
    }

    void put(string key, int val) {
        if(key.empty()) throw invalid_argument("first argument to put() is null");
        else root = put(this->root, key, val, 0);
    }

    string longestPrefixOf(string query) {
        if(query.empty()) throw invalid_argument("argument to longestPrefixOf() is null");
        int length = longestPrefixOf(root, query, 0, -1);
        if(length == -1) return "";
        else return query.substr(0, length);
    }

    queue<string> keysWithPrefix(string pre) {
        queue<string> res;
        Node* x = get(root, pre, 0);
        collect(x, pre, res);
        return res;
    }

    queue<string> keysMatch(string pat) {
        queue<string> res;
        collect(root, "", pat, res);
        return res;
    }

    void delete_(string key) {
        if(key.empty()) throw invalid_argument("argument to delete() is null");
        root = delete_(root, key, 0);
    }

    int size() { return n; }
    bool isempty() { return size() == 0; }
    queue<string> keys() {
        return keysWithPrefix("");
    }
    bool contains(string key) {
        if(key.empty()) throw invalid_argument("argument to contains() is null");
        return get(root, key, 0) != nullptr;
    }


private:
    Node* get(Node* x, string key, int d) {
        if(x == nullptr) return nullptr;
        if(d == key.length()) return x;
        char c = key[d];
        return get(x->next[c], key, d+1);

        // c = key[0] begin searching
        // start:  get(key[0], key, 1)
        // root is just a node without message
    }

    Node* put(Node* x, string key, int val, int d) {
        if(x == nullptr) x = new Node();
        if(d == key.length()) {
            x->val = val;  x->flag = true;
            return x;
        }
        char c = key[d];
        x->next[c] = put(x->next[c], key, val, d+1);
        return x;
    }

    void collect(Node* x, string pre, queue<string>& res) {
        if(x == nullptr) return;
        if(x->flag) res.push(pre);

        for(unsigned char c = 0; ; c++) {
            pre.push_back(c);
            collect(x->next[c], pre, res);
            pre.pop_back();
            if(c == R-1) break;
        }
    }
    void collect(Node* x, string pre, string pat, queue<string>& res) {
        if(x == nullptr) return;
        int d = pre.length();
        if(d == pat.length() && x->flag) res.push(pre);
        // 遇到x->flag, 进队列
        if(d == pat.length()) return;

        char c = pat[d];
        if(c == '.') {
            //
            for(unsigned char ch = 0; ; ch++) {
                pre.push_back(ch);
                collect(x->next[ch], pre, pat, res);
                pre.pop_back();

                if(ch == R-1) break;
            }
        } else {
            pre.push_back(c);
            collect(x->next[c], pre, pat, res);
            pre.pop_back();
        }
    }

    int longestPrefixOf(Node* x, string query, int d, int length) {
        if(x == nullptr) return length;
        if(x->flag) length = d;
        if(d == query.length()) return length;

        char c = query[d];
        return longestPrefixOf(x->next[c], query, d+1, length);
    }

    Node* delete_(Node* x, string key, int d) {
        if(x == nullptr) return nullptr;
        if(d == key.length()) {
            if(x->flag) n--;
            x->flag = false;
        } else {
            char c = key[d];
            x->next[c] = delete_(x->next[c], key, d+1);
        }

        // remove subtrie rooted at x if it is completely empty
        if(x->flag) return x;
        for(int c = 0; c < R; c++) if(x->next[c] != nullptr)
            return x;
        return nullptr;

        // in recur, x->next[c] = nullptr, fix the bug of Leaking memory
    }

private:
    static const int R;
    Node* root;     // root of trie
    int n;          // number of keys in trie
};

const int TrieST::R = 256;

#endif //TRIEST_TRIEST_H

main.cpp

#include "./cmake-build-debug/TrieST.h"
#include <fstream>

int main() {
    freopen("input.txt", "r", stdin);
    string tmp;
    int cnt = 0;
    TrieST st;

    while(cin >> tmp) {
        // cout << tmp << endl;
        st.put(tmp, cnt++);
    }

    if(st.size() < 100) {
        cout << "keys(\"\"):" << endl;
        auto res = st.keys();
        while(!res.empty()) {
            cout << res.front() << " " << st.get(res.front()) << endl;
            res.pop();
        }
        cout << endl;
    }

    cout << "longestPrefixOf(\"shellsort\"):" << endl;
    cout << st.longestPrefixOf("shellsort") << endl;
    cout << endl;

    cout << "longestPrefixOf(\"quicksort\"):" << endl;
    cout << st.longestPrefixOf("quicksort") << endl;
    cout << endl;

    cout << "keyWithPrefix(\"shor\"):" << endl;
    auto res = st.keysWithPrefix("shor");
    while(!res.empty()) {
        cout << res.front() << endl;
        res.pop();
    }
    cout << endl;

    cout << "keysThatMatch(\".he.l.\"):" << endl;
    auto res2 = st.keysMatch(".he.l.");
    while(!res2.empty()) {
        cout << res2.front() << endl;
        res2.pop();
    }
    cout << endl;
}

三向单词查找树

TST.h

//
// Created by zhangmin chen on 2019/2/13.
//

#ifndef TST_TST_H
#define TST_TST_H

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
#include <stdexcept>
#include <queue>

using namespace std;

class TST {
private:
    class Node {
    public:
        // construction
        Node() : left(nullptr), mid(nullptr), right(nullptr), isString(false) {}
        ~Node() {
            if(left) delete(left);
            if(right) delete(right);
            if(mid) delete(mid);
        }

        unsigned char c;
        bool isString;
        Node *left, *mid, *right;
        int val;
    };

public:
    // construction
    TST() : n(0), root(nullptr) {}
    ~TST() { delete(root); }

    int size() { return n; }
    bool contains(string key) {
        if(key.empty()) {
            throw invalid_argument("argument to contains() is null!");
        }
        return get(root, key, 0) != nullptr;
    }

    int get(string key) {
        if(key.empty()) throw invalid_argument("calls get() with null argument");
        Node *x = get(root, key, 0);
        if(x == nullptr) throw runtime_error("This key not int this table");
        return x->val;
    }

    void put(string key, int val) {
        if(key.empty()) throw invalid_argument("calls put() with null key");
        if(!contains(key)) n++;
        root = put(root, key, val, 0);
    }

    string longestPrefixOf(string query) {
        if(query.length() == 0) return "";
        int len = 0;
        Node* x = root;

        int i = 0;
        while(i < query.length() && x != nullptr) {
            char ch = query[i];
            if(ch < x->c) x = x->left;
            else if(ch > x->c) x = x->right;
            else {
                i++;
                if(x->isString) len = i;
                x = x->mid;
            }
        }

        return query.substr(0, len);
    }

    queue<string> keys() {
        queue<string> que1;
        string tmp = "";
        collect(root, tmp, que1);
        return que1;
    }

    queue<string> keysWithPrefix(string pre) {
        if(pre.empty()) throw invalid_argument("calls keysWithPrefix() with null argumemnt");

        queue<string> que2;
        Node *x = get(root, pre, 0);

        if(x == nullptr) return que2;
        if(x->isString) que2.push(pre);
        collect(x->mid, pre, que2);
        return que2;
    }

    queue<string> keysThatMatch(string pat) {
        queue<string> que;
        string pre = "";
        collect(root, pre, 0, pat, que);
        return que;
    }

private:
    Node *get(Node *x, string key, int d) {
        if(x == nullptr) return nullptr;
        if(key.length() == 0) throw invalid_argument("key must have length >= 1");
        unsigned char ch = key[d];

        if(ch < x->c) return get(x->left, key, d);
        else if(ch > x->c) return get(x->right, key, d);
        else if (d < key.length()-1) return get(x->mid, key, d+1);
        else return x;
    }

    Node *put(Node *x, string key, int val, int d) {
        char ch = key[d];
        if(x == nullptr) {
            x = new Node(); x->c = ch;
        }

        if(ch < x->c) x->left = put(x->left, key, val, d);
        else if(ch > x->c) x->right = put(x->right, key, val, d);
        else if(d < key.length()-1) x->mid = put(x->mid, key, val, d+1);
        else {
            x->val = val; x->isString = true;
        }
        return x;
    }

    void collect(Node *x, string& pre, queue<string>& res) {
        if(x == nullptr) return;
        collect(x->left, pre, res);
        if(x->isString) {
            pre.push_back(x->c); res.push(pre); pre.pop_back();
            // find prefix
        }

        pre.push_back(x->c);
        collect(x->mid, pre, res);
        pre.pop_back();

        collect(x->right, pre, res);
    }

    void collect(Node *x, string& pre, int d, const string& pat, queue<string>& res) {
        if(x == nullptr) return;
        char ch = pat[d];

        if(ch == '.' || ch < x->c) collect(x->left, pre, d, pat, res);
        if(ch == '.' || ch == x->c) {
            if(d == pat.length()-1 && x->isString) {
                pre.push_back(x->c);
                res.push(pre);
            }
            if(d < pat.length()-1) {
                pre.push_back(x->c);
                collect(x->mid, pre, d+1, pat, res);
                pre.pop_back();
            }
        }
        if(ch == '.' || ch > x->c) collect(x->right, pre, d, pat, res);
    }


private:
    int n;
    Node* root;
};

#endif //TST_TST_H

main.cpp

#include "./cmake-build-debug/TST.h"

#include <fstream>

int main() {
    freopen("input.txt", "r", stdin);

    string tmp;
    int cnt = 0;
    TST tst;
    while(cin >> tmp) {
        //
        tst.put(tmp, cnt++);
    }

    if(tst.size() < 100) {
        cout << "keys(\"\"):" << endl;
        auto res = tst.keys();
        while(!res.empty()) {
            cout << res.front() << endl;
            res.pop();
        }
        cout << endl;
    }

    cout << "longestPrefixOf(\"shellsort\"):" << endl;
    cout << tst.longestPrefixOf("shellsort") << endl;
    cout << endl;

    cout << "longestPrefixOf(\"quicksort\"):" << endl;
    cout << tst.longestPrefixOf("quicksort") << endl;
    cout << endl;

    cout << "keysWithPrefix(\"shor\"):" << endl;
    auto res = tst.keysWithPrefix("shor");
    while(!res.empty()) {
        cout << res.front() << endl;
        res.pop();
    }
    cout << endl;

    cout << "keysThatMatch(\".he.l.\"):" << endl;
    auto res2 = tst.keysThatMatch(".he.l.");
    while(!res2.empty()) {
        cout << res2.front() << endl;
        res2.pop();
    }
    cout << endl;
}

Trie树的优化

使用memset(ch[sz], 0, sizeof(ch[sz])), ch[u][c] = sz++
来开辟一个子节点
如果没到字符串末尾，val[sz] = 0
只有到达字符串末尾，才保存val值

template<maxnode, sigmaSize>
class Trie {
public:
    int ch[maxnode][sigmaSize];
    int val[maxnode];
    int sz;

    Trie() {
        sz = 1;
        memset(ch, 0, sizeof(ch[0]))
        // 相当于new Node(root)
    }

    void insert(const string& str, int v) {
        int u = 0;
        for(int i = 0; i < str.length(); i++) {
            int c = idx(str[i]);
            if(!ch[u][c]) {
                // 开辟一个子节点, 值为sz
                memset(ch[sz], 0, sizeof(ch[sz]));
                val[sz] = 0;  //没到str结尾，所有的val都为0，只在str结尾保存值
                ch[u][c] = sz++;
            }
            u = ch[u][c];
        }

        // str结尾了，保存字符串的值
        val[u] = v;
    }
};

Trie树解决大整数问题

Revenge of Fibonacci

涉及到的一些stl函数

int myints[] = {10, 20, 30, 40, 50, 60, 70};
vector<int> myvector(7);

copy(myints, myints+7, myvector.begin())

// 把myints[0]往后7个元素复制到myvector中

相似的用法

string str = "abcdefg"
string tmp;

tmp.append(str, 0, 3);
// tmp后面附加上从str[0]往后3个字符

Trie树在BigInt上的优势
完美解决前导0
比如一个数是0067
由于trie树只会在字符串末尾保存0067的val，这个val可以是真实值，也可以是索引，也可以是哈希
所以保证node u扫完整个字符串，看val[u]的值就可以

stringstream用于string类和其他值类型的转换

stringstream ss;
char buf[maxn];
for(i = 0; i < maxn; i++)
    sprintf(buf, "%d", arr[i]);

ss << buf;
cout << ss.str() << endl;

基本思想

本例和一般单词查找树的异同

if(ch[u][c] == -1) {
    memset(ch[sz], -1, sizeof(ch[sz]));
    val[sz] = v;
    // 一般单词查找树val[sz] = 0;
    ch[u][c] = sz++;
}

一般单词查找树，val[sz] = 0，只在字符串末尾保存相应的值
本例中，因为是根据前缀（斐波那契数的前几个部分数字），来猜到是第几个斐波那契数
所以所有的前缀都必须保存v信息，val[sz] = v

代码实现如下

//
//  main.cpp
//  UVA12333
//
//  Created by zhangmin chen on 2019/5/7.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int BASE = 10000;
const int MAXLEN = 6000;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

template <int maxn>
class BigInt {
public:
    int len, s[maxn];
    BigInt() {
        Set(s, 0);
        len = 1;
    }
    
    BigInt& operator= (int num) {
        if(num == 0) {
            len = 1;
            return *this;
        }
        
        len = 0;
        while(num > 0) {
            s[len++] = num % BASE;
            num /= BASE;
        }
        return *this;
    }
    
    BigInt& operator= (const BigInt& rhs) {
        len = rhs.len;
        copy(rhs.s, rhs.s + rhs.len, s);
        return *this;
    }
    
    BigInt(int num) {
        *this = num;
    }
};

typedef BigInt<MAXLEN> fBig;

string Reverse(const fBig& fi) {
    int tot = 0;
    char buf[8];
    
    stringstream ss;
    bool first = true;
    for(int i = 0; i < fi.len; i++) {
        if(first) {
            first = false;
            sprintf(buf, "%d", fi.s[fi.len - 1 - i]);
        } else sprintf(buf, "%04d", fi.s[fi.len - 1 - i]);
        
        ss << buf;
        tot += strlen(buf);
        if(tot >= 41) break;
    }
    return ss.str();
}


template <int maxNode, int sigmaSize>
class Trie {
public:
    int ch[maxNode][sigmaSize], val[maxNode];
    int sz;
    
    Trie() {
        Set(ch[0], -1);
        Set(val, 0);
        sz = 1;
    }
    
    int idx(char c) const { return c - '0'; }
    
    void insert(const string& str, int v) {
        int u = 0;
        for(int i = 0; i < str.length(); i++) {
            //
            int c = idx(str[i]);
            if(ch[u][c] == -1) {
                //
                Set(ch[sz], -1);
                val[sz] = v;
                ch[u][c] = sz++;
            }
            
            u = ch[u][c];
        }
        
        val[u] = v;
    }
    
    int getVal(const string& str) const {
        int v = -1, u = 0;
        for(int i = 0; i < str.length(); i++) {
            //
            int c = idx(str[i]);
            if(ch[u][c] == -1) return v;
            u = ch[u][c];
        }
        
        if(val[u]) v = val[u];
        return v;
    }
    
};

void Add(const fBig& f1, const fBig& f2, fBig& f3) {
    
    int len = max(f1.len, f2.len);
    
    int p = 0;
    for(int i = 0, carry = 0; ; i++) {
        if(carry == 0 && i >= len) break;
        int x = carry;
        if(i < f1.len) x += f1.s[i];
        if(i < f2.len) x += f2.s[i];
        
        f3.s[p++] = x % BASE;
        carry = x / BASE;
    }
    f3.len = p;
}

/*
ostream& operator<< (ostream& os, const fBig& fi) {
    char buf[8];
    stringstream ss;
    bool first = true;
    for(int i = fi.len - 1; i >= 0; i--) {
        if(first) {
            first = false;
            ss << fi.s[i];
        } else {
            sprintf(buf, "%04d", fi.s[i]);
            ss << buf;
        }
    }
    const string& str = ss.str();
    if(str.empty()) return os << 0;
    return os << str;
}
 */

Trie<4000000, 10> trie;
fBig f0 = 0, f1 = 1, f;
const int MAXF = 100000;

int main() {
    freopen("input.txt", "r", stdin);
    for(int i = 2; i < MAXF; i++) {
        Add(f0, f1, f);
        string rev = Reverse(f);
        
        trie.insert(rev, i-1);
        f0 = f1;
        f1 = f;
    }
    
    int kase;
    scanf("%d", &kase);
    char buf[60];
    for(int k = 1; k <= kase; k++) {
        scanf("%s", buf);
        int ans = 0;
        string str(buf);
        if(str != "1") ans = trie.getVal(str);
        printf("Case #%d: %d\n", k, ans);
    }
}

模拟操作系统：多线程处理

流水线时间 – 取出任务放入缓存表 – 更新缓存表 – 判断任务进行情况

Queue and A

分析

solution 1

//
//  main.cpp
//  LA5222
//
//  Created by zhangmin chen on 2019/5/8.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;



#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

const int MAXTIME = 500000;

class Topic {
public:
    int tid, num, t0, t, dt;
    int tot;
};

class Cust {
public:
    int pid, k;
    vector<int> cTopics;
    
    int dtime, handle, last;
    bool busy;
    
    Cust() {
        pid = -1;
        k = 0;
        cTopics.clear();
        
        dtime = 0;
        handle = -1;
        last = 0;
        busy = 0;
    }
    
    bool operator< (const Cust& rhs) const {
        if(last == rhs.last) return pid > rhs.pid;
        return last > rhs.last;
    }
};

vector<Topic> topics;
vector<Cust> custs;

map<int, int> idxT;
map<int, int> idxC;

map<int, vector<Cust> > buf;
typedef map<int, vector<Cust> >::iterator mv;

bool can_assign(int tID, int timing) {
    //
    if(timing < topics[tID].t0) return 0;
    if(topics[tID].dt == 0) return topics[tID].num > 0;
    if(topics[tID].num == 0) return 0;
    
    int arriving = (timing - topics[tID].t0) / topics[tID].dt;
    int already_assigned = topics[tID].tot - topics[tID].num;
    
    if(arriving < already_assigned) return 0;
    return 1;
}

void init() {
    topics.clear();
    custs.clear();
    idxT.clear();
    idxC.clear();
    buf.clear();
}


int main() {
    freopen("input.txt", "r", stdin);
    int n, m, kase = 0;
    
    // n topics, m custs
    while(cin >> n && n) {
        init();
        int timing = 0;
        
        for(int i = 0; i < n; i++) {
            Topic tp;
            cin >> tp.tid >> tp.num >> tp.t0 >> tp.t >> tp.dt;
            
            tp.tot = tp.num;
            idxT[tp.tid] = i;
            
            topics.push_back(tp);
        }
        
        cin >> m;
        for(int i = 0; i < m; i++) {
            Cust cst;
            cin >> cst.pid >> cst.k;
            idxC[cst.pid] = i;
            
            for(int j = 0; j < cst.k; j++) {
                int x;
                cin >> x;
                cst.cTopics.push_back(idxT[x]);
            }
            
            custs.push_back(cst);
        }
        // finished input data
        
        for(timing = 0; timing < MAXTIME; timing++) {
            buf.clear();
            // check busy of each custs
            for(int i = 0; i < m; i++) {
                if(!custs[i].busy) {
                    for(int j = 0; j < custs[i].k; j++) {
                        int tp = custs[i].cTopics[j];
                        if(can_assign(tp, timing)) {
                            // assign tp to custs[i]
                            if(!buf.count(tp)) buf[tp] = vector<Cust> ();
                            buf[tp].push_back(custs[i]);
                            break;
                        }
                    }
                }
            }
            
            // check buf
            for(mv it = buf.begin(); it != buf.end(); it++) {
                sort(it->second.begin(), it->second.end());
                int c = idxC[it->second[0].pid];
                custs[c].busy = 1;
                custs[c].last = timing;
                custs[c].handle = it->first;
                topics[it->first].num--;
            }
            
            // update custs dtime
            for(int i = 0; i < m; i++) {
                if(custs[i].busy) custs[i].dtime++;
                int tp = custs[i].handle;
                
                if(custs[i].busy && custs[i].dtime == topics[tp].t) {
                    custs[i].busy = 0;
                    custs[i].dtime = 0;
                }
            }
            
            // check finished
            int finished = 1;
            
            for(int i = 0; i < n; i++) {
                if(topics[i].num > 0) {
                    finished = 0;
                    break;
                }
            }
            
            for(int i = 0; i < m; i++) {
                if(custs[i].busy > 0) {
                    finished = 0;
                    break;
                }
            }
            
            
            if(finished) break;
            // timing loop finished!
        }
        
        
        printf("Scenario %d: All requests are serviced within %d minutes.\n", ++kase, timing + 1);
        // while finished!
    }
}

solution 2：离散跳转

//
//  main.cpp
//  LA5222B
//
//  Created by zhangmin chen on 2019/5/10.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const int inf = 0x3f3f3f3f;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

class Topic {
public:
    int t;
    queue<int> table;
    
    Topic(int t_) {
        t = t_;
        while (!table.empty()) {
            table.pop();
        }
    }
    
    Topic() {
        t = 0;
        while (!table.empty()) {
            table.pop();
        }
    }
};

class Person {
public:
    int pid, k;
    vector<int> tids;
    int last, endT;
    
    bool operator< (const Person& rhs) const {
        if(last != rhs.last) return last < rhs.last;
        return pid < rhs.pid;
    }
};

int N, M;
map<int, Topic> topics;
vector<Person> persons;

void init() {
    topics.clear();
    persons.clear();
}

/*
 *
 int timing = min {all_t0}
 while(N) {
    int jump = inf;
    // update jump through nxt
    for(p = all persons)
        int nxt = inf
        update(nxt)
        jump = min(jump, nxt)
 
    timing = jump
 }
 
 */

void assign(Person& p, int& nxt, int& ans, int timing) {
    // default: p.endT < timing
    _for(i, 0, p.k) {
        // id = p.tids[i]
        Topic& tp = topics[p.tids[i]];
        if(tp.table.empty()) continue;
        
        // nxt = latest topic time
        nxt = min(nxt, tp.table.front());
        if(tp.table.front() <= timing) {
            // assign the topic
            nxt = timing + tp.t;
            ans = max(ans, nxt);
            p.last = timing;
            
            tp.table.pop();
            if(tp.table.empty()) N--;
            
            break;
        }
    }
    p.endT = nxt;
}


int main() {
    freopen("input.txt", "r", stdin);
    int kase = 1;
    
    while (cin >> N && N) {
        init();
        
        int timing = inf, ans = 0;
        _for(i, 0, N) {
            int tid, num, t0, t, dt;
            cin >> tid >> num >> t0 >> t >> dt;
            timing = min(timing, t0);
            
            Topic tp(t);
            
            while(num--) {
                //
                tp.table.push(t0);
                t0 += dt;
            }
            
            topics[tid] = tp;
        }
        
        cin >> M;
        persons.resize(M);
        _for(i, 0, M) {
            cin >> persons[i].pid >> persons[i].k;
            persons[i].tids.resize(persons[i].k);
            _for(j, 0, persons[i].k) {
                cin >> persons[i].tids[j];
            }
        }
        
        // we get all data
        
        while(N) {
            int jump = inf;
            sort(persons.begin(), persons.end());
            for(auto& p : persons) {
                int nxt = inf;
                // update(nxt), assigned the project
                // if can assign? else ?
                
                if(p.endT > timing) {
                    nxt = p.endT;
                }
                else {
                    assign(p, nxt, ans, timing);
                }
                
                jump = min(jump, nxt);
                // for p loop finished;
            }
            
            timing = jump;
            // while N loop finished
        }
        printf("Scenario %d: All requests are serviced within %d minutes.\n", kase++, ans);
    }
}

STL高级排序：地图的放大和缩小

有的时候我们需要根据外关键字，对结构体排序

class Map {};
Map mp;
vector<Map> maps;
mps.push_back(mp);

我们需要根据外部的location，和mp.center的相对距离进行排序
其中location并不是Map的成员函数
这个时候cmp的写法

for i = 0 to maps.size()
    if Area in map[i]
        mapID.push_back(i);

check:
for i = 0 to mapID.size()
    get maps[mapID[i]];        

class Cmp {
public:
    Point loc;

    bool operator() (int lhs, int rhs) {
        const Map& m1 = maps[lhs];
        const Map& m2 = maps[rhs];

        int d = Minus(dist(loc, m1.center), dist(loc, m2.center))
            // |loc - map.center| 值大的放在前面，默认m1 > m2
            // 如果m1 > m2, 不改变位置
        
        if(d > 0) return true;
        if(d < 0) return false;
    }
};

Cmp cmp;
sort(mapID.begin(), mapID.end(), cmp);

其中cmp结构体，重载了()运算符
operator() 返回true，不换位置，返回false，互换位置

另外一般意义的写法：

bool cmp(Student& s1, Student& s2) {
    if(s1.score != s2.score) return s1.score > s2.score;
    else return strcmp(s1.name, s2.name);
}

// 默认s1在s2前面

并列情况的处理
先获取一个排名vector& rank
if score[i-1] < score[i], rank[i]++

然后把排名转换成索引, 查找rk对应的id
int p = upper_bound(rank.begin(), rank.end(), rk) - rank.begin()
**Map& res = maps[mapID[p-1]] **

最后关于排名转换成索引的问题
见level和id的图
如下所示

代码

实现方法：

//
//  main.cpp
//  LA5197
//
//  Created by zhangmin chen on 2019/5/11.
//  Copyright © 2019 zhangmin chen. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <sstream>
#include <iomanip>
#include <cmath>

using namespace std;
typedef long long llong;
typedef set<string>::iterator ssii;

const double eps = 1e-7;

#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define Set(a, v) memset(a, v, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define _rep(i, l, r) for(int i = (l); i <= (r); i++)
#define _for(i, l, r) for(int i = (l); i < (r); i++)
#define debug_(ch, i) printf(#ch"[%d]: %d\n", i, ch[i])
#define debug_m(mp, p) printf(#mp"[%d]: %d\n", p->first, p->second)
#define debugS(str) cout << "dbg: " << str << endl;

class Point {
public:
    double x, y;
    Point(double x_ = 0.0, double y_ = 0.0) : x(x_), y(y_) {}
    
};

Point operator+ (const Point& lhs, const Point& rhs) {
    return Point(lhs.x + rhs.x, lhs.y + rhs.y);
}

Point operator- (const Point& lhs, const Point& rhs) {
    return Point(lhs.x - rhs.x, lhs.y - rhs.y);
}

Point operator* (const Point& lhs, double p) {
    return Point(lhs.x * p, lhs.y * p);
}

istream& operator>> (istream& is, Point& rhs) {
    return is >> rhs.x >> rhs.y;
}
double dist(const Point& lhs, const Point& rhs) {
    double tmp = (lhs.x - rhs.x) * (lhs.x - rhs.x) + (lhs.y - rhs.y) * (lhs.y - rhs.y);
    return sqrt(tmp);
}

int Minus_(double x) {
    //
    if(fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

int Minus(double x, double y) {
    return Minus_(x - y);
}

bool inRange(double x, double left, double right) {
    //
    if(Minus(left, right) > 0) return inRange(x, right, left);
    return Minus(left, x) <= 0 && Minus(x, right) <= 0;
}

bool inArea(const Point& p, const Point& lhs, const Point& rhs) {
    return inRange(p.x, lhs.x, rhs.x) && inRange(p.y, rhs.y, lhs.y);
    // made a bug here
}


class Map {
public:
    string name;
    Point p1, p2, center, corner;
    
    double width, height, area, ratio, minx;
    
    Map(string name_, Point p1_, Point p2_) {
        name = name_;
        p1 = p1_;
        p2 = p2_;
        
        center = (p1 + p2) * .5;
        width = fabs(p1.x - p2.x);
        height = fabs(p1.y - p2.y);
        ratio = fabs(height / width - 0.75);
        area = width * height;
        
        corner = Point(center.x + width / 2, center.y - height / 2);
        minx = center.x - width / 2;
    }
};

vector<Map> map_s;
map<string, Point> locats;

class Cmp {
public:
    Point loc;
    
    bool operator() (int lhs, int rhs) {
        //
        const Map& m1 = map_s[lhs];
        const Map& m2 = map_s[rhs];
        
        int d;
        
        d = Minus(m1.area, m2.area);
        if(d > 0) return true;
        if(d < 0) return false;
        
        d = Minus(dist(m1.center, loc), dist(m2.center, loc));
        if(d > 0) return true;
        if(d < 0) return false;
        
        d = Minus(m1.ratio, m2.ratio);
        if(d > 0) return true;
        if(d < 0) return false;
        
        d = Minus(dist(loc, m1.corner), dist(loc, m2.corner));
        if(d < 0) return true;
        if(d > 0) return false;
        
        d = Minus(m1.minx, m2.minx);
        if(d > 0) return true;
        if(d < 0) return false;
        
        return false;
    }
};

void getMapLevel(const Point pt, vector<int>& level, vector<int>& id) {
    //
    id.clear();
    
    Cmp cmp;
    cmp.loc = pt;
    
    _for(i, 0, map_s.size()) {
        const Map& mp = map_s[i];
        if(inArea(pt, mp.p1, mp.p2)) {
            id.push_back(i);
            // debug(inArea(pt, mp.p1, mp.p2));
        }
    }
    
    sort(id.begin(), id.end(), cmp);
    level.clear();
    level.assign(id.size(), 1);
    
    _for(i, 1, id.size()) {
        const Map& m1 = map_s[id[i-1]];
        const Map& m2 = map_s[id[i]];
        
        level[i] = level[i-1];
        int d = Minus(m2.area, m1.area);
        if(d < 0) level[i]++;
    }
}

void solve(const string& name, int lv) {
    //
    // vector<int> levels;
    
    cout << name << " at detail level " << lv;
    if(!locats.count(name)) {
        cout << " unknown location" << endl;
        return;
    }
    
    vector<int> ID, levels;
    getMapLevel(locats[name], levels, ID);
    
    if(ID.empty()) {
        cout << " no map contains that location" << endl;
        return;
    }
    
    int maxlv = levels.back();
    // debug(maxlv);
    if(maxlv < lv) {
        //
        cout << " no map at that detail level; using " << map_s[ID.back()].name << endl;
    } else {
        //
        int p = (int)(upper_bound(levels.begin(), levels.end(), lv) - levels.begin());
        cout << " using " << map_s[ID[p-1]].name << endl;
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    string buf;
    getline(cin, buf);
    
    while (true) {
        string name;
        cin >> name;
        if(name == "LOCATIONS") break;
        
        Point p1_, p2_;
        cin >> p1_ >> p2_;
        // cout << p1_.x << " " << p1_.y << " " << p2_.x << " " << p2_.y << endl;
        Map mp(name, p1_, p2_);
        
        map_s.push_back(mp);
    }
    
    while(true) {
        string name;
        cin >> name;
        if(name == "REQUESTS") break;
        Point pt;
        cin >> pt;
        locats[name] = pt;
    }
    
    //_for(i, 0, map_s.size()) cout << map_s[i].name << " " << map_s[i].p1.x << endl;
    
    while (true) {
        string name;
        cin >> name;
        if(name == "END") break;
        int lv;
        cin >> lv;
        solve(name, lv);
    }
    return 0;
}