【UVA-814】The Letter Carrier’s Rounds【紫书】

【UVA-814】The Letter Carrier’s Rounds【紫书】

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

Solution:

这道题看着复杂,做起来并不是很难,核心需要注意的是去重,如果发送目标出现重复的话要避免加入到收件人列表中。去重使用set就好。建议在编码前有一个统筹思路充分考虑到去重问题,下面的代码最开始忽略了去重,后面虽然通过添加set去重成功ac了,但是代码有些繁杂。

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

using namespace std;

map<string, int> mtaMap;
map<int, set<string> > mtaDest;
map<int, vector<string> > sendList;
set<string> personSet;
set<int> destSet;
vector<string> dest;
vector<string> message;
int gblCnt = 1;

int main(void) {
    ios::sync_with_stdio(false);
    // cin.tie(NULL);
    string str, getter, getArea, sender, fromArea;
    int n, t;
    while (cin >> str && str[0] != '*') {
        cin >> str;
        mtaMap[str] = gblCnt++;
        t = mtaMap[str];
        cin >> n;
        while (n--) {
            cin >> str;
            mtaDest[t].insert(str);
#ifdef DBG
            cout << "crt : " << str << "\n";
#endif
        }
    }
    while (cin >> str && str[0] != '*') {
        sendList.clear();
        message.clear();
        dest.clear();
        destSet.clear();
        personSet.clear();
        str[str.find("@")] = ' ';
        stringstream ss;
        ss << str;
        ss >> sender >> fromArea;
#ifdef DBG
        cout << sender << "---" << fromArea << "\n";
#endif
        while (cin >> str && str[0] != '*') {
            str[str.find("@")] = ' ';
            stringstream ss;
            ss << str;
            ss >> getter >> getArea;
#ifdef DBG
            cout << getter << "---" << getArea << "\n";
            cout << "MAP : " << getArea << " - " << mtaMap[getArea] << "\n";
#endif
            if (personSet.find(getter) == personSet.end()) {
                personSet.insert(getter);
                sendList[mtaMap[getArea]].push_back(getter);
            }
            if (destSet.find(mtaMap[getArea]) == destSet.end()) {
                dest.push_back(getArea);
                destSet.insert(mtaMap[getArea]);
            }
        }
        while (getline(cin, str) && str[0] != '*') message.push_back(str);
        for (int i = 0; i < dest.size(); i++) {
            bool flag = false;
            cout << "Connection between " << fromArea << " and " << dest[i] << "\n";
            cout << "     HELO " << fromArea << "\n";
            cout << "     250\n";
            cout << "     MAIL FROM:<" << sender << "@" << fromArea << ">\n";
            cout << "     250\n";
            vector<string> &tmpList = sendList[mtaMap[dest[i]]];
            for (int j = 0; j < tmpList.size(); j++) {
                cout << "     RCPT TO:<" << tmpList[j] << "@" << dest[i] << ">\n";
                if (mtaDest[mtaMap[dest[i]]].find(tmpList[j]) == mtaDest[mtaMap[dest[i]]].end()) {
                    cout << "     550\n";
                } else {
                    cout << "     250\n";
                    flag = true;
                }
            }
            if (flag) {
                cout << "     DATA\n";
                cout << "     354\n";
                for (int j = 1; j < message.size(); j++)
                    cout << "     " << message[j] << "\n";
                cout << "     .\n";
                cout << "     250\n";
            }
            cout << "     QUIT\n";
            cout << "     221\n";
        }
    }
    return 0;
}

 

【UVA-1592】Database【紫书】

【UVA-1592】Database【紫书】

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

Solution:

枚举思路是:枚举任意两列,之后扫描全部行,经过的行根据该行正在枚举的两列的值,先判断是否在前几行有出现过【根据map】,如果没有就放入map中,并将值设置为行数,反之输出结果并跳出循环。这样的时间复杂度是\(O(nm^2)\)【已忽略map操作的复杂度】,其中n是行数,m是列数。由于字符串比较相当耗时,我们先将字符串的值进行离散化,给每个字符串一个id标识,存放在另外一个map中。

