P8585 球状精灵的传说 题解

bloodstalk · 2022-10-16 15:28:03 · 题解

update：修改了一下 \LaTeX

很好的一个题

题意

给你 n 个三元组 (r_1,r_2,r_3) , 并定义 ρ = \lfloor \frac{1}{4}min(r_1,r_2,r_3)^3 \rfloor 。

两个三元组能合并当且仅当这两个三元组有至少两个值相同，即从 (x_1,y,z) 和 (x_2,y,z) 变为 (x_1+x_2,y,z) 。(x,y,z)的位置不固定，可以变为 (x,z,y) 等很多种。一个三元组最多只能合并一次。

询问 ρ 最大为多少，并且询问是合并后形成的还是不合并形成的，再询问他们的编号。

，1 \leq r_{i,1},r_{i,2},r_{i,3} \leq 10^3 。

思路

贪心

• 首先，我们可以知道， ρ 的值只跟三元组中最小的一个数有关。

  因此，如果我们要合并， x_1,x_2 却不是他们所在的三元组中最小的那一个数，那么他们合并也毫无意义，因为最后还是看最小的那一个数。所以我们先给每个三元组自身从小到大排一下序。

• 再者，有了这个条件后，我们想一想：

  1.如果有多组(\geq 2)三元组的后两个元素相等，那么可以很轻松的想出，合并肯定是比不合并优的。

  2.如果有多组三元组的后两个元素相等，我们应贪心的选取最大的两个 x 值进行合并，因此，我们只需要维护最大的两个值就可以了。

• 有了基本思路后我们看一看数据范围 ：1 \leq r_{i,1},r_{i,2},r_{i,3} \leq 10^3 ，完全可以进行 O(r^2) 枚举！

因此，思路就出来了：mp[i][j][1],mp[i][j][2] 表示三元组后两个元素分别是 i,j 时，第一个元素的最大值和次大值，我们只需要对这两个值进行维护即可。 cnt[i][j] 存储后两个元素分别是 i,j 时一共有多少个三元组，id[i][j] 则存储它们的编号。

特殊地，如果我们最后枚举的时候进行合并 ，x_1+x_2 的值加起来要大于 i , 那么最小值就是 i 而不是 i+j ，不要漏掉这种情况。

不懂的看一看代码理解一下吧。

代码实现

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define next nxt
#define re register
#define il inline
const int N = 1e3 + 5;
const int M = 5e5 + 5; 
using namespace std;
int max(int x,int y){return x > y ? x : y;}
int min(int x,int y){return x < y ? x : y;}

int mp[N][N][3],cnt[N][N],id[N][N][3];
struct node{
    int x,y,z,id;
}a[M];
int n,s1,s2;

il int read()
{
    int f=0,s=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f |= (ch=='-');
    for(; isdigit(ch);ch=getchar()) s = (s<<1) + (s<<3) + (ch^48);
    return f ? -s : s;
}

il bool mysort(node a,node b) { return a.x > b.x; }

signed main()
{
    n = read();
    int ans = 0 , op = 0;
    for(re int i=1;i<=n;i++)
    {
        a[i].id = i;
        a[i].x = read() , a[i].y = read() , a[i].z = read();
        if(a[i].x > a[i].y) swap(a[i].x,a[i].y);
        if(a[i].x > a[i].z) swap(a[i].x,a[i].z);
        if(a[i].y > a[i].z) swap(a[i].y,a[i].z);/*给三元组排序*/
        int x = a[i].x , y = a[i].y , z = a[i].z;/*如果 cnt[i][j] 存储的还不到2，直接加入进去就行*/
        if(cnt[y][z] == 0 || cnt[y][z] == 1) mp[y][z][++cnt[y][z]] = x , id[y][z][cnt[y][z]] = i;
        else
        {/*cnt[i][j]为2了，我们就需要维护最大值和次大值*/
            if(mp[y][z][1] > mp[y][z][2]) swap(mp[y][z][1],mp[y][z][2]) , swap(id[y][z][1],id[y][z][2]);/*把小的交换到前面*/
            if(x > mp[y][z][1]) mp[y][z][1] = x , id[y][z][1] = i;
        }
    }
    //cout << mp[963][991][1] << " " << mp[963][991][2] << endl;
    for(re int i=1;i<=1000;i++)
        for(re int j=i;j<=1000;j++)
        {
            if(cnt[i][j] == 0) continue;
            if(cnt[i][j] == 1)/*只有一个元素，直接判断就行*/
            {
                if(ans < mp[i][j][1]) ans = mp[i][j][1] , op = 0 , s1 = id[i][j][1];
            }
            if(cnt[i][j] == 2)
            {
                if(mp[i][j][1] + mp[i][j][2] > i) /*特殊情况，最小值是i而不是x1+x2的时候*/
                {
                    if(ans < i) ans = i , op = 1 , s1 = id[i][j][1] , s2 = id[i][j][2];
                }
                else
                {
                    if(ans < mp[i][j][1] + mp[i][j][2]) ans = mp[i][j][1]+mp[i][j][2] , op = 1 , s1 = id[i][j][1] , s2 = id[i][j][2];
                }
            }
        }
    if(op == 0) cout << op << "\n" << s1 << "\n" << (ans*ans*ans)/4;
    else cout << op << "\n" << min(s1,s2) << " " << max(s1,s2) << "\n" << (ans*ans*ans)/4;/*愉快的输出*/
    /*cout << a[288].x << " " << a[288].y  << " " << a[288].z << endl;
    cout << a[727].x << " " << a[727].y  << " " << a[727].z;*/
    return 0;
}

时间复杂度 \Theta(r^2) ,可以通过。

自认为写的很详细了，有什么问题可以在评论区问。