------------恢复内容开始------------

一.p1763 埃及分数

1.对于深度搜索与广度搜索是变化的，不确定的，考虑使用迭代加深搜索。

2.对于本题，在寻找分数时，要使用到剪枝操作，首先分母确定范围，用v[n]表示分母集合，则需要满足v[n]>=v[n-1]+1,考虑分解成x项，最小分母是y,a/b=1/y+1/z.......(z>y),当x*(1/y)<a/b时，进行剪枝。

3.潜在条件：v[n]至少等于b/a+1。

#include <bits/stdc++.h>
#define re register int
#define ll long long
using namespace std;
ll a, b, m = 1, ans[2021], now[2021];
bool bj;

ll gcd(ll a, ll b) {
if (!b)
return a;
return gcd(b, a % b);
}

void yf(ll &a, ll &b) {
int g = gcd(a, b);
a /= g;
b /= g;
return;
}

void dfs(ll x, ll p, ll A, ll B) {
ll a = A, b = B;
yf(a, b);
if (x == 1) {
if (a == 1 && b > p) {
if (bj && b >= ans[1])
return;
now[1] = b;
bj = 1;
memcpy(ans, now, (m + 1) << 3);
return;
}
return;
}
for (re i = p; ceil((double)b * x / a) >= i; i++) {
now[x] = i;
dfs(x - 1, i, a * i - b, b * i);
}
return;
}

int main() {
cin >> a >> b;
yf(a, b);
while (!bj) {
dfs(m, 1, a, b);
m++;
}
for (re i = m - 1; i >= 1; i--)
cout << ans[i] << " ";
return 0;
}

二.Anya and Cubes

运用到折半搜索

#include <iostream>
#include <cstdio>
#include <unordered_map>

using namespace std;

typedef long long ll;

unordered_map<ll, ll> m[30]; // 使用了 unordered_map，比普通的 map 快，但这道题好像不卡 map？
// m[i][j] 代表用了 i 个阶乘符号，总和为 j 的方案数
int n, k;
ll ans; // 答案开 long long 好习惯
ll s, a[30];
ll fac[30];

// 对前一半数字进行搜索
void dfs1(int cur = 1, int cnt = 0, ll sum = 0) { // 当前处理到第 cur 个数字，用了 cnt 个阶乘符号，总和为 sum
if (cur >= n / 2 + 1) { // 当搜索的数字个数达到 n / 2 时，统计后退出搜索
m[cnt][sum]++;
return;
}
dfs1(cur + 1, cnt, sum); // 不取当前数字
if (sum + a[cur] <= s)
dfs1(cur + 1, cnt, sum + a[cur]); // 直接取当前数字
if (a[cur] <= 19 && sum + fac[a[cur]] <= s && cnt < k)
dfs1(cur + 1, cnt + 1, sum + fac[a[cur]]); // 将当前数字变成其阶乘后再取
// 这里要注意，由于 s <= 1e16，而 19！ 已经远大于 1e16，所以当当前数字大于19没有必要搜（而且再大的话 long long 也存不下）
// 记得判断 cnt < k
return;
}

// 对后一半数字进行搜索
void dfs2(int cur = n / 2 + 1, int cnt = 0, ll sum = 0) { // 同 dfs1
if (cur >= n + 1) {
// 这道题不要求用完所有的！
// 所以当已经搜完了整个序列时，所有满足 i + cnt <= k 并且 j + sum = s 的 m[i][j] 都需要计入总数
for (int i = 0 ; i + cnt <= k; i++) {
if (m[i].count(s - sum))
ans += m[i][s - sum];
}
return;
}
dfs2(cur + 1, cnt, sum);
if (sum + a[cur] <= s)
dfs2(cur + 1, cnt, sum + a[cur]);
if (a[cur] <= 19 && sum + fac[a[cur]] <= s && cnt < k)
dfs2(cur + 1, cnt + 1, sum + fac[a[cur]]);
return;
}

void solve() {
fac[0] = 1;
for (int i = 1; i <= 19; i++)
fac[i] = fac[i - 1] * i; // 预处理阶乘
dfs1(), dfs2();
cout << ans << endl;
return;
}

int main() {
cin >> n >> k >> s;
for (int i = 1; i <= n; i++)
cin >> a[i];
solve();
return 0;
}

三.P4799 [CEOI2015 Day2] 世界冰球锦标赛

考虑使用折半搜索

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL Storage[1 << 21];
LL Storage2[1 << 21];
LL Game[1000000];
LL n, w, cnt, sum;
LL ans;

void dfs(int x, LL s) {
if (x == n / 2 + 1) {
Storage[++cnt] = s;
return;//如果已经搜完前一半，将目前已经选的比赛加起来的耗钱存起来，返回
}
dfs(x + 1, s);//不看该比赛
if (s + Game[x] <= w) { //如果钱够，看此场比赛
dfs(x + 1, s + Game[x]);
}
}

void dfs2(int x, LL s) { //同上
if (x == n + 1) {
Storage2[++sum] = s;
return;
}
dfs2(x + 1, s);
if (s + Game[x] <= w) {
dfs2(x + 1, s + Game[x]);
}
}

