2025年清华大学计算机保研复试机试真题

2025年清华大学计算机保研复试上机真题

历年清华大学计算机保研复试上机真题

历年清华大学计算机保研复试机试真题

更多学校题目开源地址：https://gitcode.com/verticallimit1/noobdream

N 诺 DreamJudge 题库：输入 “学校名称” 即可筛选该校历年机试真题，题目均在考纲范围内，按难度自动排序。还可搭配《计算机考研机试攻略》刷题，书中题目可通过题号直接在题库中查找。

井字井字棋

题目描述

Time Limit: 1000 ms
Memory Limit: 256 mb

井字井字棋的规则如下：

- 棋盘由  的大格组成，每个大格中的所有小格构成一个井字棋，而整个棋盘中的所有大格也构成一个井字棋。从整体来看棋盘如下：

- 对每个大格进行编号，第  行第  列的大格编号为 ；同理，对每个大格内的小格也可以如此编号。我们用  指代棋盘上编号为  的大格内编号为  的小格。
- 该游戏一定能决出胜负，且在胜负决出前双方轮流落子。
- 每个大格内的规则和井字棋一样，即若一方率先有三个子连成一线（横、竖、斜均可），则占领该大格。
- 整个棋盘的规则也和井字棋一样，即若一方率先有三个子连成一线（横、竖、斜均可），则获胜。
- 不能在有棋子的小格中落子；若大格被某一方占领了，则双方均不能再在大格内的任意小格落子。
- 对于落子的限制：
    - 第一步不能下在 ，即最中心的小格。
    - 若该步不为第一步，设上一步对手下在了 ：
      - 若编号为  的大格未被占领，则当前必须下在编号为  的大格里。
      - 若编号为  的大格被占领，则当前可下在棋盘上任意一个可以下的位置。
- 若直至无地方可以落子还未决出胜负，则通过如下方法决出胜负：先比拼占领的大格数，多者获胜；若占领的大格数一样，则比拼未占领的大格中占领的小格数，多者获胜。可以证明，按照此规则一定能决出胜负。

现在，给你一个棋谱，请你帮忙判断该棋谱是否合法、若合法是否决出了胜负、若决出了胜负是谁赢了。

输入输出格式

输入描述:

从标准输入读入数据。 第一行一个整数 ，表示棋谱长度。 接下来 行，第 行输入两个整数 ，表示第 回合落子的人下在了位置 。 数据规模与约定 - 子任务 1（30 分）：棋谱不合法。 - 子任务 2（30 分）：棋谱合法但未决出胜负。 - 子任务 3（40 分）：无特殊限制。 对于 的数据，。

输出描述:

输出到标准输出。 棋谱不合法，当且仅当存在 ，，使得下第 步前每个人都下在能下的位置且没有决出胜负，而第 步下在了不能下的位置。此时输出两行，第一行为 `illegal`，第二行为 。 否则，棋谱合法。在此情况下，棋谱决出了胜负，当且仅当存在 ，，使得下第 步前未决出胜负而下第 步后决出了胜负。此时输出两行，第一行为 `first` 或 `second`，分别表示是先手获胜还是后手获胜，第二行为 。 否则，棋谱没有决出胜负，此时输出一行 `to be continued`。

输入输出样例

输入样例#:

2
5 5
5 4

输出样例#:

illegal
1

1. #include<bits/stdc++.h>
2. using namespace std;
3. int n;
4. bool ok=0;
5. int a[82],b[82],cnt[10],Board[10];
6. int board[10][10],num[8][3]={1,2,3,4,5,6,7,8,9,1,4,7,2,5,8,3,6,9,1,5,9,3,5,7};
7. inline void print_illegal(int x)
8. {
9. printf("illegal\n%d",x),ok=1;
10. }
11. inline void print_win(int x,int y)
12. {
13. puts(x? "first":"second"),printf("%d",y),ok=1;
14. }
15. inline bool check(int x)
16. {
17. for(int i=0;i<8;++i)if(board[a[x]][num[i][0]]==(x&1) && board[a[x]][num[i][1]]==(x&1) && board[a[x]][num[i][2]]==(x&1))
18. {
19. for(int j=1;j<=9;++j)board[a[x]][j]=(x&1);
20. return cnt[a[x]]=9,Board[a[x]]=(x&1),1;
21. }
22. return 0;
23. }
24. inline bool check1(int x)
25. {
26. for(int i=0;i<8;++i)if(Board[num[i][0]]==(x&1) && Board[num[i][1]]==(x&1) && Board[num[i][2]]==(x&1))return 1;
27. return 0;
28. }
29. inline bool check2()
30. {
31. for(int i=1;i<=9;++i)if(cnt[i]<9)return 1;
32. int x=0;
33. for(int i=1;i<=9;++i)
34. {
35. if(Board[i]==1)++x;
36. if(!Board[i])--x;
37. }
38. if(x>0)return print_win(1,n),0;
39. if(x<0)return print_win(0,n),0;
40. for(int i=1;i<=9;++i)for(int j=1;j<=9;++j)
41. {
42. if(board[i][j]==1)++x;
43. if(!board[i][j])--x;
44. }
45. return print_win(x>0,n),0;
46. }
47. inline void solve(int x)
48. {
49. if(ok)return ;
50. if(x==1 && a[x]==5 && b[x]==5)return print_illegal(1);
51. if(x>1 && (~board[a[x]][b[x]] || (cnt[b[x-1]]<9 && a[x]!=b[x-1])))return print_illegal(x);
52. board[a[x]][b[x]]=(x&1),++cnt[a[x]];
53. if(!check(x))return ;
54. if(check1(x))return print_win(x&1,x);
55. }
56. int main()
57. {
58. memset(board,-1,sizeof(board)),memset(Board,-1,sizeof(Board)),scanf("%d",&n);
59. for(int i=1;i<=n;++i)scanf("%d%d",&a[i],&b[i]),solve(i);
60. if(!ok && check2())puts("to be continued");
61. return 0;
62. }