【UVA-1597】Searching the Web【字符串拆分+STL的简单应用】

【UVA-1597】Searching the Web【字符串拆分+STL的简单应用】

问题链接:https://vjudge.net/problem/UVA-1597

Solution:

由于输出要求大多是按照行为单位的,所以我们使用vector来记录行,并且记录清楚行号、文章号,之后将每个句子中的单词转化成小写字母,之后拆分出来,存到一个map中,map的值是一个集合,表示这个单词出现在对应的vector中的哪些句子记录中。拆分函数cutstr()十分关键。

#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <sstream>
#include <cctype>
#define DBG

using namespace std;

struct Centence {
    string str;
    int idx;
    int pos;
};

vector<Centence> datas;
struct cmp {
    bool operator()(const int a, const int b) const {
        if (datas[a].idx != datas[b].idx) return datas[a].idx < datas[b].idx;
        else if (datas[a].pos != datas[b].pos) return datas[a].pos < datas[b].pos;
        return a < b;
    }
};

inline void tolow(string &str) {
    for (int i = 0; i < str.size(); i++)
        if (isalpha(str[i])) str[i] = tolower(str[i]);
}
string in, out;
int cut_i;
inline bool cutstr(const string s) {
    if (s != "") in = s, cut_i = 0;
    if (cut_i == in.size()) return false;
    out = "";
    for (int cnt = 0; cut_i < in.size() && cnt < 2; cut_i++) {
        if (cnt == 0 && isalpha(in[cut_i])) cnt = 1;
        else if (cnt == 1 && !isalpha(in[cut_i])) cnt = 2;
        if (cnt == 1) out += in[cut_i];
    }
    if (out == "") return false;
    else return true;
}

map<string, set<int, cmp> > wordIdx;

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int n, m;
    cin >> n;
    string tmp, t;
    Centence c;
    int cnt = 0;
    getline(cin, tmp);
    for (int i = 0; cnt < n; i++) {
        getline(cin, tmp);
        if (tmp == "**********") {
            cnt++;
            i--;
            continue;
        }
        c.str = tmp, c.idx = cnt, c.pos = i;
        datas.push_back(c);
        stringstream ss;
        ss << tmp;
        while (ss >> t) {
            tolow(t);
            cutstr(t);
            do {
                if (!wordIdx.count(out)) wordIdx[out] = set<int, cmp>();
                wordIdx[out].insert(datas.size() - 1);
            } while (cutstr(""));
        }
    }
    cin >> m;
    string str;
    getline(cin, str);
    bool flag = true;
    while (m--) {
        getline(cin, str);
        stringstream ss;
        ss << str;
        t = "";
        ss >> tmp >> t;
        flag = true;
        if (t == "AND") {
            ss >> t;
            tolow(tmp), tolow(t);
            set<int, cmp> sa, sb, sc;
            sa = wordIdx[tmp], sb = wordIdx[t];
            for (int x : sa)
                for (int y : sb)
                    if (datas[x].idx == datas[y].idx) sc.insert(x), sc.insert(y);
            int pre;
            if (sc.empty()) cout << "Sorry, I found nothing.\n";
            else pre = datas[*sc.begin()].idx;
            for (auto x : sc) {
                if (datas[x].idx != pre) cout << "----------\n";
                pre = datas[x].idx;
                cout << datas[x].str << "\n";
            }
            cout << "==========\n";
        } else if (t == "OR") {
            ss >> t;
            tolow(tmp), tolow(t);
            set<int, cmp> sa, sb;
            sa = wordIdx[tmp], sb = wordIdx[t];
            for (int x : sb) sa.insert(x);
            int pre;
            if (sa.empty()) cout << "Sorry, I found nothing.\n";
            else pre = datas[*sa.begin()].idx;
            for (auto x : sa) {
                if (datas[x].idx != pre) cout << "----------\n";
                pre = datas[x].idx;
                cout << datas[x].str << "\n";
            }
            cout << "==========\n";
        } else if (tmp == "NOT") {
            tolow(t);
            set<int, cmp> sa = wordIdx[t];
            set<int> sb;
            for (int x : sa) {
                sb.insert(datas[x].idx);
            }
            int pre;
            if (sb.size() == n) cout << "Sorry, I found nothing.\n";
            else {
                bool flag = false;
                for (int i = 0; i < datas.size(); i++) {
                    if (sb.count(datas[i].idx)) continue;
                    if (flag && datas[i].idx != pre) cout << "----------\n";
                    else flag = true;
                    pre = datas[i].idx;
                    cout << datas[i].str << "\n";
                }
            }
            cout << "==========\n";
        } else {
            tolow(tmp);
            set<int, cmp> sa = wordIdx[tmp];
            int pre;
            if (sa.empty()) cout << "Sorry, I found nothing.\n";
            else pre = datas[*sa.begin()].idx;
            for (auto x : sa) {
                if (datas[x].idx != pre) cout << "----------\n";
                pre = datas[x].idx;
                cout << datas[x].str << "\n";
            }
            cout << "==========\n";
            flag = false;
        }
    }
    return 0;
}

 

