当前位置: 首页 > 工具软件 > Cosmetic > 使用案例 >

2018 ACM ICPC Asia Regional - Seoul B.Cosmetic Survey

令狐宣
2023-12-01

参考大佬代码

题目大意

n n n个顾客, m m m种画妆品,每一个顾客会给 m m m种化妆品一个值,这个值代表这个化妆品在他心中的排名,排名越小越喜欢,如果这个值为0说明最不喜欢这一种化妆品(值为0理解为无穷大)

现在定义 d ( x , y ) d(x,y) d(x,y)表示第 x x x种化妆品和第 y y y种化妆品之间,喜欢第 x x x种化妆品的人数

定义一个序列 C 1 , C 2 , C 3 , … , C k C_1,C_2,C_3,\dots,C_k C1,C2,C3,,Ck,其中保证 d ( C i , C i + 1 ) > d ( C i + 1 , C i ) d(C_i,C_{i+1})>d(C_{i+1},C_i) d(Ci,Ci+1)>d(Ci+1,Ci),而这个路径有一个值(序列值)代表 d ( C t , C t + 1 ) , 1 ≤ t < k d(C_t,C_{t+1}),1\leq t<k d(Ct,Ct+1),1t<k的最小值。

定义 S ( x , y ) S(x,y) S(x,y),对于上述所有序列 C 1 = x C_1=x C1=x C k = y C_k=y Ck=y即以 x x x为开头, y y y结尾的序列中,序列值的最大值

如果对于一个化妆品 x x x来说的 S ( x , i ) ≥ S ( i , x ) , ( 1 ≤ i ≤ m , i ≠ x ) S(x,i)\ge S(i,x),(1\leq i\leq m,i\ne x) S(x,i)S(i,x),(1im,i=x)对于上述条件的 i i i都成立,那么它就是“好”的化妆品。

现在求出所有“好”化妆品的编号?

首先暴力求出 d ( i , j ) d(i,j) d(i,j),然后floyd暴力求出 S ( i , j ) = m a x ( S ( i , j ) , m i n ( d ( i , k ) , d ( k , j ) ) ) S(i,j)=max(S(i,j),min(d(i,k),d(k,j))) S(i,j)=max(S(i,j),min(d(i,k),d(k,j)))
最后暴力比较求出答案。

#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<random>
#include<bitset>
#include<string>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=510;
int n,m;
int a[N][N],d[N][N];
int main()
{
    IO;
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>m>>n;
        for(int i=1;i<=n;i++)   
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
                if(a[i][j]==0) a[i][j]=1e8;
            }
        for(int i=1;i<=m;i++)   
            for(int j=i+1;j<=m;j++)
            {
                for(int k=1;k<=n;k++)
                {
                    if(a[k][i]<a[k][j]) d[i][j]++;
                    if(a[k][i]>a[k][j]) d[j][i]++;
                }
                int x=d[i][j],y=d[j][i];
                if(x>=y) d[j][i]=0;
                if(y>=x) d[i][j]=0;
            }
        for(int k=1;k<=m;k++)   
            for(int i=1;i<=m;i++)
                for(int j=1;j<=m;j++)
                {
                    if(!d[i][k]||!d[k][j]) continue;
                    d[i][j]=max(d[i][j],min(d[i][k],d[k][j]));
                }
        vector<int> ans;
        for(int i=1;i<=m;i++)
        {
            bool ok=1;
            for(int j=1;j<=m;j++)
            {
                if(i==j) continue;
                if(d[i][j]<d[j][i]) ok=0;
            }
            if(ok) ans.push_back(i);
        }
        for(auto t:ans) cout<<t<<' ';
        cout<<'\n';
    }
    return 0;
}

总结:首先需要暴力理解题意

 类似资料:

相关阅读

相关文章

相关问答