2018 ACM ICPC Asia Regional - Seoul B.Cosmetic Survey

参考大佬代码

题目大意

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

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

定义一个序列$C_1,C_2,C_3,\dots ,C_k$，其中保证$d(C_i,C_{i+1})>d(C_{i+1},C_i)$，而这个路径有一个值（序列值）代表$d(C_t,C_{t+1}),1\le t<k$的最小值。

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

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

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

首先暴力求出$d(i,j)$，然后floyd暴力求出$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;
}

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