1 solutions

  • 1
    @ 2022-5-3 13:11:39

    普普通通的搜索,重点是sort的cmp该怎么写

    #include<bits/stdc++.h>
    using namespace std;
    typedef long int li;
    const int N=1e6+7;
    int n,sum,T;
    li a[N];
    vector<int>v;
    vector<vector<int> >ans;
    int cmp(vector<int> &a,vector<int> &b){
    	int l1=a.size(),l2=b.size();
    	int len=min(l1,l2);
    	for(int i=0;i<len;i++){
    		if(a[i]==b[i])continue;
    		return a[i]<b[i];
    	}
    	return l1<l2;
    }
    void dfs(int s,int su){
    	if(su==T){
    		ans.push_back(v);
    		sum++;
    	}
    	for(int i=s-1;i>=1;i--){
    		v.push_back(i);
    		dfs(i,su+a[i]);
    		v.pop_back();
    	}
    }
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++)
    		cin>>a[i];
    	cin>>T;
    	for(int i=1;i<=n;i++){
    		v.push_back(i);
    		dfs(i,a[i]);
    		v.pop_back();
    	}
    	sort(ans.begin(),ans.end(),cmp);
    	for(vector<int> t:ans){
    		for(int i=t.size()-1;i>=0;i--)
    			cout<<a[t[i]]<<" ";
    		cout<<endl;
    	}
    	cout<<sum<<endl;
    	return 0;
    }
    
    • 1

    Information

    ID
    1760
    Time
    1000ms
    Memory
    512MiB
    Difficulty
    10
    Tags
    # Submissions
    3
    Accepted
    2
    Uploaded By