https://www.luogu.com.cn/contest/110331

https://www.luogu.com.cn/team/44709#problem

可以在 https://www.luogu.com.cn/problem/T335306 下载 manual.pdf，在 https://www.luogu.com.cn/problem/T335313 下载 statement.pdf 和 simulator.cpp。

组合逻辑电路部分

此部分的要求详见 statement.pdf 的第 \(\symbfit{3}\) 页。

(40pts) Task1 投票器

题面详见 statement.pdf 的第 \(\symbfit{4}\) 页。

只需要看两两 AND 的结果有没有 \(1\) 即可。如果有，那么代表 \(A + B + C \geq 2\)，反之 \(A + B + C < 2\)。

也就是说：

5=AND(1,2);6=AND(1,3);7=AND(2,3);4=OR(5,6,7);

即可满分。

(20pts) Task2 译码器

题面详见 statement.pdf 的第 \(\symbfit{5}\) 页。

首先把 \(A\) 的每一位按位取反，枚举 \(0 \sim 31\) 的每一个数的每一位，如果是 \(1\) 直接调用 \(A\) 的相应位，否则调用 \(\neg A\) 的相应位。把这些 AND 起来。最后别忘了 AND 一下 \(E\)。

#include <bits/stdc++.h>
using namespace std;
inline void solve (int a, string type, vector < int > b) {
  int n = b.size ();
  printf ("%d=", a);
  int m = type.size ();
  for (int i = 0;i < m; ++ i) putchar (type[i]);
  printf ("(");
  for (int i = 0;i < n; ++ i) {
    assert (a != b[i]);
    printf ("%d", b[i]);
    if (i + 1 < n) printf (",");
    else printf (");");
  }
  return ;
}
int binary[5][2];
signed main () {
  for (int i = 0;i < 5; ++ i) binary[i][1] = i + 2;
  for (int i = 0;i < 5; ++ i) {
    binary[i][0] = i + 39;
    solve (binary[i][0], "NOT", {binary[i][1]});
  }
  for (int i = 0;i < 32; ++ i) {
    int cur = i + 7;
    vector < int > st;
    st.clear ();
    st.push_back (1);
    for (int j = 0;j < 5; ++ j) {
      if (i & (1 << j)) st.push_back (binary[j][1]);
      else st.push_back (binary[j][0]);
    }
    solve (cur, "AND", st);
  }
  return 0;
}

(20pts) Task3 选择器

题面详见 statement.pdf 的第 \(\symbfit{6 \sim 7}\) 页。

和 Task2 的原理差不多，只需要把 \(D\) 和 \(A\) 的译码器 AND 起来即可，设得到的是 \(D'\)，那么 \(R\) 就是 \(\text{OR}(D'_0, D'_1, \dots, D'_{31})\)。

#include <bits/stdc++.h>
using namespace std;
inline void solve (int a, string type, vector < int > b) {
  int n = b.size ();
  printf ("%d=", a);
  int m = type.size ();
  for (int i = 0;i < m; ++ i) putchar (type[i]);
  printf ("(");
  for (int i = 0;i < n; ++ i) {
    assert (a != b[i]);
    printf ("%d", b[i]);
    if (i + 1 < n) printf (",");
    else printf (");");
  }
  return ;
}
inline void solve2 (int a, int b) {printf ("%d=%d;", a, b); return ;}
int binary[5][2];
signed main () {
  for (int i = 0;i < 5; ++ i) binary[i][1] = i + 2;
  for (int i = 0;i < 5; ++ i) {
    binary[i][0] = i + 40;
    solve (binary[i][0], "NOT", {binary[i][1]});
  }
  for (int i = 0;i < 32; ++ i) {
    int cur = i + 45;
    vector < int > st;
    st.clear ();
    for (int j = 0;j < 5; ++ j) {
      if (i & (1 << j)) st.push_back (binary[j][1]);
      else st.push_back (binary[j][0]);
    }
    st.push_back (i + 7);
    solve (cur, "AND", st);
  }
  solve2 (77, 45);
  int cur = 77;
  for (int i = 78, j = 46;j <= 76; ++ i, ++ j) solve (i, "OR", {i - 1, j}), cur = i;
  solve (39, "AND", {1, cur});
  return 0;
}

