今天是SRM482。。。今天晚上留在所里做题。。估计又是一个杯具。。。
看了一下SRM 381的题目。。
DIV2
1 排序，第一个样例比较搞：
{"JOHN", "PETR", "ACRUSH"}
教主和Peter看了估计都哭了。。。把sort函数的comp条件搞一下就OK了。。
2 这个题目，说实话有点恶心。。一般一般吧。。有一个比较明显的递推公式。。搞不出来就杯具。。
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 其实解法是非常直观的。。当然直观就有直观的陷阱。。当你把数据的集合搞定之后，怎么把集合数据线序话，这个问题可以搞掉一大片人啊。。。
我开始就是想按位比较。。然后处理，写成了递归。。。但这之中的情况，那叫一个相当多。。。杯具。。。其实有一个巨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么。。。
================================================
相当不华丽的分割线
================================================
DIV 1 等着下次再搞。。。但愿今晚不要太杯具。。