Skip to content

14230: 【原4230】Paper Citation 2

题目

题目描述

author: Shuhao Li 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4230

Description

本题是Paper Citation那道题的变体。一篇论文的被引用数是衡量一篇论文价值的重要指标,论文的引用数通常会随着时间的增加而增加。现在有若干篇论文,本题给出一个论文引用序列,要求针对每一个询问,输出当前被引用数最高的论文题目以及其当前的被引用数。

Input Format

输入若干行,每行执行一个操作。

每行的第一个字段指示操作的类型,分别有cite, query, finish三种不同的操作,格式如下。

如果第一个字段是cite,则接下来输入一个字符串,表示论文的标题,该操作表示这篇论文被引用一次,其引用数加1。

如果第一个字段是query,则输出当前论文被引用数最高的被引用数和论文题目,用空格隔开,如果有两篇以上的论文符合条件,输出论文题目字典序最小的那一个。

如果第一个字段是finish,则结束输入。

Output Format

对于每个query操作,输出一行,表示引用量最高的引用量和论文标题,中间用一个空格隔开。

Sample Input

cite Evaluating Polarity for Verbal Phraseological Units
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Towards a set of Measures for Evaluating Software Agent Autonomy
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Evaluating Polarity for Verbal Phraseological Units
cite Towards a set of Measures for Evaluating Software Agent Autonomy
cite Evaluating Polarity for Verbal Phraseological Units
cite Towards a set of Measures for Evaluating Software Agent Autonomy
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
query
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Towards a set of Measures for Evaluating Software Agent Autonomy
cite Evaluating Polarity for Verbal Phraseological Units
cite Evaluating Polarity for Verbal Phraseological Units
query
cite Evaluating Polarity for Verbal Phraseological Units
cite Towards a set of Measures for Evaluating Software Agent Autonomy
cite Evaluating Polarity for Verbal Phraseological Units
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Towards a set of Measures for Evaluating Software Agent Autonomy
query
cite Towards a set of Measures for Evaluating Software Agent Autonomy
cite Towards a set of Measures for Evaluating Software Agent Autonomy
cite Evaluating Polarity for Verbal Phraseological Units
cite Evaluating Polarity for Verbal Phraseological Units
cite Towards a set of Measures for Evaluating Software Agent Autonomy
cite Evaluating Polarity for Verbal Phraseological Units
query
query
query
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Evaluating Polarity for Verbal Phraseological Units
cite Evaluating Polarity for Verbal Phraseological Units
cite Evaluating Polarity for Verbal Phraseological Units
query
query
cite Evaluating Polarity for Verbal Phraseological Units
cite Evaluating Polarity for Verbal Phraseological Units
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Towards a set of Measures for Evaluating Software Agent Autonomy
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Evaluating Polarity for Verbal Phraseological Units
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Evaluating Polarity for Verbal Phraseological Units
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Evaluating Polarity for Verbal Phraseological Units
query
cite Evaluating Polarity for Verbal Phraseological Units
cite Evaluating Polarity for Verbal Phraseological Units
cite Evaluating Polarity for Verbal Phraseological Units
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Towards a set of Measures for Evaluating Software Agent Autonomy
cite Evaluating Polarity for Verbal Phraseological Units
cite Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
cite Evaluating Polarity for Verbal Phraseological Units
cite Towards a set of Measures for Evaluating Software Agent Autonomy
finish

Sample Output

4 Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
6 Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
8 Automatic Monitoring the Content of Audio Broadcasted by Internet Radio Stations
10 Evaluating Polarity for Verbal Phraseological Units
10 Evaluating Polarity for Verbal Phraseological Units
10 Evaluating Polarity for Verbal Phraseological Units
13 Evaluating Polarity for Verbal Phraseological Units
13 Evaluating Polarity for Verbal Phraseological Units
18 Evaluating Polarity for Verbal Phraseological Units

Limits

对于100%的数据,总操作数不大于200000。

不允许使用任何c++ stl容器库,例如map等。

BugenZhao's solution

//
// Created by BugenZhao on 2019/4/29.
//

#ifndef SBL_BBINARYSEARCHTREE_H
#define SBL_BBINARYSEARCHTREE_H

template<typename Key, typename Val>
class BPair {
public:
    Key key;
    Val val;

    BPair(Key key, Val val) : key(key), val(val) {}

    BPair() = delete;
};

template<typename Key, typename Val>
class BBinarySearchTree {
    class Node {
    public:
        BPair<Key, Val> data;
        Node *left;
        Node *right;

        explicit Node(const BPair<Key, Val> &data, Node *left = nullptr, Node *right = nullptr) :
                data(data), left(left), right(right) {}
    };

    Node *root;
    int size;

private:
    BPair<Key, Val> *get(Node *node, const Key &key) {
        if (node == nullptr || node->data.key == key)
            return &node->data;
        if (key < node->data.key)
            return get(node->left, key);
        else
            return get(node->right, key);
    }

    void put(Node *&node, const Key &key, const Val &val) {
        if (node == nullptr)
            node = new Node({key, val});
        else if (key < node->data.key)
            put(node->left, key, val);
        else if (key > node->data.key)
            put(node->right, key, val);
        else
            node->data.val = val;
    }

    void remove(Node *&node, const Key &key) {
        if (node == nullptr)
            return;
        if (key < node->data.key)
            remove(node->left, key);
        else if (key > node->data.key)
            remove(node->right, key);
        else if (node->right == nullptr) {
            auto oldNode = node;
            node = node->left;
            delete oldNode;
        } else if (node->left == nullptr) {
            auto oldNode = node;
            node = node->right;
            delete oldNode;
        } else {
            auto p = node->right;
            while (p->left != nullptr) p = p->left;
            node->data = p->data;
            remove(node->right, node->data.key);
        }
    }

