Java教程

牛客小白月赛38 进击的图灵机

本文主要是介绍牛客小白月赛38 进击的图灵机,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目链接:https://ac.nowcoder.com/acm/contest/11215/H

(一)预备知识:

(1)upper_bound( begin,end,num):
    从数组的begin位置到end-1位置二分查找
    第一个大于num的数字,找到返回该数字的地址,
    不存在则返回end。通过返回的地址减去起始地址begin,
    得到找到数字在数组中的下标。
    lower_bound是找不小于,可能等于也可能大于。

(2)map的用法

https://blog.csdn.net/sevenjoin/article/details/81943864

(3)vector

构建邻接表

vector<int>pos[N];

我理解的是,表示一个动态的二维数组,pos【N】类似于C语言的指针数组。

(二)解题思路 参考链接:https://ac.nowcoder.com/discuss/750372?type=101&order=0&pos=2&page=1&channel=-1&source_id=1

 

 

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;
map<pair<int,int>,int>ma;
vector<int>pos[200005];//邻接表 
char s[200005];
int xx[200005],yy[200005];
int main()
{
    int n,m,tot=0,x=0,y=0;
    cin>>n>>m;
    scanf("%s",s+1);
    ma[{0,0}]=++tot;
    pos[tot].push_back(0);
    for(int i=1;i<=n;i++){
        if(s[i]=='U') y++;
        if(s[i]=='D') y--;
        if(s[i]=='L') x--;
        if(s[i]=='R') x++;
        if(!ma[{x,y}]) ma[{x,y}]=++tot;
        int p=ma[{x,y}];
        pos[p].push_back(i);
        xx[i]=x,yy[i]=y;
    }
    for(int i=1;i<=m;i++){
        int l,r;
        cin>>l>>r;
        l--;
        int p=ma[{xx[l],yy[l]}];
        int st=upper_bound(pos[p].begin(),pos[p].end(),l)-pos[p].begin();//大于l的第一个数字,起始在l的位置不计入 
        int ed=upper_bound(pos[p].begin(),pos[p].end(),r)-pos[p].begin();//大于r 
        cout<<ed-st<<endl;//计算[l,r]操作中经过相对起点l对应的坐标的次数 ed-1-st+1=ed-st 
     
    }
    return 0;
}

 

这篇关于牛客小白月赛38 进击的图灵机的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!