关于输入格式的处理,由于判题系统的支持,所以可以很方便地使用正则表达式就好。

需要注意的是,为了使用map,我们自行定义了结构体,并重载比较运算符<,重载的时候一定让两值取等号时返回false,不然map可能会错误地判断两个相同的key值为不同的,特别是在处理两个字符串的时候。

#include <iostream>
#include <cstring>
#include <map>
#include <set>
// #define DBG

using namespace std;

const int SIZE = 80;
struct String {
    char str[SIZE];
    bool operator < (const String & s) const {
        int i;
        for (i = 0; str[i] && s.str[i]; i++)
            if (str[i] != s.str[i]) return str[i] < s.str[i];
        if (str[i] && !s.str[i]) return false;
        if (!str[i] && !s.str[i]) return false;
        return true;
    }
} tmpStr, data[10000][10];
struct Pair {
    int a, b;
    bool operator < (const Pair & p) const {
        if (a != p.a) return a < p.a;
        return b < p.b;
    }
};
map<String, int> strMap;
map<Pair, int> vis;
int gblCnt;         //global count

inline void init() {
    strMap.clear();
    gblCnt = 1;
}

int main(void) {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        while (getchar() != '\n');
        init();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m - 1; j++) {
                scanf("%[^,]%*c", tmpStr.str);
                if (!strMap[tmpStr]) strMap[tmpStr] = gblCnt++;
                data[i][j] = tmpStr;
            }
            scanf("%[^\n]%*c", tmpStr.str);
            if (!strMap[tmpStr]) strMap[tmpStr] = gblCnt++;
            data[i][m - 1] = tmpStr;
        }
        bool flag = true;
        for (int i = 0; flag && i < m; i++) {
            for (int j = i + 1; flag && j < m; j++) {
                vis.clear();
                for (int k = 0; flag && k < n; k++) {
                    Pair tmp = {strMap[data[k][i]], strMap[data[k][j]]};
#ifdef DBG
                    printf("%d : %s\n", strMap[data[k][i]], data[k][i].str);
                    printf("%d : %s\n\n", strMap[data[k][j]], data[k][j].str);
                    printf("%d : pair()\n", vis[tmp]);
#endif
                    if (vis[tmp]) {
                        printf("NO\n");
                        printf("%d %d\n", vis[tmp], k + 1);
                        printf("%d %d\n", i + 1, j + 1);
                        flag = false;
                    } else {
                        vis[tmp] = k + 1;
                    }
                }
            }
        }
        if (flag) printf("YES\n");
    }
    return 0;
}

 

【UVA-400】Unix ls【紫书】

【UVA-400】Unix ls【紫书】

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

Solution:

控制一下输出格式,一行最多60个字符,根据题意,我们首先在读取文件名时找到最长的字符串的长度【假设叫做m】,之后计算出\(\frac{60}{m + 2}\),这个值还不是最终的每行的文件数,我们还需要考虑一下60除以m+2的余数是否不小于m,如果是的话每行还可以再多一个文件名。算出了每行最多能放多少个文件名后,就可以计算出行数了,只要用文件数除以每行个数之后向上取整就好。

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

using namespace std;

vector<string> files;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int m, n, r, numInLine;
    string str;
    while (cin >> n) {
        files.clear();
        m = 0;
        for (int i = 0; i < n; i++) {
            cin >> str;
            files.push_back(str);
            if (str.size() > m) m = str.size();
        }
        sort(files.begin(), files.end());
        numInLine = 60 / (m + 2);
        if (60 % (m + 2) >= m) numInLine++;
        r = (n + numInLine - 1) / numInLine;
        cout << "------------------------------------------------------------\n";
        for (int i = 0; i < r; i++) {
            for (int j = i; j < files.size(); j += r) {
                cout << files[j];
                int cnt = (j + r < files.size() ? m - files[j].size() + 2 : 0);
                while (cnt--) cout << ' ';
            }
            cout << "\n";
        }
    }
    return 0;
}

 

【UVA-136】Ugly Numbers【bfs+priority_queue+set】

【UVA-136】Ugly Numbers【bfs+priority_queue+set】

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

