D题：最长上升子序列
给你一个序列，请你在其中求出一段最长严格上升的部分，它不一定要连续。
#include<iostream> #include<cstring> using namespace std; int f[10000], b[10000]; int lis(int n) { memset(f, 0, sizeof f); int res = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < i; ++j) { if (b[j] < b[i]) { /*在这里填写必要的代码*/ if(f[j] + 1 > f[i]) { f[i] = f[j] + 1; res = max(res, f[i]); } } } res = max(res, f[i]); } return res+1; } int main() { int n; scanf("%d", &n); for (int i = 0; i < n; ++i) { scanf("%d", b + i); } printf("%d\n", lis(n)); return 0; }
E题：全排列
我们要找的是全排列中，排列结果互不相同的个数。比如：aab 的全排列就只有三种，那就是aab,baa,aba。
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N=1e3; char str[N], buf[N];//buffer int vis[N], total, len; void arrange(int num) { if (num == len) { printf("%s\n", buf); total++; return; } for (int i = 0; i < len; ++i) { if (!vis[i]) { int j; for (j = i + 1; j < len; ++j) { if (str[i] == str[j] && vis[j]在这里填写必要的代码) { break; } } if (j == len) { vis[i] = 1; buf[num] = str[i]; arrange(num + 1); vis[i] = 0; } } } } int main() { while (~scanf("%s",str)) { len = strlen(str); sort(str, str + len); total = 0; buf[len] = '\0'; arrange(0); printf("Total %d\n", total); } return 0; }
{思路：填空的地方的意思是，如果i的后面有和s[i] 相等且访问过的字符，则不可以（break），一旦break，j 就不能等于len，就不能继续递归。那么怎么理解这个呢？}
先想一下简化的问题吧，假如输入的字符串不重复，例如abcd，那么就是简单的
dfs了，一个for循环加一个vis判断，如果判断可以，继续递归。当有重复的字符时候就比较麻烦了，比如aab，单纯的用递归会输出重复的。那么怎么加上限定条件呢。
这里，我们让重复的这些字符只顺序输出一遍，这样就不会重复
这是什么意思呢，比如说aabc,我们只允许第一个a访问后再访问第二个a，不允许访问第二个，再第一个。再如，abacda，那三个a只能按顺序访问。
原理是什么呢，用了点高中学的排列组合的知识，先排重复的，例如我们搞abacda这例子, 先排三个a, 就是 aaa,那么剩下的就相当于直接插入到aaa中，那么如果我们aaa如果按多种顺序排，就会产生多种结果，所以只能按顺序访问。
那么又如何用算法实现呢，直接加个if判断就行了，判断i之后的有没有访问过的且相等的。例如，aabc这个例子，我们第一轮选完之后，到了第二个a,然后进入递归，for循环又从0开始，到了第一个a，然后从这个之后去判断有没有访问过的a，结果判断有，违反了顺序，所以结束。
这个题目的关键也就是排除重复的
F题：数独
标准数独是由一个给与了提示数字的 9×9 网格组成，我们只需将其空格填上数字，使得每一行，每一列以及每一个 3×3 宫都没有重复的数字出现。
提醒：两个数字之间要有一个空格，其他地方不要输出多余的符号。
#include<iostream> using namespace std; int mp[90][90]; int hs(int x , int y , int i){ //判断行和列中有没有重复出现的数字 for(int j = 0; j < 9; j++){ if(mp[x][j] == i && y != j)//行 return 0; if(mp[j][y] == i && j != x)//列 return 0; } return 1; } int jiu(int x, int y, int n){//判断九个3X3的矩阵中有没有重复的数字 int xx = x / 3;//判断3X3矩阵左上方元素的位置 int yy = y / 3; for(int i = xx * 3; i < xx * 3 + 3; i++) for(int j = yy * 3; j < yy * 3 + 3; j++){ if(mp[i][j] == n) if(i == x && j == y) continue; else return 0; } return 1; } bool dfs(int cen){ if(cen >= 81) return 1;//搜索完毕 int x = cen / 9;//判断当前位置的行坐标 int y = cen % 9;//列坐标 if(!mp[x][y]){//搜索当前位置的元素 for(int i = 1; i < 10; i++){ mp[x][y] = i;//填数 if(jiu(x,y,i) && hs(x,y,i))//如果行列不冲突 if(dfs(cen + 1))//搜索下一个，下一个也不冲突，返回true，表示填数完成 return true; mp[x][y] = 0;//回溯 } } else return dfs(cen +1);//如果已经填入数字，搜索下一个，这里的返回很有灵性。 return false; } int main(){ for(int i = 0; i < 9; i++){//输入字符，转换数字矩阵 for(int j = 0; j < 9; j++){ char a; cin >> a; if(a <= '9' && a >= '1') mp[i][j] = a - '0'; else mp[i][j] = 0; } } cout << endl; dfs(0);//从第一个开始搜索 for(int i = 0; i < 9; i++){//打印 for(int j = 0; j < 9; j++) cout << mp[i][j] << " "; cout << endl; } return 0; }
解题思路：DFS深度填数检测+回溯法
1，先把有数字的地方设置标记位为true1 2，循环遍历数组中没有标记位true1的地方，也就是需要填数的地方 如果当前为0，即a[i][j]==0，判断当前所在的九宫格，然后从数字1-9依次检测是否在行、列、宫中唯一 满足唯一的话，则吧数字赋值给a[i][j]=l+1;然后继续深度遍历为true1的话就返回true1,否则回溯a[i][j]==0等 不满足满足唯一则判断下一个数字，直到1-9都判断不满足则返回false0,会回溯到上一层 如果当前没有0，说明都已经填满且符合唯一条件，则返回true1;结束
