做的时候觉得这套题好简单，结果一看发现是2012年的模拟题，估计就是普及+的难度吧，AK无压力

总结

1. 第一题状压我智障的调了好几分钟，因为我的最终状态写的1<<n,智障了
2. 第三题的dfs调了一会,也是有点难受的
3. 吸取之前的教训,把开文件模板化了,方便检查

混乱的队伍

状压DP,注意开long long

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           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 secondtypedef long long qword;const int maxn = 20;const string task = "mixup2";qword f[1<
           
            > N >> K; forn(i, N) cin >> s[i]; forn(i, N) f[1<<(i-1)][i] = 1; // Init int LastSituation = (1<
            
              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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           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 secondtypedef 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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           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 1110struct 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;}