Спеціальні рухи#11804
Автор проблеми: | Хасан Салех (MathModel) |
Підготовлено: | Хасан Салех (MathModel) |
Редаговано: | Хасан Салех (MathModel) |
Ми можемо підтримувати карту пар до цілих чисел, тобто \mathtt{map<pair<int,int>,int>}, щоб ми могли відстежувати кількість відвідувань для кожної пари координат. Після цього ми проходимо через значення карти і перевіряємо максимальну кількість відвідувань (скажімо, це ). Потім ми проходимо через ключі карти і рахуємо, скільки mp[\{x,y\}]=m, і це буде остаточна відповідь.
Складність 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;
}