11D_Beyonder's Blog

传送门 ↬\looparrowright↬ 题目描述 在一个 n×nn \times nn×n 个方格的国际象棋棋盘上，马（骑士）可以攻击的棋盘方格如图所示。 棋盘上某些方格设置了障碍，骑士不得进入。 对于给定的 n×nn \times nn×n 个方格的国际象棋棋盘和障碍标志，计算棋盘上最多可以放置多少个骑士，使得它们彼此互不攻击。 输入格式 第一行有 222 个正整数 nnn 和 mmm ，分别表示棋盘的大小和障碍数。接下来的 mmm 行给出障碍的位置。每行 222 个正整数，表示障碍的方格坐标。 输出格式 将计算出的共存骑士数输出。 输入输出样例 输入 #1 3 2 1 1 3 3 输出 #1 5 说明/提示 对于全部的测试点，保证 1⩽n⩽2001 \leqslant n \leqslant 2001⩽n⩽200，0⩽m<n20 \leqslant m \lt n^20⩽m<n2 。 分析 如下图所示。我们将所有点分成 ××× 和 √√√ 两种点，可以发现同种点所在位置无法互相攻击。将所在行设为横坐标，所在列设为纵坐标，打叉的点坐标之和为偶数，打勾的点 ...

实验目的 帮助理解成组进位产生函数，成组进位传递函数的概念，熟悉 Logisim\text{Logisim}Logisim 平台子电路的概念，能利用前述实验封装好的 444 位先行进位子电路以及 444 位快速加法器子电路构建 161616 位，并能利用相关知识分析对应电路的时间延迟，理解电路并行的概念。 主要任务 利用四位先行进位电路和四位快速加法器构造十六位组间先行进位，组内先行进位快速加法器，并验证其功能是否正常。X,YX,YX,Y 为 161616 位被相加数，CinCinCin 为进位输入，SSS 为和数输出，CoutCoutCout 为进位输出，G,PG,PG,P 为 161616 位成组进位生成函数和成组进位传递函数。 实验原理 将 S,X,YS,X,YS,X,Y 分成四部分 S0∼S3,X0∼X3,Y0∼Y3S_0\sim S_3,X_0\sim X_3,Y_0\sim Y_3S0​∼S3​,X0​∼X3​,Y0​∼Y3​，每部分占四位。用 444 位先行加法器得到 Xi+YiX_i+Y_iXi​+Yi​ 的结果 SiS_iSi​，并输出 444 位成组进位；将 444 ...

实验目的 掌握快速加法器中先行进位的原理，能利用相关知识设计 444 位先行进位电路，并利用 444 位先行进位电路构造 444 位快速加法器，能分析对应电路的时间延迟。 主要任务 利用四位先行进位电路构造四位快速加法器。X,YX,YX,Y 为四位相加数，CinCinCin 为进位输入，SSS 为和数输出，CoutCoutCout 为进位输出，G∗,P∗G^\ast,P^\astG∗,P∗ 为 444 位成组进位生成函数和成组进位传递函数。 实验原理 在 CLA182CLA182CLA182 中，Gi=XiYiG_i=X_iY_iGi​=Xi​Yi​，Pi=Xi⊕YiP_i=X_i\oplus Y_iPi​=Xi​⊕Yi​；输入 Gi,Pi,C0G_i,P_i,C_0Gi​,Pi​,C0​，通过 CLA182CLA182CLA182 电路模块可得到 C1∼C4C_1\sim C_4C1​∼C4​ 和 P∗,G∗P^\ast,G^\astP∗,G∗；进而有 Si=Pi⊕CiS_i=P_i\oplus C_iSi​=Pi​⊕Ci​。 电路图

