题解：AT_abc219_f [ABC219F] Cleaning Robot

· · 题解

模拟赛考了这题，场上因为细节写挂，差点通过这题，特此记录。

首先，观察一下最终走过的点的坐标形式都是什么。

令前 n-1 次移动到达的点的位置集合（包括一开始的 (0,0)）为 S，第 n 次移动后的点的位置为 (dx,dy)。

那么，对于所有 Kn 次移动中到达过的点 (x,y)，必然满足以下两种情况至少一个：

换个理解方式，就是对于任意 (x,y) \in S,0 \le k \lt K，(x+k\cdot dx,y + k \cdot dy) 必然存在于最终经过的路径里，对于任意 k \le K，(k\cdot dx,k \cdot dy) 也必然存在于最终经过的路径里。

首先，由于我不喜欢比较重要的地方出现负数，所以，如果 dx,dy 某一个小于 0，那么就将整个的对应的横向或纵向翻转（比如说，U 换成 D，L 换成 R）。

答案一定不会改变，因为是对称的，然后，就能保证 dx,dy \ge 0。

然后，考虑按照顺序遍历 S 中的每个元素，依次考虑遍历到的新元素，事实上对答案新增了多少个位置的贡献。

此时，就需要分析怎么计算当前的元素产生的位置里面，有哪些是和之前遍历过的元素产生的位置重复了。

回想一下判定条件。

假设当前扫描到了 S 中的元素 (x_1,y_1)，然后需要知道其与 S 中另一个元素 (x_2,y_2) 有哪些位置重合。

综上，定义一个 S 中的元素 (x,y) 的类别属性为 (x \cdot d_y - y \cdot d_x,x \bmod {d_x},y \bmod {d_y})，只有两个 S 中的元素的类别属性相同，它们才可能产生相同的位置。

考虑开一个 map，存储每一种类别属性的所有元素。

回到原来问题，此时可以发现，和 (x_1,y_1) 处于同一种类别属性的元素中，有价值的仅包括 x 方向，y 方向上分别最接近的两个元素（总共 4 个元素）。

当前元素产生的新位置的形式为 (x_1 + k\cdot dx,y_1 + k\cdot dy)，而原本情况下 0 \le k \lt K + [(x_1,y_1)=(0,0)]。

这些邻居元素，实际的影响就是使得一段前缀或者后缀的 k 不合法，分类讨论一下就可以了。

map 里面开两个 set，分奇偶分别存储所有的位置就可以了。

