Maxsus Harakatlar#11804
Muammo Muallifi: | Hasan Saleh (MathModel) |
Tayyorlagan: | Hasan Saleh (MathModel) |
Tahrir qilgan: | Hasan Saleh (MathModel) |
Biz juftliklarni butun sonlarga xarita saqlashimiz mumkin, ya'ni \mathtt{map<pair<int,int>,int>}, shunda har bir koordinata juftligi uchun tashriflar sonini kuzatib borishimiz mumkin. Shundan so'ng, xaritaning qiymatlari bo'yicha o'tamiz va eng ko'p tashriflar sonini tekshiramiz (bu deb aytaylik). Keyin xaritaning kalitlari bo'yicha o'tamiz va nechta mp[\{x,y\}]=m ekanligini hisoblaymiz, va bu oxirgi javob bo'ladi.
Murakkablik O(n \log n).
#include <bits/stdc++.h>
using namespace std;
int solve(){
int n,x,y;cin>>n>>x>>y;
map<pair<int,int>,int>mp;
string s;cin>>s;
mp[{x,y}]++;
for(auto i:s){
if(i=='R'){
x++;
}
if(i=='L'){
x--;
}
if(i=='U'){
y++;
}
if(i=='D'){
y--;
}
mp[{x,y}]++;
}
int mx=0;int ans=0;
for(auto i:mp)mx=max(mx,i.second);
for(auto i:mp){
if(i.second==mx)ans++;
}
cout<<ans<<"\n";
return 0;
}
int main(){
int t;cin>>t;
while(t--){
solve();
}
return 0;
}