E. Careful Maneuvering

题目链接

Codeforces Round #488 by NEAR (Div. 2)--E. Careful Maneuvering

题解

中档题。题意大概是在x=100与x=-100处有多架敌机,我方在x=0处有两架小飞机,敌机会在同一时刻同时向两家小飞机发动攻击,求最大可摧毁的敌机数量。
枚举每一点敌机击落情况,使用bitset找出和最大的两个位置即可。

代码

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

vector<int> l;
vector<int> r;
int q1, q2, m, n, ans;
vector<bitset<125>>des;
set<bitset<125>>same;
bitset<125>temp;

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> q1;
        l.push_back(q1 * 2);
    }
    sort(l.begin(), l.end());
    for (int i = 0; i < m; i++) {
        cin >> q1;
        r.push_back(q1 * 2);
    }
    sort(r.begin(), r.end());
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int now = (l[i] + r[j]) / 2;
            temp.reset();
            for (int k = 0; k < n; k++) {
                for (q2 = 0; q2 < m; q2++) {
                    if (r[q2] == now + now - l[k]) {
                        temp.set(k);
                        temp.set(q2 + 60);
                    };
                }
            }
            des.push_back(temp);
        }
    }
    for (auto i : des) {
        for (auto j : des) {
            temp = i | j;
            ans = max(ans, (int)temp.count());
        }
    }
    cout << ans;
}

标签: brute force, geometry, bitmasks

添加新评论