小Y得到了一堆宝石，但是其中有一些宝石是假的没有价值，显然小Y并不想要这些假的宝石，小Y被告诉了一个鉴别真假宝石的方法。将这些宝石排成一行，按照从 1∼n标上标号并得出其真实度，如果第 i 个宝石的真实度等于标号大于 i 的三个宝石的真实度乘积(可以使用标号相同的三个宝石)，这个宝石被认为是真的，你能帮小Y找出所有真的宝石的数量吗。
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define maxnum 500005 #define inf 1000000007 usingnamespace std; constdouble PI = acos(-1.0);
intmain() { int n; cin >> n; int num[n + 100]; memset(num, 0, sizeof(num)); unordered_map<ll, bool> mp; for (int i = 0; i < n; i++) { cin >> num[i]; } //需要倒序，并且一边打表一边判断 //正序打表，储存下来不能判断是不是该宝石后的，所以必须倒序 int ans = 0; for (int i = n - 1; i >= 0; i--) //倒序，i作为判断的宝石 { for (int j = n - 1; j > i; j--) //倒序更新，并且随着i的不断减小，只更新没有出现过的乘积 { mp[num[i + 1] * num[j]] = 1; } for (int j = n - 1; j > i; j--) //关于第i个宝石，针对其后面的所有宝石，进行试除，如果可除通，并且被标记过，说明成功的 { if (num[i] == 0 && mp[0] == 1)//对于1 1 0 0 这种情况，需要特判，因为除数和被除数都为0 { ans++; break; } if (num[j] != 0 && num[i] % num[j] == 0 && mp[num[i] / num[j]] == 1)//常规判断 { ans++; break; } } } cout << ans << endl; return0; }
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define maxnum 500005 #define inf 1000000007 usingnamespace std; constdouble PI = acos(-1.0); intmain() { int t=0; int n,m; while(cin>>n>>m){ if (t!=0) { cout<<"\n**********************************\n"<<endl; } ++t; int num[11][11][11][11];//四维数组，存储 memset(num,0,sizeof(num)); for (int k = 0; k < m; k++) { char opt; int i,j; cin>>opt>>i>>j; if (opt=='H') { num[i][j][i][j+1]=1;//两双向链接 num[i][j+1][i][j]=1; }else{ num[j][i][j+1][i]=1; num[j+1][i][j][i]=1; } } //枚举i j int cnt[10]={0}; for (int i = 1; i <= n; i++) { for(int j = 1;j<= n;j++){ //对于点i，j根据步长k枚举
for(int k=1;k<=min(n-i,n-j);k++){//k为步长 bool flag=true; for (int l = 0; l < k; l++)//l为到i，j+k之间的点,一步一步判断 { if( num[i][j+l][i][j+l+1]==1 && num[i+k][j+l][i+k][j+l+1]==1 && num[i+l][j][i+l+1][j]==1 && num[i+l][j+k][i+l+1][j+k]==1) {//判断四个点的步长 continue;//步长内再走一步 } } //走完k步以后判断走不走得通 if (flag==false) { continue;//走不通,下一个步长 } if (flag==true) { cnt[k]++;//走的通,正方形大小为k的++ } } } } cout<<"Problem #"<<t<<endl<<endl; bool f=false; for (int i = 1; i < 10 ; i++) { if(cnt[i]!=0){ cout<<cnt[i]<<" "<<"square (s) of size "<<i<<endl; f=true; } } if(f==false){ cout<<"No completed squares can be found."<<endl; } } // printf("Time used = %.2lf\n", (double)clock() / CLOCKS_PER_SEC); return0; }
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define maxnum 500005 #define inf 1000000007 usingnamespace std; constdouble PI = acos(-1.0); constint N=25; int n; vector<int> v[N]; //用vector来模拟 //每次要先找到 //定理： // onto清空b上的 // move清空a上的 // 两种情况都需要把x上的放到y上 //注意： // 都设置为全局变量，方便操作 voidprint() { for (int i = 0; i < n; i++) { cout << i << ":"; for (int j = 0; j < v[i].size(); j++) cout << " " << v[i][j]; cout << endl; } } voidfind(int key,int &x,int &y){ for(int i=0;i<n;i++){ for (int j = 0; j < v[i].size(); j++){ if(v[i][j]==key){ return; } } } } //clear：把v[ax][ay]-v[ax][max]的清空，归位 voidclear(int ax,int ay){ for (int j = ay+1; j < v[ax].size(); j++) { int b = v[ax][j]; v[b].push_back(b); } v[ax].resize(ay + 1); } //把v[ax]上从ay到最大元素全部搬到v[bx]上，然后再重新resize v[ax]的大小，不需要做过多的删除操作 voidrenew(int ax,int ay,int bx){ for (int i = ay; i < v[ax].size(); i++) { v[bx].push_back(v[ax][i]); } v[ax].resize(ay); }
intmain() { cin>>n; for (int i = 0; i < n; i++) { v[i].push_back(i); } //初始化 string op; while (cin>>op && op!="quit") { string way; int a,b; cin>>a>>way>>b; //先找到点的位置，再进行下一步操作 //定义两个坐标来储存变量，让外部函数调用他们的引用 int ax,bx,ay,by; find(a,ax,ay);//操作，让ax，ay变成a所在的位置 find(b,bx,by);//操作，让bx，by变成b所在的位置 if (ax==bx) { continue; } if (op=="move") { clear(ax,ay); } if (way=="onto") { clear(bx,by); } renew(ax,ay,bx); } print(); return0; }
7.组合数问题
题目标签
搜索
题目描述
给定n个数，从中取r个数进行组合，求解法和个数
题目解析
n个数，取r个进行组合。也就是dfs r层，每层都要取数，数的范围是前一层取的数+1 ~ n。
为了保证组合没有重复的，所以每层取得数都是前一层数的+1.同时还能保证是按照升序进行输出。
通过代码
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define maxnum 500005 #define inf 1000000007 usingnamespace std; constdouble PI = acos(-1.0); int n;int r; int all; int a[22]={0}; voiddfs(int begin){ if (begin==r+1)//终点 { for (int i = 1; i <= r; i++) { printf("%3d",a[i]); } cout<<endl; return; } for (int i = a[begin-1]+1; i <= n; i++)//i是必须是递增的 { a[begin]=i; dfs(begin+1);//递增后的下一步搜索 } } intmain() { cin>>n>>r; dfs(1); return0; }
8.数的全排列
题目标签
搜索
题目描述
给定n个数1-n，求全排列
题目解析
除了next_permutation以外，还有几种使用深度优先搜素的算法来进行求解
首先将1-n全部存入数组，存进去之后，用dfs来进行数的交换，交换的顺序是从最后交换到第一个。
通过代码
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define maxnum 500005 #define inf 1000000007 usingnamespace std; constdouble PI = acos(-1.0); int a[10] = {0}; int num=0; //定义一个数组，让搜索时可以访问到那些元素 //每次让他们交换一个位置，然后该交换位置之后的继续向下搜索交换位置的 //每次交换位置的是begin和i交换，i++，也就是从begin开始，到begin以后的要进行交换 voidPerm(int begin, int end) { //先写出出口 if (begin == end) { for (int i = 0; i < end; i++)//必须是<=end { printf("%5d", a[i]); } num++; printf("\n"); } for (int i = begin; i < end; i++)//必须是<=end { swap(a[i], a[begin]); Perm(begin + 1, end); swap(a[i], a[begin]); } }
intmain() { int n; scanf("%d",&n); for (int i = 0; i < n; i++) { a[i] = i + 1; } //初始化完成 Perm(0, n); return0; }
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define maxnum 500005 #define inf 1000000007 usingnamespace std; int tree = 0; constdouble PI = acos(-1.0); int n; int a[13][13] = {0}; int ans[13] = {0}; int num = 0; voiddfs(int k) { if (k == n) //终点 { if (num < 3) { for (int i = 0; i < n; i++) { printf("%d%s", ans[i], i == n - 1 ? "\n" : " "); } } num++; return; }
//每个深度(行)，枚举列放棋子，i为列，k为行 for (int i = 0; i < n; i++) { if (a[k][i] < 1) //没被标记可以放 { tree++; ans[k] = i + 1; a[k][i]++; //标记不能放置的棋子,同行同列，斜边 //同行可以其实不标记，因为是一行一行下去的 for (int j = k; j < n; j++) //同一列 { a[j][i]++; } for (int j = k + 1, xie = 1; j < n; j++) //向下的斜边 { if (i + xie < n) a[j][i + xie]++; if (i - xie >= 0) a[j][i - xie]++; xie++; } dfs(k + 1);
//如果用新数组递归下去，回溯不用删除 for (int j = k; j < n; j++) //同一列 { a[j][i]--; } for (int j = k + 1, xie = 1; j < n; j++) //向下的斜边 { if (i + xie < n) a[j][i + xie]--; if (i - xie >= 0) a[j][i - xie]--; xie++; } a[k][i]--; } } } intmain() { cin >> n; dfs(0); cout << num << endl; return0; }
一维数组优化版本
#include<bits/stdc++.h> #define ll long long #define ull unsigned long long #define maxnum 500005 #define inf 1000000007 usingnamespace std; int tree = 0; constdouble PI = acos(-1.0); int n; int a[13][13] = {0}; int ans[13] = {0}; int num = 0; //优化方法： //主要是对判断是否被标记做优化 //引理：处于同一主对角线上的，纵坐标值-横坐标值相等。处于同一副对角线上的，纵坐标值+横坐标值值相等。 //我们也不需要使用二维数组来储存，因为a[i]的i就是行号，a[i]的值就是列号。 voiddfs(int k) { if (k == n) //终点 { if (num < 3) { for (int i = 0; i < n; i++) { printf("%d%s", ans[i], i == n - 1 ? "\n" : " "); } } num++; return; }
for (int i = 0; i < n; i++)//针对每一行有n种不同的列可以摆放棋子 { bool ok = true; ans[k] = i + 1;//下标从0开始，但输出的是从1开始，i+1。不会影响引理的判断，因为所有的列号都被+1了 for (int j = 0; j < k; j++) { if (ans[k] == ans[j] || k - ans[k] == j - ans[j] || k + ans[k] == j + ans[j]) //引理 { ok = false;//如果位于同一列/斜边---不能进行下一步dfs break; } } if (ok == true) dfs(k + 1); } } intmain() { cin >> n; dfs(0); cout << num << endl; return0; }