Solution:

看起来有些复杂,实际上只是一个bfs,从1开始搜索,每次都将2倍、3倍、5倍的值加入队列,如果它们还没有出现过的话,判断是否出现过使用set就好。之后我们定义一个结构体,重载<运算符,使用priority_queue优先队列【因为它默认是一个大顶堆,即从大到小,由于我们需要从小到大,所以通过重载结构体的<运算符来实现】。现在保证了队列中所有的数都是从小到大出现的,那么只要找到第1500个数就好了。

#include <iostream>
#include <queue>
#include <set>
// #define DBG

using namespace std;

typedef long long LL;
struct Num {
    LL num;
    bool operator<(const Num & n) const { return num > n.num; }
};
const int DEST = 1500;
set<int> vis;
LL dir[] = {2, 3, 5};

void bfs() {
    Num crt = {1};
    int cnt = 0;
    priority_queue<Num> q;
    q.push(crt);
    vis.insert(1);
    while (!q.empty()) {
        crt = q.top();
        q.pop();
        cnt++;
#ifdef DBG
        printf("crt : %d\n", crt.num);
#endif
        if (cnt == DEST) {
            printf("The 1500'th ugly number is %d.\n", crt.num);
            return;
        }
        for (int i = 0; i < 3; i++) {
            LL nxt = crt.num * dir[i];
            if (vis.find(nxt) == vis.end()) {
                q.push({nxt});
                vis.insert(nxt);
            }
        }
    }
}

int main(void) {
    bfs();
    return 0;
}

 

【UVA-540】Team Queue【紫书】【队列】

【UVA-540】Team Queue【紫书】【队列】

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

Solution:

这道题是嵌套队列,每个team内部是一个队列,之后每个team又各自作为一个元素排到一个长队列中,我们仍然可以使用对team进行唯一编号的方法,首先为team开一个queue数组,之后再开一个map来确定每个队员应当属于哪个team,之后我们需要思考一个问题是,如何决定什么时候该将team插入到长队列中,以及什么时候应当删除:其实十分简单,在给team自身的队列进行插入操作之前,先判断它是不是为空,如果是空,则说明它一定不在长队列中,所以要先把team插入;如果我们在对一个team的队列进行出队操作后,该队列变成空队列,那么就应当在长队列中把它弹出去。

#include <iostream>
#include <queue>
#include <map>
#include <cstring>
#include <string>

using namespace std;

const int SIZE = 1010;
queue<int> teams[SIZE];
queue<int> teamq;
map<int, int> teamType;
int teamCnt = 1;

inline void init() {
    teamCnt = 1;
    teamType.clear();
    for (int i = 0; i < SIZE; i++)
        while (!teams[i].empty()) teams[i].pop();
    while (!teamq.empty()) teamq.pop();
}

void enqueue(int num) {
    int team = teamType[num];
    if (teams[team].empty()) teamq.push(team);
    teams[team].push(num);
}

int dequeue() {
    int team = teamq.front();
    int ret = teams[team].front();
    teams[team].pop();
    if (teams[team].empty()) teamq.pop();
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t, n, num;
    string op;
    for (int k = 1; cin >> t && t; k++) {
        cout << "Scenario #" << k << "\n";
        init();
        while (t--) {
            cin >> n;
            while (n--) {
                cin >> num;
                teamType[num] = teamCnt;
            }
            teamCnt++;
        }
        while (cin >> op && op[0] != 'S') {
            if (op[0] == 'E') {
                cin >> num;
                enqueue(num);
            } else if (op[0] == 'D') {
                cout << dequeue() << endl;
            }
        }
        cout << '\n';
    }
    return 0;
}

 

【UVA-12096】The SetStack Computer【紫书】

【UVA-12096】The SetStack Computer【紫书】

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

Solution:

简单来说,问题要对集合进行操作,只是,它要操作的是集合与集合的集合与集合的集合的集合…显然我们不可能实现set< set< set< ……..> > >这样的类型,事实上,也不需要这样做,我们可以将不同类型的集合进行编号【独一无二的编号】,之后对于每个集合只要把编号插入其中,这样无论有多少个集合,它们的形式都是完全相同的set<int>,这样问题就可以得到解决。

