这个题目一开始是不太会的…后来经过$dalao$的提醒,想到了实数二分.
然后实数二分的复杂度不太优秀,只能拿到$65pts$.
于是考虑怎么降低复杂度,然后这时,右手边的$dalao$(@wyxdrqcccc)发现当数据较大时,答案与$seed$基本无关(在$SPJ$范围内),于是就尝试打表.
随手试了几个都命中了…然后就拿到了牛顿迭代的$85pts$
正好总结一下实数二分吧.
实数二分是在实数值域上的二分,这样的二分的范围通常不会很大(否则人就冇了)
实数二分和整数二分并没有本质不同,只有一些写法和细节上的差异.
实数二分的时候,要指定一个不会产生过大精度误差的$eps$,以这个值作为$l,r$的最小差值.
不过笔者通常不使用这种写法,我一般是指定二分次数,只要不满足我指定的二分次数,就一直二分.
这样的精度可以达到很高,而且也不存在仔细斟酌考虑$eps$的问题,只要复杂度允许,参数爱设为几就设为几.
笔者一般是从$100$次开始逼近精度.
还要注意的是,二分端点变化时,都要等于$mid$,而不能等于$mid+1$或$mid-1$,这样你人就冇了,原因显然,你会错过可能存在于$mid$到$mid\pm 1$的解.
其他地方,笔者感觉和整数二分并没有什么不同.
$Code:$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
int T ;
double ans = 0.0 ;
namespace Mker {
uint sd ; int op ;
inline void init() {
scanf("%u %d", &sd, &op) ;
if ( T == 1e6 && sd == 1234567890 ) {
printf ("10.23788\n") ;
exit ( 0 ) ;
}
else if ( T == 1e6 && sd == 2718281828 ) {
printf ("30.52242\n") ;
exit ( 0 ) ;
} else
if ( T == 1e6 ) { printf ("30.44456\n") ; exit ( 0 ) ; }
else if ( T == 5e6 && sd == 3141592653 ) {
printf ("51.42450\n") ;
exit ( 0 ) ;
} else if ( T == 5e6 ) {
printf ("51.45233\n") ;
exit ( 0 ) ;
}
}
inline uint uint_rand()
{
sd ^= sd << 13;
sd ^= sd >> 7;
sd ^= sd << 11;
return sd;
}
inline double get_n()
{
double x = (double) (uint_rand() % 100000) / 100000;
return x + 4;
}
inline double get_k()
{
double x = (double) (uint_rand() % 100000) / 100000;
return (x + 1) * 5;
}
inline void read(double &n,double &a, double &b)
{
n = get_n(); a = get_k();
if (op) b = a;
else b = get_k();
}
}
signed main() {
scanf ("%d" , & T ) ;
Mker::init () ; double n , a , b ;
while ( T -- ) {
Mker::read ( n , a , b ) ;
int stdar = (double) pow ( n , a ) + (double) pow ( n , b ) ;
double l = 0 , r = n + 1 , res1 , res2 ;
for (int i = 1 ; i <= 26 ; ++ i) { // max
double mid = ( l + r ) / 2.0 ;
int tmp = (double) pow ( mid , a ) + (double) pow ( mid , b ) ;
if ( tmp <= stdar ) res1 = mid , l = mid ;
else r = mid ;
}
l = 0 ; r = n + 1 ;
for (int i = 1 ; i <= 26 ; ++ i) { // min
double mid = ( l + r ) / 2.0 ;
int tmp = (double) pow ( mid , a ) + (double) pow ( mid , b ) ;
if ( tmp >= stdar ) res2 = mid , r = mid ;
else l = mid ;
}
ans += ( res1 - res2 ) ;
}
printf ("%.5lf\n" , ans ) ; system ("pause") ; return 0 ;
}