[题解]P13589 [NWRRC 2023] Intersegment Activation
WaterSun
·
·
题解
更好的阅读体验
思路
考虑从左往右将 i 变得可见，因为此时 1 \sim i - 1 都已经可见了，所以 \forall j < i,[j,i] 屏障都是没被激活的，只有满足 j \geq i 的 [i,j] 屏障可能会挡住 i。
操作次数 $\Theta(n^2 + \sum_{i = 1}^{n}2^i) = \Theta(n^2 + 2^{n + 1}) \leq 2500$ 很容易通过。
# Code
```cpp
#include <bits/stdc++.h>
#define re register
using namespace std;
int n,tmp;
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 3) + (r << 1) + (c ^ 48);
c = getchar();
}
return r * w;
}
inline int getst(int x){ return x ^ (x / 2); }
inline int ask(int l,int r){
printf("%d %d\n",l,r);
fflush(stdout);
return read();
}
int main(){
n = read(),tmp = read();
if (tmp == n) return 0;
for (re int i = 1,Max = tmp,MaxS = 0;i <= n;i++){
MaxS = 0;
int tot = (1 << (n - i + 1));
for (re int j = 0;j < tot;j++){
int lst = (j ? getst(j - 1) : 0),now = getst(j);
for (re int k = 0;k < n - i + 1;k++){
if (((lst >> k) & 1) != ((now >> k) & 1)){
int t = ask(i,i + k);
if (t == n) return 0;
if (t > Max){ Max = t,MaxS = now; }
}
}
} int now = getst(tot - 1);
for (re int k = 0;k < n - i + 1;k++){
if (((now >> k) & 1) != ((MaxS >> k) & 1)) ask(i,i + k);
}
}
return 0;
}
```