[传智杯]特殊的翻转（C++代码）全网首个详细题解

593 阅读 10 评论 0 点赞

## 题目看似吓人，其实就是贪心，相信我  动态规划都用不到！
**文章为作者原创内容，未经授权不允转载**
**
首先在文章首部给出代码整体框架：
**
1. 1.将所给的16进制转化为2进制字符串
1. 2.对2进制字符串进行贪心处理
1. 3.结合2.的处理给出答案

本题的难点在于**如何进行贪心处理**
#### 1.将题目给的16进制转化为2进制
我的方法是对输入的16进制字符串，进行逐位处理，每1位16进制 产生 4位2进制 然后字符串逐个拼接
代码如下：
```cpp
//单个16进制字符转2进制
string func(char c){
	string tem;
	int i,n=4;
	if(isdigit(c)) i = c-'0';
	else i = 10 +c-'A';
	while(n--){
		if(i%2==1)	tem = to_string(i%2) + tem;
		else tem = "0" + tem;
		i/=2;
	}
	return tem;
}
```
```cpp
//字符串初始化读入与拼接
	string  s,bstr;
	cin>>s; 
	for(int i=0;i<s.length();i++){
		bstr +=func(s[i]);
	}
```
注意：题目的第一个坑就是要记得删除掉前导0
代码如下：
```cpp
for(int i=0; bstr[i]=='0';){
		bstr.erase(0,1);
}
```
#### 2.对2进制字符串进行贪心处理
**难点，未看懂建议多看几遍**
我们可以把题意“对于每次“翻转”操作，k 老师可以选择这个 0/1 串中的其中一位，将这一位和这一位相邻的两位，一共三位，分别进行“翻转”（也就是 0 变 1，1 变 0）”
理解为：三个连续为1组，进行反转。当为两侧极限位置的时候只能2个反转。当字符串长度仅为1时只能自身反转。
由于首个必定为“1”，所以首个必定要反转一次，但是首个反转的方式有两种，于是有两种贪心策略；
##### 贪心策略1：
首次反转，反转下标 0，1位置；
然后 下标从1开始遍历，一直遍历到最后一个位置的前一个下标
内容若为1 则该位置p，P+1，P+2 进行反转 反转时注意记录次数
内容若位0 则不进行操作
最后：判断最后一个位置，若该位置存储的内容为 1 ，则此贪心策略不能解决问题
##### 贪心策略2：
首次反转，反转下标 0，1，2位置；
然后 下标从1开始遍历，一直遍历到最后一个位置的前一个下标
内容若为1 则该位置p，P+1，P+2 进行反转 反转时注意记录次数
内容若位0 则不进行操作
最后：判断最后一个位置，若该位置存储的内容为 1 ，则此贪心策略不能解决问题

#### 3.结合2.的处理给出答案
**这里有两种贪心策略的方法，因为策略不一样，所以造成最终结果不一样，最后取其中最优解策略，然后输出**
**若此两种策略都不能解决问题，答案为无解**
## AC代码
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
string func(char c){
	string tem;
	int i,n=4;
	if(isdigit(c)) i = c-'0';
	else i = 10 +c-'A';
	while(n--){
		if(i%2==1)	tem = to_string(i%2) + tem;
		else tem = "0" + tem;
		i/=2;
	}
	return tem;
}
int main(){
	string  s,bstr;
	cin>>s; 
	for(int i=0;i<s.length();i++){
		bstr +=func(s[i]);
	}
	for(int i=0; bstr[i]=='0';){
		bstr.erase(0,1);
	}
	int num1=0,num2=0,ok1 = 1,ok2 = 1;
	//多加一位，无所谓 ，目的方便处理 
	string s1 = bstr+'0',s2  =bstr+'0';
	//第一下转前两位
	for(int i = 1,l = bstr.length(); i < l;i++){
		if(i==1){
			num1++;
			s1[i-1] = '0';
			if(s1[i] == '1') s1[i] = '0';
			else s1[i] = '1';
		}else{
			if(s1[i-1] == '1'){
				num1++;
				s1[i-1] = '0';
				if(s1[i] == '1') s1[i] = '0';
				else s1[i] = '1';
				if(s1[i+1] == '1') s1[i+1] = '0';
				else s1[i+1] = '1';
			}
		}
	}
	if(s1[bstr.length()-1] == '1')ok1 = 0;
	
	//第一下转前三位
	for(int i = 1,l = bstr.length(); i < l;i++){
		if(s2[i-1] == '1'){
			num2++;
			s2[i-1] = '0';
			if(s2[i] == '1') s2[i] = '0';
			else s2[i] = '1';
			if(s2[i+1] == '1') s2[i+1] = '0';
			else s2[i+1] = '1';
		}
	}
	if(s2[bstr.length()-1] == '1')ok2 = 0;
	if(bstr.length() == 1 || bstr.length() == 0){
		cout<<bstr.length();
	}else if(ok1 == 0 && ok2 == 0){
		cout<<"No";
	}else{
		if(ok1 == 0)cout<<num2;
		else if(ok2 == 0)cout<<num1;
		else cout<<min(num1,num2);
	}
	//cout<<bstr;
	return 0;
}
```

0.0分

5 人评分

本文分类：题解列表
浏览次数：593 次浏览
发布日期：2020-04-12 03:01:14
本文链接：https://blog.dotcpp.com/a/69313

上一篇 > JakeLin-2313题-[传智杯]软件工程实习-题解(C++代码)-结构体排序
下一篇 > 二级C语言-分段函数（Java描述）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 10 条评论

Charles 4年前回复TA

@JakeLin 我是因为NO两个都是大写所以卡在那的

JakeLin 4年前回复TA

@JakeLin @uq_14083373143 emm啥意思呢，两个字母都是大写？

Charles 4年前回复TA

@JakeLin @starofang 谢谢大佬思路分享

Charles 4年前回复TA

@JakeLin @jake546 可能是No输出哪里，我开始两个字母都是大写一种百分6错误

李轩昂 4年前回复TA

@JakeLin 你把代码发下我看看

JakeLin 4年前回复TA

@JakeLin 哎，可是把1挑出来判断了还是错了6%  >.<

李轩昂 4年前回复TA

@JakeLin 长度为1，就只有1，不可能存在单个0的，因为删除前导0的时候会删除

JakeLin 4年前回复TA

@JakeLin 请问二进制长度为1，就是0和1两种情况而已吗

李轩昂 4年前回复TA

@JakeLin 遇到过，应该是忘记判断二进制长度为1的情况

JakeLin 4年前回复TA

请问一下博主有没有遇到过错误6%的情况

[传智杯]特殊的翻转 （C++代码）全网首个详细题解

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 10 条评论

发表评论 取消回复

[传智杯]特殊的翻转（C++代码）全网首个详细题解

评论列表共有 10 条评论

发表评论取消回复