#617(div.3):map应用

Yet Another Walking Robot

原题链接:https://codeforces.com/contest/1296

比赛时没想出来咋做,跳过去了,做了D。(D题比C题水)

主要是不知道怎样存两个数,用二维数组开不了这么大的空间

代码:

#include <bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> Map;
struct qq
{
    int l,r;
}q[200010];
int main()
{
    int t,n;
    string s;
    cin>>t;
    while(t--)
    {
        Map.clear(); /////////////////
        cin>>n;
        cin>>s;
        int zx=0,zy=0,cnt=1;
        Map[{0,0}]=cnt++;
        int ans=99999999,op=0;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='L')
            {zx--;}
            if(s[i]=='R')
            {zx++;}
            if(s[i]=='U')
            {zy++;}
            if(s[i]=='D')
            {zy--;}
            if(Map[{zx,zy}]==0)
            {Map[{zx,zy}]=cnt++;
            continue;}
            if(Map[{zx,zy}]!=0)
            {
                q[op].r=i+1;
                q[op].l=i+2-(cnt-Map[{zx,zy}]);
                op++;
                ans=min(ans,cnt-Map[{zx,zy}]);
                Map[{zx,zy}]=cnt++;
            }
        }
        if(op==0)
        {cout<<"-1"<<endl;
        continue;}
        for(int i=0;i<op;i++)
        {
            if((q[i].r-q[i].l+1)==ans)
            {cout<<q[i].l<<" "<<q[i].r<<endl;
            break;}
        }
    }
    return 0;
} 

123

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注