SRM 400 Div1_html/css_WEB-ITnose
250
简单题。 问一个数能否被表示 成 某个素数的若干次方
我用了一个很损精度得法
其实只要判平方完了直接枚举素数就OK
vectorans;bool check(int x) { int m = (int)sqrt(x * 1.0) + 1; if(x == 2) return true; for(int i = 2; i
500
区间DP
题目意思是说,给一个A串,一个B串
都是只包含0和1,然后用一些列reverse操作,将A变成B
reverse(i,j)表示把i,j这个区间反转
然后这系列操作有个限制
就是进行完一个操作之后,下一个操作必须在这个操作的区间中的子区间中进行,每个操作都是如此
然后这肯定是方便进行区间DP的
看有人写了一个很暴力的DFS, 没敢尝试,感觉复杂度没法算
dp[k][i][j][0]代表a串i位置开始长度为k的子串 不翻转 变成b串j位置开始长度为k的子串 需要的步数
dp[k][i][j][1]代表a串i位置开始长度为k的子串 翻转 变成b串j位置开始长度为k的子串 需要的步数
int n = a.size(); memset(dp, 0x3f, sizeof(dp)); for(int j = 0; j = 1000 ? -1: dp[n][0][0][0];
1000
这题公式很简单
n*(1/n+1/(n - 1) + 1/ (n - 2) +...+ 1/(n - k + 1) )
关键问题来了
n ,k都巨大
然后发现这个是个调和级数求和
数字大的时候只有近似公式
那么试试呗
(1/n+1/(n - 1) + 1/ (n - 2) +...+ 1/(n - k + 1) ) 约等于 log(n + 1) + R
R是欧拉常数
完了k大的时候就用这个公式去搞。不然直接for了
但是wa出翔了
最后发现别人这么干的 本来求出来的公式是log((n + 1) / (n - k + 1))
然后有个函数叫log1p ,是干什么的呢 log1p(x)返回的就是log(x + 1)
但是问题来了,当x巨小的时候,log1p的精度比较高,用log的时候x+1就丢精度了
然后就凑呗,凑着用log1p还不行,分母减个0.5,就是用来调控精度的。
这给我蛋疼的。
完了发现房里好多不用log1p的, 我全给cha掉了
double expectedBuy(string n, string k) { long long x = gao(n); long long y = gao(k); double ans = 0; long long s = x - y + 1; long long mx = 10000000; while(s
上一篇: jQuery实现带滚动线条导航效果的方法_jquery
下一篇: php 过滤所有html标签
推荐阅读
-
Topcoder SRM 638 DIV 2 (大力出奇迹)_html/css_WEB-ITnose
-
SRM 638 Div2_html/css_WEB-ITnose
-
SRM 638 Div2_html/css_WEB-ITnose
-
Topcoder SRM 638 DIV 2 (大力出奇迹)_html/css_WEB-ITnose
-
SRM 630 DIV2_html/css_WEB-ITnose
-
SRM 400 Div1_html/css_WEB-ITnose
-
【TopCoder SRM 157 DIV 1】 Salary 解题报告_html/css_WEB-ITnose
-
【TopCoder SRM 157 DIV 1】 Salary 解题报告_html/css_WEB-ITnose
-
SRM 400 Div1_html/css_WEB-ITnose
-
TopCoder SRM 634 Div.2[ABC]_html/css_WEB-ITnose