1 solutions

  • 0
    @ 2022-3-20 14:24:16

    使用dfs生成全排列

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 10;
    int target;
    int num[N];
    bool used[N];
    int cnt; //用来计数 
    int search(int l, int r){ ////计算num数组中一段的数是多少
    	int ans = 0;
    	for(int i = l; i <= r; i++)
    		ans = ans * 10 + num[i];
    	return ans;
    }
    void dfs(int u){ //生成全排列 
    	if(u == 9){
    		for(int i = 0; i < 7; i++)
    			for(int j = i + 1; j < 8; j++){
    				int a = search(0, i);
    				int b = search(i + 1, j);
    				int c = search(j + 1, 8);
    				//因为除法是整除,所以要换成加减乘法来运算 
    				if(a * c + b == c * target)
    					cnt++;
    			}
    	} 
    	for(int i = 1; i <= 9; i++)
    		if(!used[i]){
    			used[i] = true;
    			num[u] = i;
    			dfs(u + 1);
    			used[i] = false;//复原现场		
    		}
    }
    int main(){
    	std::ios::sync_with_stdio(false);
    	cin>>target;
    	dfs(0);
    	cout<<cnt;
    	return 0;
    }
    

    Information

    ID
    1582
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    6
    Tags
    # Submissions
    20
    Accepted
    12
    Uploaded By