題目：戳這里

題意：一個(gè)點(diǎn)在[1,n]以內(nèi)，我們可以進(jìn)行4500次查詢，每次查詢之后，該點(diǎn)會(huì)向左或向右移動(dòng)0~k步，請(qǐng)?jiān)?500次查詢以內(nèi)找到該點(diǎn)。

解題思路：一邊二分，一邊隨機(jī)。

交互題似乎有好多是二分，上次交互題的二分調(diào)了好久，這次也是。我出數(shù)據(jù)水平又很低，所以至今不知道哪些數(shù)據(jù)可以卡哪些二分的寫(xiě)法，只能改一次交一次。。。

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <string> 5 #include <vector> 6 #include <map> 7 #include <cmath> 8 #include <iostream> 9 #include <random> 10 #include <ctime> 11 using namespace std; 12 typedef long long ll; 13 const int maxn = 1e6 + 10; 14 char ans[11]; 15 bool ask(ll l, ll r) 16 { 17 //printf("$$$$"); 18 printf("%lld %lld\n", l, r); 19 fflush(stdout); 20 scanf("%s", ans); 21 if(ans[0] == 'Y') 22 { 23 if(l == r) exit(0); 24 else return 1; 25 } 26 else return 0; 27 } 28 int na[maxn]; 29 int main() 30 { 31 ll n, k; 32 srand(time(NULL)); 33 scanf("%lld %lld", &n, &k); 34 ll l = 1, r = n; 35 while(l <= r) 36 { 37 ll mid = l + (r - l) / 2; 38 if(ask(l, mid)) 39 { 40 r = mid;//注意這點(diǎn)，我的理解是mid可能就是我們要找的點(diǎn)，如果用常規(guī)寫(xiě)法r=mid-1會(huì)把這個(gè)點(diǎn)跳過(guò)去 41 //但我試了幾個(gè)樣例，發(fā)現(xiàn)在區(qū)間不斷變化且有隨機(jī)數(shù)的情況下，及時(shí)r=mid-1也能找到答案。。 42 } 43 else 44 { 45 l = mid + 1; 46 } 47 l = max(1ll, l - k); 48 r = min(n, r + k); 49 mid = l + rand()%(r - l + 1); 50 ask(mid, mid); 51 l = max(1ll, l - k); 52 r = min(n, r + k); 53 } 54 return 0; 55 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/zmin/p/9606685.html

總結(jié)

以上是生活随笔為你收集整理的codeforces 1039B Subway Pursuit【二分+随机】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。