这是一道好题目啊，放假回头准备练练手的，发现是我弱爆了。。。首先一开始就大致确定好了思路，画了一会，发现优先队列直接贪心就可以的，接下来就敲了，一开始都用了字符串导致一直WA，做了一个下午把，后来发现了错的地方，然后接着TLE，然后看网上说是不要用STL的优先队列，自己写一个小顶堆，然后套了个模板，结果还是TLE,认为自己的模板错了，可是发现跟别人的一致，又弄到了现在，实在找不出哪里有问题，然后看题解了，发现了一篇转化着做的，把字符串转化成二进制的十进制数，这样就直接利用位运算来做，总算是A掉了，去尝试了记忆化搜索，因为转化后有状态标记的，试了几次，发现不行，就放弃了，一天就做了这一道题目。。。
参考了：戳这里
做法还是比较清晰的，画一画再大胆猜测一下，留个纪念，毕竟做了一天，题意说不清楚引用别人的：题目给出nop个操作，，由N(什么都不做),S(置1),C(置0),F(反转)等基本操作组成，每一种操作会产生不同的热量。又给出nw组初始字符串和目标字符串，要求出将初始字符串转化成目标字符串至少需要产生的热量；有可能没有解，此时输出“NP”
直接bfs,类似于dfs的暴力枚举一样，队列循环，每一次都去扫一遍nop的所有操作，然后花费小的优先，暴力寻找，找到跳出，找不到就是没有答案的，同时还要标记此状态是否已经出现过了，每一个求答案都得要把状态标记数组清空，前几天因为用了memset总是TLE，坑了许久，这题目还是有点虚的，还好没有被坑
以后做题要提醒自己发现思路了，要先好好想想怎么样做最方便，不然也把自己绕醉了~
typedef struct Node {int val;int ss;friend bool operator<(Node x,Node y) {return x.val > y.val;}};int n,nop,nw;int make_true[30 + 5],make_false[30 + 5],xo[30 + 5],w[30 + 5];bool vis[1<<22];priority_queue<Node > q;void init() {memset(make_true,0,sizeof(make_true));memset(make_false,0,sizeof(make_false));memset(xo,0,sizeof(xo));memset(w,0,sizeof(w));}bool input() {while(cin>>n>>nop>>nw) {for(int i=0;i<nop;i++) {char s[20 + 5];scanf("%s %d",&s,&w[i]);for(int j=0;j<n;j++) {make_true[i] <<= 1;make_false[i] <<= 1;xo[i] <<= 1;make_false[i]++;if(s[j] == 'S')make_true[i]++;else if(s[j] == 'F')xo[i]++;else if(s[j] == 'C')make_false[i]–;}}return false;}return true;}int slove(char *s) {int len = strlen(s);int ret = 0;for(int i=0;i<len;i++) {ret <<= 1;if(s[i] == '1')ret++;}return ret;}int bfs(int start,int end) {memset(vis,false,sizeof(vis));while(!q.empty()) q.pop();Node s,e;s.val = 0;s.ss = start;q.push(s);while(!q.empty()) {s = q.top();q.pop();int pos = s.ss;if(vis[pos])continue;if(pos == end)return s.val;vis[pos] = true;for(int i=0;i<nop;i++) {int tmp = ((pos&make_false[i])|make_true[i])^xo[i];if(!vis[tmp]) {e.ss = tmp;e.val = s.val + w[i];q.push(e);}}}return -1;}void cal() {int q = nw;bool flag = false;while(q–) {char start[20 + 5],end[20 + 5];scanf("%s %s",start,end);if(flag)putchar(' ');else flag = true;int s = slove(start);int e = slove(end);int ans = bfs(s,e);if(ans < 0)printf("NP");else printf("%d",ans);//cout<<"–>";}puts("");}void output() {}int main() {int t;cin>>t;while(t–) {init();if(input())return 0;cal();output();}return 0;}
当你能飞的时候就不要放弃飞