(20pts) Task4 比较器

题面详见 statement.pdf 的第 \(\symbfit{8}\) 页。

若存在 \(i\) 满足 \(0 \leq i \leq 15\)，并且对于所有的 \(i < j \leq 15\) 有 \(A_j = B_j\)，并且有 \(A_i < B_i\)，那么就有 \(A < B\)。

这个主要难度在于代码实现，这里推荐固定的位置，写到注释里面在写代码。

#include <bits/stdc++.h>
using namespace std;
inline void solve (int a, string type, vector < int > b) {
  int n = b.size ();
  printf ("%d=", a);
  int m = type.size ();
  for (int i = 0;i < m; ++ i) putchar (type[i]);
  printf ("(");
  for (int i = 0;i < n; ++ i) {
    assert (a != b[i]);
    printf ("%d", b[i]);
    if (i + 1 < n) printf (",");
    else printf (");");
  }
  return ;
}
inline void solve2 (int a, int b) {printf ("%d=%d;", a, b); return ;}
int cnts;
/*
 34 -  49: compare   := [a_15 < b_15], [a_14 < b_14], ..., [a_0 < b_0];
 50 -  65: prefix    := [a_15 = b_15], [a_14 = b_14], ..., [a_0 = b_0];
 66 -  81: satisfy   := [ok_15], [ok_14], ..., [ok_0];
 33 -  33: answer    := OR (66, 67, ..., 81);
 82 -  97: satisfy   := [a_15 = 0], [a_14 = 0], ..., [a_0 = 0];
 98 - 113: satisfy   := [b_15 = 1], [b_14 = 1], ..., [b_0 = 1];
binary (a < b) => a = 0 & b = 1
extra varibles:
114 := number 0;
115 := number 1;
116 := input 1
*/
inline void create () {cnts ++; return ;}
signed main () {
  cnts = 116;
  solve2 (116, 1);
  solve (114, "XOR", {1, 116});
  solve (115, "NXOR", {1, 116});
  for (int i = 82, j = 16;i <= 97; ++ i, -- j) solve (i, "NXOR", {j, 114});
  for (int i = 98, j = 32;i <= 113; ++ i, -- j) solve2 (i, j);
  for (int i = 34, j = 82, k = 98;i <= 49; ++ i, ++ j, ++ k) solve (i, "AND", {j, k});
  solve (50, "NXOR", {16, 32});
  for (int i = 51, j = 15, k = 31;i <= 65; ++ i, -- j, -- k) {
    create ();
    solve (cnts, "NXOR", {j, k});
    solve (i, "AND", {i - 1, cnts});
  }
  solve2 (66, 34);
  for (int i = 67, j = 35, k = 50;i <= 81; ++ i, ++ j, ++ k) solve (i, "AND", {j, k});
  create (), solve2 (cnts, 66);
  for (int j = 67;j <= 81; ++ j) {
    create (), solve (cnts, "OR", {cnts - 1, j});
  }
  solve2 (33, cnts);
  return 0;
}

(20pts) Task5 加法器

题面详见 statement.pdf 的第 \(\symbfit{9}\) 页。

这个比较简单，只需要从低位到高位手动进位即可。具体见代码。

#include <bits/stdc++.h>
using namespace std;
inline void solve (int a, string type, vector < int > b) {
  int n = b.size ();
  printf ("%d=", a);
  int m = type.size ();
  for (int i = 0;i < m; ++ i) putchar (type[i]);
  printf ("(");
  for (int i = 0;i < n; ++ i) {
    assert (a != b[i]);
    printf ("%d", b[i]);
    if (i + 1 < n) printf (",");
    else printf (");");
  }
  return ;
}
inline void solve2 (int a, int b) {printf ("%d=%d;", a, b); return ;}
int cur, cnts, zero, one;
inline int newnode () {cnts ++; return cnts;}
inline int solve_add (int result, int a, int b, int addbit) {
  solve (result, "XOR", {a, b, addbit});
  int u = newnode ();
  int v0 = newnode (), v1 = newnode (), v2 = newnode ();
  solve (v0, "AND", {a, b});
  solve (v1, "AND", {a, addbit});
  solve (v2, "AND", {b, addbit});
  solve (u, "OR", {v0, v1, v2});
  return u;
}
inline void init () {
  int u = newnode ();
  zero = newnode ();
  one = newnode ();
  solve2 (u, 1);
  solve (zero, "XOR", {1, u});
  solve (one, "NXOR", {1, u});
  return ;
}
signed main () {
  cnts = 48;
  cur = newnode ();
  init ();
  solve2 (cur, zero);
  for (int i = 33, j = 1, k = 17;i <= 48; ++ i, ++ j, ++ k) cur = solve_add (i, j, k, cur);
  return 0;
}

