递归与递推
说白了就是搜索算法和简单动归
递归实现指数型枚举
递归实现指数型枚举
解题思路：
主要就是深搜dfs,对于一个数，我们要么选择他要么不选择他就两种情况，搜够n层，然后输出就行
用u表示现在搜第u层，status表示当前选中的点，看成二进制数，第i位为0表示不选择i，为1表示选择i。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using namespace std;
int n;
void dfs(int u,int status){
if(u==n){
for(int i=0;i<n;i++)
{
if(status>>i&1)
cout<<i+1<<" ";
}
cout<<endl;
return;
}
dfs(u+1,status);
dfs(u+1,status|1<<u);
}
int main(){
cin>>n;
dfs(0,0);
return 0;
}
|
递归实现组合枚举问题
递归实现组合枚举问题
解题思路
其实这个就是要从n个中选m个嘛，和第一题其实差不多的，但是要考虑当前的数量是不是m个，所以多加一个参数就可以了啊。
AC代码
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
| #include <bits/stdc++.h>
using namespace std;
int n,m;
void dfs(int u,int k,int status){
if(k == m){
for(int i =0;i<n;i++)
if(status>>i&1)
cout<<i+1<<' ';
cout<<endl;
return;
}
if(k+n-u < m || u == n)return;
dfs(u+1,k+1,status|1<<u);
dfs(u+1,k,status);
}
int main(){
cin>>n>>m;
dfs(0,0,0);
return 0;
}
|
费解的开关
费解的开关
解题思路
就是点击一个地方，其本身位置，上下左右都与原来的位置相反，问能否在6次内将其全部变成1
其实我们可以看第一行，对于第一行为0的位置
如果想让他变成1，是不是就需要点击他下面的那个按钮才会让他变成0并且不会影响第一行其他位置呢？
是的没错，只要我们点击他下面的按钮，就能完成，同理可以推演到第2行，第3行，第4行。
第5行不用点击，因为如果前4行全亮就够了，第五行如果不能全亮，说明这种情况下无法实现，让开关全亮。
但是，有没有可能存在存在整好点击第一行的某个位置，就全亮了或者说点击某个位置就能减少后面的步骤。
显然这种可能是存在的，因此我们还要判断点击第一行的按钮方式，我们可以用二进制的方式进行枚举，对于状态数，对应的位置为1的话，我们就认为当前这个按钮需要点击。否则就不用点击。
有5个位置，每个位置有2个选择，复杂度应该为25=32
遍历4行，每行5个对应20
检验是否能成功，5个
最大检查灯阵个数，500个
最坏计算情况为:32×20×5×500=1,600,000属于可以接收的复杂度
AC代码
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
| #include <bits/stdc++.h>
using namespace std;
const int N =5;
const int INF = 1e9;
char g[N][N];
int n;
void turn(int x,int y){
int dx[] = {0,-1,0,1,0};
int dy[] = {0,0,1,0,-1};
for(int i =0;i<5;i++){
int a = x+dx[i],b = y+dy[i];
if(a>=0&&a<5&&b>=0&&b<5)
g[a][b] ^= 1;
}
}
int work(){
int ans = INF;
for(int i =0;i<1<<5;i++){
char save[N][N];
memcpy(save,g,sizeof g);
int cnt = 0;
for(int k=0;k<N;k++){
if(i>>k&1){
cnt++;
turn(0,k);
}
}
for(int j = 0;j<4;j++)
for(int k = 0;k<N;k++){
if(g[j][k] == '0'){
cnt++;
turn(j+1,k);
}
}
bool flag = true;
for(int i= 0;i<N;i++){
if(g[N-1][i] == '0')
{
flag = false;
break;
}
}
if(flag)ans = min(ans,cnt);
memcpy(g,save,sizeof g);
}
return ans>6?-1:ans;
}
int main(){
cin>>n;
while(n--){
for(int i =0;i<N;i++)cin>>g[i];
cout<<work()<<endl;
}
return 0;
}
|
奇怪的汉诺塔问题
奇怪的汉诺塔
解题思路
仔细思考一下，如果有四根杆子，我们先移动前j个盘子到第2根杆上，是不是第2根杆就不能用了，然后问题就变成了i-j个盘子移动到第4根杆子上，只能有1，3，4三根杆子，这就变成了正常的汉诺塔问题。
文字看不懂就直接看代码，代码直接
初始条件都是，如果只有一个，那就只需要一步
先看看三个杆子的怎么算
用three[i]表示i个盘子利用3根杆子i移动到任意一根使用的移动次数，首先得先将i-1个杆子移动到第2根杆子次数应该为three[i-1]，然后最后一个盘子移动到第三根杆子，再将i-1个盘子移动到最后一根杆子上就行。
好三根杆子的弄完了，我们看看四根杆子怎么用
假设要移动i个盘子
先将前j个盘子移动到第2个位置，当前可以使用4个位置，因此移动次数为four[j]
然后将i-j个盘子移动到第4个位置，当前可以使用3个位置，因为第2个位置的盘子不可能i放下其他位置的盘子，所以移动次数为three[i-j]
最后再将前j个盘子移动到第4个位置，当前可使用的位置有4个，因此移动次数为four[i]
AC代码
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
| #include <bits/stdc++.h>
using namespace std;
int three[15],four[15];
int main(){
memset(four,0x3f,sizeof four);
three[1] = 1;
four[1] = 1;
for(int i = 2;i<=12;i++){
three[i] = three[i-1]*2+1;
}
for(int i = 2;i<= 12;i++){
for(int j = 0;j<i;j++){
four[i] = min(four[i],four[j]*2+three[i-j]);
}
}
for(int i =1;i<=12;i++)cout<<four[i]<<endl;
return 0;
}
|
约数之和
约数之和
解题思路
本质上可以利用质因素进行计算求和结果T，如下公式会比较清晰,a1,a2,...,an表示不同的质因数
T=(a10+a12+...+a1k)×(a20+a22+...+a2k)×...×(an0+an2+...+ank)
因为单个数还有计算其次方的可能，那质因数的可选个数会增大到k的b倍即kb，显然如果要使用之前写过的数论实现方式不太合适
首先，i的最后一个为奇数的情况，我们拿一个最推理,sum函数表示ai为i底，指数到k的加和，先取出他的一半,对右边的括号取出因数a2k+1,
sum(a1,k)=a10+a12+...+a1k=(a10+a12+...+a2k)+(a2k+1+...+a1k)=(a10+a12+...+a2k)+(a10+a12+...+a2k)×a2k+1=(a10+a12+...+a2k)∗(1+a12k+1)=(1+a12k+1)∗sum(a1,2k)
举个例子
sum(a,3)=a0+a1+a2+a3⌊2k⌋=⌊23⌋=1,⌊2k⌋+1=⌊23+1⌋=2sum(a,3)=(a0+a1)+(a2+a3)sum(a,3)=(a0+a1)+a2×(a0+a1)sum(a,3)=(a0+a1)×(1+a2)=sum(a,1)×(1+a2)其中子函数中的1是⌊2k⌋=⌊23⌋=1加和项的次方的2是⌊2k⌋+1=⌊23+1⌋=2
显然，这是一个递归的过程，我们都指导任意非0数的0次方应该为1，这就作为我们递归的出口
上面就是奇数的情况，那如果是偶数呢？举个例子
sum(a,4)=a0+a1+a2+a3+a4sum(a,4)=a0+a×(a0+a1+a2)=a0+a×sum(a,3)这不就转化成奇数的形式了么？推演到一般情况就是sum(a,k)=1+a×sum(a,k−1)当然要直接推奇数的也不难，但是经过测试，效率好像没有转化成偶数的高，所以如果你感兴趣可以自己推
AC代码
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
| #include <bits/stdc++.h>
using namespace std;
const int mod = 9901;
int qmi(int a,int k){
a%=mod;
int res = 1;
while(k){
if(k&1)res = res*a%mod;
a = a*a%mod;
k>>=1;
}
return res;
}
int sum(int p,int k){
if(k==0)return 1;
if(k%2==0)return (p%mod*sum(p,k-1)+1)%mod;
return (1+qmi(p,k/2+1))*sum(p,k/2)%mod;
}
int main(){
int A,B;
cin>>A>>B;
int res = 1;
for(int i =2;i<=A;i++){
int s= 0;
while(A%i == 0){
s++;
A/=i;
}
if(s)res = res*sum(i,s*B)%mod;
}
if (!A) res = 0;
cout<<res<<endl;
return 0;
}
|
分形之城
分形之城
解题思路
先定义座标轴，左上角为原点，向下为x轴，向右为y轴，与数组的结构一致
令len为N-1级别单行的长度(2n−1)换成代码为1<<(n-1)
cnt为N-1级别的总个数(2n−1×2n−1))换成代码为1<<2*(n-1)
我们先看等级1和等级2，我们可以看出，等级2可以分成四块，每一块都是由等级1的城市进行变化产生的，比如
- 等级2的左上角块，其实就是由等级1经过顺时针旋转90度，然后做一个水平翻转形成的
- 等级2的右上角块，就直接在y轴上平移等级1的长度
- 等级2的右下角块，就直接在x轴y轴上平移平移等级1的长度
- 等级2的左下角块，就先逆时针旋转90度，再做一个水平翻转，此时的1的坐标为仍在原点，为了方便平移，先将x，y向上和左平移一个长度，即-1，再将结果向下平移2个等级1长度，向右平移一个等级1的长度。
假设我们额坐标为(x,y)
-
左上角：先旋转$\theta=$90度，根据旋转公式,得到坐标(-y,x)，根据y轴进行翻转，得到(y,x)
[x,y]×[cosθ−sinθsinθsinθ]=[x,y]×[0−110]=[−y,x]
-
右上角：(x,y)->(x,y+len)
-
右下角：(x,y)->(x+len,y+len)
-
左下角：先旋转θ=-90度，根据旋转公式得到坐标,(y,-x)，根据y轴进行翻转，得到(-y,-x)，先向左向右平移1个单位得到(-y-1,-x-1)，再将结果向下平移2个等级1长度，向右平移一个等级1的长度得到(2*len-y-1,len-x-1)
将左上角，右上角，右下角，左下角分别定义为0，1，2，3
坐标变换弄好了，看代码吧，难的就是坐标变换了
AC代码
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
| #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PLL pair<ll,ll>
PLL calc(ll n,ll m){
if(n==0)return {0,0};
ll len = 1LL<<(n-1),cnt = 1LL<<(2*n-2);
PLL pos = calc(n-1,m%cnt);
ll x = pos.first,y = pos.second;
ll z = m/cnt;
if(z==0)return {y,x};
if(z==1)return {x,y+len};
if(z==2)return {x+len,y+len};
return {2*len-y-1,len-x-1};
}
int main(){
int t;
cin>>t;
while(t--){
ll N,A,B;
cin>>N>>A>>B;
PLL ac = calc(N,A-1);
PLL bc = calc(N,B-1);
ll x = ac.first-bc.first,y = ac.second-bc.second;
double res = sqrt(x*x+y*y)*10;
printf("%.0lf\n",res);
}
return 0;
}
|
微信
支付宝
