做的时候觉得这套题好简单，结果一看发现是2012年的模拟题，估计就是
普及+的难度吧，AK无压力
总结
- 第一题状压我智障的调了好几分钟，因为我的最终状态写的
1<<n,智障了 - 第三题的dfs调了一会,也是有点难受的
- 吸取之前的教训,把开文件模板化了,方便检查
混乱的队伍
状压DP,注意开long long
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <ctime>
#include <cmath>
using namespace std;
#define rep(i,s,t) for(int i=(int)(s);i<=(int)(t);++i)
#define forn(i,n) for(int i=1;i<=(int)(n);++i)
#define pb push_back
#define seta(h, x) memset(h, x, sizeof(h))
#define fr first
#define sc second
typedef long long qword;
const int maxn = 20;
const string task = "mixup2";
qword f[1<<maxn][maxn];
int s[maxn];
#define OK
int main() {
#ifdef OK
freopen((task + ".in").data(),"r",stdin);
freopen((task + ".out").data(),"w",stdout);
ios::sync_with_stdio(0);
#endif // OK
int N, K;
cin >> N >> K;
forn(i, N) cin >> s[i];
forn(i, N) f[1<<(i-1)][i] = 1; // Init
int LastSituation = (1<<N) - 1;
forn(i, LastSituation) {
forn(j, N) {
if (i & (1 << (j-1))) {
forn(next, N) {
if (abs(s[next] - s[j]) > K && (!(i & (1 << (next - 1))))) {
f[i|(1<<(next-1))][next] += f[i][j];
}
}
}
}
}
qword ans = 0;
rep(i,1,N)
ans += f[LastSituation][i];
cout << ans << endl;
}
安慰员工
这套题裸地最小生成树.
给定边的选择和出发点之后，原来的图实际上变成了一个有根树，最优路径是从根出发的Euler回路（每条边都经过两次）
一个有\(K\)个孩子的节点在Euler回路中出现了\(K+1\)次。除了根以外的其他节点，\(K+1\) 恰好是这个节点在树中的度。这就是说，度为 \(D\)的节点被访问了 \(D\) 次，根节点
要多被访问依次。这里，每一个边都被遍历了两次，每个方向各一次。我们还可以发现，计算一个点的花费\(D_i\)次等价于在连接它的每条边上计算一次。所以如果我们重
新定义边的花费的话，那么问题就转化为了求最小生成树了
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <ctime>
#include <cmath>
using namespace std;
#define rep(i,s,t) for(int i=(int)(s);i<=(int)(t);++i)
#define forn(i,n) for(int i=1;i<=(int)(n);++i)
#define pb push_back
#define seta(h, x) memset(h, x, sizeof(h))
#define fr first
#define sc second
typedef long long qword;
const int maxn = 100010;
const string task = "cheer";
int c[maxn], r[maxn];
int val[maxn];
int from[maxn], to[maxn];
int fa[maxn];
bool cmp(const int& x, const int& y) {
return val[x] < val[y];
}
int getRoot(int x) {
return fa[x] == x ? x : fa[x] = getRoot(fa[x]);
}
int main() {
#ifndef Debug
freopen((task + ".in").data(),"r",stdin);
freopen((task + ".out").data(),"w",stdout);
#endif // Debug
int n, m;
cin >> n >> m;
qword ans = 0x7fffffff;
forn(i, n) {
cin >> c[i], fa[i] = i; ans = min(c[i], (int)ans);
}
int k;
forn(i, m) {
cin >> from[i] >> to[i] >> k;
val[i] = 1ll * k * 2 + c[from[i]] + c[to[i]];
r[i] = i;
}
sort(r + 1, r + 1 + m, cmp);
forn(i, m) {
int fo = from[r[i]], t = to[r[i]];
int uu = getRoot(fo), tt = getRoot(t);
qword ww = val[r[i]];
if (tt != uu) {
fa[tt] = uu;
ans += ww;
}
}
cout << ans << endl;
}
齿轮
裸地DFS
这是一个图论问题，图中的点表示齿轮，两个点之间有边当且仅当两个齿轮相互接触。我们知道从驱动齿轮到最终工作齿轮有唯一路径，我们需要找到路径，并且算出路径上所有齿轮的速度。我们从驱动齿轮出发，使用 BFS 或者 DFS，并在搜索过程中计算齿轮速度即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <ctime>
#include <cmath>
using namespace std;
#define rep(i,s,t) for(int i=(int)(s);i<=(int)(t);++i)
#define forn(i,n) for(int i=1;i<=(int)(n);++i)
#define pb push_back
#define seta(h, x) memset(h, x, sizeof(h))
#define fr first
#define sc second
#define N 1110
struct edge{
double x, y, r, w;
}s[N];
bool flag;
int book[N], n;
double tx, ty;
bool judge(edge a, edge b) {
double R = (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
if(R == (a.r+b.r)*(a.r+b.r)) return true;
return false;
}
void dfs(double sum, int k) {
if(flag) return ;
if(s[k].x == tx && s[k].y == ty){
printf("%d\n", (int)sum);
flag = true;
return ;
}
for(int i = 0; i < n; i++){
if(!book[i] && judge(s[i], s[k])){
book[i] = 1;
s[i].w = s[k].w*s[k].r/s[i].r;
dfs(sum+s[i].w, i);
book[i] = 0;
}
}
}
const string name = "baler";
int main() {
#ifndef OK
freopen((name + ".in").data(), "r",stdin);
freopen((name + ".out").data(), "w",stdout);
#endif // OK
int i, j, k;
seta(book, 0);
scanf("%d%lf%lf", &n, &tx, &ty);
for(i = 0; i < n; i++){
s[i].w = 0;
scanf("%lf%lf%lf", &s[i].x, &s[i].y, &s[i].r);
if(!s[i].x && !s[i].y) j = i;
}
s[j].w = 10000;
flag = false;
book[j] = 1;
dfs(10000, j);
return 0;
}