【九校3D2T3】世界第一的猛汉王-白红宇

【九校3D2T3】世界第一的猛汉王

阅读量：7097 次

发布时间：2019-06-28

本文共 1728 字，大约阅读时间需要 5 分钟。

【问题描述】

卡普地公司举办了「世界第一的猛汉王」全球大会，来自世界各地的猛汉为了争夺「猛汉王」的名号前来一决高下。现在举行的是弓箭组选拔赛。卡普地公司为比赛新建了一张PVP地图——「猛汉竞技场」。有许多使用弓的猛汉在这里互相较量。他们中的一些装填了「接击瓶」，这使得他们在接近战中会占有一定优势，但是在远程战中会相当劣势。具体来说如下：

假设q装填了「接击瓶」而p没有，则当他们的曼哈顿距离大于D时，p压制q，反之q压制p。如果p和q都装填了「接击瓶」或者都没有，则他们之间仍然会存在一个客观上的单向压制关系，但是在比赛刚开始时无法得知。

竞技场上一共有n+m个猛汉，其中n个装填了「接击瓶」，另外m个没有。每个猛汉降临到竞技场时有一个坐标(x, y)。Mark Douglas作为上一届的猛汉王正在观看这场比赛，他希望得知场上有多少个「猛汉三角」。「猛汉三角」是指三个人u、v、w满足u压制v，v压制w，w压制u，且三人中至少有一人装填了「接击瓶」且至少有一人没有。由于场上尚存在一些不明了的压制关系，所以Mark希望知道可能的「猛汉三角」数量的最小值和最大值。

【输入格式】

输入文件名为mhw.in。

输入第一行为三个正整数n m D。

接下来n行每行两个正整数x y，表示装填了「接击瓶」的猛汉的坐标。

接下来m行每行两个正整数x y，表示没有装填「接击瓶」的猛汉的坐标。

可能有多个猛汉站在同一个位置。

【输出格式】

输出文件名为mhw.out。

输出两个数min max，表示答案的最小值和最大值。

【样例输入与输出】

example_mhw1.in

example_mhw1.out

2 2 1

1 2

1 1

3 1

2 2

0 2

难度确实大！

首先我们将猛汉们分为两个阵营（记为黑色与白色）。我们一个猛汉三角就是形如a->c->b（a，b同阵营），然后在确定a,b之间的压制关系得到最小或者最大值。

我们以白色阵营为例。我们设cover[v]为v压制的对方阵营的数量，cover[v,u]为v,u共同压制的对方阵营的数量。 $minans=\sum min\left \{ cover[v]-cover[v,u] \right cover[u]-cover[v,u]\},$ maxans同理。

$minans=\sum min\left \{ cover[v] \right cover[u]\}-\sum cover[v,u]$ 。对于cover[v,u]，我们就算另一方阵营对 $\sum cover[v,u]$ 的贡献就行了。如果一个猛汉被对面的k个人压制，那么他对 $\sum cover[v,u]$ 的贡献就是 $\frac{k*(k-1)}{2}$ 。

求cover数组可以用扫描+线段树。

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              #include
              
               #define ll long long#define N 100005using namespace std;inline ll Get() {ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') { if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}ll n,m,lim;ll mn,mx;ll cc;ll d[N*6];ll cnt;ll c[2][N];struct line { ll x,op,col,id; ll l,r; bool operator <(const line &a)const { if(x!=a.x) return x
               
                >1; build(v<<1,l,mid),build(v<<1|1,mid+1,r);}void Modify(ll v,ll l,ll r,ll tag,ll f) { if(tr[v].l>r||tr[v].r
                
                 pos||tr[v].r

转载于:https://www.cnblogs.com/hchhch233/p/9996736.html

你可能感兴趣的文章