1 比較簡單，不過不是那么容易想。
給定初始字符串，然后兩個(gè)緩沖隊(duì)列，把初始字符串經(jīng)過一部分操作變成目標(biāo)字符串。
由于具有兩個(gè)緩沖隊(duì)列，而且初始字符串中字符只有兩類，所以可以一次搞定！利用substr() 判斷一下就OK
2 應(yīng)該觀察到對(duì)最后的期望有貢獻(xiàn)的只是具有連續(xù)洼地的地方，所以只要枚舉出現(xiàn)連續(xù)洼地的期望就可以了，復(fù)雜度是O(n^2)的，然后下面的代碼就非常清楚了！主要是沒有注意這個(gè)關(guān)鍵點(diǎn)！
class MuddyRoad{
public:
double getExpectedValue(vector <int> road){
vector<double> prob;
for(int i=0;i<road.size();i++)prob.push_back((double)road[i]/100);
int n=prob.size();
double ans=0;
for(int i=1;i<=n-2;i++){
for(int j=i;j<=n-2;j++){
int c=(j-i+1)/2;
double p=1;
p*=(1-prob[i-1]);
p*=(1-prob[j+1]);
for(int k=i;k<=j;k++)p*=prob[k];
ans+=p*c;
}
}
return ans;
}
};
當(dāng)時(shí)比賽的時(shí)候，我在想DP的狀態(tài)轉(zhuǎn)移，貌似寫挫了，不太清楚O(n)的算法思路和我的是否相似。。
3
看來還是蠻簡單的，就是一個(gè)容斥原理啊，復(fù)雜度是O(nlogn)+O(n)* O(容斥)
容斥其實(shí)是蠻難做的！看下面這個(gè)：
The simplest approach would be to go over all 1,000,000,000,000 IP addresses individually, and for each one, check all the requests to see who offers the highest price, and then add that to the total.
This works perfectly except it will obviously be too slow. So instead of looking at individual IP addresses, we should partition the set of all IP addresses, so that each part will be assigned to a single buyer. Then, we simply need to find the size and price for each part, and we can easily multiply and add them together.
For example, if we have requests for "1.2.3.0", "1.2.3.1" and "1.2.3.*" then interesting parts would be {"1.2.3.0"}, {"1.2.3.1"}, and {"1.2.3.2","1.2.3.3",...,"1.2.3.999"}. All of these can be represented implicitly if we take a special value (like -1 in bmerry's code) to mean "all other, unused values".
Since the interesting values for each component come from the N requests in the input, there are at most N4 parts to check (or (N+1)4 in bmerry's code). With an additional loop for each part this yields an O(N5) algorithm.