题解：P12723 [KOI 2021 Round 2] 括号值比较

· · 题解

解题思路

我们将每个括号设为一层，括号外面的括号比括号里面的括号低一层（碰到左括号时层数加一，碰到右括号时层数减一），用一个数组来计算括号的每一层。最里面的括号设为 1，并列的括号数字相加，每降一层将括号内的数字乘 2。

部分正确代码。

#include<bits/stdc++.h>
using namespace std;
stack<char>s;
char c[10000001];
int cnt[10000001];//定义括号层
int ans[10];
int main()
{
    int t;
    cin>>t;
    string c;
    while(t--){
        for(int k=1;k<=2;k++){
            cnt[1]=0;
            cin>>c;
            int len=c.length();
            for(int i=0,j=1;i<len;i++){
                if(c[i]=='('){
                    s.push(c[i]);
                    j++;
                    cnt[j]=0;
                }
                else if(c[i]==')'){
                    if(!s.empty())
                        s.pop();
                    if(c[i-1]=='(')
                        cnt[j-1]++;
                    else
                        cnt[j-1]+=cnt[j]*2;
                    j--;
                }
            }
            ans[k]=cnt[1];
        }
        if(ans[1]>ans[2])
            printf(">\n");
        else if(ans[1]<ans[2])
            printf("<\n");
        else if(ans[1]==ans[2])
            printf("=\n");
    }
    return 0;
}

我们会发现，如果所有的括号扩在一起的话，计算出的数字会达到 2^{1.5 \times 10^6} 所以代码因用高精度计算。

高精代码（空间复杂度高）。

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;

struct BigInt {
    int d[1001];
    int len;

    BigInt() : len(0) {
        memset(d, 0, sizeof(d));
    }

    explicit BigInt(const string& s) : len(s.length()) {
        memset(d, 0, sizeof(d));
        for(int i = 0; i < len; i++) {
            d[i] = s[len - i - 1] - '0';
        }
    }

    void add(const BigInt& other) {
        int carry = 0;
        int max_len = max(len, other.len);
        for(int i = 0; i < max_len; i++) {
            int temp = d[i] + other.d[i] + carry;
            d[i] = temp % 10;
            carry = temp / 10;
        }
        if(carry) d[max_len] = carry;
        len = carry ? max_len + 1 : max_len;
    }

    void multiplyByTwo() {
        int carry = 0;
        for(int i = 0; i < len; i++) {
            int temp = d[i] * 2 + carry;
            d[i] = temp % 10;
            carry = temp / 10;
        }
        if(carry) d[len++] = carry;
    }

    int compare(const BigInt& other) const {
        if(len != other.len) return len > other.len ? 1 : -1;
        for(int i = len-1; i >= 0; i--) {
            if(d[i] != other.d[i]) return d[i] > other.d[i] ? 1 : -1;
        }
        return 0;
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    short t;
    cin >> t;
    string c;
    const BigInt one("1");

    while(t--) {
        BigInt ans[2];
        for(int k = 0; k < 2; k++) {
            cin >> c;
            stack<BigInt> st;
            st.push(BigInt());

            for(int i = 0; i < c.length(); i++) {
                if(c[i] == '(') {
                    st.push(BigInt());
                }
                else if(c[i] == ')') {
                    BigInt top = st.top();
                    st.pop();
                    if(c[i-1] == '(') {
                        st.top().add(one);
                    } else {
                        top.multiplyByTwo();
                        st.top().add(top);
                    }
                }
            }
            ans[k] = st.top();
        }

        int cmp = ans[0].compare(ans[1]);
        if(cmp > 0) cout << ">\n";
        else if(cmp < 0) cout << "<\n";
        else cout << "=\n";
    }

    return 0;
}

这种暴力的高精度算法空间复杂度较高，所以我们可以对整体进行优化，但还是一层一层的来计算。

最终代码（全对）。

#include <bits/stdc++.h>
using namespace std;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--){
        string A,B;
        cin>>A>>B;
        vector<int>cntA(1500001,0);
        vector<int>cntB(1500001,0);
        int max_dA=0,max_dB=0;
        int d=0;//定义层
        for(int i=0;i<A.size();i++){
            if(A[i]=='('){
                d++;//层上升
                if (d>max_dA)
                  max_dA=d;
            }
            else{
                if(i>0&&A[i-1]=='(')
                    if(d>=1&&d<=1500000)
                        cntA[d]++;//为最里面的括号，将本层的值加一（或设为一）
                d--;//层下降
            }
        }
        d=0;
        for(int i=0;i<B.size();i++){
            if(B[i]=='('){
                d++;
                if(d>max_dB)
                  max_dB = d;
            }
            else{
                if(i>0&&B[i-1]=='(')
                    if(d>=1&&d<=1500000)
                        cntB[d]++;
                d--;
            }
        }//重复处理字符串B
        int lenA=max_dA+23;
        int lenB=max_dB+23;
        vector<int>bitsA(lenA,0);
        vector<int>bitsB(lenB,0);
        for (int d_val=1;d_val<=1500000;d_val++){
            if(cntA[d_val]>0)
                if(d_val-1<lenA)
                    bitsA[d_val-1]+=cntA[d_val];//计算二进制表示
            if (cntB[d_val]>0)
                if (d_val-1<lenB)
                    bitsB[d_val-1]+=cntB[d_val];//重复处理字符串B
        }
        for(int i=0;i<lenA-1;i++){
            if(bitsA[i]>=2){
                bitsA[i+1]+=bitsA[i]>>1;
                bitsA[i]=bitsA[i]&1;//计算二进制表示
            }
        }
        for(int i=0;i<lenB-1;i++){
            if(bitsB[i]>=2){
                bitsB[i+1]+=bitsB[i]>>1;
                bitsB[i]=bitsB[i]&1;
            }
        }//重复处理字符串B
        char result='=';
        for (int i=max(lenA,lenB)-1;i>=0;i--) {
            int a_bit=(i<lenA)?bitsA[i]:0;
            int b_bit=(i<lenB)?bitsB[i]:0;
            if(a_bit!=b_bit){
                result=(a_bit>b_bit)?'>':'<';
                break;
            }
        }
        cout<<result;
        printf("\n");
    }
    return 0;
}