集合(运算符重载)

时间限制: 1 Sec 内存限制: 128 MB

题目描述

集合是由一个或多个确定的元素所构成的整体。集合的运算有并、交、相对补等。
集合A和集合B的交集:由属于A且属于B的相同元素组成的集合。
集合A和集合B的并集:由所有属于集合A或属于集合B的元素所组成的集合。
集合B关于集合A的相对补集,记做A-B:由属于A而不属于B的元素组成的集合。
假设集合A={10,20,30},集合B={1,10,50,8}。则A与B的并是{10,20,30,1,50,8},A与B的交是{10},B关于A的相对补集是{20,30}。
定义整数集合类CSet,属性包括:集合中的元素个数n,整型指针data存储集合中的元素。
方法有:重载输出,按样例格式输出集合中的元素。
重载+运算符,求集合A和集合B的并集,并返回结果集合。
重载-运算符,求集合B关于集合A的相对补集,并返回结果集合。
重载*运算符,求集合A和集合B的交集,并返回结果集合。
主函数输入集合A、B的数据,计算集合的并、交、相对补。
可根据题目,为CSet类添加需要的成员函数。

输入

测试次数
每组测试数据两行,格式如下:
第一行:集合A的元素个数和元素
第二行:集合B的元素个数和元素

输出

每组测试数据输出如下:
第一行:集合A
第二行:集合B
第三行:A和B的并
第四行:A和B的交
第五行:B关于A的相对补集 与 A关于B的相对补集的并,即(A-B)+(B-A)
每组测试数据间以空行分隔。

样例输入

2
3 10 20 30
4 10 1 2 3
5 100 2 3 4 -10
6 -34 12 2 4 90 100

样例输出

A:10 20 30
B:10 1 2 3
A+B:10 20 30 1 2 3
A*B:10
(A-B)+(B-A):20 30 1 2 3

A:100 2 3 4 -10
B:-34 12 2 4 90 100
A+B:100 2 3 4 -10 -34 12 90
A*B:100 2 4
(A-B)+(B-A):3 -10 -34 12 90

提示

解决方案

这个其实没啥好说的…思路清晰就可以了。并集运算可以先生成一个临时数组,加入集合A的元素,然后再加入集合B中不和已加入元素重复的元素。相对补集可以先生成、添加,然后再删除重复的。

主要问题可能在于有同学试图返回一个指向了即将失效的临时变量的指针。

You are returning a temporary object, but because you return it by value, the copy is created. If you return pointer or reference to temporary object, that would be a mistake.
If you change the return type to const char * and return ss.str().c_str() you would return pointer to some buffer of temporary std::string returned by ss.str() and that would be bad.

C++ returning temporary objects confusion – Stack Overflow
#include <iostream>
#include <vector>
#include <algorithm>

class Set {
public:
    explicit Set(std::vector<int> data) : data(std::move(data)) {}

    Set operator+(const Set &rhs) const {
        std::vector<int> tmp;
        tmp.assign(this->data.begin(), this->data.end());
        for (auto i : rhs.data) {
            if (std::find(tmp.begin(), tmp.end(), i) == tmp.end()) {
                tmp.push_back(i);
            }
        }
        return Set(tmp);
    }

    Set operator-(const Set &rhs) const {
        std::vector<int> tmp;
        tmp.assign(this->data.begin(), this->data.end());
        for (auto i : rhs.data) {
            auto it = std::find(tmp.begin(), tmp.end(), i);
            if (it != tmp.end()) {
                tmp.erase(it);
            }
        }
        return Set(tmp);
    }

    Set operator*(const Set &rhs) const {
        std::vector<int> tmp;
        for (auto i1 : this->data) {
            for (auto i2 : rhs.data) {
                if (i1 == i2) {
                    tmp.push_back(i1);
                }
            }
        }
        return Set(tmp);
    }

    friend std::ostream &operator<<(std::ostream &os, const Set &rhs) {
        std::cout << rhs.data.front();
        for (int i = 1; i < rhs.data.size(); ++i) {
            os << ' ' << rhs.data[i];
        }
        return os;
    }

private:
    std::vector<int> data;
};

int main() {
    int T;
    std::cin >> T;

    while (T--) {
        int sizeA, sizeB;
        std::cin >> sizeA;
        std::vector<int> vectorA(sizeA);
        for (auto &i : vectorA) {
            std::cin >> i;
        }
        std::cin >> sizeB;
        std::vector<int> vectorB(sizeB);
        for (auto &i : vectorB) {
            std::cin >> i;
        }
        Set setA(vectorA), setB(vectorB);
        std::cout << "A:" << setA << std::endl
                  << "B:" << setB << std::endl
                  << "A+B:" << setA + setB << std::endl
                  << "A*B:" << setA * setB << std::endl
                  << "(A-B)+(B-A):" << (setA - setB) + (setB - setA) << std::endl;
        std::cout << std::endl;
    }

    return 0;
}

母牛生小牛问题(静态数据成员与静态成员函数)

时间限制: 1 Sec 内存限制: 128 MB

题目描述

假设母牛从出生起第4个年头开始每年可以生一头小母牛,但是第11年后死亡。按此规律,第n年时有多少头母牛?(假设n不大于30)
定义一个母牛类CCow,能够用动态创建和撤消类对象的方式来模拟小母牛的出生和死亡规律。试编写C++程序完成上述计算。

输入

第一行输入测试次数
每次测试输入一行,表示第几年的整数n(<=30)

输出

每次测试输出一行,第n年的母牛总数

样例输入

3
7
30
25

样例输出

6
28364
4530

提示

解决方案

额,写完才看到标题…懒得改了,事实上只要去掉Solver类再稍加改动就可以符合要求。
这里主要思路就是相当于有一个上帝视角:std::vector<Cow *> cows,看着所有的牛。每次循环意味着过去一年,于是让所有牛成长、出生或是死亡。
更新:突然发现还忘记delete,别锤我…
另外每次改动容器时某些情况会让迭代器失效,太久没看《Effective STL》了,有空找来这里补上一点东西。

#include <iostream>
#include <vector>

class CowSolver {
public:
    explicit CowSolver(int limit) : limit(limit) {
        cows.push_back(new Cow());
        for (int i = 1; i < limit; ++i) {
            growUp();
            create();
            kill();
        }
    }

    void println() {
        std::cout << cows.size() << std::endl;
    }

private:
    struct Cow {
        Cow() : age(1) {}

        int age;
    };

    int limit;
    std::vector<Cow *> cows;

    void growUp() {
        for (auto item : cows) {
            item->age += 1;
        }
    }

    void create() {
        for (int i = 0; i < cows.size(); ++i) {
            if (4 <= cows[i]->age && cows[i]->age < 11) {
                cows.push_back(new Cow());
            }
        }
    }

    void kill() {
        for (auto it = cows.begin(); it != cows.end();) {
            if ((*it)->age == 11) {
                it = cows.erase(it);
            } else {
                ++it;
            }
        }
    }
};

int main() {
    int T;
    std::cin >> T;

    while (T--) {
        int year;
        std::cin >> year;

        CowSolver cowSolver(year);
        cowSolver.println();
    }

    return 0;
}

扑克牌排序(结构体)

时间限制: 1 Sec 内存限制: 128 MB

题目描述

自定义结构体表示一张扑克牌,包含类型——黑桃、红桃、梅花、方块、王;大小——2,3,4,5,6,7,8,9,10,J,Q,K,A,小王(用0表示)、大王(用1表示)。输入n,输入n张扑克牌信息,从大到小输出它们的排序结果。
假设扑克牌的排序规则是大王、小王为第一大、第二大,剩余52张扑克牌按照先花色后大小排序。
花色:黑桃>红桃>梅花>方块。
大小: A>K>Q>J>>10>9>…>2。
提示:百度sort函数、strstr函数使用。

输入

测试次数t
每组测试数据两行:
第一行:n,表示输入n张扑克牌
第二行:n张扑克牌信息,格式见样例

输出

对每组测试数据,输出从大到小的排序结果

样例输入

3
5
黑桃4 红桃10 梅花Q 方块K 黑桃A
10
大王 梅花10 红桃K 方块9 黑桃2 梅花A 方块Q 小王 黑桃8 黑桃J
5
红桃K 梅花K 黑桃K 方块K 小王

样例输出

黑桃A 黑桃4 红桃10 梅花Q 方块K
大王 小王 黑桃J 黑桃8 黑桃2 红桃K 梅花A 梅花10 方块Q 方块9
小王 黑桃K 红桃K 梅花K 方块K

提示

解决方案

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <assert.h>

class Poker {
public:
    friend std::istream &operator>>(std::istream &in, Poker &poker) {
        in >> poker.info;
        return in;
    }

    friend std::ostream &operator<<(std::ostream &out, const Poker &poker) {
        out << poker.info;
        return out;
    }

    bool operator<(const Poker &rhs) const {
        if (this->typeValue() != rhs.typeValue()) {
            return this->typeValue() < rhs.typeValue();
        } else {
            return this->sizeValue() < rhs.sizeValue();
        }
    }

private:
    std::string info;

    int typeValue() const {
        std::string type;
        if (info.find("大王") != std::string::npos) {
            return 6;
        } else if (info.find("小王") != std::string::npos) {
            return 5;
        } else if (info.find("黑桃") != std::string::npos) {
            return 4;
        } else if (info.find("红桃") != std::string::npos) {
            return 3;
        } else if (info.find("梅花") != std::string::npos) {
            return 2;
        } else if (info.find("方块") != std::string::npos) {
            return 1;
        }
        assert(0);
    }

    int sizeValue() const {
        char back = info[info.length() - 1];
        switch (back) {
            default:
                return back - '0';
            case '0':
                return 10;
            case 'J':
                return 11;
            case 'Q':
                return 12;
            case 'K':
                return 13;
            case 'A':
                return 14;
        }
    }
};

int main() {
    size_t T;
    std::cin >> T;

    while (T--) {
        size_t size;
        std::cin >> size;
        std::vector<Poker> vector(size);
        for (size_t i = 0; i < vector.size(); ++i) {
            std::cin >> vector[i];
        }

        std::sort(vector.rbegin(), vector.rend());

        std::cout << vector.front();
        for (size_t i = 1; i < vector.size(); ++i) {
            std::cout << ' ' << vector[i];
        }
        std::cout << std::endl;
    }

    return 0;
}

引用:
Check if a string contains a string in C++ – Stack Overflow
c++ – Does Overloading Operator<< works inside the class? – Stack Overflow
sort – C++ Reference

矩阵类模板(类模板)

时间限制: 1 Sec 内存限制: 128 MB

题目描述

设计一个矩阵类模板Matrix,支持任意数据类型的数据。
要求至少包含2个成员函数:矩阵转置函数transport、以及打印输出函数print
编写main函数进行测试,调用类的成员函数完成转置和输出。

输入

第一行先输入t,表示有t个测试用例
从第二行开始输入每个测试用例的数据。
首先输入数据类型,I表示int,D表示double,C表示char,接着输入两个参数m和n,分别表示矩阵的行和列
接下来输入矩阵的元素,一共m行,每行n个数据

输出

输出转置后的矩阵

样例输入

2
I 2 3
1 2 3
4 5 6
C 3 3
a b c
d e f
g h i

样例输出

1 4
2 5
3 6
a d g
b e h
c f i

提示

解决方案

冷静思考就能解决。

看到有同学重载[]运算符时返回了一个指向了T的指针(即T *)。这样的话,访问元素时,第二个[]就是在索引数组了。虽然可以做到是对的,但是我总觉得很别扭,大概是我觉得不应该直接去操作class中private的成员吧…个人觉得还好的方案就是下面这种返回结构体的,或是封装一下std::vector<std::vector<T> >也都还好。

#include <iostream>

template<typename T>
class Matrix {
public:
    Matrix(size_t row, size_t col) : row(row), col(col) {
        data = new T *[row];
        for (size_t i = 0; i < row; ++i) {
            data[i] = new T[col];
        }
    }

    void setFromCin() {
        for (size_t ir = 0; ir < row; ++ir) {
            for (size_t ic = 0; ic < col; ++ic) {
                std::cin >> data[ir][ic];
            }
        }
    }

    void transport() {
        T **tmp = new T *[col];
        for (size_t ir = 0; ir < col; ++ir) {
            tmp[ir] = new T[row];
        }
        for (size_t ir = 0; ir < col; ++ir) {
            for (size_t ic = 0; ic < row; ++ic) {
                tmp[ir][ic] = data[ic][ir];
            }
        }

        for (size_t ir = 0; ir < row; ++ir) {
            delete[](data[ir]);
        }
        delete[](data);
        std::swap(row, col);
        data = tmp;
    }

    void println() {
        for (size_t ir = 0; ir < row; ++ir) {
            std::cout << data[ir][0];
            for (size_t ic = 1; ic < col; ++ic) {
                std::cout << ' ' << data[ir][ic];
            }
            std::cout << std::endl;
        }
    }

    struct Row &operator[](int index) {
        return Row(data[index]);
    }

    ~Matrix() {
        for (size_t ir = 0; ir < row; ++ir) {
            delete[](data[ir]);
        }
        delete[](data);
    }

private:
    int row, col;
    T **data;

    struct Row {
        explicit Row(T *row) : data(row) {}

        T operator[](int index) {
            return data[index];
        }

        T *data;
    };
};

