【转】zoj 1007

很靠前的一道题,到今天才做,主要是突然发现他是一道很纯的数学题,,,拿到题后看了下,并没有怎么弄第三个式子,没管,自己化。要想减少循环的次数,必须把每次计算的级数提高,y(x) – y(1) 这个是重点,推式子就是从这里开始的,推到后来就自然地要用到第三个式子了,那些符号不知道怎么打,不过发现在网上有人已经写了,就是这样的方法,摘录如下:

假设n是要达到精度要求的要计算到的数:

到这里就差不多了,e*中我觉得只要考虑后面部分就可以了,在大于n时是小于1/(3*n^3)的,在n达到4次方的数量级时,误差就小于10^-12了,所以计算的次数就在10000以内了,开始的时候为了保险,开了100000,6秒多过了,后来一步步往下降,到8000也可以,0.5秒多,5000就不行,中间就没试了,没意思的,反正是达不到一大片人的0.00s,0.01s了,郁闷~~~~~

code:

#include "stdio.h"
int main()
{
double sum,x,k;
int i;
x=0.000;
for (i=0;i<=2000;i++)
{
   sum=0.0;
   for (k=1;k<8000;k++)
    sum+=1/(k*(k+1)*(k+2)*(k+x));
   sum=((2-x)*sum+0.25)*(1-x)+1;
   printf("%5.3f %16.12fn",x,sum);
   x+=0.001;
}
return 0;
}

[Summer2011]今天弱爆了

几乎全世界秒杀的题,我一直没看懂题目…

于是开着3个坑,全线卡题…

后来把一题比较卡常数的题目搞了以后…发现已经是122分钟了…- –

然后我继续纠结全世界人秒杀的题目…突然想起有forum这种东西可以提问= =…圡死了。

于是把这3个坑都水掉…

由于全世界人都秒杀的题至少搞了纯的2个小时…于是接着的一个简单但题意模糊的dp写不完了…

结果当然是挂了…

review一下没有泄露到题目,于是就这样…希望接下来没那么圡.

[ZOJ3209 Treasure Map] DLX解决精确覆盖问题中我的一个错误>.<

HHGG出的题T_T。

本身题目没啥好说的。很容易转化为精确覆盖。

但是我之前的DLX模板超时了。

好吧,那个在HUST1017上跑了4S的模板果然是不能用的。

然后,我照着hh(the small one)的模板YY出意思然后写了一个。HUST上…还是跑了1500+MS.这题还是TLE。

我记得之前那篇CLJ留言鄙视说暴力开指针都600+MS…

我再看了好多遍,觉得和hh的没啥区别嘛…为啥人家说200+MS

好多遍好多遍以后…我突然看到了一个不一样。

hh的:

    回溯部分:

    for (int j=L[i];j!=i;j=L[j]) resume(Col[j]);

    resume函数部分:

     for (int i=U[col];i!=col;i=U[i])

          for (int j=L[i];j!=i;j=L[j])

 

我的

    回溯部分:

     for (int j=R[i];j!=i;j=R[j]) resume(Col[j]);

    resume函数部分

     for (int i=D[col];i!=col;i=D[i])

        for (int j=R[i];j!=i;j=R[j])

 

 然而,我的其实犯了一个错误。

Dancing Link其实必须按照删除的先后顺序,依次恢复的。

比如删除的顺序是i,j,恢复的顺序就应当是j,i。举个例子就能知道原因

HUST的1017上

在for (int j=L[i];j!=i;j=L[j]) resume(Col[j]);这种方式下。无论resume函数里随便用ULDR都可以240MS左右AC。

而for (int j=R[i];j!=i;j=R[j]) resume(Col[j]);这种方式下。resume函数里如果用D可以1500MS AC。然后,如果是U的话就runtime error了。可见这种方式确实是错误的>.<

恩,终于搞了一个能用的精确覆盖模板了。

以后把mat和Num建好,一刷就好了

需要注意的是代码里,为了方便和速度,把二维点映射到一维上了。

http://ideone.com/2M7T4