填坑系列(p.246)
由函数连续性得满足二分性
1 #include2 #include 3 #include 4 #include 5 #include 6 7 using namespace std; 8 9 void setIO(const string& s) {10 freopen((s + ".in").c_str(), "r", stdin);11 freopen((s + ".out").c_str(), "w", stdout);12 }13 template Q read(Q& x) {14 static char c, f;15 for(f = 0; c = getchar(), !isdigit(c); ) if(c == '-') f = 1;16 for(x = 0; isdigit(c); c = getchar()) x = x * 10 + c - '0';17 if(f) x = -x;18 return x;19 }20 template Q read() {21 static Q x; read(x); return x;22 }23 24 const int N = 200000 + 5;25 26 int n, m;27 struct Gates {28 int a, b, o;29 }gates[N];30 31 int output(int k) {32 for(int i = 1; i <= m; i++) {33 int a = gates[i].a;34 int b = gates[i].b;35 int va = a < 0 ? -a > k : gates[a].o;36 int vb = b < 0 ? -b > k : gates[b].o;37 gates[i].o = !(va && vb);38 }39 return gates[m].o;40 }41 42 int solve(int vn) {43 int L = 1, R = n;44 while(L < R) {45 int mid = L + (R - L) / 2;46 if(output(mid) == vn) R = mid; else L = mid + 1;47 }48 return L;49 }50 51 int main() {52 #ifdef DEBUG53 freopen("in.txt", "r", stdin);54 freopen("out.txt", "w", stdout);55 #endif56 57 int T; scanf("%d", &T);58 while(T--) {59 scanf("%d%d", &n, &m);60 for(int i = 1; i <= m; i++) {61 scanf("%d%d", &gates[i].a, &gates[i].b);62 }63 int v0 = output(0), vn = output(n);64 if(v0 == vn) for(int i = 1; i <= n; i++) putchar('0');65 else {66 int p = solve(vn);67 for(int i = 1; i < p; i++) putchar('0');68 putchar('x');69 for(int i = p + 1; i <= n; i++) putchar('1');70 }71 puts("");72 }73 74 75 return 0;76 }