(40pts) Task5ex 超前进位加法器

题面详见 statement.pdf 的第 \(\symbfit{10}\) 页。

这个我还不会。

(40pts) 组合逻辑部分 Task6 ALU

题面详见 statement.pdf 的第 \(\symbfit{11 \sim 12}\) 页。

这个巨难写！

首先是先把 \(8\) 种 \(Y\) 都算出来，然后写一个 \(\text{op}[0 \sim 2]\) 的译码器，算答案的每一位时，把每一种 \(Y\) 都 AND 上译码器的相应位，然后都 OR 起来就是这一位的答案。

• \(A + B, A \wedge B, A \vee B, A \oplus B, \neg A\) 都是平凡的，这里不再赘述。

• \(A - B\) 可以在 \(\bmod 2^{16}\) 的意义下算，显然 \(-B\) 在 \(\bmod 2^{16}\) 意义下等于 \(2^{16} - B = 2^{16} - 1 - B + 1\)，然后发现 \(2^{16} - 1 - B\) 等于 \(\neg B\)，所以 \(-B\) 在 \(\bmod 2^{16}\) 意义下等于 \(\neg B + 1\)。

• \(A\) 左移 \(B \wedge 15\) 位和 \(A\) 右移 \(B \wedge 15\) 位是本质相同的，所以这里只讨论 \(A\) 右移 \(B \wedge 15\) 位。首先我们可以考虑把 \(A\) 右移 \(0 \sim 15\) 位都算出来，然后用类似计算答案的每一位的原理计算出 \(A ≫ (B \wedge 15)\)，建议写注释，难度在于代码实现。

