为啥会WA?
查看原帖
为啥会WA?
1074084
asd890123楼主2024/10/18 22:18

TLE我理解,也不需要通过TLE的点,但是谁能告诉我为啥WA,如何把WA的点AC,最好能有hack(最好短一点),现在是20pts,代码如下:

#include <iostream>
#include <queue>

const int N = 5e5 + 5;

std::string s;
int n,ans = 0,f[N];
struct TreeNode{
    char c;
    int father,l,r;
    TreeNode():father(0),l(0),r(0),c('&'){}
}tree[N];
struct BfsNode{
    int x;
    std::string ans;
};

bool isValid(std::string s){

    int cntL = 0,cntR = 0;

    for (char c : s){

        if (c == '(') cntL++;
        else if (c == ')') cntR++;
        if (cntR > cntL) return false;

    }

    return cntL && cntR && cntL == cntR;
}
std::string S(int i){

    std::queue<BfsNode> Q;

    Q.push({1,(std::string)"" + tree[1].c});
    while (!Q.empty()){

        BfsNode Front = Q.front();

        Q.pop();
        if (tree[Front.x].l != 0) Q.push({tree[Front.x].l,Front.ans + tree[tree[Front.x].l].c});
        if (Q.front().x == i) return Q.front().ans;
        if (tree[Front.x].r != 0) Q.push({tree[Front.x].r,Front.ans + tree[tree[Front.x].r].c});
        if (Q.front().x == i) return Q.front().ans;

    }

    return "I get NOI Au.";
}

int main(){

    std::cin.tie(0)->sync_with_stdio(0);

    std::cin >> n >> s;
    for (int i = 0;i < s.length();i++) tree[i + 1].c = s[i];
    for (int i = 1;i < n;i++){

        std::cin >> f[i];
        tree[i + 1].father = f[i];
        if (tree[f[i]].l == 0) tree[f[i]].l = i + 1;
        else tree[f[i]].r = i + 1;

    }
    for (int i = 1;i <= n;i++){

        int cnt = 0;
        std::string str = S(i);

        for (int j = 0;j < str.length();j++){

            std::string sub = "";

            for (int k = j;k < str.length();k++){
                
                sub += str[k];
                if (isValid(sub)) cnt++;

            }

        }
        ans ^= i * cnt;

    }
    std::cout << ans << '\n';

    return 0;
}
2024/10/18 22:18
加载中...