topcoder 650 srm

500

遇到这种构造题就给跪了

比赛的时候想很多方法 DP,贪心，模拟

发现越写越烦琐。看到别人出这么快，肯定又是奇葩思路。

后来居然想到 2^50的暴力 +剪枝不过暴力肯定卡你

IDEA: 只要我们使尽量 S[I]!=S[I-1]就好了。

对于s[0]=='?'我们枚举两次。

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 #include <set>
 8 #include <map>
 9 #include <string>
10 #include <math.h>
11 #include <stdlib.h>
12 #include <time.h>
13 #include<string>
14 using namespace std;
15 
16 class TaroFillingAStringDiv2 {
17     public:
18     int getNumber(string S) {
19     int s1,s2;
20     s1=s2=0;
21     string s=S;
22     if(S[0]=='?') s[0]='A';
23     for (int i=1;i<s.size();i++)
24     {
25         if (s[i]=='?') s[i]= s[i-1]=='A'?'B':'A';
26         if (s[i]==s[i-1]) s1++;
27     }
28 
29     s=S;
30     if(S[0]=='?') s[0]='B';
31     for (int i=1;i<s.size();i++)
32     {
33         if (s[i]=='?') s[i]= s[i-1]=='A'?'B':'A';
34         if (s[i]==s[i-1]) s2++;
35     }
36 
37     return min(s1,s2);
38    }
39 };