[Codeforces] 525E. Anya and Cubes
題目連結:http://codeforces.com/problemset/problem/525/E
一個神奇的技巧,砍半枚舉,其實就是一種枚舉的方法,不過因為可能原本$2^N$太大,所以只在兩邊各枚舉一半,變成$2^{\frac{N}{2}+1}$,不過這作法要可以有效率的枚舉出部分在左、部分在右的。像這題的話,我是先算完左半邊後,把可能的值全部塞到一個vector,sort完後,就可以在算右邊時,同時二分搜左邊可能的答案。
一個神奇的技巧,砍半枚舉,其實就是一種枚舉的方法,不過因為可能原本$2^N$太大,所以只在兩邊各枚舉一半,變成$2^{\frac{N}{2}+1}$,不過這作法要可以有效率的枚舉出部分在左、部分在右的。像這題的話,我是先算完左半邊後,把可能的值全部塞到一個vector,sort完後,就可以在算右邊時,同時二分搜左邊可能的答案。
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define ALL(x) (x).begin(), (x).end()
#define PB push_back
typedef pair<int,lld> PLI;
const int N = 25 + 3;
int n, k;
lld arr[N], jie[N], S, ans=0;
vector<PLI> set1;
void dfs(int,int,int,lld);
void dfs2(int,int,int,lld);
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>k>>S;
for(int i=0;i<n;i++) cin>>arr[i];
jie[0]=1;
for(int i=1;i<20;i++) jie[i]=jie[i-1]*i;
int mid=n>>1;
dfs(0, mid, k, 0);
sort(ALL(set1));
dfs2(mid, n, k, 0);
cout<<ans<<'\n';
return 0;
}
void dfs(int cur, int rg, int kk, lld sm){
if(cur > rg or kk < 0 or sm > S) return;
if(rg == cur){
set1.PB({sm, k-kk});
return;
}
dfs(cur+1, rg, kk, sm+arr[cur]);
dfs(cur+1, rg, kk, sm);
if(arr[cur] < 20) dfs(cur+1, rg, kk-1, sm+jie[arr[cur]]);
}
void dfs2(int cur, int rg, int kk, lld sm){
if(cur > rg or kk < 0 or sm > S) return;
if(rg == cur){
ans += upper_bound(ALL(set1), (PLI){S-sm, kk}) - lower_bound(ALL(set1), (PLI){S-sm, 0});
return;
}
dfs2(cur+1, rg, kk, sm+arr[cur]);
dfs2(cur+1, rg, kk, sm);
if(arr[cur] < 20) dfs2(cur+1, rg, kk-1, sm+jie[arr[cur]]);
}
留言
張貼留言