A. Linear Keyboard
题意:
给26个字母代表你的键盘(没错你的键盘键位是一行)
再给你一个字符串,问你打出这个字符串需要消耗多少距离
思路:
前面几个数据键位没乱当然不用管,主要是如何处理乱序键位
就用个map来映射就完事了,把乱序的字母映射到26个正序字母上即可
后面套上map后的处理就跟没乱序一样了
代码:
void solve()
{
map<char,char> 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<int> 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<int,char> x,pair<int,char> y)
{
if(x.se == y.se) return x.fi < y.fi;
else return x.se < y.se;
}
void solve()
{
cin >> n;
vector<pair<int,char>> 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$
代码:
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就是要的答案