本文章由 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？
*\/
鲁ICP备2025150228号