7-1 懂的都懂

（分数 20）
众所周知，在互联网上有很多话是不好直接说出来的，不过一些模糊的图片仍然能让网友看懂你在说什么。然而对这种言论依然一定要出重拳，所以请你实现一个简单的匹配算法。

现在我们采集了原图的一些特征数据，由 N 个小于 255 的非负整数组成，假设对于给定的若干张由 M
i
​
个同样小于 255 的非负整数组成的新图的特征数据，每个数据都可以由原图中任意四个不同数据的平均值计算而来，则称新图为原图的相似图片。对于给出的数据，请你判断是不是相似图片。

注意，不同数据指的并非是数据的值不同，而是不能取同一个数据多次。对于两个相同值的数据，如果给出两次，则可以取两次。

输入格式:
输入第一行是两个整数 N,K (1 ≤ N ≤ 50, 1 ≤ K ≤ 200)，表示采集的原图的特征数据个数和新图的张数。

接下来一行为 N 个小于 255 的非负整数，表示原图的特征数据。

最后的 K 行，每行第一个数是 M
i
​
(1 ≤ M
i
​
≤ 200)，表示新图的特征数据个数。然后是 M
i
​
个小于 255 的非负整数，表示新图的特征数据。

输出格式:
对于每一张新图，如果为相似图片，则在一行中输出 Yes，否则输出 No。

输入样例:
5 3
4 8 12 20 40
3 11 16 19
3 12 16 19
10 11 11 11 11 11 11 11 11 11 11
输出样例:
Yes
No
Yes
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB

思路 ：

• 用原图的特征值得出所有合法的平均值，再依次判断每次的图中每个数
• dfs枚举有两种方式；第一种：将50个特征值枚举一遍，每次枚举选或者不选，等到选了四个return，这样是$4^{50}$；第二种：枚举四个数分别选什么，这样是$50^4$；因此，选后者
• 还要注意算出的平均值可能非整数，这种舍弃

#include <iostream>
using namespace std;
const int N = 55, INF = 1e6;

int n, k;
int a[N];
bool st[INF];
bool vis[N];

void dfs(int u, int sum) {
    if (u == 5) {
        if (sum % 4 == 0) {
            st[sum / 4] = true;
        }
        return ;
    }
    for (int i = 1; i <= n; ++ i) {
        if (!vis[i]) {
            vis[i] = true;
            dfs(u + 1, sum + a[i]);
            vis[i] = false;
        }
    }
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++ i) {
        cin >> a[i];
    }
    dfs(1, 0);
    while (k -- ) {
        int m;
        cin >> m;
        bool ok = true;
        for (int i = 0; i < m; ++ i) {
            int x;
            cin >> x;
            if (!st[x]) {
                ok = false;
            }
        }
        if (ok) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

7-2 芬兰木棋

（分数 25）
芬兰木棋（Mölkky，又称芬兰木柱）是源自芬兰的一项运动。哲哲将这个运动改造成了赛博朋克单人版，现在场上一开始有 N 根立起的小木棋（上面分别标有一个非负整数），哲哲投掷一根大木棋去击倒这些小木棋以获得分数。分数规则如下：

如果仅击倒 1 根木棋，则得木棋上的分数。
如果击倒 2 根或以上的木棋，则只得击倒根数的分数。（例如击倒 5 根，则得 5 分。）
哲哲固定站在 (0,0) 点上，四周放着若干个小木棋 (X
i
​
,Y
i
​
)，坐标均为整数。每次哲哲可以朝一个方向扔出大木棋，大木棋会打倒这个方向上离哲哲最近的 k 个小木棋。哲哲游戏水平很高超，所以这个 k 可以自由控制。

请问哲哲最多能拿多少分，在获得最多分数的情况下最少需要扔出多少次大木棋？

规则与真实规则有较大出入，真实游玩时请以国际莫尔基组织的规则为准

输入格式:
输入第一行是一个正整数 N (1 ≤ N ≤ 10
5
)，表示场上一开始有 N 个木棋。

接下来 N 行，每行 3 个整数 X
i
​
,Y
i
​
,P
i
​
，分别表示木棋放置在 (X
i
​
,Y
i
​
)，木棋上的分数是 P
i
​
。坐标在 32 位整数范围内，分数为小于等于 1000 的正整数。

保证 (0,0) 点没有木棋，也没有木棋重叠放置。

输出格式:
输出一行两个数，表示最多分数以及获得最多分数最少需要投掷大木棋多少次。

输入样例:
11
1 2 2
2 4 3
3 6 4
-1 2 2
-2 4 3
-3 6 4
-1 -2 1
-2 -4 1
-3 -6 1
-4 -8 2
2 -1 999
输出样例:
1022 9
代码长度限制
16 KB
Java (javac)
时间限制
1800 ms
内存限制
256 MB
Python (python3)
时间限制
800 ms
内存限制
64 MB
Python (python2)
时间限制
800 ms
内存限制
64 MB
其他编译器
时间限制
400 ms
内存限制
64 MB

题意：

• 如果击倒一根，获得这根上的分数；如果击倒大于等于两根，则击倒的根的分数等于1，累加；
• 每次可以控制同一个方向上，从近到远的 任意数量 的根数
• 无限次，问最大分数，以及最大分数下的最小次数

思路 ：

• 如果击倒大于等于2根，击倒的所有分数都变成了1，因此大于1的最好是一根拿，等于1怎么拿对分数无影响，在最大分数情况下，最好是多根拿；因此，最大分数就是所有和
• 最小次数，按方向枚举，因此用到map；不是连续的1就单独拿
• 排序时，由于只需要保证不是连续的1就单独拿，因此其实从近到远和从远到近是等价的，因此，我们将方向作为枚举依据，不需要考虑象限，直接从最左边到最右边
• 注意斜率方向double
• 道理我都懂，为什么在同一个方向上，x相同，y还会不相同？？？可能是因为精度

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

struct Node {
    int x, y, v;
    bool operator< (const Node &w) const {
        return x != w.x ? x < w.x : y < w.y;
    }
};

int n;
map<double, vector<Node>> ma;

int main() {
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; ++ i) {
        int x, y, v;
        cin >> x >> y >> v;
        sum += v;
        ma[y * 1.0 / x].push_back({x, y, v});
    }
    cout << sum << ' ';
    int cnt = 0;
    for (auto x : ma) {
        vector<Node> ve = x.second;
        sort(ve.begin(), ve.end());
        for (int i = 0; i < (int)ve.size(); ++ i) {
            cnt ++ ;
            if (ve[i].v == 1) {
                int j = i;
                while (j < ve.size() && ve[j].v == ve[i].v) j ++ ;
                j -- ;
                i = j;
            }
        }
    }
    cout << cnt;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43