Codeforces Round #389 (Div. 2,) B C

时间：2021-08-02 00:28:30

考完复变之后沉迷联盟不能自拔...明天就开始抢救计组 ...

B 一个人装错了键帽 选择几个pair 把pair里面的键帽交换 并且每个键帽最多可以换一次 给出按键序列和输出序列 判断是否可以 如果可以输出pair

因为每个键帽最多可以换一次 所以如果错了 一定是一一对应的

于是设定一个表存每个键帽对应的实际字母

需要注意的是 ac cc 这种情况下是 -1 很多人wa在了test14

C 在一个格子图里给出一个路径 里面有UDLR四种移动方向 问 我在格子路径里面最少选几个点 可以让我沿着格子路径走 其实是在相邻的点与点之间走最短路

可以想到 如果一个图中同时出现了LR UD 肯定不是最短路

所以将移动方向视为1-n 初始自己在0处 每次二分查找出自己位置到最后的四种移动方式的最左的位置

可见 此时可移动到 min(max(L,R)-1,max(U,D)-1)

连续二分 直到走到n处

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<math.h>

#include<map>

#include<string>

#include<vector>

#include<queue>

#include<iostream>

using namespace std;

#define L long long

char s[200050];

int n ;

int su[200050];

int sd[200050];

int sr[200050];

int sl[200050];

int ef(int a[],int ll,int rr,int val){

    int res = n + 1;

    int l = ll ;

    int r = rr ;

    while(l <= r){

        int mid = (l + r) / 2;

        if(a[mid]>val){

            res = mid ;

            r = mid - 1;

        }

        else {

            l = mid + 1;

        }

    }

    return res ;

}

int main(){

    scanf("%d",&n);

    scanf("%s",s+1);

    su[0] = sl[0] = sr[0] = sd[0] = 0;

    for(int i=1;i<=n;i++){

        su[i] = su[i-1];

        sr[i] = sr[i-1];

        sd[i] = sd[i-1];

        sl[i] = sl[i-1];

        if(s[i] =='U')su[i]++;

        if(s[i] =='D')sd[i]++;

        if(s[i] =='R')sr[i]++;

        if(s[i] =='L')sl[i]++;

    }

    int w = 0;

    int ans = 0;

    while(w < n){

        char c = s[w+1];

        int uu = ef(su,w+1,n,su[w]);

        int dd = ef(sd,w+1,n,sd[w]);

        int rr = ef(sr,w+1,n,sr[w]);

        int ll = ef(sl,w+1,n,sl[w]);

        int ky1 = max(uu,dd)-1;

        int ky2 = max(rr,ll)-1;

        int res = min(ky1,ky2);

        ans ++ ;

        w = res ;

    }

    printf("%d\n",ans);

}

　　

相关文章