题解归档 - cf321A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf321A
• 本地来源：problems/cf321A/idea.md
• 题目链接：https://codeforces.com/contest/321/problem/A
• 原始标题：CF321A — Ciel and Robot

思路

CF321A — Ciel and Robot

题意

机器人从 (0,0) 出发，无限循环执行命令串 s（U/D/L/R）。判断能否在某时刻到达 (a,b)。

做法

记一轮周期内前缀位移 (px[i], py[i])（i=0..|s|，含起点），周期总位移 (tx,ty)=(px[|s|],py[|s|])。

任意可达点为 px[i]+k*tx, py[i]+k*ty（k≥0）。

对每个前缀点分类讨论：

1. tx=ty=0：只能在一轮内到达，直接判 (a,b) 是否等于某个前缀点。
2. tx=0：需 a=px[i] 且 (b-py[i]) 能被 ty 整除，商 ≥0。
3. ty=0：对称。
4. 一般情况：存在同一 k 使 a-px[i]=k*tx 且 b-py[i]=k*ty，等价于交叉相乘 da*ty==db*tx，再检查 da%tx==0 且 da/tx≥0。

复杂度 O(|s|)。

验证

• 官方 4 组样例全部通过。
• 对拍：brute 枚举 k≤500 与所有前缀点比对（小坐标随机数据）。

结论

经典周期 + 前缀枚举；Div.1 A，实现注意 long long 与整除方向。

代码

来源：problems/cf321A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:57:52
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string s;
ll px[105],py[105];
bool chk(ll da,ll db,ll dx,ll dy){
    if(dx==0 and dy==0) return da==0 and db==0;
    if(dx==0){
        if(da!=0) return 0;
        if(dy==0) return db==0;
        if(db%dy) return 0;
        return db/dy>=0;
    }
    if(dy==0){
        if(db!=0) return 0;
        if(da%dx) return 0;
        return da/dx>=0;
    }
    if(da%dx or db%dy) return 0;
    ll k1=da/dx,k2=db/dy;
    return k1==k2 and k1>=0;
}
int main(){
    ll a,b,i,n,dx,dy,ans;
    cin>>a>>b;
    cin>>s;
    n=(ll)s.size();
    dx=dy=0;
    px[0]=py[0]=0;
    for(i=0;i<n;i++){
        if(s[i]=='U') py[i+1]=py[i]+1,px[i+1]=px[i];
        if(s[i]=='D') py[i+1]=py[i]-1,px[i+1]=px[i];
        if(s[i]=='L') px[i+1]=px[i]-1,py[i+1]=py[i];
        if(s[i]=='R') px[i+1]=px[i]+1,py[i+1]=py[i];
        dx=px[i+1];
        dy=py[i+1];
    }
    ans=0;
    if(a==0 and b==0) ans=1;
    for(i=0;i<nand!ans;i++){
        if(chk(a-px[i],b-py[i],dx,dy)) ans=1;
    }
    if(ans) cout<<"Yes\n";
    else cout<<"No\n";
    return 0;
}