#include <iostream>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <string>

using namespace std;

map<set<int>, int> idmap;
stack<set<int> > sets;
set<int> stop, ssec;
int gblid;

inline void check(const set<int> &s) {
    if (!idmap[s]) idmap[s] = gblid++;
}

inline void init() {
    idmap.clear();
    while (!sets.empty()) sets.pop();
    gblid = 1;
}

void popTwo() {
    stop = sets.top();
    sets.pop();
    ssec = sets.top();
    sets.pop();
}

int push() {
    set<int> s;
    check(s);
    sets.push(s);
    return 0;
}

int dup() {
    set<int> s = sets.top();
    sets.push(s);
    return s.size();
}

int unionOp() {
    popTwo();
    for (set<int>::iterator ite = ssec.begin(); ite != ssec.end(); ite++)
        stop.insert(*ite);
    check(stop);
    sets.push(stop);
    return stop.size();
}

int interOp() {
    popTwo();
    set<int> s;
    for (set<int>::iterator ite = ssec.begin(); ite != ssec.end(); ite++)
        if (stop.find(*ite) != stop.end()) s.insert(*ite);
    check(s);
    sets.push(s);
    return s.size();
}

int add() {
    popTwo();
    set<int> s = ssec;
    s.insert(idmap[stop]);
    check(s);
    sets.push(s);
    return s.size();
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t, n;
    string op;
    cin >> t;
    while (t--) {
        init();
        cin >> n;
        while (n--) {
            cin >> op;
            if (op == "PUSH") cout << push() << "\n";
            else if (op == "DUP") cout << dup() << "\n";
            else if (op == "UNION") cout << unionOp() << "\n";
            else if (op == "INTERSECT") cout << interOp() << "\n";
            else if (op == "ADD") cout << add() << "\n";
        }
        cout << "***\n";
    }
    return 0;
}

 

【UVA-815】Flooded!【紫书】【浮点误差处理】

【UVA-815】Flooded!【紫书】【浮点误差处理】

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

Solution:

这道题的思路十分简单,问水能严格淹没多少个区域,我们可以先将所有区域的高度从小到大排个序,之后从第二个(也就是数组中1号元素)开始枚举【因为水在地面上,它的高度不可能比高度最低的那个地面还要低】。我们预先将水的体积除以了单位底面积100,之后枚举的时候,它占几个格除以几就可以,不需要再除以100。对于每次枚举,我们要将前一次已经淹没的部分并入v中,因为它们也会占据一定的体积。之后就是关键的部分:浮点误差。由于是浮点数计算,很容易产生浮点误差,我们的做法是:指定一个精度常量EPS,每次浮点除法计算后,要将EPS加入到结果中。【需要注意一点,由于运算结果是负数,所以我们要判断一下结果的正负来决定应该加或减去EPS,判断正负的方法就是和0比大小,当然,由于浮点误差,我们自然不能直接判断<0,而是用结果-0<EPS来判断,由于-0计算没有意义,直接判断一个数<EPS就好】。

#include <iostream>
#include <algorithm>
#include <cmath>
// #define DBG

using namespace std;

const int LIM = 30 * 30 + 10;
const double AREA = 100;
const double EPS = 1e-6;
int data[LIM];

int main(void) {
    int n, m, len, i;
    double height, v;
    for (int k = 1; ~scanf("%d%d", &n, &m) && n && m; k++) {
        printf("Region %d\n", k);
        len = n * m;
        for (i = 0; i < len; i++) scanf("%d", data + i);
        scanf("%lf", &v);
        v = v / AREA + EPS;
        sort(data, data + len);
        for (i = 1; i < len; i++) {
            v += data[i - 1];
            height = v / i + (height < EPS ? -EPS : EPS);
#ifdef DBG
            printf("height : %f\n", height);
#endif
            if (height - data[i] <= EPS) break;
        }
        if (i == len) height = (v + data[i - 1]) / i + (height < EPS ? -EPS : EPS);
        printf("Water level is %.2f meters.\n"
            "%.2f percent of the region is under water.\n\n", height, i * 100.0 / len + (height < EPS ? -EPS : EPS));
    }
    return 0;
}

 