    void clear(Node *&node) {
        if (node == nullptr) return;
        clear(node->left);
        clear(node->right);
        delete node;
        --size;
    }

public:
    BBinarySearchTree() : root(nullptr), size(0) {}

    BPair<Key, Val> *get(const Key &key) {
        return get(root, key);
    }

    void put(const Key &key, const Val &val) {
        put(root, key, val);
    }

    void remove(const Key &key) {
        remove(root, key);
    }

    void clear() {
        clear(root);
    }

    virtual ~BBinarySearchTree() {
        clear();
    }
};


#endif //SBL_BBINARYSEARCHTREE_H

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    BBinarySearchTree<string, int> counts;
    string maxTitle;
    int maxCount = 0;

    string cmd;
    string title;
    int count;
    while (true) {
        cin >> cmd;
        if (cmd[0] == 'f') break;
        else if (cmd[0] == 'c') {
            getline(cin, title);
            auto p = counts.get(title);
            if (p) count = (++p->val);
            else counts.put(title, count = 1);
            if (count == maxCount) {
                maxTitle = maxTitle < title ? maxTitle : title;
            } else if (count == maxCount + 1) {
                maxCount += 1;
                maxTitle = title;
            }
        } else if (cmd[0] == 'q') {
            cout << maxCount << ' ' << maxTitle << '\n';
        }
    }

    return 0;
}

skyzh's solution

#include <iostream>
#include <cstring>
#include <memory>

using namespace std;

class NotFoundError {
};

class DuplicateKeyError {
};

int cmp(const char *a, const char *b) {
    return strcmp(a, b);
}

struct String {
    const char *str;

    String(const char *str) : str(str) {}

    friend int cmp(const String &a, const String &b) {
        return cmp(a.str, b.str);
    }
};

template<typename Key, typename T>
struct LLRB {
    struct Node {
        Key key;
        T x;
        Node *l, *r;
        bool is_red;

        Node(const Key &key, const T &x, Node *l = nullptr, Node *r = nullptr) : key(key), x(x), l(l), r(r),
                                                                                 is_red(true) {}

        friend bool is_red(const Node *ptr) {
            return ptr && ptr->is_red;
        }

        friend Node *rotate_left(Node *h) {
            Node *r = h->r;
            // assert(r->is_red);
            h->r = r->l;
            r->l = h;
            r->is_red = h->is_red;
            h->is_red = true;
            return r;
        }

        friend Node *rotate_right(Node *h) {
            Node *l = h->l;
            // assert(l->is_red);
            h->l = l->r;
            l->r = h;
            l->is_red = h->is_red;
            h->is_red = true;
            return l;
        }

        friend void flip_colors(Node *h) {
            // assert(!h->is_red);
            // assert(h->l->is_red);
            // assert(h->r->is_red);
            h->is_red = true;
            h->l->is_red = h->r->is_red = false;
        }
    } *root;

    LLRB() : root(nullptr) {}

    Node *find(const Key &key, Node *ptr) {
        if (!ptr) return nullptr;
        int _ = cmp(key, ptr->key);
        if (_ < 0) return find(key, ptr->l);
        if (_ > 0) return find(key, ptr->r);
        return ptr;
    }

    T &find(const Key &key) {
        return find(key, root)->x;
    }

    Node *exist(const Key &key) {
        return find(key, root);
    }

    Node *insert(const Key &key, const T &x, Node *ptr) {
        if (!ptr) return new Node(key, x);
        int _ = cmp(key, ptr->key);
        if (_ < 0) ptr->l = insert(key, x, ptr->l);
        if (_ > 0) ptr->r = insert(key, x, ptr->r);
        if (_ == 0) throw DuplicateKeyError();

        if (!is_red(ptr->l) && is_red(ptr->r)) ptr = rotate_left(ptr);
        if (is_red(ptr->l) && is_red(ptr->l->l)) ptr = rotate_right(ptr);
        if (is_red(ptr->l) && is_red(ptr->r)) flip_colors(ptr);

        return ptr;
    }

    void insert(const Key &key, const T &x) {
        root = insert(key, x, root);
    }

    template<typename U>
    void traverse(U *func, Node *ptr) {
        if (!ptr) return;
        traverse(func, ptr->l);
        func(ptr);
        traverse(func, ptr->r);
    }

    template<typename U>
    void traverse(U *func) {
        traverse(func, root);
    }
};

char get_cmd() {
    char cmd;
    while (cmd = getchar()) {
        if ('a' <= cmd && cmd <= 'z') break;
    }
    char _;
    while (_ = getchar()) { if (_ == '\n' || _ == ' ') break; };
    return cmd;
}

void get_line(char* str) {
    char ch;
    while(ch = getchar()) {
        if (ch != '\n') {
            *(str++) = ch;
        } else break;
    }
    *str = '\0';
}

int main() {
    LLRB<String, int> cite;
    int cur_max = 0;
    char *cur_title = nullptr;
    while (true) {
        char cmd = get_cmd();
        if (cmd == 'c') {
            char *title = new char[512];
            get_line(title);
            auto ptr = cite.exist(String(title));
            int cnt;
            if (!ptr) {
                cite.insert(String(title), 1);
                cnt = 1;
            } else {
                ++ptr->x;
                cnt = ptr->x;
            }
            if (cnt > cur_max || cnt == cur_max && cmp(title, cur_title) < 0) {
                cur_max = cnt;
                cur_title = title;
            }
        } else if (cmd == 'q') {
            printf("%d %s\n", cur_max, cur_title);
        } else if (cmd == 'f') break;
    }
}