[MtOI2019]灵梦的计算器

蔚落 2023-06-02 11:57 3阅读 0赞

[\[MtOI2019\]灵梦的计算器][MtOI2019]

这个题目一开始是不太会的...后来经过\\(dalao\\)的提醒,想到了实数二分.  
然后实数二分的复杂度不太优秀,只能拿到\\(65pts\\).  
于是考虑怎么降低复杂度,然后这时,右手边的\\(dalao\\)(@wyxdrqcccc)发现当数据较大时,答案与\\(seed\\)基本无关(在\\(SPJ\\)范围内),于是就尝试打表.  
随手试了几个都命中了...然后就拿到了牛顿迭代的\\(85pts\\)

正好总结一下实数二分吧.  
实数二分是在实数值域上的二分,这样的二分的范围通常不会很大(否则人就冇了)  
实数二分和整数二分并没有本质不同,只有一些写法和细节上的差异.  
实数二分的时候,要指定一个不会产生过大精度误差的\\(eps\\),以这个值作为\\(l,r\\)的最小差值.  
不过笔者通常不使用这种写法,我一般是指定二分次数,只要不满足我指定的二分次数,就一直二分.  
这样的精度可以达到很高,而且也不存在仔细斟酌考虑\\(eps\\)的问题,只要复杂度允许,参数爱设为几就设为几.  
笔者一般是从\\(100\\)次开始逼近精度.  
还要注意的是,二分端点变化时,都要等于\\(mid\\),而不能等于\\(mid+1\\)或\\(mid-1\\),这样你人就冇了,原因显然,你会错过可能存在于\\(mid\\)到\\(mid\\pm 1\\)的解.  
其他地方,笔者感觉和整数二分并没有什么不同.

\\(Code:\\)

#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <string> #include <vector> #include <queue> #include <cmath> #include <map> #define MEM(x,y) memset ( x , y , sizeof ( x ) ) #define rep(i,a,b) for (int i = a ; i <= b ; ++ i) #define per(i,a,b) for (int i = a ; i >= b ; -- i) #define pii pair < int , int > #define X first #define Y second #define rint read<int> using std::pair ; using std::max ; using std::min ; using std::priority_queue ; using std::vector ; int T ; double ans = 0.0 ; namespace Mker { #define uint unsigned int 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 ; }

转载于:https://www.cnblogs.com/Equinox-Flower/p/11405212.html

[MtOI2019]: https://www.luogu.org/problem/P5515