YL 模拟赛总结 13

Problem

T1

略。

T2

略。

T3

考虑对于每一头向北的牛，计算它能够挡住 / 被挡住几头向东的牛。

一头向北的牛 \(i\) 能够被向东的牛 \(j\) 挡住的条件是：

• \(x_i<x_j\) 且 \(y_i<y_j\)（\(x_i,y_i\) 分别表示牛 \(i\) 的 \(x\) 坐标与 \(y\) 坐标）；

• \(l_j\) 没有被更新（\(l_i\) 表示第 \(i\) 头牛吃的草的数量），因为如果 \(l_j\) 已经被更新则说明它已被另一头向北的牛挡住。

若牛 \(i\) 满足上述条件，则更新 \(l_i\) 为 \(\min(l_i,y_j-y_i)\)。

一头向北的牛 \(i\) 能够挡住向东的牛 \(j\) 的条件是：

• \(x_i<x_j\) 且 \(y_i<y_j\)；

• \(x_j-x_i>y_i-y_j\)；

• \(l_i+y_i \ge y_j\)。

若牛 \(i\) 满足上述条件，则更新 \(l_j\) 为 \(\min(l_j,x_j-x_i)\)。

完结撒花~

#include<bits/stdc++.h>
using namespace std;

int n;
struct node{
    int x,y,z,d,l;
}a[131];
int id[131];

bool cmp(int u,int v){
    return a[u].x<a[v].x;
}

int main(){
    cin>>n;
    char c;
    for(int i=1;i<=n;i++) 
        cin>>c>>a[i].x>>a[i].y,
        a[i].z=a[i].x+a[i].y,
        a[i].d=(c=='N'),
        a[i].l=1e9,
        id[i]=i;
    sort(id+1,id+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(a[id[i]].d){
            for(int j=1;j<i;j++)
                if(!a[id[j]].d&&a[id[j]].z>a[id[i]].z&&a[id[j]].l==1e9)
                    a[id[i]].l=min(a[id[i]].l,a[id[j]].y-a[id[i]].y);
            for(int j=1;j<i;j++)
                if(!a[id[j]].d&&a[id[j]].z<a[id[i]].z&&a[id[i]].y<a[id[j]].y&&a[id[i]].l+a[id[i]].y>=a[id[j]].y)
                    a[id[j]].l=min(a[id[j]].l,a[id[i]].x-a[id[j]].x);
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i].l==1e9) cout<<"Infinity\n";
        else cout<<a[i].l<<'\n';
    }
    return 0;
}

T4

略。