NWERC 2018 E. Equality Control

题面

E. Equality Control

题意

判断两段 "程序" 是否等价. 细节参见题面(懒得翻译)

暴力模拟写法

很简单, 递归模拟即可. 你问结果? 当然是喜闻乐见的TLE了.

投机取巧

我们可以发现如下性质: + shuffle中如果是一个常数列, 那么这个shuffle只有唯一确定的排列, 也就是说这个shuffle没有意义 + 遇到contract直接读过去就行, 它也是没有意义的 + sorted和shuffle是相互覆盖的关系, 也就是说, 如果它们相互嵌套, 只要读最外面的就可以了 + 等价的条件是: 两段 "程序" 中所有有意义的shuffle区间相等(不管是位置还是其中的数列)

踩的坑

首先是被string坑了, 在某个测试点出现了MLE, 换成char[]就将错误变成了TLE. TLE很显然是单纯暴力递归导致的, 于是开始研究如何优化. 没考虑第一条性质, WA. 理解错题意, 傻乎乎的认为不是整段 "程序" 最外层的shuffle都是没有意义的, WA. 上面这个解决了自然就能想到第四条性质, 遂AC.

完整AC代码

点我查看完整代码

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<map> 
#include<string>
#include<vector>
using namespace std;
typedef pair<int, int> pii;
struct node{
    //int zt;//zhuang tai, 1~s, 0~not s
    vector<int> sz; 
    vector<pii> qj;
    bool operator == (const node &a){
        if (sz != a.sz || qj != a.qj){
            return false;
        }
        else{
            return true;
        }
    }
    node operator += (const node &a){
        sz.insert(sz.end(), a.sz.begin(), a.sz.end());
        return *this;
    }
    bool judge(){
        vector<int> s = sz;
        sort(s.begin(), s.end());
        return unique(s.begin(), s.end()) - s.begin() == 1;
    }
    void sort_node(){
        sort(sz.begin(), sz.end());
    }
    void print(){
        printf("__________________________\n");
        //printf("%d\n", zt);
        for (auto i:sz){
            printf("%d ", i);
        }
        printf("\n_________________________\n");
    }
};
inline int find_r (char *s, const int &l, const int &len){
    int lcnt = 0, rcnt = 0;
    for (int i = l; i < len; i++){
        if (s[i] == '('){
            lcnt++;
        }
        else if (s[i] == ')'){
            rcnt++;
            if (lcnt == rcnt){
                return i;
            }
        }
    }
}
inline node get (char *s, const int &l, const int &r, const int &len){
    node ans;
    int x = 0, flag = 0;
    for (int i = l; i < r; i++){
        if (s[i] == '['){
            flag = 1;
        }
        else if (s[i] >= '0' && s[i] <= '9'){
            x = 10 * x + (s[i] ^ 48);
        }
        else if (flag){
            if (s[i] == ']'){
                flag = 0;
            }
            ans.sz.push_back(x);
            x = 0;
        }
    }
    return ans;
}
inline node deal(char* s, int &pos, const int &len){
    node ans;
    int x = 0, flag = 0;
    for (int i = 0; i < len; i++){
        if (s[i] == 's' && s[i + 1] == 'o'){
            i += 6;
            int r = find_r(s, i, len);
            node temp = get(s, i, r, len);
            temp.sort_node();
            ans += temp;
            i = r;
        }
        else if (s[i] == 's' && s[i + 1] == 'h'){
            i += 7;
            int r = find_r(s, i, len);
            node temp = get(s, i, r, len);
            temp.sort_node();
            if (!temp.judge()){
                ans.qj.push_back(make_pair(ans.sz.size(), ans.sz.size() + temp.sz.size()));
            }
            ans += temp;
            i = r;
        }
        if (s[i] == '['){
            flag = 1;
        }
        else if (s[i] >= '0' && s[i] <= '9'){
            x = 10 * x + (s[i] ^ 48);
        }
        else if (flag){
            if (s[i] == ']'){
                flag = 0;
            }
            ans.sz.push_back(x);
            x = 0;
        }
    }
    return ans;
}
char s1[1000009], s2[1000009];
int main(){
    //freopen("E.in", "r", stdin);
    //string s1, s2;
    scanf("%s", s1);
    scanf("%s", s2);
    int pos = 0, len1 = strlen(s1), len2 = strlen(s2);
    node a = deal(s1, pos, len1);
    pos = 0;
    node b = deal(s2, pos, len2);
    //a.print();
    //b.print();
    if (a == b){
        printf("equal");
    }
    else{
        printf("not equal");
    }
    return 0;
}