【UVA-12108】Extraordinarily Tired Students【紫书】

【UVA-12108】Extraordinarily Tired Students【紫书】

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

Solution:

看到这个题莫名想到一个东西——元胞自动机,虽然和这道题差距很大,但是基本思路能确定下来——模拟。模拟每分钟的情况就好了。需要注意的是这道题初始状态时间为1。关于判重,仍然可以用set+hash判重的常见方法,学生数不超过时,同时每个学生的状态只用两个十进制数就可以表示,我将每个学生高位记录它当前所处时间(取值范围是0到a+b),低位存1(表示睡着)或0(表示清醒)。

#include <iostream>
#include <set>

using namespace std;

typedef unsigned long long ULL;
const int LIM = 11;
bool state[LIM];        // true is sleep
int minut[LIM], period[LIM], a[LIM], b[LIM], n, cnt;
set<ULL> vis;

inline ULL getHash(void) {
    ULL ret = 0;
    for (int i = 0; i < n; i++)
        ret = ret * 100 + minut[i] * 10 + (state[i] ? 1 : 0);
    return ret;
}

int main(void) {
    int ans;
    for (int k = 1; ~scanf("%d", &n) && n; k++) {
        printf("Case %d: ", k);
        ans = 1;
        cnt = 0;
        vis.clear();
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d", a + i, b + i, minut + i);
            period[i] = a[i] + b[i];
            minut[i] %= period[i];
            if (period[i] > a[i] || !minut[i]) {
                state[i] = true;
                cnt++;
            }
        }
        vis.insert(getHash());
        for (; cnt; ans++) {
            int tmpcnt = 0;
            for (int i = 0; i < n; i++) {
                minut[i] = (minut[i] + 1) % period[i];
                if ((minut[i] > a[i] || !minut[i]) && cnt > (n / 2)) state[i] = true;
                else if (minut[i] && minut[i] <= a[i]) state[i] = false;
                if (state[i]) tmpcnt++;
            }
            cnt = tmpcnt;
            ULL tmp = getHash();
            if (vis.find(tmp) != vis.end()) {
                printf("-1\n");
                break;
            } else {
                vis.insert(tmp);
            }
        }
        if (!cnt) printf("%d\n", ans);
    }
    return 0;
}

 

【UVA-12412】A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)

【UVA-12412】A Typical Homework (a.k.a Shi Xiong Bang Bang Mang)

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

Solution:

这个题。。。有一种《C Primer Plus》或《C++ Primer Plus》课后作业的感觉。难度不大,题目要求查询的时候按照原顺序输出,同时注意到学生数最多100个,预估没有使用其它更快查找方法的必要,每次直接\(O(n)\)遍历查询。

建议在编码前设计好各个模块,采用模块化的思路,减少模块间的耦合度,这样可以减少人为出错的几率,同时也对排查错误很有帮助。

然后这道题比较有价值的是:

1)我下面的代码使用了链表的数据结构,使用数组来实现,让0号结点的下一个结点将是链表的开头,同时规定最后一个结点的下一个结点是0号结点,使用一个变量【我把它叫做last】表示尾结点在数组中的位置,使用另外一个变量【我叫做pos】表示目前最大使用到的数组位置,如果移除某个结点后,就把那个结点的位置加到一个vector或者queue里,表示数组中前面有位置已经失效,可以被新的数据覆盖了,每次插入结点先判断vector或queue里是否存放有已经失效的结点位置,如果有就优先放到数组中那个位置,如果没有则放在pos处,并将pos增加。这样链表实现方法在实际项目中不建议使用,由于是竞赛题目,为了减少不必要的申请内存时间消耗,可以这样实现。

2)这道题在精度上有坑点,数据会有浮点误差,将那几个浮点数加上一个精度值【经测设1e-4、 1e-5、 1e-6都是可行的】后就可以通过了。

