[ICPC 2018 Nanjing Onsite E]Eva and Euro coins

Link

Solution

核心思想就是将连续的k1和连续的k0消掉。。消到最后是否相同。。
训练的时候PY想法是对的,但没想好怎么写,于是我写的十分野蛮,不出意料地TLE了。。。

Code

const int XN=1e6+11;

int n,k;
std::string Do(std::string s) {
    if(k==1)
        return "";
    else {
        static std::pair<char,int> stack[XN];
        int top=0;
        stack[++top]={s[0],1};
        for(int i=1;i<n;++i)
            if(stack[top].first==s[i]) {
                if(++stack[top].second==k)
                    top--;
            } else
                stack[++top]={s[i],1};
        s="";
        for(int i=1;i<=top;++i)
            while(stack[i].second--)
                s+=stack[i].first;
        return s;
    }
}

int main() {
    //freopen("input","r",stdin);
    std::string s,t;
    std::cin>>n>>k>>s>>t;
    std::cout<<(Do(s)==Do(t)?"Yes":"No")<<'\n';
    return 0;
}

大力代码

const int XN=1e6+11;

int n,k;

void Move(std::list<int> &a) {
    while(*a.begin()>k)
        *a.begin()-=k;  
    auto pred=a.begin(),it=pred;
    ++it;
    for(;it!=a.end();pred=it,++it)
        while(*it-*pred>k)
            *it-=k;
}

bool Flip(std::list<int> &a) {
    if(a.empty())
        return 0;
    int len=1;
    auto pred=a.rbegin(),it=pred;
    ++it;
    bool tak=0;
    std::vector<int> del;
    for(;it!=a.rend();pred=it,++it)
        if(*pred-*it==1) {
            if(++len==k) {
                auto x=it;
                for(int t=k;t--;) {
                    del.push_back(*x--);
                }
                std::reverse(&del.back()-k+1,&del.back()+1);
            }
        } else
            len=1;
    std::reverse(del.begin(),del.end());
    if(del.size()==0)
        return 0;
    int i=0;
    for(auto it=a.begin();it!=a.end();)
        if(*it==del[i]) {
            ++i;
            a.erase(it++);
        } else
            ++it;
    return 1;
}

std::list<int> Do(char *a) {
    std::list<int> id;
    for(int i=1;i<=n;++i)
        if(a[i]=='1')
            id.push_back(i);
    if(id.size()) {
        do {
            Move(id);
        } while(Flip(id));
    }
    return id;
}

int main() {
    //freopen("input","r",stdin);
    static char s[XN],t[XN];
    std::cin>>n>>k;
    std::cin>>(s+1)>>(t+1);
    if(k==1)
        std::cout<<"Yes"<<'\n';
    else {
        auto s1=Do(s),t1=Do(t);
        bool tak=s1==t1;//s1.size()==t1.size();
        std::cout<<(tak?"Yes":"No")<<'\n';
    }   
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注