814D. An overnight dance in discotheque

发表于 | 分类于 |
字数统计: 1.2k | 阅读时长 ≈ 5

题面：https://codeforces.com/contest/814/problem/D

题意

给定一个坐标系，里面有$n$个圆心坐标不同，半径不同的圆。
现在需要你将这$n$个圆划分成两组。

每一组内的所有圆，
如果被覆盖奇数次，则加上这一个圆的面积。
如果被覆盖偶数次，则减去这一个圆的面积。
最后求这两部分和的最大值。

解法

树形dp

首先可以建出一个树结构来，每个结点的父节点是最小的包含它的圆，整张图就变成了一片森林。
因为需要将森林分成两个部分，容易发现，深度为奇数的圆贡献为$S$，偶数为$-S$，
于是对于每棵树分别dp，$f[i][0/1][0/1]$表示以$i$为根，01变量表示到达$i$时两棵树的深度的奇偶性。
显然，因为是树上深度相关，这两个01变量应该从根到儿子进行转移，通过枚举在i位置的选择，dp数组的求解由儿子到根进行转移。

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define ll long long
#define pi acos(-1)
using namespace std;
const int maxn = 2e3 + 10;
struct circle{
    ll x, y, r;
};
circle a[maxn];
vector<int> g[maxn];
int par[maxn];
double dp[maxn][2][2];
bool isInclude(int i, int j)
{
    if(a[i].r >= a[j].r)
        return false;
    ll dis = (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);
    return dis <= (a[i].r - a[j].r) * (a[i].r - a[j].r);
}
double S(int i)
{
    return pi * a[i].r * a[i].r;
}
void dfs(int id)
{
    double temp[2][2] = {{0}};
    for(auto e: g[id])
    {
        dfs(e);
        for(int i = 0; i <= 1; i++)
            for(int j = 0; j <= 1; j++)
                temp[i][j] += dp[e][i][j];
    }
    dp[id][0][0] = max(temp[0][1] + S(id), temp[1][0] + S(id));
    dp[id][1][0] = max(temp[0][0] - S(id), temp[1][1] + S(id));
    dp[id][0][1] = max(temp[0][0] - S(id), temp[1][1] + S(id));
    dp[id][1][1] = max(temp[0][1] - S(id), temp[1][0] - S(id));
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i].x >> a[i].y >> a[i].r;
    double ans = 0;
    for(int i = 0; i < n; i++){//找出i的父结点
        par[i] = -1;
        for(int j = 0; j < n; j++){
            if(isInclude(i, j)){
                if(par[i] == -1 || a[par[i]].r > a[j].r)
                    par[i] = j;
            }
        }
        if(par[i] != -1)
            g[par[i]].push_back(i);
    }
    for(int i = 0; i < n; i++)
    {
        if(par[i] == -1)
        {
            dfs(i);
            ans += dp[i][0][0];
        }
    }
    cout << setprecision(10) << ans << endl;
    return 0;
}

贪心

其实这里存在着贪心解。大圆包含小圆的状态下，大圆取或不取的结果比剩下小圆里所有子圆的影响都要大。
这棵树肯定包括很多层,每一层都有几个节点,但是每一层的圆的面积和肯定是没有上一层大的.
故此可以贪心.
那么很显然第一层的圆的面积肯定要加上去,第二层也要.
第三层开始不管放在哪里面积都要减掉,随便选择一个.
而第四层开始不能放在与第三层相异的一边,否则会被减掉,而后面不管怎么加都没有第四层面积大,所以第四层要和第三层放在一起.
而第五层和第六层也要放在一起……等等等等.
所以只需要贪心的取尽可能大的圆就好了。
所以预处理出每个圆被覆盖的次数。
最后把被覆盖次数度为0和奇数的圆的面积全部加起来,减掉覆盖次数为正偶数的圆的面积即为答案.

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
#include <bits/stdc++.h>
#define ll long long
#define pi acos(-1)
using namespace std;
const int maxn = 2e3 + 10;
struct circle{
    ll x, y;
    ll r;
};
circle a[maxn];
int deg[maxn];
bool isInclude(int i, int j)
{
    if(a[i].r > a[j].r)
        return false;
    ll dis = (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);
    return dis <= (a[i].r - a[j].r) * (a[i].r - a[j].r);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i].x >> a[i].y >> a[i].r;
    double ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(isInclude(i, j))
                deg[i]++;
            if(isInclude(j, i))
                deg[j]++;
        }
    }
    for(int i = 0; i < n; i++)
    {
        if(deg[i] % 2 || !deg[i])
            ans += pi * a[i].r * a[i].r;
        else
            ans -= pi * a[i].r * a[i].r;
    }
    cout << setprecision(10) << ans << endl;
    return 0;
}