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

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

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);
}