Q1
题目
我叫王大锤,是一家出版社的编辑。我负责校对投稿来的英文稿件,这份工作非常烦人,因为每天都要去修正无数的拼写错误。但是,优秀的人总能在平凡的工作中发现真理。我发现一个发现拼写错误的捷径:
- 三个同样的字母连在一起,一定是拼写错误,去掉一个的就好啦:比如 helllo -> hello
- 两对一样的字母(AABB型)连在一起,一定是拼写错误,去掉第二对的一个字母就好啦:比如 helloo -> hello
- 上面的规则优先“从左到右”匹配,即如果是AABBCC,虽然AABB和BBCC都是错误拼写,应该优先考虑修复AABB,结果为AABCC
我特喵是个天才!我在蓝翔学过挖掘机和程序设计,按照这个原理写了一个自动校对器,工作效率从此起飞。用不了多久,我就会出任CEO,当上董事长,迎娶白富美,走上人生巅峰,想想都有点小激动呢!
……
万万没想到,我被开除了,临走时老板对我说: “做人做事要兢兢业业、勤勤恳恳、本本分分,人要是行,干一行行一行。一行行行行行;要是不行,干一行不行一行,一行不行行行不行。” 我现在整个人红红火火恍恍惚惚的……
请听题:请实现大锤的自动校对程序
数据范围: ,每个用例的字符串长度满足
解答
#include<iostream>
#include<string>
using namespace std;
int main() {
//自动机
int n;
cin >> n;
while (n--) {
int state = 0;//初始化为状态0
char cur;//当前字符
string str;//目标字符串
cin >> str;
char last = str[0];//初始化为第一个字符
string ans = "";
ans += str[0];//初始化
for (int i = 1; i < str.size(); ++i) {//开始
cur = str[i];
switch (state)
{
case 0:
{
if (cur == last)//如果是相等的,进入状态1,否则继续状态0;
state = 1; //进入状态1:AA形式
else state = 0; //继续状态0:AB形式,即正常形式
break;
}
case 1:
{
if (cur == last)
continue;//AAA,忽略即可
else
state = 2;//进入状态3:AAB形式
break;
}
case 2:
{
if (cur == last)
continue;//AABB,忽略即可
else
state = 0;//AABC,就是状态0
break;
}
default:
break;
}
ans = ans + cur;
last = cur;
}
cout << ans << endl;
}
return 0;
}
分析
自动机是根据当前字符和前一字符比较的结果,来运转的
语法:
自动机可以通过循环内嵌switch实现
c语言的break;
如果是在循环内的switch内使用,则,只会跳出switch,而不是跳出循环
continue,即使在循环内的switch中使用,也会直接到下一次循环
Q2
题目
我叫王大锤,是一名特工。我刚刚接到任务:在字节跳动大街进行埋伏,抓捕恐怖分子孔连顺。和我一起行动的还有另外两名特工,我提议
- 我们在字节跳动大街的 N 个建筑中选定 3 个埋伏地点。
- 为了相互照应,我们决定相距最远的两名特工间的距离不超过 D 。
我特喵是个天才! 经过精密的计算,我们从X种可行的埋伏方案中选择了一种。这个方案万无一失,颤抖吧,孔连顺!
……
万万没想到,计划还是失败了,孔连顺化妆成小龙女,混在cosplay的队伍中逃出了字节跳动大街。只怪他的伪装太成功了,就是杨过本人来了也发现不了的!
请听题:给定 N(可选作为埋伏点的建筑物数)、 D(相距最远的两名特工间的距离的最大值)以及可选建筑的坐标,计算在这次行动中,大锤的小队有多少种埋伏选择。
注意:
- 两个特工不能埋伏在同一地点
- 三个特工是等价的:即同样的位置组合( A , B , C ) 只算一种埋伏方法,不能因“特工之间互换位置”而重复使用
数据范围:
解答
#include <iostream>
#include <vector>
using namespace std;
long long C(long long n) {
return (n-1) * n / 2;
}
int main()
{
int N, D; cin>> N >> D;
long long count = 0;
vector<int> res(N);
for (int end = 0, begin = 0; end < N; end++) {
cin>> res[end];
while (end >= 2 && (res[end] - res[begin]) > D) {
begin++;//不满足则begin往前移动
}
count += C(end - begin);//由于判断一次往前移动(for循环中的end++),即可以采用每次固定首位的组合。
}
cout << count % 99997867;
}
分析
定一移一
如果Cn3,则情况难以排重
如果定下最左边,则找出右边满足条件的最右边的那个值,从而确定一个范围,然后cn2
如上遍历所有最左边,最后结果相加。
也可以定下最右边,找出左边可取的最远位置,同样确定了一个范围,cn2
遍历
Q3
题目
链接:https://www.nowcoder.com/questionTerminal/448127caa21e462f9c9755589a8f2416?answerType=1&f=discussion
来源:牛客网
小包最近迷上了一款叫做雀魂的麻将游戏,但是这个游戏规则太复杂,小包玩了几个月了还是输多赢少。
于是生气的小包根据游戏简化了一下规则发明了一种新的麻将,只留下一种花色,并且去除了一些特殊和牌方式(例如七对子等),具体的规则如下:
总共有36张牌,每张牌是1~9。每个数字4张牌。
你手里有其中的14张牌,如果这14张牌满足如下条件,即算作和牌
14张牌中有2张相同数字的牌,称为雀头。
除去上述2张牌,剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌(例如234,567等),刻子的意思是相同数字的3个数字牌(例如111,777)
例如:
1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头,可以和牌
1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头,组123,123,567,789的四个顺子,可以和牌
1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头,都无法组成和牌的条件。
现在,小包从36张牌中抽取了13张牌,他想知道在剩下的23张牌中,再取一张牌,取到哪几种数字牌可以和牌。
解答
#include <iostream>
(720)#include <vector>
using namespace std;
vector<int> card(9);
//检查剩余的牌能否组成n个顺子或刻子
bool hasTrible(int n){
if(n==0) return true;
for(int i=0; i<card.size(); ++i){
//因为仍是从1开始查验,因此若检查到其牌数>=3,则必定是刻子
if(card[i]>2){
card[i] -= 3;
if(hasTrible(n-1)){ //检查余下的牌能否组成n-1个顺子或刻子
card[i] += 3;
return true;
}
card[i] += 3;
}
//否则只能是顺子
else if(i<card.size()-2 && card[i]>0 && card[i+1]>0 && card[i+2]>0){
card[i]--;
card[i+1]--;
card[i+2]--;
if(hasTrible(n-1)){
card[i]++;
card[i+1]++;
card[i+2]++;
return true;
}
card[i]++;
card[i+1]++;
card[i+2]++;
}
}
return false;
}
//检查14张牌能否和牌
bool isWin(){
for(int i=0; i<9; ++i){ //依次把1~9作为雀头拿出来,检查剩下的12张牌能否顺或刻子
if(card[i]<2)
continue;
card[i] -= 2;
if(hasTrible(4)){
card[i] += 2;
return true;
}
card[i] += 2;
}
return false;
}
int main(){
vector<int> res;
int tmp;
for(int i=0; i<13; ++i){
cin >> tmp;
card[tmp-1]++;
}
for(int i=0; i<9; ++i){ //1~9依次添加,检查是否可以和牌
if(card[i]>3)
continue;
card[i]++;
if(isWin()) //如果添加的这张牌可以和牌,则将其加入输出结果
res.push_back(i+1);
card[i]--;
}
if(res.empty()) res.push_back(0);
for(int i=0; i<res.size(); ++i)
cout << res[i] << ' ';
return 0;
}
分析
实际上是遍历,回溯
Q4
题目
链接:https://www.nowcoder.com/questionTerminal/5afcf93c419a4aa793e9b325d01957e2?answerType=1&f=discussion
来源:牛客网
小明是一名算法工程师,同时也是一名铲屎官。某天,他突发奇想,想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息,他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x_1=x_2 and y_1=y_2,那么这俩是同一个特征。
因此,如果喵咪特征连续一致,可以认为喵咪在运动。也就是说,如果特征<a, b>在持续帧里出现,那么它将构成特征运动。比如,特征<a, b>在第2/3/4/7/8帧出现,那么该特征将形成两个特征运动2-3-4 和7-8。
现在,给定每一帧的特征,特征的数量可能不一样。小明期望能找到最长的特征运动。
题解
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
int n, m;
cin >> n;
int len;
pair<int, int> xy;
while (n--)
{
cin >> m;
int maxCnt = 0;
map<pair<int, int>, int> preFeaTimes;
map<pair<int, int>, int> feaTimes;
while (m--)
{
cin >> len;
for (int i = 0; i < len; i++)
{
cin >> xy.first >> xy.second;
if (preFeaTimes.count(xy))
feaTimes[xy] = preFeaTimes[xy] + 1;
else
feaTimes[xy] = 1;
if (feaTimes[xy] > maxCnt)
maxCnt = feaTimes[xy];
}
preFeaTimes.clear();
preFeaTimes.swap(feaTimes);
}
cout << maxCnt << endl;
}
return 0;
}
分析
两个map,一个用于记录历史记录的各特征动作,另一个则是历史+当前帧的特征动作(先查找历史是否有,无则置为1,有则累加),然后清空历史记录,交换两个map
注意map.swap(),是交换,内容互换,因此要先清空历史,或者交换后清空当前。
unordered_map 底层是hash
map则是红黑树