今天是SRM482。。。今天晚上留在所里做題。。估計又是一個杯具。。。
看了一下SRM 381的題目。。
DIV2
1 排序，第一個樣例比較搞：
{"JOHN", "PETR", "ACRUSH"}
教主和Peter看了估計都哭了。。。把sort函數(shù)的comp條件搞一下就OK了。。
2 這個題目，說實(shí)話有點(diǎn)惡心。。一般一般吧。。有一個比較明顯的遞推公式。。搞不出來就杯具。。
const int maxn=1000010;
double f[maxn];
struct TheDiceGame {
double expectedThrows(int candies) {
f[0]=0;
for (int i=1; i<=candies; i++) {
f[i]=0;
for (int j=1; j<=6; j++) {
int x=i-j;
if (x<0) x=0;
f[i]+=(f[x]+1)/6;
}
}
return f[candies];
}
};
3 其實(shí)解法是非常直觀的。。當(dāng)然直觀就有直觀的陷阱。。當(dāng)你把數(shù)據(jù)的集合搞定之后，怎么把集合數(shù)據(jù)線序話，這個問題可以搞掉一大片人啊。。。
我開始就是想按位比較。。然后處理，寫成了遞歸。。。但這之中的情況，那叫一個相當(dāng)多。。。杯具。。。其實(shí)有一個巨trick的方法：
Suppose, we have two strings s and t. If t comes immediately after s in some arrangement and s+t < t+s we can easily swap them and receive bigger number. So, we can sort all strings according to this rule. It reminds bubble sort. Proof of this is a home task too and you should make it until next SRM.
不得不說，思維真不錯，很靈活。。。比較誰在前面，不就是比較一下就OK么。。。
================================================
相當(dāng)不華麗的分割線
================================================
DIV 1 等著下次再搞。。。但愿今晚不要太杯具。。