[Practice]SRM 490 DIV I

>.<深切感受到自己蒟蒻。

 

250题意

N,M<=10^9

i=N;

j=M;

while (j<=lcm(N,M)){

while (i

ans+=j-i;

j+=M;

}

return (double)ans/(lcm(N,M)/M);(平均数)

、

然后发现其实每次j-i都是gcd(N,M)的倍数，设g=gcd(N,M)，然后j-i刚好是0,g,2*g,3*g,…,(lcm(N,M)/M-1)*g

、

lcm(N,M)/M=N/g

于是ans=(N/g)*(N/g-1)/2 * g  / (N/g)

然后最终代码是

int gcd(int x,int y){return y?gcd(y,x%y):x;}

double Starport::getExpectedTime(int N, int M) {

long long g=gcd(N,M);

long long t=N/g;

return g*(t*(t-1)/2)/(double)(t);

}

 

 

550

弄完以后交FST了….

题目大意就是给定一组字典，再给出一个字符串，让你用手机T9的方式最少要多少次按键把字符串打出来。

对我来说很考验coding啊>.<...

思路不太难，就模拟每次弄一个字典里字符的前缀。然后由于是类似栈的形式，只能从后面删和插入，所以可以F[i]表示前i个弄好最少多少次按键，然后弄个邻接矩阵mat[i][j]表示两两状态间转移最少需要多少步.

最后来个floyd就OK…

个中细节和处理技巧多多= =，请自行体会。。。

2Y。

 

被屠什么的，无所谓的。