BZOJ 2731: [hnoi 2012]三角面积覆盖

这题开始写了一个容斥 T成沙茶了= =
想了很久还是没想到科学的算法 就查了下题解
发现所有题解都用的是一个Σ(d[i] * 2)的算法。。
就是按行扫描
先记录第i行会新出现那些三角形
开一个max_x的数组记录这个x坐标上叠着几个三角形
每到新的一行更新
把每个当前存在的三角形的当前右边界-1
如果一个x减到0当前就少了一个被覆盖的点
如果一个三角形被减没了 它就不是当前存在的三角形了
然后把当前行的三角形更新进去

各种裸啊啊。。。。。。。。。这样据说是可以80分
再加一个优化
到一行暴力去掉被覆盖的三角形
据说就能A了 = =

然后我基于这个题解的思路yy出了一个Σd[i]的算法
虽然好像看起来快不多 但是常数会小很多 至少我没加优化就A了
而且也会比较好打~

同样按行扫描
维护一个mx数组 mx[i]表示x为i的点上的覆盖最晚在什么时候消失
每加一个三角形更新下这个数组就行了
再开个数组记录在行覆盖会消失的点有几个 到时候直接减掉即可~

另外在提下骗分算法吧
随机抛点什么的 虽然是可以 但是好像几率略小啊
于是我在昨天yy了一个随机抛线算法。
拿这题说
随机一个y 画一条(minx, y)  -> (maxx, y)的线段
nlogn的计算出在这条线段上有覆盖的长度 设为l
对于这条线的期望ans就是max_s / (maxx – minx) * l
随机多条线取个平均值
这样check虽然比抛点慢了logn 但是每次相当于抛了无数个点~~~
好像挺科学的 但是没去写 说不定也可以拿几分~
————————————–
#include <cstdio>

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
#include <functional>
using namespace std;
typedef long long ll;
struct tr
{
  int x, y, d;
}a[10005];
const int maxn = 1000005;
struct line
{
  int to, next;
}li[maxn];
int n, be[maxn], tot[maxn], mx[maxn], l;
double ans;
void makeline(int fr, int to)
{
  l++;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
}
int main()
{
  freopen(“input.in”, “r”, stdin);
  freopen(“output.out”, “w”, stdout);
  cin >> n;
  int m = 0;
  for (int i = 0; i < n; i++)
  {
    cin >> a[i].x >> a[i].y >> a[i].d;
    makeline(a[i].y, i);
    if (a[i].y + a[i].d > m) m = a[i].y + a[i].d;
  }
  int la = 0;
  for (int i = 0; i <= m; i++)
  {
    ans += (la + la – tot[i]) / (double) 2;
    la -= tot[i];
    for (int j = be[i]; j; j = li[j].next)
    {
      int to = li[j].to;
      for (int k = 0; k < a[to].d; k++)
        if (mx[a[to].x + k] < i + a[to].d – k)
        {
          if (mx[a[to].x + k] <= i) la++;
          tot[mx[a[to].x + k]]–;
          tot[mx[a[to].x + k] = i + a[to].d – k]++;
        }
    }
  }
  printf(“%.1f”, ans);
  fclose(stdin);fclose(stdout);
}

 

BZOJ 2731: [hnoi 2012]三角面积覆盖》上有3条评论

发表评论