题目132棋盘多项式作者: turbo时间限制: 1s章节: 深度优先搜索问题描述八皇后问题是在棋盘上放皇后互相不攻击求方案。变换一下棋子还可以有八车问题八马问题八兵问题八王问题注意别念反。在这道题里棋子换成车同时棋盘也得换确切说是进行一些改造。比如现在有一张n*n的棋盘我们在一些格子上抠几个洞这些洞自然不能放棋子了会漏下去的。另外一个车本来能攻击和它的同行同列。现在你想想在攻击的过程中如果踩到一个洞便会自取灭亡。故车的攻击范围止于洞。此题给你棋盘的规模n以及挖洞情况求放k个车的方案数(k从0到最多可放车数)输入说明第一行一个整数n表示棋盘大小接下来n行每行n个用空格隔开的数字0或10的形状表示洞1表示没有洞数据规模和约定n8输出说明若干行第i行表示放i个车的方案数总结不会代码链接https://blog.csdn.net/zhou_hao_ran/article/details/106556648?fromshareblogdetailsharetypeblogdetailsharerId106556648sharereferPCsharesourceweixin_55934052sharefromfrom_link1. 冲突检测函数 judge()检查在(x,y)位置放置的车是否与已放置的车冲突遇到洞0就停止检查攻击被阻挡遇到已放置的车10就返回冲突检查方向是双向的但每辆车只检查与自己相关的方向2. 深度优先搜索函数 dfs()采用递归方式搜索所有方案deepx, deepy当前搜索的起始位置counter当前已放置的车数maxnum最多可放置的车数从(1,1)开始深度优先搜索,对每个可放位置尝试放车检查是否冲突考虑洞阻挡如果不冲突递归继续回溯每次进入递归就记录当前方案#includestdio.h//Author:summershell int a[50][50], n, ans[100]; int judge(int x, int y){ for(int i x - 1; i 0 a[i][y] ! 0; --i)//向上检查同一列 if(a[x][y] a[i][y]) return 1;//冲突 for(int i x 1; i n a[i][y] ! 0; i)//向下检查同一列 if(a[x][y] a[i][y]) return 1;//冲突 for(int i y - 1; i 0 a[x][i] ! 0; --i)//向左检查同一行 if(a[x][y] a[x][i]) return 1;//冲突 for(int i y 1; i n a[x][i] ! 0; i)//向右检查同一行 if(a[x][y] a[x][i]) return 1;//冲突 return 0; } void dfs(int deepx,int deepy,int counter,int maxnum){//counter是放置了几个maxnum是最多几个车 if(counter n * n)//能进到本次循环的都是可以放置的 ans[counter]; for(int i deepx; i n; i){ for(int j (i deepx ? deepy : 1); j n; j)//保证从刚进入本层dfs时候从当前坐标往下判断。然后下一层时候j需要从1开始了。 if(a[i][j] 1){//可放位置 a[i][j] 10;//放置车标记为10 if(judge(i, j) 0)//不冲突 dfs(i, j, counter 1, maxnum);//递归继续 a[i][j]1;//回溯撤销放置 } } } int main(){//改进dfs过程的结果可以保存起来这样避免了许多重复的计算。用ans[100] scanf(%d, n); for(int i 1; i n; i) for(int j 1; j n; j) scanf(%d, a[i][j]); for(int i 0; i 100; i) ans[i] 0; dfs(1, 1, 0, n * n);//10代表车 for(int i 1; i n * n; i) if(ans[i]) printf(%d\n, ans[i]); return 0; }题目1343000米排名预测作者: turbo时间限制: 1s章节: 深度优先搜索问题描述3000米长跑时围观党们兴高采烈地预测着最后的排名。因为他们来自不同的班对所有运动员不一定都了解于是他们分别对自己了解的一些运动员的实力作出了评估即对部分运动员做了相对排名的预测并且告诉了可怜留守的班长。因为无聊于是他们就组团去打Dota去了。比赛结束后他们向班长询问最后的排名但班长不记得了只记得他们中哪些人的预测是正确的哪些人的预测是错误的。他们想知道比赛的排名可能是什么。输入说明第一行两个整数n mn为运动员数量m为围观党数量。运动员编号从0到n-1。接下来m行每行为一个围观党的相对排名预测。每行第一个数c表示他预测的人数后面跟着c个0~n-1的不同的数表示他预测的运动员相对排名最后还有一个数0表示这个预测是错误的1表示是正确的。数据规模和约定1n10, 2cn, 1m10保证数据合法且答案中排名可能数不超过20000。对于一个排名序列一个预测是正确的当且仅当预测的排名的相对顺序是排名序列的一个子序列。一个预测是错误的当且仅当这个预测不正确。输出说明第一行一个数k为有多少种排名的可能。下面k行每行一个0~n-1的排列为某一个可能的排名每个数字后有一个空格即行尾也有一个空格。所有排名按字典序依次输出。总结先使用 dfs() 生成所有排列随后验证单个排列​对每个排列检查 m 个预测对每个预测判断预测序列是否是当前排名的子序列如果是子序列且预测标志1则排列符合这个预测如果不是子序列且预测标志0则排列也符合这个预测。如果该排列符合 m 个预测这个排列为一个可能的排名ans[ans_count] 记录该排列ans_count#include stdio.h #include stdlib.h int n, m; int predictions[10][10]; //存储每个预测的运动员序列 int pred_len[10]; //每个预测的长度 int pred_correct[10]; //每个预测的正确标志 (0/1) int result[10]; //当前生成的排列 int visited[10] {0}; //DFS访问标记 int ans[20000][10]; //存储所有有效排名 int ans_count 0; //有效排名数量 //检查预测序列是否是最终排名的子序列 int is_subsequence(int pred_idx, int rank[]){ int *seq predictions[pred_idx]; int len pred_len[pred_idx]; int i 0, j 0; while(i len j n){ if(seq[i] rank[j]){ i; } j; } return i len; //匹配完整个预测序列 } //检查当前排名是否满足所有预测 int check_rank(int rank[]){ for(int i 0; i m; i){ int is_subseq is_subsequence(i, rank); if(is_subseq ! pred_correct[i]){ return 0; //预测结果与标志不符 } } return 1; //所有预测都符合 } //DFS生成所有排列 void dfs(int depth){ if(depth n){ if(check_rank(result)){//满足所有预测 for(int i 0; i n; i){ ans[ans_count][i] result[i]; } ans_count; } return; } for(int i 0; i n; i){ if(!visited[i]){ visited[i] 1; result[depth] i; dfs(depth 1); visited[i] 0; } } } int main(){ scanf(%d %d, n, m); for(int i 0; i m; i){ int c; scanf(%d, c); pred_len[i] c; for(int j 0; j c; j) scanf(%d, predictions[i][j]); scanf(%d, pred_correct[i]); } dfs(0);//生成所有排列并验证 printf(%d\n, ans_count); for(int i 0; i ans_count; i){ for(int j 0; j n; j) printf(%d , ans[i][j]); printf(\n); } return 0; }题目135芯片测试作者: Turbo时间限制: 1s章节: 深度优先搜索问题描述有n2≤n≤20块芯片有好有坏已知好芯片比坏芯片多。每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时会随机给出好或是坏的测试结果即此结果与被测试芯片实际的好坏无关。给出所有芯片的测试结果问哪些芯片是好芯片。输入说明输入数据第一行为一个整数n表示芯片个数。第二行到第n1行为n*n的一张表每行n个数据。表中的每个数据为0或1在这n行中的第i行第j列1≤i, j≤n的数据表示用第i块芯片测试第j块芯片时得到的测试结果1表示好0表示坏ij时一律为1并不表示该芯片对本身的测试结果。芯片不能对本身进行测试。输出说明按从小到大的顺序输出所有好芯片的编号总结对于一个好芯片在它的测试结果列中即其他芯片对它的测试结果1 的数量一定大于 0 的数量即 1 的数量大于 n / 2。因为所有好芯片测试它都会给出 1正确结果。坏芯片测试它可能随机给 0 或 1。好芯片数量 坏芯片数量所以即使所有坏芯片都给它 01 的数量也超过一半。1. func() 判断一个芯片是好是坏对该芯片的测试结果列进行遍历若 1 的数量大于 n / 2则该芯片是好芯片对 n 个芯片遍历它们的测试结果列好芯片则输出2. 在调用函数传递数组时只需要写数组名 arr不需要加下标// 一维数组void func(int arr[]) 或 void func(int *arr)调用func(arr); // 不是 func(arr[])// 二维数组需要指定列数void func(int arr[][n]) 或 void func(int (*arr)[n])调用func(arr); // 不是 func(arr[n][n])#include stdio.h int n; int func(int i, int arr[][n]){ int count 0; for(int j 0; j n; j){ if(arr[j][i] 1) count; } if(count n / 2) return 1; return 0; } int main(){ scanf(%d, n); int arr[n][n]; for(int i 0; i n; i){ for(int j 0; j n; j) scanf(%d, arr[i][j]); } for(int i 0; i n; i){ if(func(i, arr)) printf(%d , i 1); } return 0; }翻译调制解调器代表调制器-解调器是连接电脑和电话线并且允许信息传输给另一个电脑或者从另一个电脑接收信息的设备。每一个发送和接收信息的电脑必须连接到调制解调器。从一台计算机发送的信号通过调制解调器被转化为音频信号音频信号随后被电话线运输到接收的调制解调器调制解调器将信息转化为接收的电脑可以理解的信息。III.输出硬件仅仅展示文本和图像的电脑展示设备被分类为输出设备。然而触控屏可以同时归类为输入和输出设备因为他们接收输入也展示输出。独立的展示设备有时候被称为显示屏在台式电脑中很受欢迎。笔记本电脑、平板电脑和手持设备的展示设备内置于系统单元中但是这些设备也接受外部的显示屏。用于展示设备的两个常见的技术LCD和LED。LCD液晶显示屏技术通过让光线穿过一层液晶单元进行滤光来产生图像。LCD屏的优点包括显示清晰低辐射排放便携性和紧凑性。透过液晶显示器LCD进行滤光的光源被称为背光。很多现代屏幕采用LED发光二极管技术进行背光并以LED显示屏的名义在市场上销售。现在销售最好的多功能打印机用喷墨或者激光技术也可以担任扫描仪复印机和传真机。喷墨打印机有一个喷嘴状的打印头在纸上喷洒墨水形成文字和图像。彩色喷墨打印机的打印头由一系列喷嘴组成每一个喷嘴都有它自己的墨盒。激光打印机用相同的技术作为照片复印者在感光鼓上用光点绘制图像。带静电的墨水被施加到感光鼓上随后转印到纸张上。一个基本的激光打印机只能产生黑白打印物。彩色激光打印机已上市但是他们比基本的黑白打印机要稍贵。将墨水沉积在纸张上的技术是3D打印的基础3D打印沉积塑料树脂或金属层逐层构建成一个三维物体。3D打印在技术上被称为增材制造。存在多种增材制造技术但是很多消费级的3D打印机使用被称为熔融沉积成型FDM技术这个技术融化卷绕的丝材并将其逐层沉积冷却固化后形成物体。单词​​​​​​​