3)Fast I/O,对于这道问题并不需要的,从最后结果来看,它的数据很水,0ms跑完,在有些竞赛程序中十分重要,特别是题目明确说明输入会很大的时候,这个时候可以通过:

ios::sync_with_stdio(false);

cin.tie(NULL);

来提速,但是需要注意,上面那行将使C++提供的iostream解除与C的stdio的同步,默认是true,设为false后就不要使用scanf和printf了;而cin.tie(NULL)则是将cin和cout解绑,这个绑定原本的作用是保证在cin尝试读取输入时刷新输出流【这个操作会产生一些耗时】,在交互式程序中十分必要,在竞赛程序中不需要,因为输入都是预先设定好的。【需要注意的是,如果手动在控制台中调试的时候要把这个注释掉,否则可能会出现输入输出顺序混乱的问题】

还有一种更快的Fast I/O方法,常常是大量输入的情况下,手动通过getchar()来实现一个输入函数读取整数、浮点数,如这道题目:https://www.spoj.com/problems/INTEST/

 

C++实现:

#include <iostream>
#include <queue>
#include <string>
#include <set>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

const int LIM = 120;
const int SIZE = 4;
const int CLASSCNT = 20 + 1;
const double EPS = 1e-6;
struct Student {
    string sid, name;
    int cid;
    int score[SIZE];
    int rank, tot;
    int nxt, pre;
};
struct Rank {
    int idx, score;
    bool operator < (const Rank & r) const { return score > r.score; }
};
Student list[LIM];
Rank val[LIM];
queue<int> emptyIdx;
set<string> exists;
vector<Student> ret;
enum {CH, MATH, EN, PRO, ALL};
int pos = 1, last = 0, rankLen, passedCnt[CLASSCNT][SIZE], overCnt[CLASSCNT][SIZE + 1], num[CLASSCNT] = {0}, sum[CLASSCNT][SIZE];
bool newestRank = false;

bool isSid(const string &str) {
    return isdigit(str[0]);
}

bool add(const Student & stu) {
    if (exists.find(stu.sid) != exists.end()) return false;
    newestRank = false;
    int p;
    if (!emptyIdx.empty()) {
        p = emptyIdx.front();
        emptyIdx.pop();
    } else {
        p = pos++;
    }
    list[p] = stu;
    for (int i = 0; i < SIZE; i++) list[p].tot += list[p].score[i];
    list[last].nxt = p;
    list[p].pre = last;
    list[p].nxt = 0;
    last = p;
    exists.insert(stu.sid);
    num[list[p].cid]++, num[0]++;
    return true;
}

int del(const string &str) {
    newestRank = false;
    int cnt = 0, p;
    if (isSid(str)) {
        for (p = list[0].nxt; p; p = list[p].nxt)
            if (list[p].sid == str) {
                list[list[p].pre].nxt = list[p].nxt;
                list[list[p].nxt].pre = list[p].pre;
                if (p == last) last = list[p].pre;
                emptyIdx.push(p);
                exists.erase(list[p].sid);
                num[list[p].cid]--, num[0]--;
                return 1;
            }
    } else {
        last = 0;
        for (p = list[0].nxt; p; p = list[p].nxt)
            if (list[p].name == str) {
                list[list[p].pre].nxt = list[p].nxt;
                list[list[p].nxt].pre = list[p].pre;
                emptyIdx.push(p);
                exists.erase(list[p].sid);
                num[list[p].cid]--, num[0]--;
                cnt++;
            } else {
                last = p;
            }
    }
    return cnt;
}

void calRank(void) {
    if (!newestRank) {
        int rank = 1;
        memset(passedCnt, 0, sizeof passedCnt);
        memset(overCnt, 0, sizeof overCnt);
        memset(sum, 0, sizeof sum);
        rankLen = 0;
        for (int p = list[0].nxt; p; p = list[p].nxt, rankLen++) {
            val[rankLen].score = 0;
            val[rankLen].idx = p;
            int tmp = SIZE;
            for (int i = 0; i < SIZE; i++) {
                val[rankLen].score += list[p].score[i];
                if (list[p].score[i] >= 60) passedCnt[0][i]++, passedCnt[list[p].cid][i]++;
                else tmp--;
                sum[0][i] += list[p].score[i];
                sum[list[p].cid][i] += list[p].score[i];
            }
            overCnt[0][tmp]++, overCnt[list[p].cid][tmp]++;
        }
        sort(val, val + rankLen);
        for (int i = 0; i < rankLen; i++) {
            if (i && val[i].score != val[i - 1].score) rank = i + 1;
            list[val[i].idx].rank = rank;
        }
        newestRank = true;
    }
}

