ABC219F - Cleaning Robot题解

Iceturky · 2024-07-29 21:35:17 · 题解

按照二元组意义下的模等价类分类。

考虑如何定义二元组下的模。考虑到模实际是减去若干次某一个数字，那么二元组下两个元素减去数字的次数也肯定要相同。若二元组是 (x,y) ，模数是 (a,b) ，那么结果可以为 (x\bmod a,y-\lfloor\frac{x}{a}\rfloor b) 。

分完类就一眼了。

实现时需要注意正负号。

无论是 x,y,a,b 都可以为负。

实现的很唐。

code

const int N=2e5+5;

char s[N];

pir p[N];

map<pir,bool>apr;

map<int,set<int> >mp[N<<1];

int k[N];

int c,d;
bool same(pir aa,pir bb){
    return (aa.fi%c+c)%c==(bb.fi%c+c)%c&&aa.se-floor(aa.fi*1.0/c)*d==bb.se-floor(bb.fi*1.0/c)*d;
}
bool cmp(pir aa,pir bb){
    if((aa.fi%c+c)%c==(bb.fi%c+c)%c&&aa.se-floor(aa.fi*1.0/c)*d==bb.se-floor(bb.fi*1.0/c)*d){
        return aa.fi<bb.fi;
    }
    if((aa.fi%c+c)%c==(bb.fi%c+c)%c)
        return aa.se-floor(aa.fi*1.0/c)*d<bb.se-floor(bb.fi*1.0/c)*d;
    return (aa.fi%c+c)%c<(bb.fi%c+c)%c;
}

signed main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    int T=read();
    c=0,d=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='L')
            c--;
        if(s[i]=='R')
            c++;
        if(s[i]=='U')
            d++;
        if(s[i]=='D')
            d--;
    }

    {
        if(c<0){
            for(int i=1;i<=n;i++){
                if(s[i]=='L')
                    s[i]='R';
                else if(s[i]=='R')
                    s[i]='L';
            }
        }
        if(d<0){
            for(int i=1;i<=n;i++){
                if(s[i]=='U')
                    s[i]='D';
                else if(s[i]=='D')
                    s[i]='U';
            }
        }
    }

    c=0,d=0;
    apr[{0,0}]=1;
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(s[i]=='L')
            c--;
        if(s[i]=='R')
            c++;
        if(s[i]=='U')
            d++;
        if(s[i]=='D')
            d--;
        if(apr[{c,d}])
            continue;
        p[++cnt]={c,d};
        apr[{c,d}]=1;
    }
    n=cnt;
    if(c==0){
        for(int i=1;i<=n;i++)swap(p[i].fi,p[i].se);
        swap(c,d);
    }
    if(T==1||(c==0&&d==0)){
        print(n+1),pc('\n');
        return 0;
    }
    p[++n]={0,0};
    sort(p+1,p+1+n,cmp);
    int ans=T;
    for(int i=2;i<=n;i++){
        if(same(p[i-1],p[i]))
            ans+=min(T,(p[i].fi-p[i-1].fi)/c);
        else
            ans+=T;
    }print(ans),pc('\n');
    return 0;
}