【UVA-1596】Bug Hunt【紫书】

【UVA-1596】Bug Hunt【紫书】

问题链接:https://vjudge.net/problem/UVA-1596

Solution:

数组本身便可以看成一种映射,从序号(键)到数值(值)的映射,那么我们显然可以使用map来描述一个数组,同时我们还需要一个int类型的变量来描述它的长度(这样就不必每次都调用map.size()了),因此我们可以写一个结构体来为数组类型。题目要判断的bug其实只有:无效访问【越界或访问未声明的数组】、未初始化使用这两种,数组越界可以通过比较数组的大小来确定;我们使用vector来存放数组的数据,使用map来存储数组名称到vector中存储位置的映射,这样,对于未声明的数组,该数组名称一定不存在于这个map中;对于未初始化,该键一定不存在于对应的数组对象的map中。

考虑到中括号这个运算可以嵌套使用,并且每次嵌套都具有一定的形式不变性【每个中括号中不是形如xxxx[xxxx]这样的,就是形如xxxx这样的数了】,那么我们可以写一个递归函数,参数就是字符串和中括号的起始位置,返回中括号内的值,如果返回中途遇到了无效值,就返回-1表示无效。

#include <iostream>
#include <map>
#include <vector>
#include <cctype>
// #define DBG

using namespace std;

const int NIL = -1;
struct Array {
    map<int, int> dat;
    int size;
    bool isOverflow(int idx) { return idx >= size; }
    bool isAssigned(int idx) { return dat.find(idx) != dat.end(); }
};
vector<Array> data;
map<string, int> arraymap;

