首页 > ACM题库 > HDU-杭电 > HDU 1119 Simple Algorithmetics-线段树-[解题报告] C++
2013
11-27

HDU 1119 Simple Algorithmetics-线段树-[解题报告] C++

Simple Algorithmetics

问题描述 :

One part of the new WAP portal is also a calculator computing expressions with very long numbers. To make the output look better, the result is formated the same way as is it usually used with manual calculations.
Your task is to write the core part of this calculator. Given two numbers and the requested operation, you are to compute the result and print it in the form specified below. With addition and subtraction, the numbers are written below each other. Multiplication is a little bit more complex: first of all, we make a partial result for every digit of one of the numbers, and then sum the results together.

输入:

There is a single positive integer T on the first line of input. It stands for the number of expressions to follow. Each expression consists of a single line containing a positive integer number, an operator (one of +, – and *) and the second positive integer number. Every number has at most 500 digits. There are no spaces on the line. If the operation is subtraction, the second number is always lower than the first one. No number will begin with zero.

输出:

For each expression, print two lines with two given numbers, the second number below the first one, last digits (representing unities) must be aligned in the same column. Put the operator right in front of the first digit of the second number. After the second number, there must be a horizontal line made of dashes (-).For each addition or subtraction, put the result right below the horizontal line, with last digit aligned to the last digit of both operands.

For each multiplication, multiply the first number by each digit of the second number. Put the partial results one below the other, starting with the product of the last digit of the second number. Each partial result should be aligned with the corresponding digit. That means the last digit of the partial product must be in the same column as the digit of the second number. No product may begin with any additional zeros. If a particular digit is zero, the product has exactly one digit — zero. If the second number has more than one digit, print another horizontal line under the partial results, and then print the sum of them.

There must be minimal number of spaces on the beginning of lines, with respect to other constraints. The horizontal line is always as long as necessary to reach the left and right end of both numbers (and operators) right below and above it. That means it begins in the same column where the leftmost digit or operator of that two lines (one below and one above) is. It ends in the column where is the rightmost digit of that two numbers. The line can be neither longer nor shorter than specified.

Print one blank line after each test case, including the last one.

样例输入:

4
12345+67890
324-111
325*4405
1234*4

样例输出:

 12345
+67890
------
 80235

 324
-111
----
 213

    325
  *4405
  -----
   1625
     0
 1300
1300
-------
1431625

1234
  *4
----
4936

终于做到了这部分,以前看到这种类型的题只能直接放弃的,现在终于AC了第一个这种题

因为坐标都是浮点数,所以需要对坐标进行离散化(需要插入线段树的坐标进行离散化),为了方便,我直接用了map

将每个矩形的上下两条水平边存到数组中(得记录这条边是下边还是上边,为了计算覆盖次数,下边记为1,上边记为-1),按y的大小排序;从y最小的边开始向上扫描,首先将一条边插入线段树,然后得到当前当前扫描线所在位置的覆盖到的边的总长,                                                                                                  

第一次是A1B1边插入到书中,扫描线覆盖到的边的总长就是A1B1,再拿他乘以当前高度和下一条边的高度差,得到底下那个矩形的面积

第二次是第二条黑边插入线段树,这时扫描到的总长度为A2B2,再拿他乘以当前高度和下一条边的高度差,得到中间那个长矩形的面积

第三次是A1B1的对边插入线段树,因为这条边是上边,所以覆盖次数会被-1,挺次,原先线段树中被A1B1覆盖的部分会被-1,所以,此时线段树中能够计算得到扫面线扫到的总长为A3B3的长度,再拿他乘以当前高度和下一条边的高度差,得到最上面那个矩形的面积

三者相加就是总面积了

插入的时候也得注意,不是根据坐标计算出其离散值就当做区间直接插入,而是要将右坐标的离散值减1,这样做的原因是:

这样的两条线段其实没有相互覆盖,但是如果r不减1的话,他们就会变成彼此覆盖的了……在这颗线段树中,一个点其实表示一个区间

这么做了以后,在计算时只要再把r加上1就好了

以下是代码:

#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
const int MAX = 210;
struct line
{
    double l,r,h;
    int f;
    line(){}
    line(double a,double b,double c,int d):l(a),r(b),h(c),f(d){}
}a[MAX<<1];
double sum[MAX<<2],x0[MAX];
int cov[MAX<<2];
map<double,int>m;
int cmp(const line &a,const line &b)
{
    return a.h<b.h;
}
void push_up(int l,int r,int rt)
{
    if(cov[rt]) sum[rt] = x0[r+1] - x0[l];
    else if(l==r) sum[rt]=0;
    else sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void update(int c,int L,int R,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        cov[rt]+=c;
        push_up(l,r,rt);
        return;
    }
    int mid = r+l>>1;
    if(L<=mid) update(c,L,R,l,mid,rt<<1);
    if(R>mid) update(c,L,R,mid+1,r,rt<<1|1);
    push_up(l,r,rt);
}
int main()
{
    int n;
    double x1,x2,y1,y2;
    int cas = 0;
    while(scanf("%d",&n)&&n)
    {
        int cnt = 0;
        int flag = 0;

        for(int i=0; i<n; i++)
        {
            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
            a[cnt++] = line(x1,x2,y1,1);
            a[cnt++] = line(x1,x2,y2,-1);
            if(m[x1]==0) m[x1] = ++flag;
            if(m[x2]==0) m[x2] = ++flag;
        }
        map<double,int>::iterator iter;
        int k = 0;
        for(iter=m.begin(); iter!=m.end(); iter++)
        {
            x0[++k] = iter->first;
            iter->second = k;
        }
        sort(a,a+cnt,cmp);
        double ans = 0;
        memset(sum,0,sizeof(sum));
        memset(cov,0,sizeof(cov));
        for(int i=0; i<cnt-1; i++)
        {
            int l = m[a[i].l];
            int r = m[a[i].r]-1;
            update(a[i].f,l,r,1,flag,1);
            ans+=(a[i+1].h-a[i].h)*sum[1];
        }
        printf("Test case #%d\n",++cas);
        printf("Total explored area: %.2lf\n\n",ans);
        m.clear();
    }
    return 0;
}

  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

  3. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  4. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测