本文主要是介绍暴力出奇迹，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
LA4253 Archery 二分，给出ｎ条水平线段，问能否在[0,w]区间选一个点当发出一条射线穿过所有的线段，先把线段按高度排序，然后二分射线起点的位置。
http://acm.bnu.edu.cn/v3/problem_show.php?pid=11135
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3+10;
const double eps = 1e-8;
const double PI = acos(-1);
struct Node{double d,l,r;bool operator < (const Node & rhs) const {return d < rhs.d;}
}a[maxn];
int n;
double w;
int check(double x)
{double L = atan2(a[0].d, a[0].r - x);double R = atan2(a[0].d, a[0].l - x);for (int i = 1; i < n; i++){double l = atan2(a[i].d, a[i].r - x);double r = atan2(a[i].d, a[i].l - x);if (r - L < -eps)return -1;if (l - R > eps)return 1;L = max(L, l);R = min(R, r);}return 0;
}
int main()
{int T;scanf("%d",&T);while(T--) {scanf("%lf%d",&w,&n);for(int i = 0; i < n; ++i) {scanf("%lf%lf%lf",&a[i].d,&a[i].l,&a[i].r);}sort(a,a+n);double l = 0,r = w;int ok = 0;while(l + eps < r) {double mid = (l+r)/2;int t = check(mid);if(!t) {ok = 1;break;}if(t < 0) r = mid;else l = mid;}puts(ok?"YES":"NO");}return 0;
}
http://acm.bnu.edu.cn/v3/problem_show.php?pid=19243
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e2 + 10;
int n,m;
int a[maxn],b[maxn],c[maxn];
bool check()
{for(int i = 0; i < m; ++i) b[i] = c[i] = a[i];c[m] = 0;for(int i = 2; i <= m; ++i) {for(int j = 0; j < m; ++j) {c[j] += b[j];c[j+1] += c[j]/n;c[j] %= n;}}if(c[m]) return false;sort(b,b+m);sort(c,c+m);return memcmp(b,c,sizeof(*b)*m) == 0;
}
bool dfs(int cur)
{if(cur == m) return check();for(int i = cur; i < m; ++i) {swap(a[cur],a[i]);if(dfs(cur+1)) return true;swap(a[cur],a[i]);}return false;
}
bool solve(int x)
{int now = 0;for(int i = 0; i < m; ++i) {now = (now + x) % n;a[i] = now;}return dfs(0);
}
int main()
{while(scanf("%d%d",&m,&n)==2) {if(n==0&&m==0) return 0;int ok = 0;for(int i = 1; i < n; ++i) if(solve(i)) {ok = 1;break;}if(ok) {for(int i = m-1; i >= 0; --i) printf("%d%c",a[i]," \n"[i==0]);}else {puts("Not found.");}}return 0;
}LA 3403 Mobile Computing 枚举二叉树，给出ｎ个砝码的质量和一个宽度ｗ，可以在天平的挂钩处挂砝码或者天平，求使得所有天平都平衡且宽度不超过ｗ的最大宽度，枚举天平装入集合ｓ里砝码的左右臂长度。
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int maxn = 6;
const int maxm = (1<<maxn)+10;
bool vis[maxm];
int w[maxn];
double sum[maxm];///集合里砝码重量
vector<pair<double,double> >Info[maxm];///当前砝码集合在天平上的最左和最右信息
void dfs(int s) ///计算把ｓ里的砝码全部放入天平时，天平所有可能的左右边界
{if(vis[s])return;vis[s] = true;if((s&-s)==s) {///只有一个砝码，直接挂在该点Info[s].push_back(make_pair(0,0));return ;}for(int l = (s-1)&s; l; l = (l-1)&s) {int r = s^l;dfs(l);dfs(r);double lx = sum[r]/(sum[l]+sum[r]),rx = 1-lx;for(unsigned i = 0; i != Info[l].size(); ++i) {for(unsigned j = 0; j != Info[r].size(); ++j) {double L = min(Info[l][i].fi-lx,rx+Info[r][j].fi); ///注意当前天平右边可以延伸到当前天平的更左边double R = max(Info[l][i].se-lx,Info[r][j].se+rx); ///当前天平的左边可以延伸到更右边Info[s].push_back(make_pair(L,R));}}}
}
int main()
{int T;scanf("%d",&T);for(int cas = 1; cas <= T; ++cas) {double limt;scanf("%lf",&limt);int n;scanf("%d",&n);for(int i = 0; i < n; ++i) scanf("%d",w+i);int ALL = (1<<n)-1;for(int s = 0; s <= ALL; ++s) {sum[s] = 0;Info[s].clear();for(int b = 0; b < n; ++b) if((s>>b)&1){sum[s] += w[b];}}memset(vis,0,sizeof(*vis)*(ALL+1));dfs(ALL);double ans = -1;for(unsigned i = 0; i != Info[ALL].size(); ++i) {double dist = Info[ALL][i].se - Info[ALL][i].fi;if(dist <= limt && dist > ans) ans = dist;}if(ans == -1) puts("-1");else printf("%.10f\n",ans);}return 0;
}LA 3621 Power Calculus,迭代加深搜索。计算ｘ^k最少需要多少次 乘除法。因为解的深度很小，所有可以用跌代加深搜索来做，限制搜索的深度。注意枚举的时候只用当前那一层的数和前面的数相乘或相除。
http://acm.bnu.edu.cn/v3/problem_show.php?pid=9797
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const int maxn = 2e3 + 10;
int dep;
int a[maxn],k;
bool dfs(int step)
{if(step > dep) return false;if(a[step-1] == k) return true;if(a[step-1] << (dep-step) < k) return false;for(int i = 0; i < step; ++i) {a[step] = a[step-1] + a[i];if(a[step] < maxn && dfs(step+1)) return true;a[step] = a[step-1] - a[i];if(a[step] > 0 && dfs(step+1)) return true;}return false;
}
int solve()
{dep = 1;for(;(1<<dep) < k; ++dep);a[0] = 1;for(;!dfs(1); ++dep);return dep-1;
}
int main()
{while(scanf("%d",&k)==1&&k) {printf("%d\n",solve());}return 0;
}UVA 529 Addition Chains 跌代加深搜索，一个序列，第一项是１，后面的项可以通过前面的两个项相加得到，可以是相同的项，问最少哪一项才会出现ｎ。思路同上题．
http://acm.bnu.edu.cn/v3/problem_show.php?pid=17668
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;
const int maxn = 1e4 + 10;
int dep;
int a[maxn],k;
bool dfs(int step)
{if(step > dep) return false;if(a[step-1] == k) return true;if(a[step-1] << (dep-step) < k) return false;for(int i = 0; i < step; ++i) {a[step] = a[step-1] + a[i];if(a[step] < maxn && dfs(step+1)) return true;}return false;
}
int solve()
{dep = 1;for(;(1<<dep) < k; ++dep);a[0] = 1;for(;!dfs(1); ++dep);for(int i = 0; i < dep; ++i) printf("%d%c",a[i]," \n"[i+1==dep]);return dep-1;
}
int main()
{while(scanf("%d",&k)==1&&k) {solve();}return 0;
}这篇关于暴力出奇迹的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