int getIndex(string &str, int pos) {
    pos++;
    if (isdigit(str[pos])) {
        int ret = 0;
        for (; pos < str.size() && str[pos] != ']'; pos++)
            ret = ret * 10 + str[pos] - '0';
        return ret;
    } else {
        string type = "";
        int ret = 0, get;
        for (; pos < str.size(); pos++) {
            if (str[pos] == '[') {
                get = getIndex(str, pos);
                if (get == NIL) return NIL;
                break;
            }
            type += str[pos];
        }
        if (arraymap.find(type) == arraymap.end()) return NIL;
        if (data[arraymap[type]].isOverflow(get)) return NIL;
        if (!data[arraymap[type]].isAssigned(get)) return NIL;
        return data[arraymap[type]].dat[get];
    }
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string op;
    string var, var2;
    int val, val2;
    int i, cnt;
    bool flag;
    while (getline(cin, op) && op[0] != '.') {
        flag = true;
        data.clear();
        arraymap.clear();
        cnt = 1;
        do {
            if (op.find('=') != string::npos) {
                var = var2 = "";
                val = val2 = 0;
                for (i = 0; op[i] != '['; i++)
                    var += op[i];
                val = getIndex(op, i);
                if (val == NIL ||
                    arraymap.find(var) == arraymap.end() ||
                    data[arraymap[var]].isOverflow(val)) {
                    cout << cnt << "\n";
                    flag = false;
                    break;
                }
                for (; op[i] != '='; i++);
                for (i++; op[i] == ' '; i++);
                if (isdigit(op[i])) {
                    for (; i < op.size() && isdigit(op[i]); i++)
                        val2 = val2 * 10 + op[i] - '0';
                } else {
                    for (; i < op.size() && op[i] != '['; i++)
                        var2 += op[i];
                    val2 = getIndex(op, i);
                    if (val2 == NIL ||
                        arraymap.find(var2) == arraymap.end() ||
                        data[arraymap[var2]].isOverflow(val2) ||
                        !data[arraymap[var2]].isAssigned(val2)) {
                        cout << cnt << "\n";
                        flag = false;
                        break;
                    }
                    val2 = data[arraymap[var2]].dat[val2];
                }
                data[arraymap[var]].dat[val] = val2;
            } else {
                var = "";
                val = 0;
                for (i = 0; op[i] != '['; i++)
                    var += op[i];
                val = getIndex(op, i);
                if (val == NIL ||
                    arraymap.find(var) != arraymap.end()) {
                    cout << cnt << "\n";
                    flag = false;
                    break;
                }
                arraymap[var] = data.size();
                data.push_back(Array());
                data[arraymap[var]].size = val;
            }
            cnt++;
        } while (getline(cin, op) && op[0] != '.');
        if (flag)
            cout << 0 << "\n";
        else
            while (getline(cin, op) && op[0] != '.');
    }
    return 0;
}

 

【UVA-230】Borrowers【紫书】

【UVA-230】Borrowers【紫书】

问题链接:https://vjudge.net/problem/UVA-230

Solution:

参考了绿书上描述的方法。我们使用vector来存全部书籍的数据,之后使用map来将书名映射到vector中的位置,开两个set分别管理剩下的书和刚还回来的书,利用struct实现一个伪函数,传给set模板第二参数,用它来进行题意上的排序【如果不清楚伪函数,可以去翻看《C++ Primer Plus》,或者直接百度一下】。

关于格式字符串,我们将一行字符串读进来后

使用for(; str[i] != ‘ ‘; i++);来跳过非空格字符,

使用for(; str[i] == ‘ ‘; i++);来跳过空格字符。

接着使用string类的assign()函数赋值将子串赋值给另一个字符串。

#include <iostream>
#include <set>
#include <unordered_map>
#include <string>
#include <vector>
// #define DBG

using namespace std;

struct Book {
    string title, author;
};
vector<Book> data;
struct cmp {
    bool operator() (const int a, const int b) {
        return data[a].author < data[b].author || (data[a].author == data[b].author && data[a].title < data[b].title);
    }
};
set<int, cmp> rest, back;
unordered_map<string, int> titlemap;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string str;
    int gblcnt;
    Book tmp;
    while (getline(cin, str) && str[0] != 'E') {
        gblcnt = data.size();
        int i;
        for (i = 1; str[i] != '\"'; i++);
        tmp.title.assign(str, 0, i + 1);
        for (i++; str[i] == ' '; i++);
        for (; str[i] != ' '; i++);
        for (; str[i] == ' '; i++);
        tmp.author.assign(str, i, str.size() - i);
#ifdef DBG
        cout << "title: " << tmp.title << endl;
        cout << "author: " << tmp.author << endl;
#endif
        data.push_back(tmp);
        titlemap[tmp.title] = gblcnt;
        rest.insert(gblcnt);
    }
    while (cin >> str && str[0] != 'E') {
#ifdef DBG
        cout << "operation: " << str << endl;
#endif
        if (str[0] == 'B') {
            string tmp;
            getline(cin, tmp);
            int i;
            for (i = 0; tmp[i] == ' '; i++);
            str.assign(tmp, i, tmp.size() - i);
            rest.erase(titlemap[str]);
        } else if (str[0] == 'R') {
            string tmp;
            getline(cin, tmp);
            int i;
            for (i = 0; tmp[i] == ' '; i++);
            str.assign(tmp, i, tmp.size() - i);
            back.insert(titlemap[str]);
        } else {
            set<int, cmp>::iterator ite;
            for (auto idx : back) {
                rest.insert(idx);
                ite = rest.find(idx);
                if (ite == rest.begin())
                    cout << "Put " << data[idx].title << " first\n";
                else
                    cout << "Put " << data[idx].title << " after " << data[*(--ite)].title << "\n";
            }
            back.clear();
            cout << "END\n";
        }
    }
    return 0;
}

 

