最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

环球短讯！Codeforces Round #753 (Div. 3)(ABCDE)

来源：博客园

A. Linear Keyboard

题意:

给26个字母代表你的键盘(没错你的键盘键位是一行)

再给你一个字符串,问你打出这个字符串需要消耗多少距离

思路:

前面几个数据键位没乱当然不用管,主要是如何处理乱序键位


(资料图片仅供参考)

就用个map来映射就完事了,把乱序的字母映射到26个正序字母上即可

后面套上map后的处理就跟没乱序一样了

代码:

void solve(){map mp;int ans = 0;string s1,s2;cin >> s1;cin >> s2;char x = "a";for(int i = 0;i < 26;i++){mp[s1[i]] = (char)x;x++;}for(int i = 0;i < s2.size() - 1;i++){// cout << abs(mp[s2[i]] - mp[s2[i + 1]]) << endl;ans += abs(mp[s2[i]] - mp[s2[i + 1]]);}cout << ans << endl;}

总结:

没啥说的,水题

B. Odd Grasshopper

题意:

给一个起始点x,要跳跃k次

从时间1开始,每秒跳当前时间的距离

如果当前脚下是奇数,向正半轴跳,如果是负数,向负半轴跳

思路:

经过简单模拟,得出了一个假规律(

主要是脑补了一个很对称的规律:向左跳1格,向右跳2格,向左跳3格,向右跳4格.......

但是但是,写完了发现对不上样例,这时才发现规律找假了(

然后又模拟了一遍找规律:

发现每4次跳跃后都会回到原点

那我们就只用考虑后面0-3秒怎么跳的了

模拟一下即可

代码:

void solve(){int x,k,op;cin >> x >> k;temp = k % 4;op = k - temp + 1;while(temp--){if(x&1) x += op;else x -= op;op++;}cout << x << endl;}

总结:

找规律环节千万不要脑补,是啥规矩就是啥规律(

最好把样例全部模拟一遍再开始写代码

C. Minimum Extraction

题意:

给n个数,每次能去掉数组中的最小的数,然后让所有数减去这个数

问最后能剩下的最小数的最大值是多少

思路:

一开始想的是负数是好东西啊,减一个就能加

然后就把负数和正数分开来算,想先算负数的,再算正数的

其实这里我就犯了一个很大的错误

就是每次减去一个负数,负数也会变大的,甚至减去最小的负数的话整体就没负数了

然后是关于正数的处理也很犯病(

用个vector来模拟,还用了erase和pop

就每次判断最大值减最小值是否大于最小值

但是这样弄显然是不对的,就算后面用个变量来模拟也很难对(

正确做法就是:

先考虑暴力,排完序以后减去最小值,更新右边的所有值,然后继续

但是暴力肯定过不了,想个优化

优化就是其实不用每次都更新后面的所有值,只要用个变量来记录即可

然后每次值再加上这个变量,用个ans变量来记录最大值

就能$O(n)$地解决这个问题

代码:

void solve(){cin >> n;vector a(n + 1);for(int i = 1;i <= n;i++) cin >> a[i];sort(all(a));int x = 0,ans = a[1];for(int i = 1;i <= n;i++){a[i] += x;x -= a[i];ans = max(ans,a[i]);}cout << ans << endl;}

总结:

对于求最大值最小值问题大可不必用个条件来判断退出,这样很容易WA

可以直接用个maxn或者minn来记录,跑完整个数组即可

先考虑暴力再考虑优化,不然容易错得离谱(((((

vector的erase和pop少用,一般用变量标记即可,这两个玩意太容易re了

D. Blue-Red Permutation

题意:

给n个数字,再给n个字符来决定这个数字能向上还是向下变化

问是否能让这n个数字变成1到n的序列(不需要排序)

思路:

最开始想的是弄个差分数组

然后统计出1到n每个位置能变的次数

后来发现没卵用(

随便交了一发贪心居然过了((

贪心思路就是:

排序,先看字符是啥,把字符B全部放在前面

然后字符相同的话数字升序排序

由于是组成一个排列,所以每个元素都是一一对应的

所以这个贪心思路显然是可以的

代码:

bool cmp(pair x,pair y){if(x.se == y.se) return x.fi < y.fi;else return x.se < y.se;} void solve(){cin >> n;vector> a(n + 1);for(int i = 1;i <= n;i++) cin >> a[i].fi;for(int i = 1;i <= n;i++) cin >> a[i].se;sort(all(a),cmp);// for(int i = 1;i <= n;i++) cout << a[i].fi << " " << a[i].se << endl;int idx = 1;for(int i = 1;i <= n;i++){if(a[i].fi < idx&&a[i].se == "B"){NO;return;}else if(a[i].fi > idx&&a[i].se == "R"){NO;return;}idx++;}YES;}

总结:

先把思路想通了再写代码

贪心比较玄学,多试试,能对上样例的话再考虑证明(

E. Robot on the Board 1

题意:

给出一个机器人的行动轨迹和场地大小n和m

让你判断在哪个点能执行最多的命令

思路:

当时第一眼感觉就是先求出每个方向的最大值

然后我求出来了

然后就不知道干啥了(

惯例,先想想暴力思路

每个点都模拟一遍那个路线,然后选出适合的

优化方案就是:

先求出每个方向的最大值

然后每次都检查一下能否放得下点

就是判断一下需要的横坐标长度$r - l + 1$是否大于本来的横坐标长度$m$

需要的纵坐标长度$d - u + 1$是否大于本来的纵坐标长度$n$

然后记录一下合适的点的坐标:$abs(u) + 1$,$abs(l) + 1$

一旦不满足条件了就直接break然后输出记录的上一个点即可

代码:

void solve(){string s1;cin >> n >> m;cin >> s1;int x = 0,y = 0,l = 0,r = 0,u = 0,d = 0,q1 = 1,q2 = 1;for(auto it : s1){if(it == "L") y--;else if(it == "R") y++;else if(it == "U") x--;else x++;l = min(l,y);r = max(r,y);u = min(u,x);d = max(d,x);if(r - l + 1 > m||d - u + 1 > n) break;q1 = abs(u) + 1;q2 = abs(l) + 1;// cout << q1 << " " << q2 << endl;}// cout << endl;cout << q1 << " " << q2 << endl;// cout << l << " " << r << " " << u << " " << d << endl;}

总结:

一般有很多个答案不知道咋个取答案的就是用缩小区间的方法

最小区间+1就是要的答案

关键词： 没啥说的 升序排序 就不知道