对于 (0,0) 这个特殊的点，它有一个 k 可以等于 K 的特权，为了简单处理这种情况，可以额外建立一个节点 (dx,dy)。 

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
void ioopti(){
    ios::sync_with_stdio(0);
    cin.tie(0);
}
#define int ll
#define pii pll
#define vi vector<ll>
const int maxn=2e5+5;
int n;
char s[maxn];
ll k;
struct REM{
    ll mx=-2e18,my=-2e18,cha=-2e18;
    void init(){
        mx=-2e18,my=-2e18,cha=-2e18;
    }
    bool operator<(const REM& b)const{
        if(mx!=b.mx)return mx<b.mx;
        if(my!=b.my)return my<b.my;
        return cha<b.cha;
    }
};
map<REM,set<int> > oklistx,oklisty;
vector<pii> rem;
ll dx,dy;
void solve(int id_of_test){
    scanf("%s",s+1);
    n=strlen(s+1);
    read(k);
    {
        pii cur=mkpr(0,0);
        FOR(i,1,n){
            rem.eb(cur);
         //   printf("%d %d\n",cur.fi,cur.se);
            if(s[i]=='L')cur.fi--;
            if(s[i]=='R')cur.fi++;
            if(s[i]=='U')cur.se++;
            if(s[i]=='D')cur.se--;
        }
        dx=cur.fi,dy=cur.se;
    }
    {
        if(dx<0){
            FOR(i,1,n){
                if(s[i]=='L')s[i]='R';
                else if(s[i]=='R')s[i]='L';
            }
        }
        if(dy<0){
            FOR(i,1,n){
                if(s[i]=='U')s[i]='D';
                else if(s[i]=='D')s[i]='U';
            }
        }
        rem.clear();
        pii cur=mkpr(0,0);
        FOR(i,1,n){
            rem.eb(cur);
         //   printf("%d %d\n",cur.fi,cur.se);
            if(s[i]=='L')cur.fi--;
            if(s[i]=='R')cur.fi++;
            if(s[i]=='U')cur.se++;
            if(s[i]=='D')cur.se--;
        }
        dx=cur.fi,dy=cur.se;
    }

  //  printf("dx %d dy %d\n",dx,dy);
    if(!dx&&!dy){
        auto tmp=rem;
        sort(tmp.begin(),tmp.end());
        printf("%lld\n",ll(unique(tmp.begin(),tmp.end())-tmp.begin()));
        return;
    }
    {
        int cnt=0;
        ll ans=0;
        for(auto [x,y]:rem){
            cnt++;
            REM tmp;
            tmp.init();
            if(dx)tmp.mx=(x%dx+dx)%dx;
            else tmp.mx=x;
            if(dy)tmp.my=(y%dy+dy)%dy;
            else tmp.my=y;
            if(dx&&dy){
                tmp.cha=x*dy-y*dx;
            }
            ll l=0,r=k-1;// 至少增长 0 次，最多增长 k-1 次。
            if(cnt==1){
                r++;
            }
            {
                {// 处理 x 方向限制
                    auto& okl=oklistx[tmp];
                    auto pos=okl.lower_bound(x);
                    if(pos!=okl.end()){
                        // 第一个大于等于 x 的位置。
                        if(dx>0){
                            // 当前主动向 x 更大延申
                            ckmn(r,(*pos-x)/dx-1);
                        }
                    }
                    if(pos!=okl.begin()){
                        pos--;
                        // x 更小的位置
                        if(dx>0){
                            // 需要考虑更小位置向当前延申
                            ckmx(l,((*pos+(k-1)*dx)-x)/dx+1);

                        }
                    }
                }
                #define x y
                #define dx dy
                #define oklistx oklisty 
                {// 处理 x 方向限制
                    auto& okl=oklistx[tmp];
                    auto pos=okl.lower_bound(x);
                    if(pos!=okl.end()){
                        // 第一个大于等于 x 的位置。
                        if(dx>0){
                            // 当前主动向 x 更大延申
                            ckmn(r,(*pos-x)/dx-1);
                        }
                    }
                    if(pos!=okl.begin()){
                        pos--;
                        // x 更小的位置
                        if(dx>0){
                            // 需要考虑更小位置向当前延申
                            ckmx(l,((*pos+(k-1)*dx)-x)/dx+1);

                        }
                    }
                }
                #undef x
                #undef dx
                #undef oklistx
            //    printf("[%lld %lld]\n",l,r);
                ans+=max(0ll,r-l+1);
            }
            {
                REM tmp;
                tmp.init();
                if(dx)tmp.mx=(x%dx+dx)%dx;
                else tmp.mx=x;
                if(dy)tmp.my=(y%dy+dy)%dy;
                else tmp.my=y;
                if(dx&&dy)tmp.cha=x*dy-y*dx;
                oklistx[tmp].insert(x);
                oklisty[tmp].insert(y);
                if(cnt==1){
                    oklistx[tmp].insert(x+dx);
                    oklisty[tmp].insert(y+dy);
                }
            }
        }
        printf("%lld\n",ans);
    }
}
signed main()
{
    int T;
    T=1;
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}
/*
1. 对题意的理解能否和样例对的上？  
2. 每一步操作，能否和自己的想法对应上？  
3. 每一步操作的正确性是否有保证？  
4. 是否考虑到了所有的 case？特别是极限数据。
5. 变量的数据类型是否与其值域匹配？
6. 时间复杂度有保证吗？
7. 空间多少 MB？  
*/