题解：P11372 加训

WsW_ · 2024-12-02 17:58:26 · 题解

前言

上位黄，非 STL 的模拟题。

思路

对于每个教练，其他教练对他来说都相当于障碍，所以在输入教练的时候直接把所有教练同时加到障碍里面。

对于每个教练，我们考虑他能发现几个人在摸鱼。
因为只有 k 个维度，所以每个教练最多只能往 2k 个方向看。因为往每个方向看的时候，只能看见离自己最近的人，所以最多只能发现 2k 个人在摸鱼。

首先预处理出每个方向上里教练最近的障碍。
接着，对于每个学生，判断他在这个方向上到教练的距离是不是比障碍到教练的距离更近。如果不是，那不用管这个学生；如果是，那么这个学生成了这个方向上新的障碍，且这个方向上离教练最近的是学生。
以上过程中记得判断障碍或学生是不是有且仅有 k-1 维和教练不同。

最后统计有几个方向上离教练最近的是学生即可。

时间复杂度 O\left(y(m+x+y)\times k\right)。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int n,k,m,x,y;
int a[maxn][5],b[2*maxn][5],c[maxn][5];
int tag[2][5];//存储每个方向上到教练最近的障碍
bool vis[2][5];//标记每个方向上到教练最近的是不是学生

void work(int p){
    int ans=0;
    memset(tag[0],0,sizeof(tag[0]));
    memset(tag[1],0x7f,sizeof(tag[1]));
    memset(vis,0,sizeof(vis));//初始化

    for(int i=1;i<=x;i++){//预处理障碍
        int scnt=0,dif=-1;//scnt记录有几个维度不同；dif记录不同的是哪个维度
        for(int j=1;j<=k;j++){
            if(b[i][j]!=c[p][j])dif=j;
            else scnt++;
        }
        if(scnt!=k-1)continue;//不满足，直接跳过
        if(b[i][dif]<c[p][dif])tag[0][dif]=max(tag[0][dif],b[i][dif]);
        else tag[1][dif]=min(tag[1][dif],b[i][dif]);
    }

    for(int i=1;i<=m;i++){//对每个学生进行处理
        int scnt=0,dif=-1;
        for(int j=1;j<=k;j++){
            if(a[i][j]!=c[p][j])dif=j;
            else scnt++;
        }
        if(scnt!=k-1)continue;
        if(a[i][dif]<c[p][dif]&&a[i][dif]>tag[0][dif]){
            tag[0][dif]=a[i][dif];
            if(!vis[0][dif]){
                ans++;
                vis[0][dif]=1;
            }
        }
        if(a[i][dif]>c[p][dif]&&a[i][dif]<tag[1][dif]){
            tag[1][dif]=a[i][dif];
            if(!vis[1][dif]){
                ans++;
                vis[1][dif]=1;
            }
        }
    }
    cout<<ans<<' ';//遍历vis，求其中有几个1也可
}

int main(){
    cin>>n>>k>>m>>x>>y;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=k;j++)
            cin>>a[i][j];
    for(int i=1;i<=x;i++)
        for(int j=1;j<=k;j++)
            cin>>b[i][j];
    for(int i=1;i<=y;i++)
        for(int j=1;j<=k;j++){
            cin>>c[i][j];
            b[x+i][j]=c[i][j];//教练相当于障碍
        }
    x+=y;//障碍数要加上教练数
    for(int i=1;i<=y;i++)
        work(i);
    return 0;
}