1 条题解
-
1Takagi-san (njnu19200437) LV 10 MOD @ 2021-05-27 23:26:18
F题题解:
可以看出
①奇数x出现次数一定没有偶数x+1多(1是唯一的特例)。这样看来,答案只会是偶数或1.
②我们这样来计算x在Path[1..n]的出现次数,且设x是偶数,则
x-1,x
2x-3 2x-2 2x-1 2x
4x-7 4x-6 ... 4x
...
它们的路径列表都包含了x。
并且从这里我们还可以明显看出,x的出现次数一定比x+2多。所以,我们只需要在范围内对于所有偶数进行二分查找即可。
Code:#include<bits/stdc++.h> using namespace std; #define ll long long int ll solve(ll x,ll y)//在1~x中假设答案是y,返回出现次数 { if(x == y - 1 && x % 2) return 1; if(x < y)return 0; if (y == 1) return x; if(y == 2) return x - 1; ll ans,p = 2; if (y % 2) p = 1; //对于奇数(虽然本题并不需要考虑) ans = p; while(1) { y *= 2; p *= 2; if(y - p + 1 > x) return ans; ans += min(y, x) - (y - p + 1) + 1; } } int main() { ll n, k;cin>>n>>k; if(n == k) {cout<<1<<endl; return 0;} ll l = 1,r = n / 2 + 1, ans = 0; while(l <= r){ ll mid = (l + r) / 2 ; if(solve(n, mid*2) >= k){ ans = max(ans, mid * 2); l = mid + 1; } else r = mid - 1; } cout<<ans; return 0; }
- 1