int main() {
cin >> n >> w;
for (int i = 1; i <= n; i++) {
cin >> Game[i];
}
dfs(1, 0);//搜索前一半
dfs2(n / 2 + 1, 0);//搜索后一半
sort(Storage2 + 1, Storage2 + sum + 1);//将后一半的搜索结果排序
for (int i = 1; i <= cnt; i++) { //枚举前一半的所有结果
LL l = 0, r = sum, mid;
LL all = 0;
while (l <= r)
//搜寻到后一半中能与前一半的当前方案
//融合在一起的最后一种方案
{
mid = l + (r - l) / 2;
if (Storage[i] + Storage2[mid] <= w) {
all = mid;
l = mid + 1;
} else
r = mid - 1;
}
ans += all;
// 由于前面已经将后一半排序，
// 故当前这个最大的后一半的方案及其之前的所有
// 后一半的方案都能和现在枚举的前一半的方案构成一种新的方案，
// 所以答案直接累加
}
cout << ans;//输出答案
return 0;
}

四.Prime gift

本题运用折半搜索+二分答案#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
#define REP(a,b,c) for(int a=b;a<=c;a++)
int n,a[110],k;
LL A[5000010],B[5000010];
int lenA=0,lenB=0;
inline void dfs1(int x,LL s) {
	A[++lenA]=s;
	if (x>n) return ;
	for(LL i=1;;i*=a[x]) {
		if (1e18/i<s) break;
		dfs1(x+2,s*i);
	}
}
inline void dfs2(int x,LL s) {
	B[++lenB]=s;
	if (x>n) return ;
	for(LL i=1;;i*=a[x]) {
		if (1e18/i<s) break;
		dfs2(x+2,s*i);
	}
}
inline LL check(LL mid) {
	LL ans=0; int j=lenB;
	REP(i,1,lenA) {
		while (j>0&&B[j]>mid/A[i]) j--;
		ans+=1ll*j;
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>n; REP(i,1,n) cin>>a[i]; cin>>k;
	sort(a+1,a+n+1);
	dfs1(1,1); dfs2(2,1);
	LL l=0,r=1e18;
	sort(A+1,A+lenA+1);
	sort(B+1,B+lenB+1);
	lenA=unique(A+1,A+lenA+1)-A-1;
	lenB=unique(B+1,B+lenB+1)-B-1;
	while (l<r) {
		LL mid=(l+r)>>1;
		if (check(mid)>=k) r=mid;
		else l=mid+1;
	}
	cout<<r<<endl;
	return 0;
}

五.P1312 [NOIP2011 提高组] Mayan 游戏

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#define z 10
using namespace std;
int m[z][z], ms[z][z][z], cl[z][z], ans[z][z], fin[z][z];
int n, ti;

void fall() {
for (int i = 0; i < 5; i++) {
int zero = 0;
for (int j = 0; j < 7; j++) {
if (m[i][j] == 0)
++zero;
else {
if (zero == 0)
continue;
m[i][j - zero] = m[i][j];
m[i][j] = 0;
}
}
}

}

bool clear() {
int cnt = 0;
memset(cl, 0, sizeof cl);
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++) {
if (i - 1 >= 0 && i + 1 < 5 && m[i][j] && m[i][j] == m[i - 1][j] && m[i][j] == m[i + 1][j]) {
cl[i][j] = 1;
cl[i + 1][j] = 1;
cl[i - 1][j] = 1;
cnt = 1;
}
if (j - 1 >= 0 && j + 1 < 7 && m[i][j] && m[i][j] == m[i][j - 1] && m[i][j] == m[i][j + 1]) {
cl[i][j] = 1;
cl[i][j + 1] = 1;
cl[i][j - 1] = 1;
cnt = 1;
}
}
if (!cnt)
return 0;
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++) {
if (cl[i][j]) {
m[i][j] = 0;
}
}
return 1;
}

void save(int d) {
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++)
ms[d][i][j] = m[i][j];
}

void re(int d) {
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++)
m[i][j] = ms[d][i][j];
for (int i = 0; i < 3; i++)
ans[d][i] = -1;
}

bool check() {
for (int i = 0; i < 5; i++)
for (int j = 0; j < 7; j++)
if (m[i][j] != 0)
return 0;
return 1;
}

void move(int i, int j, int p) {
int t = m[i][j];
m[i][j] = m[i + p][j];
m[i + p][j] = t;
fall();
while (clear()) {
fall();
}
}

void dfs(int d) {
if (check()) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < 3; j++) {
printf("%d ", ans[i][j]);
}
printf("\n");
}
exit(0);
}
if (d == n)
return;
save(d);
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 7; j++) {
if (m[i][j]) {
if (i < 4 && m[i + 1][j] != m[i][j]) {
move(i, j, 1);
ans[d][0] = i;
ans[d][1] = j;
ans[d][2] = 1;
dfs(d + 1);
re(d);
}
if (i > 0 && m[i - 1][j] == 0) {
move(i, j, -1);
ans[d][0] = i;
ans[d][1] = j;
ans[d][2] = -1;
dfs(d + 1);
re(d);
}
}
}
}
}

int main() {
scanf("%d", &n);
for (int i = 0; i < 5; i++) {
for (int j = 0; j <= 7; j++) {
int tt;
scanf("%d", &tt);
if (tt == 0)
break;
m[i][j] = tt;
}
}
memset(fin, -1, sizeof fin);
dfs(0);
if (fin[1][0] == -1)
printf("-1\n");
return 0;
}