int main() {
    int T;
    std::cin >> T;

    while (T--) {
        char type;
        std::cin >> type;
        int row, col;
        std::cin >> row >> col;
        switch (type) {
            case 'I': {
                Matrix<int> matrix(row, col);
                matrix.setFromCin();
                matrix.transport();
                matrix.println();
                break;
            }
            case 'D': {
                Matrix<double> matrix(row, col);
                matrix.setFromCin();
                matrix.transport();
                matrix.println();
                break;
            }
            case 'C': {
                Matrix<char> matrix(row, col);
                matrix.setFromCin();
                matrix.transport();
                matrix.println();
                break;
            }
            default: ;
        }
    }

    return 0;
}

动态矩阵(指针与堆内存分配)

时间限制: 1 Sec 内存限制: 128 MB

题目描述

未知一个整数矩阵的大小,在程序运行时才会输入矩阵的行数m和列数n
要求使用指针,结合new方法,动态创建一个二维数组,并求出该矩阵的最小值和最大值,可以使用数组下标法。
不能先创建一个超大矩阵,然后只使用矩阵的一部分空间来进行数据访问、
创建的矩阵大小必须和输入的行数m和列数n一样

输入

第一行输入t表示t个测试实例
第二行输入两个数字m和n,表示第一个矩阵的行数和列数
第三行起,连续输入m行,每行n个数字,表示输入第一个矩阵的数值
依次输入t个实例

输出

每行输出一个实例的最小值和最大值

样例输入

2
2 3
33 22 11
66 88 55
3 4
19 38 45 14
22 65 87 31
91 35 52 74

样例输出

11 88
14 91

提示

解决方案

#include <iostream>

int main() {
    size_t T;
    std::cin >> T;

    while (T--) {
        size_t row, col;
        std::cin >> row >> col;
        int **matrix = new int *[row];
        for (size_t ir = 0; ir < row; ++ir) {
            matrix[ir] = new int[col];
            for (size_t ic = 0; ic < col; ++ic) {
                std::cin >> matrix[ir][ic];
            }
        }
        int min = matrix[0][0], max = matrix[0][0];
        for (size_t ir = 0; ir < row; ++ir) {
            for (size_t ic = 0; ic < col; ++ic) {
                if (min > matrix[ir][ic]) {
                    min = matrix[ir][ic];
                }
                if (max < matrix[ir][ic]) {
                    max = matrix[ir][ic];
                }
            }
        }
        std::cout << min << ' ' << max << std::endl;
    }

    return 0;
}

三串合一(指针与字符数组)

时间限制: 1 Sec 内存限制: 128 MB

题目描述

输入三个字符串,通过指针读取各个字符串的子串(子串是指字符串中连续的一小部分),把它们合并成一个新字符串

要求:

  1. 三个字符串的创建和输入可以使用数组,也可以不用
  2. 输入后,根据三个字符串的子串的长度,计算出新字符串的长度
  3. 使用动态数组的方法创建新的字符串,并且使用指针读取三个字符串的不同部分,并且复制到新字符串中,要求整个过程都不能使用数组下标
  4. 使用指针输出新的字符串

输入

第一行输入t表示有t个测试实例
连续三行输入三个字符串,每个字符串都包含10个字符
连续三行,每行输入数字a和b,表示每个子串的开始和结束位置。注意字符串的位置是按照一般意义从1开始计算,和编程中的数组位置不同。例如字符串abcdefg,开始位置是3,结束位置是5,那么子串就是cde
依次输入t个实例

输出

每行输出合并后的新字符串

样例输入

2
abcdefghij
ABCDEFGHIJ
aabbccddee
3 5
2 6
8 10
AABBCCDDEE
ffgghhiijj
FFGGHHIIJJ
1 4
5 8
2 7

样例输出

cdeBCDEFdee
AABBhhiiFGGHHI

提示

解决方案

我也不知道我到底要说多少遍,各位大佬才会记得C风格字符串后面还有个’\0’要占空间的…

#include <iostream>

int main() {
    size_t T;
    std::cin >> T;

    while (T--) {
        char strings[3][16];
        std::cin >> strings[0] >> strings[1] >> strings[2];
        size_t bound[3][2] = {}, size = 0;
        for (size_t ir = 0; ir < 3; ++ir) {
            for (size_t ic = 0; ic < 2; ++ic) {
                std::cin >> bound[ir][ic];
                bound[ir][ic] -= 1;
            }
            size += (bound[ir][1] - bound[ir][0]);
        }
        char *string = new char[size + 1];
        char *dst = string;
        for (size_t i = 0; i < 3; ++i) {
            char *src = strings[i] + bound[i][0];
            while (src <= strings[i] + bound[i][1]) {
                *dst++ = *src++;
            }
        }
        *dst = '\0';
        std::cout << string << std::endl;
    }

    return 0;
}