PTA-人工智能内部训练赛题解

//万能头
#include <bits/stdc++.h>

using std::string;  //字符串
using std::vector;  //变长数组

//结构体，用于存储系数和次幂，同时承担部分运算
struct node {
    long long a;
    long long e;

    //重载乘法运算
    node operator *(const node& obj) const {
        return {a * obj.a, e + obj.e};
    }

    //重载+=
    node& operator +=(const node& obj) {
        a += obj.a;
        return *this;
    }

    //重载<运算，用于排序操作
    bool operator <(const node& obj) const  {
        return e > obj.e;
    }

};

int main() {
    vector<node> arg[2];    //存储输入的两组数据
    int n, a, e;
    for (int i = 0; i != 2; ++i) {
        scanf("%d", &n);
        while (n--) {
            scanf("%d%d", &a, &e);
            arg[i].push_back({a, e});   //将新输入的数据存储到数组的末尾
        }
    }
    vector<node> c; //存储乘法操作的结果
    //进行乘法操作
    for (const auto &node0 : arg[0]) {
        for (const auto &node1 : arg[1]) {
            node temp = node0 * node1;
            //遍历数组查看是否存在次幂一样的项，如果存在则直接合并同类项
            for (auto &item : c) {
                if (item.e == temp.e) {
                    item += temp;
                    goto hear;  //用goto跳出循环
                }
            }
            c.push_back(temp);  //否则将该项运行结果存储到数组末尾
            hear:;
        }
    }
    vector<int> j;  //存储相加结果
    bool *isAdd = new bool[arg[1].size()];  //存储对应项是否参与相加操作
    //进行加法操作
    for (int i = 0; i != arg[0].size(); ++i) {
        node result = arg[0][i];    //将值从数组中复制出来
        for (int l = 0; l != arg[1].size(); ++l) {
            //如果次幂相等则进行相加，否则跳过
            if (arg[1][l].e == result.e) {
                result += arg[1][l];    //相加
                isAdd[l] = true;    //如果进行了加操作则将对应的标志设置为true
            }
        }
        j.push_back(result);    //将本次结果放置到数组末尾
    }
    //将没有参与加法运算的项直接放置到数组末尾
    for (int i = 0; i != arg[1].size(); ++i) {
        if (!isAdd[i]) j.push_back(arg[1][i]);
    }

    //排序两个数组，使其中元素按照次幂从小到大排列，比较函数是上文中写的<函数
    std::sort(c.begin(), c.end());
    std::sort(j.begin(), j.end());
    bool start = false; //存储是否有打印内容
    for (const auto &item : c) {
        if (item.a == 0) continue;
        if (start) printf(" ");
        printf("%lld %lld", item.a, item.e);
        start = true;
    }
    //如果没有打印内容说明是零多项式
    if (!start) printf("0 0");
    //下面代码同理
    printf("\n");
    start = false;
    for (const auto &item : j) {
        if (item.a == 0) continue;
        if (start) printf(" ");
        printf("%lld %lld", item.a, item.e);
        start = true;
    }
    if (!start) printf("0 0");
    return 0;
}

#include <bits/stdc++.h>

int n;

int costIndex(int index) {
    return index < n ? index : index - n;
}

struct array {
public:
    explicit array(int init) {
        memset(value, init, sizeof(value));
    }
    int& at(int start, int end) {
        return value[costIndex(start)][costIndex(end)];
    }
private:
    int value[300][300] = { };
};

array minResult(0b01111111);
array maxResult(0);
array sum(0);

int stone[300];

int main() {
    int temp;
    scanf("%d", &n);
    for (int i = 0; i != n; ++i) {
        scanf("%d", &stone[i]);
        minResult.at(i, i) = 0;
        sum.at(i, i) = stone[i];
    }

    for (int start = 0; start != n; ++start) {
        for (int len = 1; len != n; ++len) {
            sum.at(start, len + start) =
                sum.at(start, len + start - 1) + stone[costIndex(len + start)];
        }
    }

    for (int len = 1; len != n; ++len) {
        for (int start = 0; start != n; ++start) {
            int end = start + len;
            for (int k = start; k != end; ++k) {
                minResult.at(start, end) = std::min(minResult.at(start, end),
                        minResult.at(start, k) + minResult.at(k + 1, end) + sum.at(start, end));
                maxResult.at(start, end) = std::max(maxResult.at(start, end),
                        maxResult.at(start, k) + maxResult.at(k + 1, end) + sum.at(start, end));
            }
        }
    }

    int min = INT_MAX, max = INT_MIN;
    for (int i = 0; i != n; ++i) {
        int minValue = minResult.at(i, i + n - 1);
        int maxValue = maxResult.at(i, i + n - 1);
        if (min > minValue) min = minValue;
        if (max < maxValue) max = maxValue;
    }

    printf("%d\n%d", min, max);
    return 0;
}