Logo __vector__ 的博客

博客

题解：AT_abc219_f [ABC219F] Cleaning Robot

...
__vector__
2025-12-01 12:56:05

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-08-06 22:13:02

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

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

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

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

  • 存在一个非负整数 $k \lt K$，以及 $(sx,sy) \in S$，使得 $(sx+k\cdot dx,sy+k\cdot dy) = (x,y)$
  • 存在一个非负整数 $k \le K$，使得 $(x,y) = (k\cdot dx,k\cdot dy)$

换个理解方式，就是对于任意 $(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)$ 有哪些位置重合。

  • 首先，需要满足 $\frac{x_1-x_2}{dx} = \frac{y_1-y_2}{dy}$。
    本条件的原因是，加上的 $dx,dy$ 分别乘上的倍数都是相等的。
    本条件可以转化为 $x_1\cdot dy - y_1 \cdot dx = x_2 \cdot dy - dx \cdot y_2$，这样等式两边分别都只包含来自同一个元素的值，以及差不多相当于常量的 $dx,dy$。
  • 其次，需要满足 $x_1 \equiv x_2 \pmod {dx},y_1 \equiv y_2 \pmod {dy}$。
    如果不满足这个，那么当然是不能相等的，因为不能有小数。
  • 然后，需要满足 $|\frac{x_1-x_2}{d_x}| \lt k + [(x_2,y_2) = (0,0)]$。

综上，定义一个 $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？  
*\/

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

中文 English

鲁ICP备2025150228号

Server Time: 2025-12-15 05:57:47 | OpenSource Project