---
tags: 题解,算法
---

# 部分题解：[从入门到头秃周末休闲赛73 (F ~ I)](https://vjudge.net/contest/444713)

## F 秤 **

对w集合进行DFS，找出所有能称出来的质量集合，然后对每个不能称出来的ai求一个需要添加的w质量的集合，最后求它们的交集的最小值。

### 参考代码（C++11）

#include <iostream>
#include <set>
#include <vector>

using namespace std;

void dfs(int w[], int len, int sum, set<int>& s) {
    if (len == 0) { s.insert(sum); return; }
    dfs(w, len - 1, sum, s);
    dfs(w, len - 1, sum + w[len - 1], s);
    dfs(w, len - 1, sum - w[len - 1], s);
}

int solve(int n, int a[], int m, int w[]) {
    set<int> s, r;
    dfs(w, m, 0, s);
    for (int i = 0; i < n; ++i)
        if (s.count(a[i])) swap(a[i--], a[--n]);
    if (n == 0) return 0;
    for (auto& it : s)
        r.insert(abs(it - a[0]));
    for (int i = 1; i < n; ++i) {
        set<int> t;
        for (auto& it : s) {
            int v = abs(it - a[i]);
            if (r.count(v))
                t.insert(v);
        }
        r = move(t);
    }
    if (r.empty()) return -1;
    return *r.begin();
}

int main() {
    int n, m;
    int a[200], w[20];
    while (cin >> n >> m && n + m > 0) {
        for (int i = 0; i < n; ++i) cin >> a[i];
        for (int i = 0; i < m; ++i) cin >> w[i];
        cout << solve(n, a, m, w) << endl;
    }
    return 0;
}

以上方法不是最优，换个迭代方式可以节省2/3时间。

## G 最大矩形 ***

### 方法1

设`'#'`表示1，`'.'`表示0的话，通过观察你会发现，这个最大矩形里，假设第一行是v0，那么接下来的几行，要么是v0，要么是~v0，同样，按列算也是一样。那么，我们穷举这个最大矩形的下边界，然后以此计算相邻的两列，最高有多高满足它们是完全相等或完全相反，这样就得到一个大小为w-1的高度数组，那就变成典型的单调栈题。本题也类似01矩阵里面找最大的全0矩阵的题目。

### 方法2

通过方法1的规律做出推论，把原矩阵里，共`(h-1)*(w-1)`个2x2小矩阵，我们就来生成这个新的`(h-1)*(w-1)`矩阵，如果这个小矩阵里面1的个数是奇数，那用1表示，否则用0表示，那么原题就变成在新矩阵里找最大的全0矩阵，套模板即可。

## H 困兽斗 ***

求出所有交点，并根据线段相连成若干个平面图，这些图之间没有交点。然后，对于每个平面图，扫描出它的包围多边形（度为1的点可以在生成平面图时删去），最后就转化成判断原点在不在多边形内的问题，解法是计算这个多边形有多少次穿越x正半轴，如果是奇数次，那么原点在多边形内，否则就在多边形外。如果原点在任一多边形内，输出yes，否则输出no就可以了。

## I 树上游戏 ****

本题网上到处都是题解，直接搜索或看[这个](https://blog.csdn.net/baidu_36797646/article/details/88571722)