传送门 ↬\looparrowright↬ 题目描述 有一个 mmm 行 nnn 列的方格图，每个方格中都有一个正整数。现要从方格中取数，使任意两个数所在方格没有公共边，且取出的数的总和最大，请求出最大的和。 输入格式 第一行是两个用空格隔开的整数，分别代表方格图的行数 mmm 和列数 nnn。 第 222 到第 (m+1)(m + 1)(m+1) 行，每行 nnn 个整数，第 (i+1)(i + 1)(i+1) 行的第 jjj 个整数代表方格图第 iii 行第 jjj 列的的方格中的数字 ai,ja_{i, j}ai,j​。 输出格式 输出一行一个整数，代表和最大是多少。 输入输出样例 输入 #1 3 3 1 2 3 3 2 3 2 3 1 输出 #1 11 说明/提示 数据规模与约定 对于 $100\%$ 的数据，保证 1⩽n,m⩽1001 \leqslant n, m \leqslant 1001⩽n,m⩽100，1⩽ai,j⩽1051 \leqslant a_{i, j} \leqslant 10^51⩽ai,j​⩽105。 提示 请注意输入的第一行先读入 mmm ...

传送门 ↬\looparrowright↬ 题目描述 有来自 mmm 个不同单位的代表参加一次国际会议。第 iii 个单位派出了 rir_iri​ 个代表。 会议的餐厅共有 nnn 张餐桌，第 iii 张餐桌可容纳 cic_ici​ 个代表就餐。 为了使代表们充分交流，希望从同一个单位来的代表不在同一个餐桌就餐。请给出一个满足要求的代表就餐方案。 输入格式 输入的第一行是用空格隔开的两个整数，分别代表单位的个数 mmm 和餐桌的个数 nnn。 第二行有 mmm 个用空格隔开的整数，第 iii 个整数代表第 iii 个单位的代表人数 rir_iri​。 第三行有 nnn 个用空格隔开的整数，第 iii 个整数代表第 iii 张餐桌能容纳的人数 cic_ici​。 输出格式 本题存在 Special Judge。 请输出是否存在满足要求的就餐方案，若存在，请给出任意一种可行的方案。 输出的第一行是一个非 000 即 111 的整数，若存在方案则输出 111，否则输出 000。 若存在方案，则对于第 222 到第 (m+1)(m + 1)(m+1) 行，在第 (i+1)(i + 1)(i ...

传送门 ↬\looparrowright↬ 题目描述 假设有 nnn 根柱子，现要按下述规则在这 nnn 根柱子中依次放入编号为 1,2,3⋯1,2,3\cdots1,2,3⋯ 的球。 每次只能在某根柱子的最上面放球。同一根柱子中，任何 222 个相邻球的编号之和为完全平方数。 试设计一个算法，计算出在 nnn 根柱子上最多能放多少个球。例如，在 444 根柱子上最多可放 111111 个球。 对于给定的 nnn，计算在 nnn 根柱子上最多能放多少个球。 输入格式 只有一行一个整数 nnn，代表柱子数。 输出格式 本题存在 Special Judge。 请将 nnn 根柱子上最多能放的球数以及相应的放置方案输出。 输出的第一行是球数。 接下来的 nnn 行，每行若干个整数，代表一根柱子上的球的编号，数字间用单个空格隔开。 输入输出样例 输入 #1 4 输出 #1 11 1 8 2 7 9 3 6 10 4 5 11 说明/提示 对于 $100\%$ 的数据，保证 1⩽n⩽551 \leqslant n \leqslant 551⩽n⩽55。 分析 设当前有 xxx 个球， ...

传送门 ↬\looparrowright↬ 题目描述 给定有向图 G=(V,E)G=(V,E)G=(V,E) 。设 PPP 是 GGG 的一个简单路（顶点不相交）的集合。如果 VVV 中每个定点恰好在 PPP 的一条路上，则称 PPP 是 GGG 的一个路径覆盖。PPP 中路径可以从 VVV 的任何一个定点开始，长度也是任意的，特别地，可以为 000 。GGG 的最小路径覆盖是 GGG 所含路径条数最少的路径覆盖。设计一个有效算法求一个有向无环图 GGG 的最小路径覆盖。 输入格式 第一行有 222 个正整数 nnn 和 mmm 。nnn 是给定有向无环图 GGG 的顶点数，mmm 是 GGG 的边数。接下来的 mmm 行,每行有两个正整数 iii 和 jjj 表示一条有向边 (i,j)(i,j)(i,j)。 输出格式 从第 111 行开始，每行输出一条路径。文件的最后一行是最少路径数。 输入输出样例 输入 #1 11 12 1 2 1 3 1 4 2 5 3 6 4 7 5 8 6 9 7 10 8 11 9 11 10 11 输出 #1 1 4 7 10 11 2 5 8 ...

传送门 ↬\looparrowright↬ 题目描述 给定一个 n×nn \times nn×n 的方形网格，设其左上角为起点◎，坐标 (1,1)(1,1)(1,1)，XXX 轴向右为正，YYY 轴向下为正，每个方格边长为 111，如图所示。 一辆汽车从起点◎出发驶向右下角终点▲，其坐标为 (n,n)(n,n)(n,n)。 在若干个网格交叉点处，设置了油库，可供汽车在行驶途中加油。汽车在行驶过程中应遵守如下规则。汽车只能沿网格边行驶，装满油后能行驶 kkk 条网格边。出发时汽车已装满油，在起点与终点处不设油库。 汽车经过一条网格边时，若其 xxx 坐标或 yyy 坐标减小，则应付费用 bbb，否则免付费用。 汽车在行驶过程中遇油库则应加满油并付加油费用 AAA。 在需要时可在网格点处增设油库，并付增设油库费用 ccc（不含加油费用 aaa ）。 n,k,a,b,cn,k,a,b,cn,k,a,b,c 均为正整数， 且满足约束: 2⩽n⩽1002\leqslant n\leqslant 1002⩽n⩽100，2⩽k⩽102 \leqslant k \leqslant 102⩽k⩽1 ...

传送门 ↬\looparrowright↬ 题目描述 问题描述 假设一个试题库中有 nnn 道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取 mmm 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 编程任务 对于给定的组卷要求，计算满足要求的组卷方案。 输入格式 第一行有两个正整数 kkk 和 nnn。kkk 表示题库中试题类型总数，nnn 表示题库中试题总数。 第二行有 kkk 个正整数，第 iii 个正整数表示要选出的类型 iii 的题数。这 kkk 个数相加就是要选出的总题数 mmm。 接下来的 nnn 行给出了题库中每个试题的类型信息。每行的第一个正整数 ppp 表明该题可以属于 ppp 类，接着的 ppp 个数是该题所属的类型号。 输出格式 输出共 kkk 行，第 iii 行输出 i: 后接类型 iii 的题号。 如果有多个满足要求的方案，只要输出一个方案。 如果问题无解，则输出No Solution!。 输入输出样例 输入 #1 3 15 3 3 4 2 1 2 1 3 1 3 1 3 1 3 3 1 2 3 ...

传送门 ↬\looparrowright↬ 题目描述 有 nnn 件工作要分配给 nnn 个人做。第 iii 个人做第 jjj 件工作产生的效益为 cijc_{ij}cij​。试设计一个将 nnn 件工作分配给 nnn 个人做的分配方案，使产生的总效益最大。 输入格式 文件的第 111 行有 111 个正整数 nnn，表示有 nnn 件工作要分配给 nnn 个人做。 接下来的 nnn 行中，每行有 nnn 个整数 cijc_{ij}cij​，表示第 iii 个人做第 jjj 件工作产生的效益为cijc_{ij}cij​。 输出格式 两行分别输出最小总效益和最大总效益。 输入输出样例 输入 #1 5 2 2 2 1 2 2 3 1 2 4 2 0 1 1 1 2 3 4 3 3 3 2 1 2 1 输出 #1 5 14 说明/提示 1⩽n⩽1001 \leqslant n \leqslant 1001⩽n⩽100。 一个人只能修一个工件。 分析 将全体工人看作点集 S1\mathbb{S_1}S1​，将所有工作看作点集 S2\mathbb{S_2}S2​；两个集合内部的点各自 ...