void query(const string &str) {
    if (!newestRank) calRank();
    int p;
    ret.clear();
    if (isSid(str)) {
        for (p = list[0].nxt; p; p = list[p].nxt) {
            if (list[p].sid == str) {
                ret.push_back(list[p]);
                return;
            }
        }
    } else {
        for (p = list[0].nxt; p; p = list[p].nxt)
            if (list[p].name == str) ret.push_back(list[p]);
    }
}

inline void statics(void) {
    if (!newestRank) calRank();
}

inline void showMenu() {
    cout << "Welcome to Student Performance Management System (SPMS).\n\n"
        << "1 - Add\n"
        << "2 - Remove\n"
        << "3 - Query\n"
        << "4 - Show ranking\n"
        << "5 - Show Statistics\n"
        << "0 - Exit\n\n";
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.setf(ios::fixed);
    cout.precision(2);
    int op = 0;
    Student tmp;
    string str;
    tmp.tot = 0;
    showMenu();
    while (cin >> op && op) {
        if (op == 1) {
            while (true) {
                cout << "Please enter the SID, CID, name and four scores. Enter 0 to finish.\n";
                cin >> tmp.sid;
                if (tmp.sid == "0") break;
                cin >> tmp.cid >> tmp.name;
                for (int i = 0; i < SIZE; i++) cin >> tmp.score[i];
                if (!add(tmp)) cout << "Duplicated SID.\n";
            }
        } else if (op == 2) {
            while (true) {
                cout << "Please enter SID or name. Enter 0 to finish.\n";
                cin >> str;
                if (str == "0") break;
                int cnt = del(str);
                cout << cnt << " student(s) removed.\n";
            }
        } else if (op == 3) {
            while (true) {
                cout << "Please enter SID or name. Enter 0 to finish.\n";
                cin >> str;
                if (str == "0") break;
                query(str);
                for (int i = 0; i < ret.size(); i++) {
                    cout << ret[i].rank << " "
                        << ret[i].sid << " "
                        << ret[i].cid << " "
                        << ret[i].name;
                    for (int j = 0; j < SIZE; j++) cout << " " << ret[i].score[j];
                    cout << " " << ret[i].tot
                        << " " << 1.0 * ret[i].tot / SIZE + EPS << "\n";
                }
            }
        } else if (op == 4) {
            cout << "Showing the ranklist hurts students' self-esteem. Don't do that.\n";
        } else if (op == 5) {
            cout << "Please enter class ID, 0 for the whole statistics.\n";
            statics();
            cin >> op;
            cout << "Chinese\n"
                << "Average Score: " << 1.0 * sum[op][CH] / num[op] + EPS << "\n"
                << "Number of passed students: " << passedCnt[op][CH] << "\n"
                << "Number of failed students: " << num[op] - passedCnt[op][CH] << "\n\n"
                << "Mathematics" << "\n"
                << "Average Score: " << 1.0 * sum[op][MATH] / num[op] + EPS << "\n"
                << "Number of passed students: " << passedCnt[op][MATH] << "\n"
                << "Number of failed students: " << num[op] - passedCnt[op][MATH] << "\n\n"
                << "English\n"
                << "Average Score: " << 1.0 * sum[op][EN] / num[op] + EPS << "\n"
                << "Number of passed students: " << passedCnt[op][EN] << "\n"
                << "Number of failed students: " << num[op] - passedCnt[op][EN] << "\n\n"
                << "Programming\n"
                << "Average Score: " << 1.0 * sum[op][PRO] / num[op] + EPS << "\n"
                << "Number of passed students: " << passedCnt[op][PRO] << "\n"
                << "Number of failed students: " << num[op] - passedCnt[op][PRO] << "\n\n"
                << "Overall:\n"
                << "Number of students who passed all subjects: " << overCnt[op][4] << "\n"
                << "Number of students who passed 3 or more subjects: " << overCnt[op][3] + overCnt[op][4] << "\n"
                << "Number of students who passed 2 or more subjects: " << overCnt[op][2] + overCnt[op][3] + overCnt[op][4] << "\n"
                << "Number of students who passed 1 or more subjects: " << overCnt[op][1] + overCnt[op][2] + overCnt[op][3] + overCnt[op][4] << "\n"
                << "Number of students who failed all subjects: " << overCnt[op][0] << "\n\n";
        }
        showMenu();
    }
}

 