【UVA-1595】Symmetry【紫书】

【UVA-1595】Symmetry【紫书】

问题链接:https://vjudge.net/problem/UVA-1595

Solution:

可以求出对称轴,之后判断一下每个点是否都有与它对称的点就好,仍然是set判重。

#include <iostream>
#include <set>
#include <cmath>

using namespace std;

struct Point {
    double x, y;
    bool operator < (const Point &p) const {
        if (x != p.x) return x < p.x;
        return y < p.y;
    }
};
set<Point> vis;

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    int t, n;
    double mid;
    Point crt;
    cin >> t;
    while (t--) {
        cin >> n;
        mid = 0;
        vis.clear();
        for (int i = 0; i < n; i++) {
            cin >> crt.x >> crt.y;
            mid += crt.x;
            vis.insert(crt);
        }
        mid /= n;
        bool flag = true;
        for (auto &p : vis) {
            if (p.x == mid) continue;
            if (!vis.count({p.x + (p.x < mid ? 2 * (mid - p.x) : -2 * (p.x - mid)), p.y})) {
                cout << "NO\n";
                flag = false;
                break;
            }
        }
        if (flag) cout << "YES\n";
    }
    return 0;
}

 

【UVA-12100】Printer Queue【紫书】

【UVA-12100】Printer Queue【紫书】

问题链接:https://vjudge.net/problem/UVA-12100

Solution:

模拟,使用STL的队列,我们需要用一个数组来判断是否存在比当前优先级更高优先级的打印任务,由于优先级的范围是1到9,假设当前任务的优先级为p,那么判断是否可以打印这个任务实际上就是判断p+1开始的后缀和是否为0,如果是0就打印,我们设置一个偏移变量,叫做OFF,它的值设置成最大优先级+2就可以,接着将每个优先级p映射为下标OFF – p,这样我们把对后缀和的查询转化为了对前缀和的查询,可以使用树状数组来实现动态前缀和,对于每个任务,我们判断树状数组中OFF – p – 1前缀和是否为0.【注:正是因为这里要取OFF – p – 1,并且树状数组下标最小应当设置成1,那么我们应当保证\(OFF – p_{max} – 1 = 1\),求解可以确定\(OFF = p_{max} + 2\)】。接着,每次打印一个任务都将一个计数变量cnt自增一。而关于m,我们只要判断它是不是0,如果不是0,就说明当前任务不是要找的那个任务,直接判断它能否打印来控制,m固定会自减1,正常模拟就好;如果是0,则说明这个任务就是题目要找的任务,如果它还不能打印,则移到队尾时一定要把m设置为队列大小-1,如果可以打印就先自增cnt,之后输出答案,结束循环。

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int OFF = 11;
int bit[OFF], cnt;
queue<int> list;

inline void init() {
    memset(bit, 0, sizeof bit);
    cnt = 0;
    while (!list.empty()) list.pop();
}

inline int lowbit(int x) {return x & (-x);}

void update(int x, int diff) {
    while (x < OFF) {
        bit[x] += diff;
        x += lowbit(x);
    }
}

