[Codeforces] 525E. Anya and Cubes

題目連結:http://codeforces.com/problemset/problem/525/E
一個神奇的技巧,砍半枚舉,其實就是一種枚舉的方法,不過因為可能原本$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]]);
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology