【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-10087】The Tajmahal of ++Y2k【幻方构造】

【UVA-10087】The Tajmahal of ++Y2k【幻方构造】

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

Solution:

关于幻方构造,阅读:幻方的构造方法

除了二阶幻方不存在外,这道题只要在判断要求的一个方向上所有数的和减去标准幻方一个方向上所有数的和【标准幻方求和公式,对于n阶幻方,\(Sum = \frac{n * (n^2 + 1)}{2}】后是否是[latex]n^2\)的倍数就好,如果是,则可以通过给每个方格加上相同的一定数,获得要求的方阵。

#include <iostream>

using namespace std;

typedef long long LL;
const int LIM = 101;
struct Matrix {
    int v[LIM][LIM];
    int size;
};

inline LL getSum(LL n) {
    return n * (n * n + 1) / 2;
}

Matrix odd_msquare(int n) {
    Matrix ret = {{0}, n};
    int lim = n * n;
    int r = 0, c = n / 2;
    for (int i = 1; i <= lim; i++) {
        ret.v[r][c] = i;
        int nr = (r - 1 + n) % n;
        int nc = (c + 1 + n) % n;
        if (ret.v[nr][nc]) r++;
        else r = nr, c = nc;
    }
    return ret;
}

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

Matrix m4_msquare(int n) {
    Matrix ret = {{0}, n};
    int crt = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ret.v[i][j] = crt;
            crt++;
        }
    }
    int lim = n / 2;
    for (int i = 0; i < lim; i += 4) {
        for (int j = 0; j < n; j += 4) {
            if (i + 2 == lim && j > lim) break;
            if (j + 2 == lim && i + 2 == lim) {
                for (int k = 0; k < 2; k++) {
                    for (int m = 0; m < 4; m++) {
                        if (k == m || k == 4 - m - 1)
                            swap(ret.v[i + k][j + m], ret.v[n - 1 - (i + k)][n - 1 - (j + m)]);
                    }
                }
            } else {
                for (int k = 0; k < 4; k++) {
                    for (int m = 0; m < 4; m++) {
                        if (k == m || k == 4 - m - 1)
                            swap(ret.v[i + k][j + m], ret.v[n - 1 - (i + k)][n - 1 - (j + m)]);
                    }
                }
            }
        }
    }
    return ret;
}

Matrix m4p2_msquare(int n) {
    int m = (n - 2) / 4;
    Matrix tmp = odd_msquare(n / 2), ret = {{0}, n};
    for (int i = 0; i < tmp.size; i++)
        for (int j = 0; j < tmp.size; j++)
            tmp.v[i][j] = tmp.v[i][j] * 4 - 4;
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j < tmp.size; j++) {
            ret.v[i << 1][j << 1] = 4 + tmp.v[i][j];
            ret.v[i << 1][(j << 1) + 1] = 1 + tmp.v[i][j];
            ret.v[(i << 1) + 1][j << 1] = 2 + tmp.v[i][j];
            ret.v[(i << 1) + 1][(j << 1) + 1] = 3 + tmp.v[i][j];
        }
    }
    ret.v[m << 1][tmp.size - 1] = 1 + tmp.v[m][tmp.size >> 1];
    ret.v[m << 1][tmp.size] = 4 + tmp.v[m][tmp.size >> 1];
    ret.v[(m << 1) + 1][tmp.size - 1] = 2 + tmp.v[m][tmp.size >> 1];
    ret.v[(m << 1) + 1][tmp.size] = 3 + tmp.v[m][tmp.size >> 1];
    for (int j = 0; j < tmp.size; j++) {
        ret.v[(m + 1) << 1][j << 1] = 1 + tmp.v[m + 1][j];
        ret.v[(m + 1) << 1][(j << 1) + 1] = 4 + tmp.v[m + 1][j];
        ret.v[((m + 1) << 1) + 1][j << 1] = 2 + tmp.v[m + 1][j];
        ret.v[((m + 1) << 1) + 1][(j << 1) + 1] = 3 + tmp.v[m + 1][j];
    }
    ret.v[(m + 1) << 1][tmp.size - 1] = 4 + tmp.v[m + 1][tmp.size >> 1];
    ret.v[(m + 1) << 1][tmp.size] = 1 + tmp.v[m + 1][tmp.size >> 1];
    ret.v[((m + 1) << 1) + 1][tmp.size - 1] = 2 + tmp.v[m + 1][tmp.size >> 1];
    ret.v[((m + 1) << 1) + 1][tmp.size] = 3 + tmp.v[m + 1][tmp.size >> 1];
    for (int i = m + 2; i < tmp.size; i++) {
        for (int j = 0; j < tmp.size; j++) {
            ret.v[i << 1][j << 1] = 1 + tmp.v[i][j];
            ret.v[i << 1][(j << 1) + 1] = 4 + tmp.v[i][j];
            ret.v[(i << 1) + 1][j << 1] = 3 + tmp.v[i][j];
            ret.v[(i << 1) + 1][(j << 1) + 1] = 2 + tmp.v[i][j];
        }
    }
    return ret;
}

int main(void) {
    LL s;
    int n;
    Matrix ans;
    while (~scanf("%d%lld", &n, &s)) {
        if (n == 1) printf("%10lld\n", s);
        else if (n == 2) printf("You can't be like Shahjahan!\n");
        else {
            LL diff = s - getSum(n);
            if (diff % n) printf("You can't be like Shahjahan!\n");
            else {
                LL add = diff / n;
                if (n % 2) {
                    ans = odd_msquare(n);
                } else {
                    if (n % 4) ans = m4p2_msquare(n);
                    else ans = m4_msquare(n);
                }
                for (int i = 0; i < ans.size; i++) {
                    for (int j = 0; j < ans.size; j++) {
                        if (j) putchar(' ');
                        printf("%10lld", ans.v[i][j] + add);
                    }
                    putchar('\n');
                }
            }
        }
        putchar('\n');
    }
    return 0;
}