int query(int x) {
    int ret = 0;
    while (x > 0) {
        ret += bit[x];
        x -= lowbit(x);
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, t, tmp;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        init();
        while (n--) {
            cin >> tmp;
            list.push(tmp);
            update(OFF - tmp, 1);
        }
        while (true) {
            tmp = list.front();
            list.pop();
            if (m) {
                if (query(OFF - tmp - 1)) list.push(tmp);
                else {
                    update(OFF - tmp, -1);
                    cnt++;
                }
                m--;
            } else {
                if (query(OFF - tmp - 1)) {
                    list.push(tmp);
                    m = list.size() - 1;
                } else {
                    cnt++;
                    cout << cnt << "\n";
                    break;
                }
            }
        }
    }
    return 0;
}

 

【UVA-10391】Compound Words【紫书】

【UVA-10391】Compound Words【紫书】

问题链接:https://vjudge.net/problem/UVA-10391

Solution:

两种思路,枚举所有拼接方式再根据set判重或枚举每个字符串的子串后set判重,前者复杂\(O(n^2)\),后者\(O(nm)\)。【其中m是字符串长度,这里忽略二者都需要的set判重的时间消耗】,结果是,前者会超时,后者可以ac。

后者的办法将每个字符串拆开成两个字符串,枚举所有拆法,判断两部分是否都在set中。使用string类下的assign()函数可以很方便的将子串摘出来。

另外,set判重除了可以使用find()函数,也可以用count()函数,对于set,count()的返回值只可能是0或1.

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

vector<string> data;
set<string> vis;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string str, l, r;
    while (cin >> str) vis.insert(str);
    for (auto &str : vis) {
        for (int i = 1; i < str.size() - 1; i++) {
            l.assign(str, 0, i);
            if (vis.find(l) != vis.end()) {
                r.assign(str, i, str.size() - i);
                if (vis.find(r) != vis.end()) {
                    cout << str << "\n";
                    break;
                }
            }
        }
    }
    return 0;
}

 

【UVA-10763】Foreign Exchange【紫书】

【UVA-10763】Foreign Exchange【紫书】

问题链接:https://vjudge.net/problem/UVA-10763

Solution:

排序,常见的无序变有序解决问题的方法。

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Node {
    int a, b;
    bool operator < (const Node & n) const {
        if (a != n.a) return a < n.a;
        return b < n.b;
    }
    bool operator != (const Node &n) const {
        return a != n.a || b != n.b;
    }
};
vector<Node> data;

