CF1117C 解题报告

elbissoPtImaerD · 2024-03-02 19:05:39 · 题解

联合省选 2024 D1T1 弱化版。
贝省选形式化题意创到了。

将位移拆成两类考虑：一类是风被动产生的，一类是人主动产生的。

不妨设前者起点为 T(x_2-x_1,y_2-y_1)，后者起点为 S(0,0)。

设答案为 m，枚举 i = m \bmod n，记 N = \lfloor\frac mn \rfloor。

不难发现若存在余数为 i 的合法步数，等价于存在正整数 N 使得 |Fx(N)| + |Fy(N)| \le Fn(N) ，其中 Fx,Fy,Fn 均为关于 N 的一次函数。具体地，记前 i 步位移为 s，一轮 n 步位移为 S，Fx(N) = S_xN + s_x + T_x，Fy(N) = S_yN + s_y + T_y，Fn(N) = Nn + i。

将绝对值拆开解一元一次不等式即可求出 N 的范围，从而得到余数为 i 时的最小 m。

细节看代码：

#define int long long
const map<char,pii>dr={{'U',{0,1}},{'D',{0,-1}},{'L',{-1,0}},{'R',{1,0}}};
il pii operator+(pii x,pii y){return pii(x.x+y.x,x.y+y.y);}
il pii operator+=(pii&x,pii y){return x=x+y;}
il pii operator-(pii x,pii y){return pii(x.x-y.x,x.y-y.y);}
il pii operator-=(pii&x,pii y){return x=x-y;}
il pii operator*(pii x,pii y){return pii(max(x.x,y.x),min(x.y,y.y));} // cap
il pii operator*=(pii&x,pii y){return x=x*y;}
const int inf=1LL<<60;
il void Solve()
{
  pii S,T;rd(S.x),rd(S.y),rd(T.x),rd(T.y),T-=S;
  int n;rd(n);
  str s;rd(s);
  pii d=T,ds{};
  for(int i=0;i<n;++i) ds-=dr.at(s[i]);
  int ans=inf;
  for(int i=0;i<=n;++i) {
    pii fx(ds.x,d.x),fy(ds.y,d.y),fn(n,i),rag(0,inf);
    // |fx(N)| + |fy(N)| \le fn(N)
    auto F=[&](pii x)->pii // g(x) \ge 0 => x \in [l,r]
    {
      if(x.x) {
        if(x.x>0) return pii(ceil((db)-x.y/x.x),inf);
        else return pii(-inf,floor((db)-x.y/x.x));
      }
      else return x.y<0?pii(inf,-inf):pii(-inf,inf);
    };
    for(pii g:{fn-fx-fy,fn-fx+fy,fn+fx-fy,fn+fx+fy}) rag*=F(g);
    if(rag.x<=rag.y) {
      cn(ans,rag.x*n+i);
    }
    if(i<n) d-=dr.at(s[i]);
  }
  wrt(ans<inf?ans:-1);
  return;
}

\color{green}{\checkmark}