E23563: 多项式时间复杂度

http://cs101.openjudge.cn/pctbook/E23563/

解题步骤

分割字符串 按照 '+' 拆分每一项。
解析每一项
- 可能形式：
  - ax^b （如 6n^2）
  - n^b （相当于系数 1）
  - an^b （如 99n^10）
  - 0n^b （等价于 0）
  - 纯常数 5 （等价于 5n^0）
- 提取指数 b，如果该项系数为 0，则忽略。
找最大指数 遍历所有项，记录最大 b。
输出输出 n^最大指数。

cpp

//#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
using namespace std;

int main() {
    string s;
    cin >> s;

    int maxExp = 0;  // 记录最大指数
    stringstream ss(s);
    string term;

    while (getline(ss, term, '+')) {
        int coef = 1;  // 默认系数
        int exp = 0;   // 默认指数

        size_t nPos = term.find('n');
        if (nPos == string::npos) {
            // 没有 n，纯常数项
            coef = stoi(term);
            exp = 0;
        } else {
            // 处理系数
            if (nPos == 0) {
                coef = 1; // "n^b"
            } else {
                coef = stoi(term.substr(0, nPos));
            }

            // 处理指数
            size_t powPos = term.find('^');
            if (powPos == string::npos) {
                exp = 1; // 只有 "n"，即 n^1
            } else {
                exp = stoi(term.substr(powPos + 1));
            }
        }

        if (coef != 0) {
            maxExp = max(maxExp, exp);
        }
    }

    cout << "n^" << maxExp << endl;
    return 0;
}

E23563: 多项式时间复杂度 ​

E23563: 多项式时间复杂度