- 1python爬虫 笔趣阁_笔趣阁 python
- 2AndroidX包冲突导致的错误 Manifest merger failed : Attribute application_manifest merger failed : attribute application@nam
- 3探索ReasonML世界的Apollo神器：reason-apollo-hooks
- 4latex表格示例（背景颜色、行距、线粗细、标题、表格长度）_latex表格横线宽度
- 5Pycharm基础——文件操作（IO）技术_pycharm文件操作
- 6AI量化交易（一）——量化交易简介_ai量化交易是什么
- 7Android基本布局和登录界面的设计_(1)使用各种布局管理器实现登录界面的基本布局效果; (2)使用编辑框设计用户名和
- 8SQL Server维护计划_sql server 维护计划
- 9Hive原理与工作机制
- 10Web 中POST为什么会发送两次请求
DFS——《算法竞赛入门到进阶》（N皇后问题，Shredding Company，Sudoku和Channel Allocation问题详解）_输入格式: 共有若干行,每行一个正整数n≤10,表示棋盘和皇后的数量;如果n=0,表示结
赞
踩
DFS
从初始状态出发，下一步可能有多种状态；选其中一个状态深入，到达新的状态；直到无法继续深入，回退到前一步，转移到其他状态，然后再深入下去。最后，遍历完所有可以到达的状态，并得到最终的解。
题目 N皇后问题（涉及回溯和剪枝）
在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。
你的任务是，对于给定的N，求出有多少种合法的放置方法。
Input
共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。
Output
共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。
Sample Input
1
8
5
0
Sample Output
1
92
10
思路
设左上角是 原点（0，0），已经放好的皇后的坐标是（i，j），不同行不同列不同斜线的新皇后的坐标是（r，c），它们的关系如下：
- 横向，不同行，i != r
- 纵向，不同列，j != c
- 斜对角：从（i，j）向斜对角走a步，那么新坐标（r，c）有4种情况，即左上（i-a，j-a）、右上（i+a，j-a）、左下（i-a，j+a）、右下（i+a，j+a），综合起来就是| i - r |=| j - c |。新皇后的位置不能放在斜线上，需满足| i - r | !=| j - c |。
#include <bits/stdc++.h> using namespace std; int n,tot=0; int col[12]={0}; bool check(int c,int r) { for(int i=0;i<r;i++)//i这里就是行，col[i]也是列 { if(col[i]==c||(abs(col[i]-c)==abs(i-r)))//排除同行同列以及对角线情况 return false; } return true; } void DFS(int r) { if(r==n)//所有都放好了，递归返回 { tot++;//统计合法的棋局个数 return; } for(int c=0;c<n;c++)//每列放 { if (check(c,r)) { col[r]=c;//第r行的c列放 DFS(r+1);//继续放下一行 } } } int main() { int ans[12]={0}; for(n=0;n<=10;n++)//算出所有的答案，先打表，不然会超时 { memset(col,0,sizeof(col));//每次都先清空 tot=0; DFS(0); ans[n]=tot;//打表 } while(cin>>n) { if(n==0) { return 0; } cout<<ans[n]<<endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
题目 Shredding Company
You have just been put in charge of developing a new shredder for the Shredding Company Although a “normal” shredder would just shred sheets of paper into little pieces so that the contents would become unreadable, this new shredder needs to have the following unusual basic characteristics.
1.The shredder takes as input a target number and a sheet of paper with a number written on it.
2.It shreds (or cuts) the sheet into pieces each of which has one or more digits on it.
3.The sum of the numbers written on each piece is the closest possible number to the target number, without going over it.
For example, suppose that the target number is 50, and the sheet of paper has the number 12346. The shredder would cut the sheet into four pieces, where one piece has 1, another has 2, the third has 34, and the fourth has 6. This is because their sum 43 (= 1 + 2 + 34 + 6) is closest to the target number 50 of all possible combinations without going over 50. For example, a combination where the pieces are 1, 23, 4, and 6 is not valid, because the sum of this combination 34 (= 1 + 23 + 4 + 6) is less than the above combination’s 43. The combination of 12, 34, and 6 is not valid either, because the sum 52 (= 12 + 34 + 6) is greater than the target number of 50.
Figure 1. Shredding a sheet of paper having the number 12346 when the target number is 50
There are also three special rules :
1.If the target number is the same as the number on the sheet of paper, then the paper is not cut.
For example, if the target number is 100 and the number on the sheet of paper is also 100, then
the paper is not cut.
2.If it is not possible to make any combination whose sum is less than or equal to the target number, then error is printed on a display. For example, if the target number is 1 and the number on the sheet of paper is 123, it is not possible to make any valid combination, as the combination with the smallest possible sum is 1, 2, 3. The sum for this combination is 6, which is greater than the target number, and thus error is printed.
3.If there is more than one possible combination where the sum is closest to the target number without going over it, then rejected is printed on a display. For example, if the target number is 15, and the number on the sheet of paper is 111, then there are two possible combinations with the highest possible sum of 12: (a) 1 and 11 and (b) 11 and 1; thus rejected is printed. In order to develop such a shredder, you have decided to first make a simple program that would simulate the above characteristics and rules. Given two numbers, where the first is the target number and the second is the number on the sheet of paper to be shredded, you need to figure out how the shredder should “cut up” the second number.
Input
The input consists of several test cases, each on one line, as follows :
tl num1
t2 num2
…
tn numn
0 0
Each test case consists of the following two positive integers, which are separated by one space : (1) the first integer (ti above) is the target number, (2) the second integer (numi above) is the number that is on the paper to be shredded.
Neither integers may have a 0 as the first digit, e.g., 123 is allowed but 0123 is not. You may assume that both integers are at most 6 digits in length. A line consisting of two zeros signals the end of the input.
Output
For each test case in the input, the corresponding output takes one of the following three types :
sum part1 part2 …
rejected
error
In the first type, partj and sum have the following meaning :
1.Each partj is a number on one piece of shredded paper. The order of partj corresponds to the order of the original digits on the sheet of paper.
2.sum is the sum of the numbers after being shredded, i.e., sum = part1 + part2 +…
Each number should be separated by one space.
The message error is printed if it is not possible to make any combination, and rejected if there is
more than one possible combination.
No extra characters including spaces are allowed at the beginning of each line, nor at the end of each line.
Sample Input
50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0
Sample Output
43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected
思路
dfs搜索时，把每种情况都列出来，然后筛出最合适的情况进行判断就好啦。
#include <iostream> #include <cstring> using namespace std; int d[1000000],e[10],v[10];//d[i]数组用来存计算的和i的重复次数，e[i]数组存符合题意的拆分方式所拆分出来的各个数 int n,len,maxn,ss; char m[10];//用来存纸上的数，用char型，可以一位一位看 void dfs(int a,int b,int c)//a代表位数，b代表拆的数的和，c代表拆成了几个数 { int i,y,flag;//flag代表拆的数是否相同 if(a>len-1){ flag=1; for(i=0;i<c;i++) if(e[i]!=v[i]) flag=0; if(maxn<b){//maxn代表得到的和 maxn=b; ss=c; for(i=0;i<c;i++) e[i]=v[i];//v[i]和e[i]表示的意义相同 } if(flag==0) d[b]++; return; } y=0; for(i=a;i<len;i++){ y=y*10+(m[i]-'0');//y在存新的拆的数 if(y+b<=n){ v[c]=y; dfs(i+1,y+b,c+1); }else break; } } int main() { int sum; while(cin>>n>>m) { memset(d,0,sizeof(d)); memset(v,0,sizeof(v)); memset(e,0,sizeof(e)); len=strlen(m); if(m[0]=='0'&&n==0&&len==1) break;//结束 sum=0; for(int i=0;i<len;i++) { sum+=m[i]-'0';//每一位上的数字相加（这肯定是最小的值） } if(sum>n)//最小的值都大了，肯定是error { printf("error\n"); continue; } maxn=0; ss=0; dfs(0,0,0);//从0开始 if(d[maxn]!=1)//有重复的情况出现 printf("rejected"); else { printf("%d",maxn); for(int i=0;i<ss;i++) { printf(" %d",e[i]); } } printf("\n"); } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
题目Sudoku
Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.
Input
The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.
Output
For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.
Sample Input
1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107
Sample Output
143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127
这次思路都在代码里解释清楚啦啦啦
#include <iostream> #include<stdio.h> #include<string.h> using namespace std;//注意，如果开的二维数组是[9][9]会超时 int suduku[9][10]; //存放数独 int d[9][10];//标记是否在第i行出现过 int j[9][10];//标记是否在第i列出现过 int c[9][10];//标记是否在第i个小方块出现过 int a;//是否成立的标记 void shuru(){ int i,t; for(i=0;i<9;i++){ char temp[10];//用char型方便一位一位读取 scanf("%s",temp);//以字符串形式输入 for(t=0;t<9;t++){ suduku[i][t]=temp[t]-'0'; //转化为数字 if(suduku[i][t]){//如果不为0 int k=i/3*3+t/3;//求出此时在第几个小方块里 d[i][suduku[i][t]]=1; j[t][suduku[i][t]]=1; c[k][suduku[i][t]]=1; } } } } void dfs(int x,int y){//遍历每一点 if(x==9){//输出 a=1; int i,j; for(i=0;i<9;i++){ for(j=0;j<9;j++) printf("%d",suduku[i][j]); printf("\n"); } } if(a) return; if(suduku[x][y]){//首先满足不为空的条件 if(y==8) dfs(x+1,0);//每一行遍历结束，继续dfs下一行 else dfs(x,y+1);//否则，继续dfs下一列 } else{ int num; for(num=1;num<=9;num++){ int k=x/3*3+y/3; if(!j[y][num]&&!d[x][num]&&!c[k][num]){//满足没有重复过的条件 suduku[x][y]=num; j[y][num]=1; d[x][num]=1; c[k][num]=1; if(y==8) dfs(x+1,0); else dfs(x,y+1); suduku[x][y]=0;//如果不符合条件，就都恢复为0 j[y][num]=0; d[x][num]=0; c[k][num]=0; } } } } int main(){ int n; scanf("%d",&n); while(n--){ memset(suduku,0,sizeof(suduku)); memset(d,0,sizeof(d)); memset(j,0,sizeof(j)); memset(c,0,sizeof(c)); shuru(); a=0; dfs(0,0); } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
题目Channel Allocation
When a radio station is broadcasting over a very large area, repeaters are used to retransmit the signal so that every receiver has a strong signal. However, the channels used by each repeater must be carefully chosen so that nearby repeaters do not interfere with one another. This condition is satisfied if adjacent repeaters use different channels.
Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required.
Input
The input consists of a number of maps of repeater networks. Each map begins with a line containing the number of repeaters. This is between 1 and 26, and the repeaters are referred to by consecutive upper-case letters of the alphabet starting with A. For example, ten repeaters would have the names A,B,C,…,I and J. A network with zero repeaters indicates the end of input.
Following the number of repeaters is a list of adjacency relationships. Each line has the form:
A:BCDH
which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form
A:
The repeaters are listed in alphabetical order.
Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross.
Output
For each map (except the final one with no repeaters), print a line containing the minumum number of channels needed so that no adjacent channels interfere. The sample output shows the format of this line. Take care that channels is in the singular form when only one channel is required.
Sample Input
2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
4
A:BCD
B:ACD
C:ABD
D:ABC
0
Sample Output
1 channel needed.
3 channels needed.
4 channels needed.
#include<cstdio> #include<cstring> #include<iostream> using namespace std; const int N=27; int n,ans,c[N],g[N][N]; char s[N]; inline void Solve(){ ans=1; for(int i=1;i<=n;i++){ bool vis[27]={0};//记录有没有重复 c[i]=n+1;//c[i]保证一个最大的数，i是第i行 for(int j=1;j<=g[i][0];j++){ int k=g[i][j]; if(c[k]) vis[c[k]]=1; } for(int j=1;j<=26;j++){ if(!vis[j]&&c[i]>j){ c[i]=j; break; } } if(ans<c[i]){ ans=c[i]; if(ans==4) break; } } if(ans==1) printf("%d channel needed.\n",ans); else printf("%d channels needed.\n",ans); } int main(){ while(scanf("%d",&n)==1&&n){ memset(c,0,sizeof c);//每次while前先初始化 memset(g,0,sizeof g); for(int i=1;i<=n;i++){ scanf("%s",s); for(int j=2;s[j];j++){ g[i][++g[i][0]]=s[j]-'A'+1;//每一行“：”后的字母转化成数字存进去,而g[i][0]到最后就存了每一行有的字母个数 } } Solve(); } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
