做二手手机交易网站,vue做的pc线上网站,零壹网站建设,模板式网站建设寒假刷题
92. 递归实现指数型枚举 解法1递归
使用递归对每一个坑位进行选择#xff0c;每个坑位有两种选择#xff0c;填或者不填#xff0c;使用st数组来记录每个坑位的状态#xff0c;u来记录已经有多少坑位有了选择。 每个坑位有2钟选择#xff0c;n个坑位的复杂度就…寒假刷题
92. 递归实现指数型枚举 解法1递归
使用递归对每一个坑位进行选择每个坑位有两种选择填或者不填使用st数组来记录每个坑位的状态u来记录已经有多少坑位有了选择。 每个坑位有2钟选择n个坑位的复杂度就是2的n次方。
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N 16;
int n;
int st[N];
void dfs(int u){if(un){for(int i 1;in;i){if(st[i]1)printf(%d ,i);}printf(\n);return;}st[u] 1;dfs(u1);st[u]0;dfs(u1);
}
int main(){scanf(%d,n);dfs(1);return 0;
}坑位的下标和这个坑位的数字是存在对应关系的所以可以用一个u来控制递归的出口。我们只关心u位置是否有数字。 st[u] 1; dfs(u1); 这两句相当于是将这个位置画对勾然后跳到下一个位置进行选择 st[u]0; dfs(u1); 这两句就是这个位置不填数进入下一轮顺便回到dfs之前的状态。(这题无所谓)
解法2二进制压缩
1-n的所有整数排列的方案可以看作一个二进制序列例如1-3的排列中1 3就对应二进制101。有数字用1表示没有数字用0表示。 1-n共有2的n次方钟方案。将所有方案数枚举然后判断位数是否是1。
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int n;
int main()
{scanf(%d,n);for(int i 0;i 1n;i ){for(int j 0;j n;j ){if(i j 1)printf(%d ,j 1);}printf(\n);}return 0;
}94. 递归实现排列型枚举
这题就是一个全排列问题和上一题的区别是很明显的。上一个的每个坑位的数字是固定的可能有或没有这个题的每个坑位的数是不固定的且必须有。这个题需要使用st记录是否使用过。这个st和上一个题的st代表的意义不一样。
使用循环来进行dfs。循环从1开始到n结束。通过st[i]可以知道数字i是否被使用过。如果没被使用过就使用i然后进入下一层搜索。使用后一定要恢复现场。 #includecstdio
#includecstring
#includeiostream
#includealgorithm
using namespace std;
const int N 10;
int m,st[N],ans[N];
int n;
void dfs(int x)
{if(x n) {for(int i 1;i n;i ){printf(%d ,ans[i]);}printf(\n);}for(int i 1;i n;i ){if(!st[i]){st[i] 1;ans[x] i;dfs(x1);st[i] 0;}}
}
int main()
{scanf(%d,n);dfs(1);return 0;
}717. 简单斐波那契 使用递推来进行求解通过观察可以发现这个数列的第n项只与n-1和n-2项有直接关系所以使用三个变量a b fn依次向后轮转。
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int main(){int n,fn;scanf(%d,n);int a 0,b 1;for(int i 1;i n;i ){couta ;fn ab;ab,bfn;}
}95. 费解的开关 样例 改变右上角的开关 两步即可让所有的灯变亮。
观察题意可以发现能影响灯本身的除了灯自己还有灯上下左右的灯可以枚举第一行灯的32种按法记得备份原数组然后从第一行按到第四行第i行可以通过第i1行的灯来控制遍历完第四行后看看第五行还有没有灭的灯如果有的话那这个方案就是不可行的。因为没有第六行来控制第五行。如果第五行全亮那这个就是可以调判断一下和ans哪个更小。
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N 6;
char g[N][N],backup[N][N];
int n;
int dx[] {1,-1,0,0,0};
int dy[] {0,0,-1,1,0};
void turn(int x,int y){for(int i 0;i 5;i ){int a x dx[i];int b y dy[i];if(a 0 || b 0 || a 4 || b 4)continue;g[a][b] ^ 1;}
}
int main(){scanf(%d,n);while(n --){for(int i 0;i 5;i )scanf(%s,g[i]);int ans 10;for(int op 0;op 32;op ){memcpy(backup,g,sizeof g);int step 0;for(int i 0;i 5;i ){if(op i 1){turn(0,i);step ;}}for(int i 0;i 4;i ){for(int j 0;j 5;j ){if(g[i][j] 0){turn(i1,j);step ;}}}int drak 0;for(int j 0;j 5;j ){if(g[4][j] 0){drak 1;break;}}if(drak 0)ans min(ans,step);memcpy(g,backup,sizeof g);}if(ans 6)ans -1;cout ans endl;}return 0;
}93. 递归实现组合型枚举 这题与全排列的区别就是字典序只需要在判断是否使用过的时候加上一个判断条件是当前的i是否大于ans数组的的最后一个元素大于往里面添加小于直接就跳过即可。ans数组初始化时要将元素变为-1,否则开头将无法添加。
#includecstdio
#includecstring
#includealgorithm
#includeiostream
using namespace std;
const int N 26;
int n,m;
int ans[N] {-1},st[N]{0};
void dfs(int c,int m){if(c m){for(int i 1;i m; i ){cout ans[i] ;}coutendl;return;}for(int i c ;i n; i ){if(!st[i]i ans[c-1]){ans[c] i;st[i] 1;dfs(c 1,m);st[i] 0;}}
}
int main(){scanf(%d%d,n,m);dfs(1,m);return 0;
}1209. 带分数 题意是 n a b / c n a b/c nab/c 等式两边同时×c c ∗ n c ∗ a b c*n c*ab c∗nc∗ab 通过dfs枚举a和c然后计算出b然后遍历st数组看看是否b的每一位都没有被用到。
#includeiostream
#includealgorithm
#includecstdio
#includecstring
using namespace std;
const int N 30;
int st[N],backup[N];
int n,ans,test;
bool check(int a,int c)
{long long b (long long) n * c -a * c;if(!a || !b || !c)return false;memcpy(backup,st,sizeof st);while(b){int ge b % 10;if(ge 0 || backup[ge])return false;backup[ge] 1;b / 10;}for(int i 1;i 9;i ){if(backup[i] 0) return false;}return true;
}
void dfs_c(int a,int c)
{if(check(a,c))ans ;for(int i 1; i 9; i ){if(st[i] 0){st[i] 1;dfs_c(a,c*10 i);st[i] 0;}}
}
void dfs_a(int a)
{if(a n)return;if(a)dfs_c(a,0);for(int i 1;i 9; i ){if(st[i] 0){st[i] 1;dfs_a(a*10 i);st[i] 0;}}
}
int main()
{scanf(%d,n);dfs_a(0);cout ans endl;return 0;
}116. 飞行员兄弟
和费解的开关类似只不过这个题的数量比较下所以枚举所有行的全部可能共65536种对每一种方案进行操作记录最少的方案数。
#includeiostream
#includecstdio
#includecstring
#includealgorithm
#includevector
#define x first
#define y second
using namespace std;typedef pairint,int PII;
const int N 5;
char st[N][N],backup[N][N];
vector PII ans;
int get(int x,int y)
{return x*4 y;
}
void turn(int x,int y)
{if(st[x][y])st[x][y]-;else st[x][y];
}
void turnall(int x,int y)
{for(int i 0;i 4;i ){turn(x,i);turn(i,y);}turn(x,y);
}
int main()
{for(int i 0;i 4;i ){scanf(%s,st[i]);}for(int i 0;i 1 16;i ){vector PII step;memcpy(backup,st,sizeof st);for(int x 0;x 4;x ){for(int y 0;y 4;y ){if(i get(x,y) 1){turnall(x,y);step.push_back({x,y});}}}int dark 0;for(int x 0;x 4;x ){for(int y 0;y 4;y ){if(st[x][y]){dark 1;break;}}}if(dark 0){if(ans.empty()||ans.size() step.size()) ans step;}memcpy(st,backup,sizeof st);}cout ans.size() endl;for(auto p:ans){cout p.x1 p.y1endl;}return 0;
}1208. 翻硬币
有个初始态有个结束态。将初始态与结束态一一对比遇到不一样的就将移动次数加一并且变换硬币状态。
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
int ans;
string start,aim;
void turn(int i)
{if(start[i]*)start[i] o;else start[i] *;
}
int main()
{cinstartaim;for(int i 0;i start.size() - 1;i ){if(start[i]!aim[i])turn(i1),ans;}cout ans endl;return 0;
}