【UVA-512】Spreadsheet Tracking【紫书】

【UVA-512】Spreadsheet Tracking【紫书】

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

Solution:

不需要模拟,提前把操作存储下来,之后每一次查询顺着遍历一次操作就好。

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

using namespace std;

const int LIM = 10;
const int NIL = -1;
enum {EX, DC, DR, IC, IR};
struct Operation {
    int t, val[LIM];
};
struct Node {
    int r, c;
};
vector<Operation> ops;

int main(void) {
    Operation tmp;
    Node tnode;
    char op[3];
    int n, R, C, a;
    for (int k = 1; ~scanf("%d%d", &R, &C) && R && C; k++) {
        if (k - 1) putchar('\n');
        printf("Spreadsheet #%d\n", k);
        ops.clear();
        scanf("%d", &n);
        while (n--) {
            memset(tmp.val, NIL, sizeof(int) * LIM);
            scanf("%s", op);
            if (!strcmp(op, "EX")) tmp.t = EX;
            else if (!strcmp(op, "DC")) tmp.t = DC;
            else if (!strcmp(op, "DR")) tmp.t = DR;
            else if (!strcmp(op, "IC")) tmp.t = IC;
            else if (!strcmp(op, "IR")) tmp.t = IR;
            if (tmp.t != EX) scanf("%d", &a);
            else a = 4;
            for (int i = 0; i < a; i++) scanf("%d", tmp.val + i);
            ops.push_back(tmp);
        }
        scanf("%d", &n);
        while (n--) {
            scanf("%d%d", &tnode.r, &tnode.c);
            Node bak = tnode;
            bool flag = true;
            int cnt;
            for (int i = 0; i < ops.size(); i++) {
                cnt = 0;
                if (ops[i].t == EX) {
                    if (ops[i].val[0] == tnode.r && ops[i].val[1] == tnode.c)
                        tnode.r = ops[i].val[2], tnode.c = ops[i].val[3];
                    else if (ops[i].val[2] == tnode.r && ops[i].val[3] == tnode.c)
                        tnode.r = ops[i].val[0], tnode.c = ops[i].val[1];
                } else {
                    for (int j = 0; j < LIM; j++) {
                        if (ops[i].val[j] == NIL) break;
                        if (ops[i].t == DC && ops[i].val[j] == tnode.c) {
                            flag = false;
                            break;
                        }
                        if (ops[i].t == DR && ops[i].val[j] == tnode.r) {
                            flag = false;
                            break;
                        }
                        if ((ops[i].t == DC || ops[i].t == IC) && ops[i].val[j] <= tnode.c) cnt++;
                        if ((ops[i].t == DR || ops[i].t == IR) && ops[i].val[j] <= tnode.r) cnt++;
                    }
                    if (!flag) {
                        printf("Cell data in (%d,%d) GONE\n", bak.r, bak.c);
                        break;
                    }
                    if (ops[i].t == DR) tnode.r -= cnt;
                    else if (ops[i].t == DC) tnode.c -= cnt;
                    else if (ops[i].t == IR) tnode.r += cnt;
                    else tnode.c += cnt;
                }
            }
            if (flag) printf("Cell data in (%d,%d) moved to (%d,%d)\n", bak.r, bak.c, tnode.r, tnode.c);
        }
    }
    return 0;
}