今天发现了一个函数
next_permutation(a,a+n)
即求当前排列的下n个排列
例如n=1 对1234用 求出1243
在全排列问题中很有效
火星人这道题就是说 求一个全排列之下的第n个排列
正常也可以dfs写 只需要res到m+1时输出就行了 并且注意要剪枝
[p1088火星人] [c++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include<bits/stdc++.h>
using namespace std;
int n,m;
int a[10100];
int main()
{
cin>>n;
cin>>m;
for(int i=0;i<n;i++) cin>>a[i];
for(int i=0;i<m;i++)
{
next_permutation(a,a+n);
}
for(int i=0;i<n;i++) cout<<a[i]<<" ";
return 0;
}
|
烤鸡这道题要先输出方案数 所以要特别做法 用一个二维数组存
并且注意剪枝 如果调料还没选完都已经大于n了 那么就不用再往下了
[p2089] [c++]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
| #include<iostream>
using namespace std;
const int N=5020;
int n,sum=0;
int mem[59055][20];
int a[N];
int res=0;
void dfs(int x,int sum)
{
if(sum>n) return;
if(x>10)
{
if(sum==n)
{
res++;
for(int i=1;i<n;i++)
{
mem[res][i]=a[i];
}
}
return;
}
for(int i=1;i<=3;i++)
{
a[x]=i;
dfs(x+1,sum+i);
a[x]=0;
}
}
int main()
{
cin>>n;
dfs(1,sum);
cout<<res<<endl;
for(int i=1;i<=res;i++)
{
for(int j=1;j<=10;j++)
{
cout<<mem[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
|
火柴这道题非常有意思
有两个必须满足的条件
一个是a+b=c
一个是num[a]+num[b]=num[c]-4
最关键的就是对于总和的处理 需要额外写个函数计算二位数及以上的火柴数
也可以用递推求出10-1000的 节省时间到原来的三分之一
也要记得剪枝 如果还没枚举完 火柴数都超了 那么直接return
[p1149] [c++]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
| #include<bits/stdc++.h>
using namespace std;
int n,m,res=0;
int num[10010]={6,2,5,5,4,5,6,3,7,6};
int arr[10010];
int col(int x)
{
int sum2=0;
if(num[x]>0) return num[x];
else
{
while(x)
{
sum2+=num[x%10];
x/=10;
}
}
return sum2;
}
void dfs(int x,int sum)
{
if(sum>n) return;
if(x>3)
{
if(arr[1]+arr[2]==arr[3] && sum==n) res++;
return;
}
for(int i=0;i<=1000;i++)
{
arr[x]=i;
dfs(x+1,sum+col(i));
arr[x]=0;
}
}
int main()
{
cin>>n;
n-=4; //预处理一下 清晰一点
dfs(1,0);
cout<<res<<endl;
return 0;
}
|
这道题是有坑的 就是至少添加一个调料
我们可以全局定义一个bool 选择先搜不选 因为从不选搜到第一个有选以后 之后都起码选了一个
也可以定义在函数里 先搜全选
[p2036] [c++]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
| #include<bits/stdc++.h>
using namespace std;
const int N=20;
int n;
int res=1e9;
int s[N],b[N],st[N];
void dfs(int x)
{
if(x>n)
{
bool has_s=false;
int sum1=1;
int sum2=0;
for(int i=1;i<=n;i++)
{
if(st[i]==1)
{
has_s=true;
sum1*=s[i];
sum2+=b[i];
}
}
if(has_s==true) res=min(res,abs(sum1-sum2));
return;
}
st[x]=1;
dfs(x+1);
st[x]=0;
st[x]=2;
dfs(x+1);
st[x]=0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>s[i];
cin>>b[i];
}
dfs(1);
cout<<res<<endl;
return 0;
}
|
接下来是迷宫环节
这道题有一个剪枝难点 和之前的电梯一样
namo就是 走过一次的话 就没必要走多次
还有一点就是 这道题不能回溯 因为路径是单一的 回溯了会重复计数
[P1683] [c++]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
| #include<bits/stdc++.h>
using namespace std;
const int N=30;
int w,h,res=0;
char zi[N][N];
bool st[N][N];
int zoux[]={-1,0,1,0};
int zouy[]={0,1,0,-1};
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int a=x+zoux[i];
int b=y+zouy[i];
if(a<1 ||a>h ||b<1 ||b>w) continue;
if(zi[a][b]!='.') continue;
if(st[a][b]) continue;
st[a][b]=true;
res++;
dfs(a,b);
}
}
int main()
{
cin>>w>>h;
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++) cin>>zi[i][j];
}
for(int i=1;i<=h;i++)
{
for(int j=1;j<=w;j++)
{
if(zi[i][j]=='@')
{
st[i][j]=true;
dfs(i,j);
}
}
}
cout<<++res<<endl;
return 0;
}
|
