P1088[火星人]

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 10000+10;
int m, n;
int flag = 0;
int arr[N];
bool st[N];
int owari=0;
int sum = 0;
int res = 0;

void dfs(int x) {
    if(owari==1) return;
    if (sum == m) {
        flag = 1;
        ++res;
        if (res == n+1) { // 当找到第 n 个排列时输出并终止
            for (int i = 1; i <= m; i++) {
                cout << arr[i] << ' ';
            }
            cout << endl;
            owari=1;
            return;
        }
    }
    
    for (int i = 1; i <= m; i++) {
        if(flag==0) i=arr[x];
        if (!st[i]) { // 检查当前位置是否使用
            st[i] = true;
            arr[x] = i;
            sum += 1;

            dfs(x + 1);

            // 回溯时重置状态
            st[i] = false;
            arr[x] = 0;
            sum -= 1;
            
        }
    }
}

int main() {
    cin >> m >> n;
    for(int i =1;i<=m;i++){
        scanf("%d",&arr[i]);
    }
    memset(st, false, sizeof(st));
    dfs(1);

    return 0;
}

P1149[火柴棒等式]

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 <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int res=0;
int st[10000];
int n;
int m=0;
int arr[4]={0};

int ls[10]={6,2,5,5,4,5,6,3,7,6};
int number(int x) {
    int count = 0;
    if (x == 0) return ls[0];  // 处理0的特殊情况
    while (x > 0) {
        count += ls[x % 10];  // 获取当前数字的最后一位
        x /= 10;  // 去掉最后一位
    }
    return count;
}

void dfs(int x){
    
    if(x>=3){
        int A = arr[1];
        int B = arr[2];
        int C = A + B;
        if(number(A)+number(B)+number(C)+4==n){
        ++res; 
        } 
        
        return;
    }
    for(int i=0;i<1000;i++){
        arr[x]=i;
        dfs(x+1);
        arr[x]=0;

    }
}

int main(){
    scanf("%d",&n);
    dfs(1);
    cout<<res<<endl;
    return 0;
}


P2036[PERKET]

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 10000+10;
int acid[N];
int bitter[N];
int n;
int st[N];
int minum=100000;
int cnt=0;
int dfs(int x){
    
    if(x>n){
        if(cnt==0) return 0;
        int pro=1;
        int sum=0;
        for(int i=1;i<=n;i++){
            if(st[i]==1){
            pro*=(acid[i]);
            sum+=(bitter[i]);
            }
        }
        if(abs(pro-sum)<=minum) {
            minum=abs(pro-sum);
        
                
        }
        return abs(pro-sum);
    }
    for(int s=0;s<=1;++s){
            if(s==1){
                cnt+=1;}
            st[x]=s;
            dfs(x+1);
            if(s==1){
            cnt-=1;}
    }return 0;

}



int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d",&acid[i],&bitter[i]);
    }
    dfs(1);
    cout<<minum<<endl;
    return 0;
}

P2089[烤鸡]

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
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N=20;
int n;
int arr[N];
int res=0;

void dfs(int x,int sum){
    if(sum>n) return;
    if(x==11){
        if(sum==n){
        res++;
        for(int i=1;i<=10;i++){
            printf("%d",arr[i]);
        }
        printf("\n");
        return;
        }
    }
    

    for(int i=1;i<=3;i++){
        arr[x]=i;
        dfs(x+1,sum+i);
        arr[x]=0;

    }
}

int main(){
    scanf("%d",&n);
    dfs(1,0);
    printf("%d",res);
    return 0;
}