P6366特殊的翻转

P6366特殊的翻转

调试了一节课,几乎是把整个代码删了重改又不断改,没看任何题解和提示,是真硬调试出来的绿题,当然测试样例也给的好

这题有两个关键点

1.十六进制转成二进制,就是,每个数,转成4位的2进制

string temp = "";while (n--) {temp += v % 2 + '0';v >>= 1;}reverse(temp.begin(), temp.end());s += temp;

我就用的这种方法,一开始看这个字符串长度,10^6,还担心会不会爆内存,但现在看是多余了,所以说还是得先尝试,别被自己设想的困难吓到(励志鸡汤走一波)

2.解题的关键

这题和传智杯的那道补刀是一样的,实际上就是当前转还是不转的问题,什么时候转?什么时候不转?这跟选还是不选貌似很像啊! 感觉应该会有大佬用动态规划,但我是真不会,只好用dfs搜索替代,本质是一样的

步入正题,这个转还是不转需要限制条件

题目要求的是最少步数,那我们肯定是优先考虑不转的情况,因为不转起码少1步

也就是先考虑不转,记录不转情况下的最少步数

用-1作特殊值,返回来的是个-1,说明当前这个点不转不行,就继续向下走

能到这,说明当前的这个点是必须转的

注意,这里需要一个特判,因为我们其实已经知道了当前是必须转的,所以,

一旦,我当前的这个位置,它前面的元素值是          0        (很关键的一点)

那我就会把前面的变成1,同时,注意,我是已经处理完了这个点,不会再处理,那也就是说,这个1,是不会再有机会变成0的了,所以,这种情况,直接return -1,这说明了,不管这个点转还是不转,都不可能全转0,必然No

处理完特殊情况,那么接下来就是正常处理,1 - 0  , 0 - 1,然后就是继续深搜,按照上面的情况继续算

出现的问题点:

1.因为我最最开始想着前面设个虚拟头,结果最后特判的时候忘了这个虚拟头也得占长度,导致一直return -1    别忘了设置的虚拟头

2.1 - 0 ,0 - 1的时候没仔细想,就写成 1 - s[idx] + '0' ,这个乍一看好像没啥问题,但一想,不对啊,这个s[idx]是字符,怎么能数字减字符呢?所以,1得换成'1'

3.这个s得用引用传递,不然得爆MLE,然后,你一旦用的是引用传递,就得有个回溯的过程,还得把它们再全变回去 为啥? 不对啊,这前面不是说,到了该变换的位置一定要转,不应该是不用变的吗? 因为这其实是每个栈都在共用的,你当前改了符合自己,后面退回来的时候要改回去的,好怪,我自己也有点想不明白了,但却是得变回来

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define endl '\n'
#define int int64_t
using namespace std;
int dfs(string& s,int idx) {if (idx == s.size() - 1) {//  0 0		0 1		1 0		 1 1if ((s[idx - 1] == '0' || s[idx - 1] == '!') && s[idx] == '0') return 0;if ((s[idx - 1] == '1' || s[idx - 1] == '!') && s[idx] == '1') return 1;return -1;}//当前转还是不转//这个转和不转要有限制条件//先考虑不转的  什么时候才能不转//  1 1  1 0   0  1   0  0if (s[idx - 1] != '1') {int len = dfs(s, idx + 1);if (len != -1) return len;}//转  1 1  1 0   0  1   0  0// a   b   cif (s[idx - 1] == '0') return -1;s[idx - 1] = '1' - s[idx - 1] + '0';s[idx + 1] = '1' - s[idx + 1] + '0';s[idx] = '1' - s[idx] + '0';int len = dfs(s, idx + 1);s[idx - 1] = '1' - s[idx - 1] + '0';s[idx + 1] = '1' - s[idx + 1] + '0';s[idx] = '1' - s[idx] + '0';if (len == -1) return -1;return len + 1;
}// 10101   0 1 0  0 1		0  0  1  1  1   
signed main() {ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);string str, s = ""; cin >> str;for (int i = 0; i < str.size(); ++i) {int v; if (isalpha(str[i])) v = str[i] - 'A' + 10;else v = str[i] - '0';int n = 4;string temp = "";while (n--) {temp += v % 2 + '0';v >>= 1;}reverse(temp.begin(), temp.end());s += temp;}int idx = 0;while (idx < s.size() && s[idx] == '0')++idx;if (idx == s.size())  s = "0";else s = s.substr(idx);//cout << s << endl;s.insert(0, "!");int len = dfs(s, 1);if (len == -1) cout << "No" << endl;else cout << len << endl;//cout << "s = " << s << endl;return 0;
}