inline void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, a, b;
    while (cin >> n && n) {
        data.clear();
        while (n--) {
            cin >> a >> b;
            if (a > b) swap(a, b);
            data.push_back({a, b});
        }
        if (data.size() & 1) {
            cout << "NO\n";
            continue;
        }
        sort(data.begin(), data.end());
        int i;
        for (i = 1; i < data.size(); i += 2)
            if (data[i] != data[i - 1]) break;
        if (i >= data.size()) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

 

【UVA-1594】Ducci Sequence【紫书】

【UVA-1594】Ducci Sequence【紫书】

问题链接:https://vjudge.net/problem/UVA-1594

Solution:

十分常见的方法,使用set进行判重,找循环节。

#include <iostream>
#include <set>
#include <vector>
#include <cmath>

using namespace std;

set<vector<int> > vis;
vector<int> tv, tvv;

inline bool isZero(const vector<int> &v) {
    for (int i = 0; i < v.size(); i++) if (v[i]) return false;
    return true;
}

int main(void) {
    int t, n, tmp;
    scanf("%d", &t);
    while (t--) {
        vis.clear();
        scanf("%d", &n);
        tv.clear();
        for (int i = 0; i < n; i++) {
            scanf("%d", &tmp);
            tv.push_back(tmp);
        }
        while (true) {
            tvv.clear();
            if (isZero(tv)) {
                printf("ZERO\n");
                break;
            }
            if (vis.find(tv) != vis.end()) {
                printf("LOOP\n");
                break;
            }
            vis.insert(tv);
            for (int i = 1; i < tv.size(); i++) {
                tvv.push_back(abs(tv[i - 1] - tv[i]));
            }
            tvv.push_back(abs(tv[tv.size() - 1] - tv[0]));
            tv = tvv;
        }
    }
    return 0;
}

 

【UVA-1593】Alignment of Code【紫书】

【UVA-1593】Alignment of Code【紫书】

问题链接:https://vjudge.net/problem/UVA-1593

Solution:

开数组,记录每行同一列单词的最大长度,用这个来补空格数量就可以了。

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

using namespace std;

const int LIM = 80;
int cnt[LIM];
int len = 0;
vector<vector<string> > data;

inline int maxi(int a, int b) {
    return a > b ? a : b;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string str, tmp;
    for (int i = 0; getline(cin, str); i++) {
        stringstream ss;
        ss << str;
        data.push_back(vector<string>());
        for (int j = 0; ss >> tmp; j++) {
            data[i].push_back(tmp);
            if (data[i][j].size() > cnt[j]) cnt[j] = data[i][j].size();
            if (j > len) len = j;
        }
    }
    for (int i = 0; i < data.size(); i++) {
        for (int j = 0; j < data[i].size(); j++) {
            cout << data[i][j];
            if (j != data[i].size() - 1)
                for (int k = data[i][j].size(); k <= cnt[j]; k++) cout << ' ';
        }
        cout << "\n";
    }
    return 0;
}

 

【UVA-221】Urban Elevations【紫书】【离散化】

【UVA-221】Urban Elevations【紫书】【离散化】

问题链接:https://vjudge.net/problem/UVA-221

Solution:

按照紫书上的方法写的,所以只记录一点个人理解。数据取值范围是实数域,枚举x坐标无法做到,所以我们将x坐标离散化,专门开一个数组,存储所有端点x坐标,从小到大排序,去重【可以使用unique函数】,构成了一个无重复端点值数组,由于数据量不大, 可以对于每个建筑物都暴力找它在那个区间中,对于每个建筑物,都暴力判断它是否被遮挡,得益于离散化,这个端点数组中任意两个相邻值之间不存在额外的端点,因此这中间任意一个数值坐标都可以用来判断一个建筑是否包含这组端点,这里可以取中点,能很大程度上避免浮点误差的问题。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int LIM = 100 + 10;
const double EPS = 1e-6;
struct Building{
    int id;
    double x, y, w, h;
    bool operator < (const Building &p) {
        if (x != p.x) return x < p.x;
        return y < p.y;
    }
} builds[LIM];
double points[LIM * 2];
int gblCnt, n;

inline void init() {
    memset(points, 0, sizeof points);
    memset(builds, 0, sizeof builds);
    gblCnt = 1;
}

inline bool isInRange(int idx, double pos) {
    return builds[idx].x <= pos && pos <= builds[idx].x + builds[idx].w;
}

bool isVisible(int idx, double mid) {
    for (int i = 0; i < n; i++) {
        if (i == idx) continue;
        if (builds[i].y < builds[idx].y && builds[i].h >= builds[idx].h && isInRange(i, mid))
            return false;
    }
    return true;
}

int main(void) {
    for (int k = 1; ~scanf("%d", &n) && n; k++) {
        init();
        if (k - 1) putchar('\n');
        printf("For map #%d, the visible buildings are numbered as follows:\n", k);
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf%lf%*lf%lf", &builds[i].x, &builds[i].y, &builds[i].w, &builds[i].h);
            builds[i].id = i + 1;
            points[i << 1] = builds[i].x, points[(i << 1) + 1] = builds[i].x + builds[i].w;
        }
        sort(points, points + n * 2);
        sort(builds, builds + n);
        int len = unique(points, points + n * 2) - points;
        printf("%d", builds[0].id);
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < len; j++) {
                int mid = (points[j] + points[j - 1]) / 2;
                if (!isInRange(i, mid)) continue;
                if (isVisible(i, (points[j] + points[j - 1]) / 2)) {
                    printf(" %d", builds[i].id);
                    break;
                }
            }
        }
        putchar('\n');
    }
    return 0;
}