暴搜版求调
查看原帖
暴搜版求调
234992
SkyWave楼主2022/10/29 19:59
//
//  main.cpp
//  P8815 [CSP-J2022] 逻辑表达式(暂无数据)
//
//  Created by SkyWave Sun on 2022/10/29.
//

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define N (int)1e6 + 1
char str[N];
int sum1;
int sum2;
int dfs(int l,int r) {
    int x = 0,orpos = 0, andpos = 0;
    for (int i = l; i<=r; ++i) {
        if (str[i] == '(') {
            ++x;
        }else {
            if (str[i] == ')') {
                --x;
            }else {
                if (!x) {
                    if (str[i] == '|') {
                        orpos = i;
                    }else {
                        if (str[i] == '&') {
                            andpos = i;
                        }
                    }
                }
            }
        }
    }
    if (orpos) {
        if (str[orpos] == '|') {
            int tmp1 = dfs(l, orpos - 1);
            if (tmp1 == 1) {
                ++sum1;
                return 1;
            }else {
                int tmp2 = dfs(orpos + 1, r);
                return tmp1 | tmp2;
            }
        }
    }
    if (andpos) {
        if (str[andpos] == '&') {
            int tmp1 = dfs(l, andpos - 1);
            if (tmp1 == 0) {
                ++sum2;
                return 0;
            }else {
                int tmp2 = dfs(andpos + 1, r);
                return tmp1 & tmp2;
            }
        }
    }
    if (str[l] == '(' && str[r] == ')') {
        return dfs(l + 1, r - 1);
    }else {
        return str[l] - '0';
    }
}
int main(int argc, const char * argv[]) {
    scanf("%s",str + 1);
    size_t len = strlen(str + 1);
    printf("%d\n%d %d\n",dfs(1, len), sum2, sum1);
    return 0;
}

2022/10/29 19:59
加载中...