题目132：棋盘多项式
作者: turbo
时间限制: 1s
章节: 深度优先搜索
问题描述
八皇后问题是在棋盘上放皇后，互相不攻击，求方案。变换一下棋子，还可以有八车问题，八马问题，八兵问题，八王问题，注意别念反。在这道题里，棋子换成车，同时棋盘也得换，确切说，是进行一些改造。比如现在有一张n*n的棋盘，我们在一些格子上抠几个洞，这些洞自然不能放棋子了，会漏下去的。另外，一个车本来能攻击和它的同行同列。现在，你想想，在攻击的过程中如果踩到一个洞，便会自取灭亡。故，车的攻击范围止于洞。
此题，给你棋盘的规模n，以及挖洞情况，求放k个车的方案数(k从0到最多可放车数)
输入说明
第一行一个整数n表示棋盘大小
接下来n行，每行n个用空格隔开的数字0或1，0的形状表示洞，1表示没有洞
数据规模和约定
n<=8
输出说明
若干行，第i行表示放i个车的方案数
总结：
不会，代码链接：
https://blog.csdn.net/zhou_hao_ran/article/details/106556648?fromshare=blogdetail&sharetype=blogdetail&sharerId=106556648&sharerefer=PC&sharesource=weixin_55934052&sharefrom=from_link
1. 冲突检测函数 judge()：检查在(x,y)位置放置的车是否与已放置的车冲突：遇到洞（0）就停止检查（攻击被阻挡），遇到已放置的车（10）就返回冲突，检查方向是双向的，但每辆车只检查与自己相关的方向
2. 深度优先搜索函数 dfs()：采用递归方式搜索所有方案，deepx, deepy：当前搜索的起始位置，counter：当前已放置的车数，maxnum：最多可放置的车数
从(1,1)开始深度优先搜索,对每个可放位置：尝试放车，检查是否冲突（考虑洞阻挡），如果不冲突，递归继续，回溯，每次进入递归就记录当前方案
#include<stdio.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;
}
题目134：3000米排名预测
作者: turbo
时间限制: 1s
章节: 深度优先搜索
问题描述
3000米长跑时，围观党们兴高采烈地预测着最后的排名。因为他们来自不同的班，对所有运动员不一定都了解，于是他们分别对自己了解的一些运动员的实力作出了评估，即对部分运动员做了相对排名的预测，并且告诉了可怜留守的班长。因为无聊，于是他们就组团去打Dota去了。比赛结束后他们向班长询问最后的排名，但班长不记得了，只记得他们中哪些人的预测是正确的，哪些人的预测是错误的。他们想知道比赛的排名可能是什么。
输入说明
第一行两个整数n， m，n为运动员数量，m为围观党数量。运动员编号从0到n-1。
接下来m行，每行为一个围观党的相对排名预测。每行第一个数c表示他预测的人数，后面跟着c个0~n-1的不同的数，表示他预测的运动员相对排名，最后还有一个数，0表示这个预测是错误的，1表示是正确的。
数据规模和约定
1<=n<=10, 2<=c<=n, 1<=m<=10，保证数据合法，且答案中排名可能数不超过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
章节: 深度优先搜索
问题描述
有n（2≤n≤20）块芯片，有好有坏，已知好芯片比坏芯片多。 每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时，能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时，会随机给出好或是坏的测试结果（即此结果与被测试芯片实际的好坏无关）。 给出所有芯片的测试结果，问哪些芯片是好芯片。
输入说明
输入数据第一行为一个整数n，表示芯片个数。 第二行到第n+1行为n*n的一张表，每行n个数据。表中的每个数据为0或1，在这n行中的第i行第j列（1≤i, j≤n）的数据表示用第i块芯片测试第j块芯片时得到的测试结果，1表示好，0表示坏，i=j时一律为1（并不表示该芯片对本身的测试结果。芯片不能对本身进行测试）。
输出说明
按从小到大的顺序输出所有好芯片的编号
总结：
对于一个好芯片，在它的测试结果列中（即其他芯片对它的测试结果），1 的数量一定大于 0 的数量（即 1 的数量大于 n / 2）。因为：
所有好芯片测试它都会给出 1（正确结果）。
坏芯片测试它可能随机给 0 或 1。
好芯片数量 > 坏芯片数量，所以即使所有坏芯片都给它 0，1 的数量也超过一半。
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）技术，这个技术融化卷绕的丝材，并将其逐层沉积，冷却固化后形成物体。
单词：
