Count the Number（set 金马五校赛-东华大学）
Problem C : Count the Number
From: DHUOJ, 2017060303
<center> Time Limit: 3 s </center>
Description
Given n numbers, your task is to insert '+' or '-' in front of each number to construct expressions. Note that the position of numbers can be also changed.
You can calculate a result for each expression. Please count the number of distinct results and output it.
Input
There are several cases.
For each test case, the first line contains an integer n (1 ≤ n ≤ 20), and the second line contains n integers a1,a2, ... ,an (-1,000,000,000 ≤ ai ≤ 1,000,000,000).
Output
For each test case, output one line with the number of distinct results.
Sample Input
2 1 2 3 1 3 5
Sample Output
4 8
题意就是给你n个数，对它们进行加减，看能得到多少种结果。dfs进行搜索，用set来维护整个结果集的无重复性。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<map>
#include<set>
using namespace std;
long long a[25];
int n;
set<long long>s;
void dfs(int step,long long sum){
if(step==n){
s.insert(sum);
return;
}
for(int i=0;i<2;i++){
dfs(step+1,sum+a[step]*pow(-1,i));
}
return;
}
int main(){
while(~scanf("%d",&n)){
memset(a,0,sizeof(a));
s.clear();
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
dfs(0,0);
cout<<s.size()<<endl;
}
return 0;
}
投递TP-LINK等公司8个岗位