洛谷 P3355 骑士共存问题
传送门 ↬\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 。
分析
如下图所示。我们将所有点分成 ××× 和 √√√ 两种点,可以发现同种点所在位置无法互相攻击。将所在行设为横坐标,所在列设为纵坐标,打叉的点坐标之和为偶数,打勾的点 ...
16位快速加法器设计实验
实验目的
帮助理解成组进位产生函数,成组进位传递函数的概念,熟悉 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 ...
4位快速加法器设计实验
实验目的
掌握快速加法器中先行进位的原理,能利用相关知识设计 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=XiYi,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。
电路图
洛谷 P2774 方格取数问题
传送门 ↬\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 ...
洛谷 P3254 圆桌问题
传送门 ↬\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 ...
洛谷 P2765 魔术球问题
传送门 ↬\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 个球, ...
洛谷 P2764 最小路径覆盖问题
传送门 ↬\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 ...
洛谷 P4009 汽车加油行驶问题
传送门 ↬\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 ...
洛谷 P2763 试题库问题
传送门 ↬\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
...
洛谷 P4014 分配问题
传送门 ↬\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;两个集合内部的点各自 ...