#include <bits/stdc++.h>
using namespace std;
inline void solve (int a, string type, vector < int > b) {
  if (type == "NOT") assert (b.size () == 1);
  int n = b.size ();
  printf ("%d=", a);
  int m = type.size ();
  for (int i = 0;i < m; ++ i) putchar (type[i]);
  printf ("(");
  for (int i = 0;i < n; ++ i) {
    assert (a != b[i]);
    printf ("%d", b[i]);
    if (i + 1 < n) printf (",");
    else printf (");");
  }
  return ;
}
inline void solve2 (int a, int b) {
  printf ("%d=%d;", a, b);
  return ;
}
int cnts;
inline int newnode () {cnts ++; return cnts;}
/*
list 1:
001 ~ 003 := op[0 ~ 2]
004 ~ 019 := a[0 ~ 15]
020 ~ 035 := b[0 ~ 15]
036 ~ 051 := y[0 ~ 15]
052 ~ 059 := op?[0 ~ 7]
060 ~ 075 := c(a + b)[0 ~ 15]
076 ~ 078 := !op[0 ~ 2]
082 ~ 097 := c(a & b)[0 ~ 15]
098 ~ 113 := c(a | b)[0 ~ 15]
114 ~ 129 := c(a ^ b)[0 ~ 15]
130 ~ 145 := c(!a)[0 ~ 15]
146 ~ 161 := (!b)[0 ~ 15]
162 ~ 177 := ((!b) + 1)[0 ~ 15]
178 ~ 193 := (a + (!b) + 1)[0 ~ 15]
194 ~ 197 := (b & 15)[0 ~ 3]
199 ~ 202 := !(b & 15)[0 ~ 3]
215 ~ 230 := choose(b & 15)[0 ~ 15]
231 ~ 246 := (a >> 0)
247 ~ 262 := (a >> 1)
263 ~ 278 := (a >> 2)
279 ~ 294 := (a >> 3)
295 ~ 310 := (a >> 4)
311 ~ 326 := (a >> 5)
327 ~ 342 := (a >> 6)
343 ~ 358 := (a >> 7)
359 ~ 374 := (a >> 8)
375 ~ 390 := (a >> 9)
391 ~ 406 := (a >> 10)
407 ~ 422 := (a >> 11)
423 ~ 438 := (a >> 12)
439 ~ 454 := (a >> 13)
455 ~ 470 := (a >> 14)
471 ~ 486 := (a >> 15)
487 ~ 502 := (a >> (b & 15))
other variables:
079 := number 0
080 := number 1
081 := input 0
*/
namespace rightmove {
  int leftpoint[16]  = {231, 247, 263, 279, 295, 311, 327, 343, 359, 375, 391, 407, 423, 439, 455, 471};
  int rightpoint[16] = {246, 262, 278, 294, 310, 326, 342, 358, 374, 390, 406, 422, 438, 454, 470, 486};
  #define L leftpoint
  #define R rightpoint
  inline void init_b_AND_15 () {
    for (int i = 194, j = 20;i <= 197; ++ i, ++ j) solve2 (i, j);
    for (int i = 199, j = 20;i <= 202; ++ i, ++ j) solve (i, "NOT", {j});
    return ;
  }
  inline void init_choose_b_AND_15 () {
    for (int i = 215, j = 0;i <= 230; ++ i, ++ j) {
      vector < int > st;
      st.clear ();
      for (int k = 0;k < 4; ++ k) {
        if (j & (1 << k)) st.push_back (k + 194);
        else st.push_back (k + 199);
      }
      solve (i, "AND", st);
    }
    return ;
  }
  inline void rightmove_bits (int x) {
    for (int i = L[x], j = x + 4;i <= R[x]; ++ i, ++ j) {
      if (j <= 19) solve2 (i, j);
      else solve2 (i, 79);
    }
    return ;
  }
  inline void init_rightmove_of_a () {
    for (int i = 0;i <= 15; ++ i) rightmove_bits (i);
    return ;
  }
  inline void solveall () {
    init_b_AND_15 ();
    init_choose_b_AND_15 ();
    init_rightmove_of_a ();
    for (int i = 487, cur = 231;i <= 502; ++ i, ++ cur) {
      vector < int > st;
      st.clear ();
      for (int j = 0, k = cur;j <= 15; ++ j, k += 16) {
        int u = newnode ();
        solve (u, "AND", {j + 215, k});
        st.push_back (u);
      }
      int u = newnode (), v = newnode ();
      solve (u, "OR", {st[0], st[1], st[2], st[3], st[4], st[5], st[6], st[7]});
      solve (v, "OR", {st[8], st[9], st[10], st[11], st[12], st[13], st[14], st[15]});
      solve (i, "OR", {u, v});
    }
    return ;
  }
  #undef L
  #undef R
}
/*
list 2:
503 ~ 518 := (a << 0)
519 ~ 534 := (a << 1)
535 ~ 550 := (a << 2)
551 ~ 566 := (a << 3)
567 ~ 582 := (a << 4)
583 ~ 598 := (a << 5)
599 ~ 614 := (a << 6)
615 ~ 630 := (a << 7)
631 ~ 646 := (a << 8)
647 ~ 662 := (a << 9)
663 ~ 678 := (a << 10)
679 ~ 694 := (a << 11)
695 ~ 710 := (a << 12)
711 ~ 726 := (a << 13)
727 ~ 742 := (a << 14)
743 ~ 758 := (a << 15)
759 ~ 774 := (a << (b & 15))
*/
namespace leftmove {
  int leftpoint[16]  = {503, 519, 535, 551, 567, 583, 599, 615, 631, 647, 663, 679, 695, 711, 727, 743};
  int rightpoint[16] = {518, 534, 550, 566, 582, 598, 614, 630, 646, 662, 678, 694, 710, 726, 742, 758};
  #define L leftpoint
  #define R rightpoint
  inline void leftmove_bits (int x) {
    for (int i = L[x], j = 4 - x;i <= R[x]; ++ i, ++ j) {
      if (j >= 4) solve2 (i, j);
      else solve2 (i, 79);
    }
    return ;
  }
  inline void init_leftmove_of_a () {
    for (int i = 0;i <= 15; ++ i) leftmove_bits (i);
    return ;
  }
  inline void solveall () {
    init_leftmove_of_a ();
    for (int i = 759, cur = 503;i <= 774; ++ i, ++ cur) {
      vector < int > st;
      st.clear ();
      for (int j = 0, k = cur;j <= 15; ++ j, k += 16) {
        int u = newnode ();
        solve (u, "AND", {j + 215, k});
        st.push_back (u);
      }
      int u = newnode (), v = newnode ();
      solve (u, "OR", {st[0], st[1], st[2], st[3], st[4], st[5], st[6], st[7]});
      solve (v, "OR", {st[8], st[9], st[10], st[11], st[12], st[13], st[14], st[15]});
      solve (i, "OR", {u, v});
    }
    return ;
  }
  #undef L
  #undef R
}
inline int solve_add (int result, int a, int b, int addbit) {
  solve (result, "XOR", {a, b, addbit});
  int u = newnode ();
  int v0 = newnode (), v1 = newnode (), v2 = newnode ();
  solve (v0, "AND", {a, b});
  solve (v1, "AND", {a, addbit});
  solve (v2, "AND", {b, addbit});
  solve (u, "OR", {v0, v1, v2});
  return u;
}
inline void init () {
  solve2 (81, 1);
  solve (79, "XOR", {1, 81});
  solve (80, "NXOR", {1, 81});
  return ;
}
int binary[3][2], op[8];
signed main () {
//  freopen ("answer.txt", "w", stdout);
  cnts = 774;
  init ();
  binary[0][1] = 1, binary[1][1] = 2, binary[2][1] = 3;
  binary[0][0] = 76, binary[1][0] = 77, binary[2][0] = 78;
  for (int i = 0;i < 8; ++ i) op[i] = i + 52;
  for (int i = 76;i <= 78; ++ i) {
    int id = i - 75;
    solve (i, "NOT", {id});
  }
  for (int i = 146, j = 20;i <= 161; ++ i, ++ j) solve (i, "NOT", {j});
  int cur = newnode ();
  solve2 (cur, 79);
  for (int i = 162, j = 146;i <= 177; ++ i, ++ j) {
    int val = (i == 162) ? (80) : (79);
    cur = solve_add (i, j, val, cur);
  }
  for (int i = 0, j = 52;i <= 7; ++ i, ++ j) {
    vector < int > st;
    st.clear ();
    for (int k = 0;k < 3; ++ k) {
      if (i & (1 << k)) st.push_back (binary[k][1]);
      else st.push_back (binary[k][0]);
    }
    solve (j, "AND", st);
  }
  cur = newnode ();
  solve2 (cur, 79);
  for (int i = 178, j = 4, k = 162;i <= 193; ++ i, ++ j, ++ k) cur = solve_add (i, j, k, cur);
  cur = newnode ();
  solve2 (cur, 79);
  for (int i = 60, j = 4, k = 20;i <= 75; ++ i, ++ j, ++ k) cur = solve_add (i, j, k, cur);
  for (int i = 82, j = 4, k = 20;i <= 97; ++ i, ++ j, ++ k) solve (i, "AND", {j, k});
  for (int i = 98, j = 4, k = 20;i <= 113; ++ i, ++ j, ++ k) solve (i, "OR", {j, k});
  for (int i = 114, j = 4, k = 20;i <= 129; ++ i, ++ j, ++ k) solve (i, "XOR", {j, k});
  for (int i = 130, j = 4;i <= 145; ++ i, ++ j) solve (i, "XOR", {j, 80});
  rightmove :: solveall ();
  leftmove :: solveall ();
  for (int i = 36, v0 = 60, v1 = 178, v2 = 82, v3 = 98, v4 = 114, v5 = 130, v6 = 759, v7 = 487;i <= 51; ++ i, ++ v0, ++ v1, ++ v2, ++ v3, ++ v4, ++ v5, ++ v6, ++ v7) {
    printf ("%d=OR(AND(%d,%d),AND(%d,%d),AND(%d,%d),AND(%d,%d),AND(%d,%d),AND(%d,%d),AND(%d,%d),AND(%d,%d));", i, op[0], v0, op[1], v1, op[2], v2, op[3], v3, op[4], v4, op[5], v5, op[6], v6, op[7], v7);
  }
  return 0;
}