dd's site \#

Posted on In ,

题意 从n个数的数组中选出不相交的m段 求被选数的和的最大值

Max Sum 的升级版 不只是要选一段连续的了 而是选m段 思想还是类似 依旧dp

状态和状态转移方程不是很难想 在 Max Sum 这个问题中 dp[i] 表示的是以第i个数结尾的一段的 Max Sum 由于这里还有一个多少段的状态 于是这里令 dp[i][j] 表示在前 i 个数中选取 j 组 且第 i 个数在最后一组中的 Max Sum Plus Plus

那么现在对于第i个数有两种决策

1, 第 i 个数和第 i-1 个数连接成一段dp[i][j] = dp[i-1][j] + a[i]

2, 第 i 个数自己单独做一段 那么前面就需要有 j-1 段dp[i][j] = max{dp[k][j-1] | j - 1<= k < i} + a[i]

那么也就有了状态转移方程dp[i][j] = max(dp[i-1][j], max{dp[k][j-1] | j - 1<= k < i}) + a[i];

有了方程就可以写了呀 我们先不考虑复杂度问题 假设时间空间都是无限的 恩 无限的

那么很容易有下面的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 10005, INF = 1e9;
int a[N], dp[N][N];

int main()
{
    int n, m;
    while(~scanf("%d%d", &m, &n))
    {
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof dp);

        //dp[i][j] 表示前i个数第i个数被选 选j组的Max Sum Plus Plus
        //dp[i][j] = max(dp[i-1][j], max{dp[k][j-1], j - 1 <= k < i}) + a[i]
        int ans = -INF;
        for(int j = 1; j <= m; j++)
        {
            for(int i = j; i <= n; i++)
            {
                dp[i][j] = i - 1 < j ? -INF : dp[i - 1][j]; //i-1 < j时dp[i - 1][j]是没意义的
                for(int k = j - 1; k < i; ++k)
                    dp[i][j] = max(dp[i][j], dp[k][j - 1]);
                dp[i][j] += a[i];
                if(j == m) ans = max(ans, dp[i][j]);
            }
        }

        printf("%d\n", ans);
    }
    return 0;
}

可是并不是无限的呀 上面这个时间复杂度0(n/*n/*m) 空间复杂度O(n/*n) n高达1000000 简直可怕

再来看看转移方程dp[i][j] = max(dp[i-1][j],max{dp[k][j-1] | j - 1<= k < i}) + a[i];

发现更新 dp[i][j] 的时候只用到了 dp[.][j] 和 dp[.][j-1] 里面的值 也就是 dp[.][0~j-2] 都已经没用了 那也就不用存这些没用的了 也就是j只用开两维就够了 也就是所谓的滚动数组了 用 dp[.][1] 和 dp[.][0] 来轮换表示 dp[.][j] 和 dp[.][j-1] 这样空间复杂度就降到了O(n) 这是可以接受的 那么有空间优化后的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1000005, INF = 1e9;
int a[N], dp[N][2];

int main()
{
    int n, m;
    while(~scanf("%d%d", &m, &n))
    {
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof dp);

        //dp[i][j] 表示前i个数第i个数被选 选j组的Max Sum Plus Plus
        //dp[i][j] = max(dp[i-1][j], max{dp[k][j-1], j - 1 <= k < i}) + a[i]
        int ans = -INF, j0 = 0, j1 = 1;
        for(int j = 1; j <= m; j++)
        {
            for(int i = j; i <= n; i++)
            {
                //dp[i][j0]存的是dp[i][j-1]的值 dp[i][j1] 存的是dp[i][j]的值
                dp[i][j1] = i - 1 < j ? -INF : dp[i - 1][j1]; //i-1 < j时dp[i - 1][j]是没意义的
                for(int k = j - 1; k < i; ++k)
                    dp[i][j1] = max(dp[i][j1], dp[k][j0]);
                dp[i][j1] += a[i];
                if(j == m) ans = max(ans, dp[i][j1]);
            }
            swap(j0, j1); //滚动数组交换0, 1  因为这轮的j在下轮就变成j - 1了
        }

        printf("%d\n", ans);
    }
    return 0;
}

现在空间问题解决了 那么时间问题呢 来看这段代码

1
2
3
4
5
6
7
8
9
10
11
12
13
<span style="white-space:pre">	</span>for(int j = 1; j <= m; j++)
      <span style="white-space:pre">	</span>{
            for(int i = j; i <= n; i++)
            {
                //
                dp[i][j1] = i - 1 < j ? -INF : dp[i - 1][j1]; //
                for(int k = j - 1; k < i; ++k)
                    dp[i][j1] = max(dp[i][j1], dp[k][j0]); //这轮循环只比上轮多了个dp[i-1][j0]！！！
                dp[i][j1] += a[i];
                if(j == m) ans = max(ans, dp[i][j1]);
            }
            swap(j0, j1); //
        }

看注释部分！！！ 这轮只比上轮多了一个数 我还循环那么多是什么鬼 把上轮的值 ma 记录下来 这轮只用和 dp[i-1][j0] 比较一下就行了 那么就有了可以ac的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1000005, INF = 1e9;
int a[N], dp[N][2];

int main()
{
    int n, m;
    while(~scanf("%d%d", &m, &n))
    {
        for(int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof dp);

        //dp[i][j] 表示前i个数第i个数被选 选j组的Max Sum Plus Plus
        //dp[i][j] = max(dp[i-1][j], max{dp[k][j-1], j - 1 <= k < i}) + a[i]
        int ans = -INF, j0 = 0, j1 = 1;
        for(int j = 1; j <= m; j++)
        {
            int ma = dp[j - 1][j1] = -INF; //dp[j - 1][j]是没意义的
            for(int i = j; i <= n; i++)
            {
                //dp[i][j0]存的是dp[i][j-1]的值 dp[i][j1]存的是dp[i][j]的值
                ma = max(ma, dp[i - 1][j0]); //ma维护max{dp[k][j-1], j - 1 <= k < i}
                dp[i][j1] = max(dp[i - 1][j1], ma) + a[i];
                if(j == m) ans = max(ans, dp[i][j1]);
            }
            swap(j0, j1); //滚动数组交换0, 1  因为这轮的j在下轮就变成j - 1了
        }

        printf("%d\n", ans);
    }
    return 0;
}

Max Sum Plus Plus

Problem Description

Now I think you have got an AC in Ignatius.L’s “Max Sum” problem. To be a brave ACMer, we always challenge ourselves to more difficult problems. Now you are faced with a more difficult problem.
Given a consecutive number sequence S 1, S 2, S 3, S 4 … S x, … S n (1 ≤ x ≤ n ≤ 1,000,000, -32768 ≤ S x ≤ 32767). We define a function sum(i, j) = S i + … + S j (1 ≤ i ≤ j ≤ n).
Now given an integer m (m > 0), your task is to find m pairs of i and j which make sum(i 1, j 1) + sum(i 2, j 2) + sum(i 3, j 3) + … + sum(i m, j m) maximal (i x ≤ i y ≤ j x or i x ≤ j y ≤ j x is not allowed).
But I`m lazy, I don’t want to write a special-judge module, so you don’t have to output m pairs of i and j, just output the maximal summation of sum(i x, j x)(1 ≤ x ≤ m) instead. ^_^
Input

Each test case will begin with two integers m and n, followed by n integers S 1, S 2, S 3 … S n.
Process to the end of file.
Output

Output the maximal summation described above in one line.
Sample Input

1 3 1 2 3 2 6 -1 4 -2 3 -2 3
Sample Output

6 8

Hint Huge input, scanf and dynamic programming is recommended.
Author

JGShining（极光炫影）

Posted on In ,

题意 给你一些矩形框堆叠后的俯视图 判断这些矩形框的堆叠顺序 每个矩形框满足每边都至少有一个点可见 输入保证至少有一个解 按字典序输出所有可行解

和上一题有点像 只是这个要打印所有的可行方案 建图还是类似 因为每个矩形框的四边都有点可见 所以每个矩形框的左上角和右下角的坐标是可以确定的 然后一个矩形框上有其它字符时 就让这个矩形框对应的字符和那个其它字符建立一个小于关系 由于要打印方案 所以在有多个入度为0的点时需要用DFS对每种选择都进行一遍拓扑排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 50;
char ans[N], g[N][N], tp[N][N];
int x1[N], y1[N], x2[N], y2[N];
//(x1,y1)为对应字母的左上角坐标  (x2,y2)为右下
int in[N], n;

void addTopo(int i, int j, int c)
{
    int t = g[i][j] - 'A';
    if(t != c && !tp[c][t])
    {
        ++in[t];
        tp[c][t] = 1;
    }
}

void build()
{
    memset(tp, 0, sizeof(tp)); //tp[i][j] = 1表示有i < j的关系
    for(int c = n = 0; c < 26; ++c)
    {
        if(in[c] < 0) continue;
        for(int i = x1[c]; i <= x2[c]; ++i)
        {
            addTopo(i, y1[c], c);
            addTopo(i, y2[c], c);
        }
        for(int j = y1[c]; j <= y2[c]; ++j)
        {
            addTopo(x1[c], j, c);
            addTopo(x2[c], j, c);
        }
        ++n;//统计出现了多少个字符
    }
}

void topoSort(int k)
{
    if(k == n)
    {
        ans[k] = 0;
        puts(ans);
        return;
    }

    //从前往后找入度为0的点保证升序
    for(int i = 0; i < 26; ++i)
    {
        if(in[i] == 0)
        {
            ans[k] = i + 'A'; //这一位放i
            in[i] = -1;
            for(int j = 0; j < 26; ++j)
                if(tp[i][j]) --in[j];

            topoSort(k + 1); //找下一位

            in[i] = 0; //回溯
            for(int j = 0; j < 26; ++j)
                if(tp[i][j]) ++in[j];
        }
    }
}

int main()
{
    int h, w, c;
    while(~scanf("%d%d", &h, &w))
    {
        for(int i = 0; i < 26; ++i)
        {
            x1[i] = y1[i] = N;
            x2[i] = y2[i] = 0;
        }

        memset(in, -1, sizeof(in));
        for(int i = 0; i < h; ++i)
        {
            scanf("%s", g[i]);
            for(int j = 0; j < w; ++j)
            {
                if((c = g[i][j] - 'A') < 0) continue; //g[i][j] ='.'
                if(i < x1[c]) x1[c] = i;
                if(i > x2[c]) x2[c] = i;
                if(j < y1[c]) y1[c] = j;
                if(j > y2[c]) y2[c] = j;
                in[c] = 0;  //出现过的字母in初始为0  否则为-1
            }
        }
        build();
        topoSort(0);
    }
    return 0;
}

Frame Stacking

Description
Consider the following 5 picture frames placed on an 9 x 8 array.
…….. …….. …….. …….. .CCC…. EEEEEE.. …….. …….. ..BBBB.. .C.C…. E….E.. DDDDDD.. …….. ..B..B.. .C.C…. E….E.. D….D.. …….. ..B..B.. .CCC…. E….E.. D….D.. ….AAAA ..B..B.. …….. E….E.. D….D.. ….A..A ..BBBB.. …….. E….E.. DDDDDD.. ….A..A …….. …….. E….E.. …….. ….AAAA …….. …….. EEEEEE.. …….. …….. …….. …….. 1 2 3 4 5
Now place them on top of one another starting with 1 at the bottom and ending up with 5 on top. If any part of a frame covers another it hides that part of the frame below.
Viewing the stack of 5 frames we see the following.
.CCC…. ECBCBB.. DCBCDB.. DCCC.B.. D.B.ABAA D.BBBB.A DDDDAD.A E…AAAA EEEEEE..
In what order are the frames stacked from bottom to top? The answer is EDABC.
Your problem is to determine the order in which the frames are stacked from bottom to top given a picture of the stacked frames. Here are the rules:

  1. The width of the frame is always exactly 1 character and the sides are never shorter than 3 characters.
  2. It is possible to see at least one part of each of the four sides of a frame. A corner shows two sides.
  3. The frames will be lettered with capital letters, and no two frames will be assigned the same letter.

Input

Each input block contains the height, h (h<=30) on the first line and the width w (w<=30) on the second. A picture of the stacked frames is then given as h strings with w characters each.
Your input may contain multiple blocks of the format described above, without any blank lines in between. All blocks in the input must be processed sequentially.

Output

Write the solution to the standard output. Give the letters of the frames in the order they were stacked from bottom to top. If there are multiple possibilities for an ordering, list all such possibilities in alphabetical order, each one on a separate line. There will always be at least one legal ordering for each input block. List the output for all blocks in the input sequentially, without any blank lines (not even between blocks).

Sample Input

9 8 .CCC…. ECBCBB.. DCBCDB.. DCCC.B.. D.B.ABAA D.BBBB.A DDDDAD.A E…AAAA EEEEEE..

Sample Output

EDABC

Posted on In ,

题意 有一个4/*4的显示器 有9个程序 每个程序占2/*2个格子 他们的位置如图所示 当你运行某个程序时 这个程序就会显示在顶层覆盖其它的程序 给你某个时刻显示器的截图 判断此时电脑是否死机了（出现了不合法的覆盖关系）

拓扑排序的应用 关键是建图 当一个程序A的区域上有其它程序B时 说明A是在B之前运行的 那么我们可以建立一个A<B的拓扑关系 最后判断是否有环就行了 个人认为下标换为0操作起来比较方便 所以都还为了0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 10;
int g[N][N], in[N], q[N];
vector<int> e[N];

void build() //建图
{
    memset(in, 0, sizeof(in));
    for(int k = 0; k < 9; ++k)
    {
        e[k].clear();
        int i = k / 3, j = k % 3, t; //获取程序k的左上角坐标
        for(int x = 0; x < 2; ++x)
        for(int y = 0; y < 2; ++y)
        {
            t = g[i + x][j + y];
            if(t != k) //程序k在程序t之前运行 k < t
            {
                e[k].push_back(t);
                ++in[t];
            }
        }
    }
}

bool topo()
{
    build();
    int front = 0, rear = 0, cur;
    for(int i = 0; i < 9; ++i)
        if(!in[i]) q[rear++] = i;
    while(front < rear)
    {
        cur = q[front++];
        for(int i = 0; i < e[cur].size(); ++i)
        {
            int j = e[cur][i];
            if(!(--in[j])) q[rear++] = j;
        }
    }
    return front >= 9; //front < 9 时有环
}

int main()
{
    char s[100];
    while(scanf("%s", s), s[0] != 'E')
    {
        for(int i = 0; i < 4; ++i)
            for(int j = 0; j < 4; ++j)
                scanf("%d", &g[i][j]), --g[i][j];
        scanf("%s", s);
        printf("THESE WINDOWS ARE ");
        puts(topo() ? "CLEAN" : "BROKEN");
    }
    return 0;
}

Window Pains

Description
Boudreaux likes to multitask, especially when it comes to using his computer. Never satisfied with just running one application at a time, he usually runs nine applications, each in its own window. Due to limited screen real estate, he overlaps these windows and brings whatever window he currently needs to work with to the foreground. If his screen were a 4 x 4 grid of squares, each of Boudreaux’s windows would be represented by the following 2 x 2 windows:
1 1 . . 1 1 . . . . . . . . . . . 2 2 . . 2 2 . . . . . . . . . . . 3 3 . . 3 3 . . . . . . . . . . . . 4 4 . . 4 4 . . . . . . . . . . . 5 5 . . 5 5 . . . . . . . . . . . 6 6 . . 6 6 . . . . . . . . . . . . 7 7 . . 7 7 . . . . . . . . . . . 8 8 . . 8 8 . . . . . . . . . . . 9 9 . . 9 9 When Boudreaux brings a window to the foreground, all of its squares come to the top, overlapping any squares it shares with other windows. For example, if window 1 and thenwindow 2 were brought to the foreground, the resulting representation would be: 1 2 2 ? 1 2 2 ? ? ? ? ? ? ? ? ? If window 4 were then brought to the foreground: 1 2 2 ? 4 4 2 ? 4 4 ? ? ? ? ? ? . . . and so on . . .
Unfortunately, Boudreaux’s computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly. And this is where you come in . . .

Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.
A single data set has 3 components:

After the last data set, there will be a single line:
ENDOFINPUT
Note that each piece of visible window will appear only in screen areas where the window could appear when brought to the front. For instance, a 1 can only appear in the top left quadrant.

Output

For each data set, there will be exactly one line of output. If there exists a sequence of bringing windows to the foreground that would result in the graphical representation of the windows on Boudreaux’s screen, the output will be a single line with the statement:
THESE WINDOWS ARE CLEAN
Otherwise, the output will be a single line with the statement:
THESE WINDOWS ARE BROKEN

Sample Input

START 1 2 3 3 4 5 6 6 7 8 9 9 7 8 9 9 END START 1 1 3 3 4 1 3 3 7 7 9 9 7 7 9 9 END ENDOFINPUT

Sample Output

THESE WINDOWS ARE CLEAN THESE WINDOWS ARE BROKEN

Posted on In ,

题意 由一些不同元素组成的升序序列是可以用若干个小于号将所有的元素按从小到大的顺序 排列起来的序列。例如，排序后的序列为 A, B, C, D，这意味着 A < B、B < C和C < D。在本题中， 给定一组形如 A < B的关系式，你的任务是判定是否存在一个有序序列。 输出到哪一项可以确定顺序或者在这一项最先出现冲突，若所有的小于关系都处理完了都不能确定顺序也没有出现冲突，就输出不能确定

每来一个小于关系就进行一次拓扑排序 直到出现冲突（也就是出现了环）或者已经能确定顺序 当结果已经确定时 后面的小于关系也就没有必要处理了 因此可以用一个flag标记结果是否已经确定

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 30;
int n, m, in[N];
char ans[N], q[N];
vector<int> e[N];

int topoSort() //拓扑排序
{
    int d[N], ret = 1;
    memcpy(d, in, sizeof(d));
    int front  = 0, rear = 0, p = 0;
    for(int i = 0; i < n; ++i)
        if(d[i] == 0) q[rear++] = i;
    while(front < rear)
    {
        if(rear - front > 1) ret = 0; //顺序不能确定
        int cur = q[front++];
        ans[p++] = 'A' + cur;
        for(int i = 0; i < e[cur].size(); ++i)
        {
            int j = e[cur][i];
            if((--d[j]) == 0) q[rear++] = j;
        }
    }
    if(p < n) return -1; //有环
    ans[p] = 0;
    return ret;
}

int main()
{
    char a, b;
    while(scanf("%d%d", &n, &m), n || m)
    {
        for(int i = 0; i < n; ++i) e[i].clear();
        memset(in, 0, sizeof(in));
        int flag = 0;
        for(int i = 0; i < m; ++i)
        {
            scanf(" %c<%c", &a, &b);
            if(flag) continue;

            a -= 'A', b -= 'A';
            e[a].push_back(b);
            ++in[b];
            flag = topoSort();
            if(flag == 1)
                printf("Sorted sequence determined after %d relations: %s.\n", i + 1, ans);
            if(flag == -1)
                printf("Inconsistency found after %d relations.\n", i + 1);

        }
        if(!flag) puts("Sorted sequence cannot be determined.");
    }
    return 0;
}
//Last modified :  2015-08-19 13:45 CST

Sorting It All Out

Description
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.

Input

Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character “<” and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.

Output

For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined after xxx relations: yyy…y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy…y is the sorted, ascending sequence.

Sample Input

4 6 A<B A<C B<C C<D B<D A<B 3 2 A<B B<A 26 1 A<Z 0 0

Sample Output

Sorted sequence determined after 4 relations: ABCD. Inconsistency found after 2 relations. Sorted sequence cannot be determined.

Posted on In ,

题意 模拟内存申请 有n个内存单元 有以下4种操作

Reset 将n个内存单元全部清空

New x 申请一个长度为x的连续内存块 申请成功就输出左端

Free x 将x所在的内存块空间释放 释放成功输出释放的内存始末位置

Get x 输出第x个内存块的起始位置

Reset 和 New 都是基本的区间合并知识 比较简单 Free和Get需要知道内层块的位置 所以我们在New的时候要将申请的内存块的始末位置都存起来 两个内层块不会相交 这样就能通过二分找到需要的内层块了 Free后要删去对应的内存块 用vector是为了使Get操作能在O(1)时间内完成 用List的话插入删除快一些但是Get就慢了 所以随便用什么来保存被占的内层块 相对来说vector比较容易实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <cstdio>
#include <vector>
#include <algorithm>
#define lc p<<1, s, mid
#define lp p<<1
#define rc p<<1|1, mid + 1, e
#define rp p<<1|1
#define mid ((s+e)>>1)
using namespace std;
const int N = 50005;
int len[N << 2], lle[N << 2], lri[N << 2], setv[N << 2];

struct Block //内层块结构体
{
    int l, r;
    bool operator< (const Block &b) const{
        return l < b.l;
    }
} block;
vector<Block> vb;
vector<Block>::iterator it;

void pushup(int p, int s, int e)
{
    len[p] = max(len[lp], len[rp]);
    len[p] = max(len[p], lri[lp] + lle[rp]);
    lle[p] = lle[lp], lri[p] = lri[rp];
    if(lle[p] == mid - s + 1) lle[p] += lle[rp];
    if(lri[p] == e - mid)  lri[p] += lri[lp];
}

void pushdown(int p, int s, int e)
{
    if(setv[p] == -1) return;
    setv[lp] = setv[rp] = setv[p];
    len[lp] = lle[lp] = lri[lp] = setv[p] * (mid - s + 1);
    len[rp] = lle[rp] = lri[rp] = setv[p] * (e - mid);
    setv[p] = -1;
}

void build(int p, int s, int e)
{
    setv[p] = -1;
    if(s == e)
    {
        len[p] = lle[p] = lri[p] = 1;
        return;
    }
    build(lc);
    build(rc);
    pushup(p, s, e);
}

void update(int p, int s, int e, int l, int r, int v)
{
    if(l <= s && e <= r)
    {
        setv[p] = v;
        len[p] = lle[p] = lri[p] = v * (e - s + 1);
        return;
    }
    pushdown(p, s, e);
    if(l <= mid) update(lc, l, r, v);
    if(r > mid) update(rc, l, r, v);
    pushup(p, s, e);
}

int query(int p, int s, int e, int v)
{
    if(s == e) return s;
    pushdown(p, s, e);
    if(len[lp] >= v) return query(lc, v);
    if(lri[lp] + lle[rp] >= v) return mid + 1 - lri[lp];
    return query(rc, v);
}

int main()
{
    int n, m, x, p;
    char op[10];
    while(~scanf("%d%d", &n, &m))
    {
        build(1, 1, n);
        vb.clear();
        while(m--)
        {
            scanf("%s", op);

            if(op[0] == 'R') //Reset
            {
                update(1, 1, n, 1, n, 1); //用build会TLE
                vb.clear();
                puts("Reset Now");
            }

            if(op[0] == 'N')  //New
            {
                scanf("%d", &x);
                if(len[1] < x) puts("Reject New");
                else
                {
                    p = query(1, 1, n, x);
                    printf("New at %d\n", p);
                    update(1, 1, n, p, p + x - 1, 0);

                    block.l = p;
                    block.r = p + x - 1;
                    it = upper_bound(vb.begin(), vb.end(), block);
                    //找到第一个起点大于p的位置 确保插入后还是升序的
                    vb.insert(it, block);
                }
            }

            if(op[0] == 'G')  //Get
            {
                scanf("%d", &x);
                if(x > vb.size()) puts("Reject Get");
                else printf("Get at %d\n", vb[x - 1].l);
            }

            if(op[0] == 'F') //Free
            {
                scanf("%d", &x);
                block.l = block.r = x;
                it = upper_bound(vb.begin(), vb.end(), block);
                int i = it - vb.begin() - 1;
                if(i < 0 || vb[i].r < x) puts("Reject Free");
                else
                {
                    printf("Free from %d to %d\n", vb[i].l, vb[i].r);
                    update(1, 1, n, vb[i].l, vb[i].r, 1);
                    vb.erase(--it);
                }
            }
        }
        puts("");
    }
    return 0;
}

Memory Control

Problem Description

Memory units are numbered from 1 up to N.
A sequence of memory units is called a memory block.
The memory control system we consider now has four kinds of operations:

  1. Reset Reset all memory units free.
  2. New x Allocate a memory block consisted of x continuous free memory units with the least start number
  3. Free x Release the memory block which includes unit x
  4. Get x Return the start number of the xth memory block(Note that we count the memory blocks allocated from left to right)
    Where 1<=x<=N.You are request to find out the output for M operations.
    Input

Input contains multiple cases.
Each test case starts with two integer N,M(1<=N,M<=50000) ,indicating that there are N units of memory and M operations.
Follow by M lines,each line contains one operation as describe above.
Output

For each “Reset” operation, output “Reset Now”.
For each “New” operation, if it’s possible to allocate a memory block,
output “New at A”,where Ais the least start number,otherwise output “Reject New”.
For each “Free” operation, if it’s possible to find a memory block occupy unit x,
output “Free from A to B”,where A and B refer to the start and end number of the memory block,otherwise output “Reject Free”.
For each “Get” operation, if it’s possible to find the xth memory blocks,
output “Get at A”,where A is its start number,otherwise output “Reject Get”.
Output one blank line after each test case.
Sample Input

6 10 New 2 New 5 New 2 New 2 Free 3 Get 1 Get 2 Get 3 Free 3 Reset
Sample Output

New at 1 Reject New New at 3 New at 5 Free from 3 to 4 Get at 1 Get at 5 Reject Get Reject Free Reset Now

Posted on In ,

题意 有一个Crane由n条线段连接组成 每个连接点处均可以任意旋转 给你n条线段的长度 然后又m次旋转操作 给你p和r 将第p和第p+1条线段之间的角度旋转为r 即第p条线段绕p的终点逆时针旋转r度后能够与第p+1条重合 问每次旋转后最后一条线段的终点坐标

可以发现 旋转第p+1条线段时 p+1后面的所有线段也一起旋转了 可以把Crane分解为n个向量 这些向量的和也就是Crane终点的坐标 用rad[i]保存第i个向量与第i+1个向量之间的夹角 每次旋转操作时 我们要把rad[i]变为r 也就是要把第i+1和后面的所有向量逆时针旋转r - rad[i] 对于向量的旋转操作有

**(x,y)逆时针旋转 r 弧度 –>(x/*cos(r) - y/*sin(r), x/sin(r) + y/cos(r))

**(x,y)顺时针旋转 r 弧度 –>(-x/*cos(r) + y/*sin(r), x/sin(r) + y/cos(r))

那么我们可以用线段树来维护对应区间的向量的和 根节点对应的x, y也就是答案了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <cstdio>
#include <cmath>
#define lc p<<1, s, mid
#define rc p<<1|1, mid+1, e
#define mid ((s+e)>>1)
using namespace std;
const int N = 10005;
const double pi = acos(-1.0);
const double eps = 1e-8;
double x[N << 2], y[N << 2], rot[N << 2];
//x 对应区间所有向量的和的横坐标
//y 对应区间所有向量的和的纵坐标
//rot 子节点对应区间所有向量需要逆时针旋转的弧度
double rad[N]; //rad[i] 保存第i个向量和第i+1个向量间的弧度

void rotate(double &x, double &y, double r)
{
    //将向量(x, y)逆时针旋转r弧度
    double xx = x;
    x = xx * cos(r) - y * sin(r);
    y = xx * sin(r) + y * cos(r);
}

void pushup(int p)
{
    x[p] = x[p << 1] + x[p << 1 | 1];
    y[p] = y[p << 1] + y[p << 1 | 1];
}

void pushdown(int p, int s, int e)
{
    if(fabs(rot[p]) < eps) return;
    int lp = p << 1, rp = p << 1 | 1;
    rot[lp] += rot[p];
    rot[rp] += rot[p];
    rotate(x[lp], y[lp], rot[p]);
    rotate(x[rp], y[rp], rot[p]);
    rot[p] = 0;
}

void build(int p, int s, int e)
{
    rot[p] = 0;
    if(s == e)
    {
        scanf("%lf", &y[p]);
        x[p] = 0;
        rad[s] = pi;
        return;
    }
    build(lc);
    build(rc);
    pushup(p);
}

void update(int p, int s, int e, int l, int r, double v)
{
    if(l <= s && e <= r)
    {
        rot[p] += v;
        rotate(x[p], y[p], v);
        return;
    }
    pushdown(p, s, e);
    if(l <= mid) update(lc, l, r, v);
    if(r > mid) update(rc, l, r, v);
    pushup(p);
}

int main()
{
    int n, m, p, first = 1;
    double r;
    while(~scanf("%d%d", &n, &m))
    {
        if(!first) puts("");
        else first = 0;
        build(1, 1, n);
        while(m--)
        {
            scanf("%d%lf", &p, &r);
            r = r / 180 * pi;
            //p与p+1之间的弧度为rad[p] 要达到r p+1还需要逆时针旋转r - rad[p]弧度
            update(1, 1, n, p + 1, n, r - rad[p]);
            rad[p] = r;  //旋转后p与p+1之间的弧度变为r
            printf("%f %f\n", x[1], y[1]); //x[1], y[1]为所有向量和的坐标
        }
    }
    return 0;
}

Crane

Description
ACM has bought a new crane (crane – jeřáb) . The crane consists of n segments of various lengths, connected by flexible joints. The end of the i-th segment is joined to the beginning of the i + 1-th one, for 1 ≤ i < n. The beginning of the first segment is fixed at point with coordinates (0, 0) and its end at point with coordinates (0, w), where w is the length of the first segment. All of the segments lie always in one plane, and the joints allow arbitrary rotation in that plane. After series of unpleasant accidents, it was decided that software that controls the crane must contain a piece of code that constantly checks the position of the end of crane, and stops the crane if a collision should happen.
Your task is to write a part of this software that determines the position of the end of the n-th segment after each command. The state of the crane is determined by the angles between consecutive segments. Initially, all of the angles are straight, i.e., 180 o. The operator issues commands that change the angle in exactly one joint.

Input

The input consists of several instances, separated by single empty lines.
The first line of each instance consists of two integers 1 ≤ n ≤10 000 and c 0 separated by a single space – the number of segments of the crane and the number of commands. The second line consists of n integers l1,…, ln (1 li 100) separated by single spaces. The length of the i-th segment of the crane is li. The following c lines specify the commands of the operator. Each line describing the command consists of two integers s and a (1 ≤ s < n, 0 ≤ a ≤ 359) separated by a single space – the order to change the angle between the s-th and the s + 1-th segment to a degrees (the angle is measured counterclockwise from the s-th to the s + 1-th segment).

Output

The output for each instance consists of c lines. The i-th of the lines consists of two rational numbers x and y separated by a single space – the coordinates of the end of the n-th segment after the i-th command, rounded to two digits after the decimal point.
The outputs for each two consecutive instances must be separated by a single empty line.

Sample Input

2 1 10 5 1 90 3 2 5 5 5 1 270 2 90

Sample Output

5.00 10.00 -10.00 5.00 -5.00 10.00

Posted on In ,

题意 把一些矩形海报挖去一部分小矩形贴在指定位置 问最后海报覆盖的面积

一个矩形框可以分割成4个独立的小矩形 然后就能用扫描线求面积并了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100005, M = N << 2;
typedef long long ll;

struct SLine
{
    int x, y1, y2, flag;
    SLine() {};
    SLine(int xx, int a, int b, int f) :
        x(xx), y1(a), y2(b), flag(f) {}
    bool operator< (const SLine &s) const{
        return x < s.x;
    }
} line[N << 3];

int len[M], cnt[M];

void pushup(int p, int s, int e)
{
    if(cnt[p]) len[p] = e - s + 1;
    else if(s == e) len[p] = 0;
    else len[p] = len[p << 1] + len[p << 1 | 1];
}

void update(int p, int s, int e, int l, int r, int v)
{
    if(r < l) return; //分割后矩形有y1 = y2 的情况
    if(l <= s && e <= r)
    {
        cnt[p] += v;
        pushup(p, s, e);
        return;
    }
    int mid = (s + e) >> 1;
    if(l <= mid) update(p << 1, s, mid, l, r, v);
    if(r > mid) update(p << 1 | 1, mid + 1, e, l, r, v);
    pushup(p, s, e);
}

int main()
{
    int n, m, x1, y1, x2, y2, x3, y3, x4, y4, f;
    while(scanf("%d", &n), n)
    {
        m = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            scanf("%d%d%d%d", &x3, &y3, &x4, &y4);
            //将矩形框分成4个矩形
            line[m++] = SLine(x1, y1, y2, 1);
            line[m++] = SLine(x3, y1, y2, -1);
            line[m++] = SLine(x4, y1, y2, 1);
            line[m++] = SLine(x2, y1, y2, -1);

            line[m++] = SLine(x1, y1, y3, 1);
            line[m++] = SLine(x2, y1, y3, -1);
            line[m++] = SLine(x1, y4, y2, 1);
            line[m++] = SLine(x2, y4, y2, -1);
        }
        sort(line, line + m);

        ll ans = 0;
        for(int i = 0; i < m; ++i)
        {
            update(1, 1, N, line[i].y1 + 1, line[i].y2, line[i].flag);
            ans += ll(len[1]) * (line[i + 1].x - line[i].x);
        }
        printf("%lld\n", ans);
    }

    return 0;
}
//Last modified :  2015-08-14 14:29 CST

Posters

Problem Description

Ted has a new house with a huge window. In this big summer, Ted decides to decorate the window with some posters to prevent the glare outside. All things that Ted can find are rectangle posters.
However, Ted is such a picky guy that in every poster he finds something ugly. So before he pastes a poster on the window, he cuts a rectangular hole on that poster to remove the ugly part. Ted is also a careless guy so that some of the pasted posters may overlap when he pastes them on the window.
Ted wants to know the total area of the window covered by posters. Now it is your job to figure it out.
To make your job easier, we assume that the window is a rectangle located in a rectangular coordinate system. The window’s bottom-left corner is at position (0, 0) and top-right corner is at position (50000, 50000). The edges of the window, the edges of the posters and the edges of the holes on the posters are all parallel with the coordinate axes.
Input

The input contains several test cases. For each test case, the first line contains a single integer N (0<N<=50000), representing the total number of posters. Each of the following N lines contains 8 integers x1, y1, x2, y2, x3, y3, x4, y4, showing details about one poster. (x1, y1) is the coordinates of the poster’s bottom-left corner, and (x2, y2) is the coordinates of the poster’s top-right corner. (x3, y3) is the coordinates of the hole’s bottom-left corner, while (x4, y4) is the coordinates of the hole’s top-right corner. It is guaranteed that 0<=xi, yi<=50000(i=1…4) and x1<=x3<x4<=x2, y1<=y3<y4<=y2.
The input ends with a line of single zero.
Output

For each test case, output a single line with the total area of window covered by posters.
Sample Input

2 0 0 10 10 1 1 9 9 2 2 8 8 3 3 7 7 0
Sample Output

56

Posted on In ,

题意 给你一些矩形的左下和右上的坐标 求这些矩形的周长并

也先来看点图

和面积并类似 求周长并也可以对每条竖边从左往右进行扫描 每次周长增加了多少呢 可以发现y方向上对周长增加的量就是扫描线上线段的总长度的改变量 x方向增加了线段段数 /* 2 倍的与下一条竖边间的距离 因为每一段都会对应两个横边

那么我们需要维护线段的总长度len和线段的段数num len和面积并的是一样的 num有点类似区间合并 由子节点更新父节点的时候 先让父节点的num等于两个子节点的num的和 但是当左孩子结点的右端有线段 而其右孩子的左端有线段的时候 这两段是可以连在一起的 父节点的num就要减去1 所以我们还要维护每个区间左端是否有线段lh 右边是否有线段rh

另外求周长并还要注意当两个竖边的x值相等时 要把入边放前面 出边放后面 也就是排序时要注意一下 否则会多加上一些长度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 10005, M = N * 4;

struct SLine
{
    int x, y1, y2, flag;
    SLine() {}
    SLine(int xx, int a, int b, int f):
        x(xx), y1(a), y2(b), flag(f) {}
    bool operator< (const SLine &s) const
    {
        if(x == s.x) return flag > s.flag;
        //有入边出边在一条线上时 要先扫描入边 不然周长可能会多算重叠部分
        return x < s.x;
    }
} line[N];

int num[M], cnt[M], len[M], y[N];
bool lh[M], rh[M];

void pushup(int p, int s, int e)
{
    if(cnt[p]) //cnt == 0 时才需要由子节点来更新父节点
    {
        len[p] = y[e] - y[s - 1];
        num[p] = lh[p] = rh[p] = 1;
    }
    else if(s == e)
        len[p] = num[p] = lh[p] = rh[p] = 0;
    else  //区间合并
    {
        len[p] = len[p << 1] + len[p << 1 | 1];
        num[p] = num[p << 1] + num[p << 1 | 1];
        lh[p] = lh[p << 1], rh[p] = rh[p << 1 | 1];
        if(rh[p << 1] && lh[p << 1 | 1]) --num[p];
    }
}

void update(int p, int s, int e, int l, int r, int v)
{
    if(l <= s && e <= r)
    {
        cnt[p] += v;
        pushup(p, s, e);
        return;
    }
    int mid = (s + e) >> 1;
    if(l <= mid) update(p << 1, s, mid, l, r, v);
    if(r > mid) update(p << 1 | 1, mid + 1, e, l, r, v);
    pushup(p, s, e);
}

int main()
{
    int n, m, x1, y1, x2, y2;
    while(~scanf("%d", &n))
    {
        for(int i = m = 0; i < n; ++i)
        {
            scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
            y[m] = y1, y[m + 1] = y2;
            line[m++] = SLine(x1, y1, y2, 1);
            line[m++] = SLine(x2, y1, y2, -1);
        }
        sort(line, line + m);
        sort(y, y + m);  //离散化

        int ans = 0, last = 0, l, r;
        for(int i = 0; i < m; ++i)
        {
            l = lower_bound(y, y + m, line[i].y1) - y + 1;
            r = lower_bound(y, y + m, line[i].y2) - y;
            update(1, 1, m, l, r, line[i].flag);
            if(i < m - 1) ans += 2 * num[1] * (line[i + 1].x - line[i].x); //横边
            ans += abs(len[1] - last); //竖边
            last = len[1];
        }
        printf("%d\n", ans);
    }
    return 0;
}

Picture

Problem Description

A number of rectangular posters, photographs and other pictures of the same shape are pasted on a wall. Their sides are all vertical or horizontal. Each rectangle can be partially or totally covered by the others. The length of the boundary of the union of all rectangles is called the perimeter.
Write a program to calculate the perimeter. An example with 7 rectangles is shown in Figure 1.

The corresponding boundary is the whole set of line segments drawn in Figure 2.

The vertices of all rectangles have integer coordinates.
Input

Your program is to read from standard input. The first line contains the number of rectangles pasted on the wall. In each of the subsequent lines, one can find the integer coordinates of the lower left vertex and the upper right vertex of each rectangle. The values of those coordinates are given as ordered pairs consisting of an x-coordinate followed by a y-coordinate.
0 <= number of rectangles < 5000
All coordinates are in the range [-10000,10000] and any existing rectangle has a positive area.
Please process to the end of file.
Output

Your program is to write to standard output. The output must contain a single line with a non-negative integer which corresponds to the perimeter for the input rectangles.
Sample Input

7 -15 0 5 10 -5 8 20 25 15 -4 24 14 0 -6 16 4 2 15 10 22 30 10 36 20 34 0 40 16
Sample Output

228

Posted on In ,

题意 给你n个矩形 每个矩形都有自己的value 你可以任意改变矩形的表里关系 被覆盖的地方的value取最表层的 求总value的最大值

刚看了扫描线 感觉这个可以用扫描线做就直接写了 其实直接离散化就行了 因为最多也就20个矩形 那坐标最多也就40个 那我们对坐标进行离散化 然后将矩形按value从小到大一个个的放 暴力更新覆盖格子的value 最后直接将2n /* 2n个小格子的value加起来就行了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long ll;
const int N = 50;
int y[N], x[N], n, m;
ll val[N][N];

struct Rect
{
    int x1, y1, x2, y2, v;
    bool operator< (const Rect &r) const{
        return v < r.v;
    }
} r[N];

int fid(int a[], int k){
    return lower_bound(a, a + m, k) - a;
}

int main()
{
    int T, x1, y1, x2, y2, cas = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = m = 0; i < n; ++i, m += 2)
        {
            scanf("%d%d%d%d%d", &r[i].x1, &r[i].y1, &r[i].x2, &r[i].y2, &r[i].v);
            x[m] = r[i].x1, x[m + 1] = r[i].x2;
            y[m] = r[i].y1, y[m + 1] = r[i].y2;
        }
        sort(r, r + n); //将value小的大楼放前面
        sort(x, x + m); //离散化x
        sort(y, y + m); //离散化y

        memset(val, 0, sizeof(val));
        for(int i = 0; i < n; ++i)
        {
            x1 = fid(x, r[i].x1), x2 = fid(x, r[i].x2);  //获得x离散化后的坐标
            y1 = fid(y, r[i].y1), y2 = fid(y, r[i].y2);  //获得y离散化后的坐标
            for(int j = x1; j < x2; ++j)
                for(int k = y1; k < y2; ++k)  val[j][k] = r[i].v;
        }

        ll ans = 0;
        for(int i = 0; i < m - 1; ++i)
            for(int j = 0; j < m - 1; ++j)
                ans += val[i][j] * (x[i + 1] - x[i]) * (y[j + 1] - y[j]);
        printf("Case %d: %I64d\n", ++cas, ans);
    }
    return 0;
}

还有扫描线a的代码 用扫描线的时候是将矩形value从大到小排序 每放置一个矩形 看面积改变了多少 然后就用value乘以这个改变的面积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lc p<<1, s, mid
#define rc p<<1|1, mid+1, e
#define mid ((s+e)>>1)
using namespace std;
typedef long long ll;
const int N = 50;
int y[N], flag[N * 2], len[N * 2];

struct Rect
{
    int x1, y1, x2, y2, v;
    bool operator< (const Rect &r) const
    {
        return v > r.v;
    }
} r[N];

struct SLine
{
    int x, y1, y2, flag;
    SLine() {}
    SLine(int xx, int a, int b, int f):
        x(xx), y1(a), y2(b), flag(f) {}
    bool operator< (const SLine &s) const
    {
        return x < s.x;
    }
} line[N];

void build()
{
    memset(flag, 0, sizeof(flag));
    memset(len, 0, sizeof(len));
}

void pushup(int p, int s, int e)
{
    if(flag[p]) len[p] = y[e] - y[s - 1];
    else if(s == e) len[p] = 0;
    else len[p] = len[p << 1] + len[p << 1 | 1];
}

void update(int p, int s, int e, int l, int r, int v)
{
    if(l <= s && e <= r)
    {
        flag[p] += v;
        pushup(p, s, e);
        return;
    }
    if(l <= mid) update(lc, l, r, v);
    if(r > mid) update(rc, l, r, v);
    pushup(p, s, e);
}

int main()
{
    int T, n, m, cas = 0;
    int x1, y1, x2, y2, v;
    ll ans;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; ++i)
            scanf("%d%d%d%d%d", &r[i].x1, &r[i].y1, &r[i].x2, &r[i].y2, &r[i].v);
        sort(r, r + n);
        ll ans = 0, last = 0, area;

        for(int i = m = 0; i < n; ++i)
        {
            build();
            area = 0;
            y[m] = r[i].y1, y[m + 1] = r[i].y2;
            line[m++] = SLine(r[i].x1, r[i].y1, r[i].y2, 1);
            line[m++] = SLine(r[i].x2, r[i].y1, r[i].y2, -1);
            sort(y, y + m);
            sort(line, line + m);

            for(int j = 0; j < m - 1; ++j)
            {
                int l = lower_bound(y, y + m, line[j].y1) - y;
                int r = lower_bound(y, y + m, line[j].y2) - y;
                update(1, 1, m, l + 1, r, line[j].flag);
                area += len[1] * (line[j + 1].x - line[j].x);
            }

            ans += (area - last) * r[i].v;
            last = area;
        }
        printf("Case %d: %I64d\n", ++cas, ans);
    }
    return 0;
}

City Planning

Problem Description

After many years, the buildings in HDU has become very old. It need to rebuild the buildings now. So Mr dragon (the president of HDU’s logistics department ) ask Mr Wan (a very famous engineer) for help.
Mr Wan only draw one building on a construction design drawings(all the buildings are rectangle and each edge of buildings’ is paraller or perpendicular to others buildings’ edge ). And total draw n drawings (all the drawings have same width and length . And bottomleft point is (0, 0)). Due to possible overlap of conditions, so when they build a new building, they should to remove all the overlapping part of it. And for each building, HDU have a jury evaluate the value per unit area. Now Mr dragon want to know how to arrange the order of build these buildings can make the highest value.
Input

The first line of input is a number T which indicate the number of cases . (1 < T < 3000);
Each test case will begin with a single line containing a single integer n (where 1 <= n <= 20).
Next n line will contain five integers x1, y1, x2, y2 ,value . x1,y1 is bottomleft point and x2,y2 is topright point , value is the value of the buildings’ unit area.((0 <= x1, y1, x2, y2 <= 10000) (x1 < x2, && y1 < y2) (1 <= value <= 22)
Output

For each case. You just ouput the highest value in one line.
Sample Input

1 3 1 1 10 10 4 4 4 15 5 5 7 8 20 30 6
Sample Output

Case 1: 2047

Posted on In ,

题意 给你一些矩形的左下和右上的坐标 求这些矩形的面积并

最基础的扫描线 理解了就是个水题了 先看一些图吧

恩 看完了有什么感觉没有 那些红色的线就可以当作传说中的扫描线 就像从左到右扫描嘛 可以发现 矩形有竖直边的地方就有这些线 这些线把把拼在一起的矩形切成了一个个的小矩形 我们把这些小矩形的面积加起来不就是要求的面积吗

那么现在这些小矩形的面积怎么求呢 长乘宽嘛 长是什么 两条红线之间的距离 恩 我们要先把所有矩形的竖直边存起来 然后按横坐标排个序 那么相邻两个竖边的横坐标的差不就是长吗

那么宽呢 宽就是扫描线右边有矩形部分的长度呀 那么现在的问题就是怎么求这个长度了 我们是依次对矩形竖边进行扫描的 我们的扫描线就可以用来维护这个长度(len) 开始让扫描线上所有位置值(cnt)都为0 每来一条竖边 如果这个竖边是矩形左边的边(入边) 我们就让扫描线对应区间的值都加上1 如果这个竖边是矩形右边的边(出边) 我们就让扫描线对应区间的值都减去1 那么我们每次只用知道扫描线上非0部分有多长 这个长度不就是扫描线右边有矩形部分的长度了

噢 对区间进行加1减1操作 是不是很熟悉呀

你可以当作普通的区间更新来做 但是扫描线有个特殊的性质可以让你省掉lazy标记 因为减1的区间肯定是之前加过1的 我们更新时找到满足条件的区间后不用再往下推(pushdown)了 而且只有cnt = 0的地方才需要pushup

由于这道题的y坐标的范围比较大 而且不是整数 所以需要进行离散化操作 离散化只用把原来的值替换为排序后的下标就行了 因为这样不会改变他们y坐标的相对顺序 计算len的时候再把下标对应的y值取出来

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lc p<<1, s, mid
#define rc p<<1|1, mid + 1, e
#define mid ((s+e)>>1)
using namespace std;
const int N = 205;
int cnt[N * 4];
double len[N * 4], y[N];

struct SLine
{
    double x, y1, y2;
    int flag;
    SLine() {}
    SLine(double a, double b, double c, int t):
        x(a), y1(b), y2(c), flag(t) {}
    bool operator< (const SLine &s) const
    {
        return x < s.x;
    }
} line[N];

void pushup(int p, int s, int e) //只有cnt = 0时才需要更新
{
    if(cnt[p]) len[p] = y[e] - y[s - 1];
    else if(s == e) len[p] = 0;
    else len[p] = len[p << 1] + len[p << 1 | 1];
}

void build()
{
    memset(len, 0, sizeof(len));
    memset(cnt, 0, sizeof(cnt));
}

void update(int p, int s, int e, int l, int r, int v)
{
    if(l <= s && e <= r)
    {
        cnt[p] += v;
        pushup(p, s, e);
        return;
    }
    if(l <= mid) update(lc, l, r, v);
    if(r > mid) update(rc, l, r, v);
    pushup(p, s, e);
}

int main()
{
    int n, m, cas = 0;
    double x1, y1, x2, y2;
    while(scanf("%d", &n), n)
    {
        build();
        m = 0;
        for(int i = 0; i < n; ++i)
        {
            scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
            y[m] = y1, y[m + 1] = y2;
            line[m++] = SLine(x1, y1, y2, 1);
            line[m++] = SLine(x2, y1, y2, -1);
        }
        sort(line, line + m);
        sort(y, y + m); //离散化

        double sum = 0;
        for(int i = 0; i < m - 1; ++i)
        {
            int l = lower_bound(y, y + m, line[i].y1) - y;
            int r = lower_bound(y, y + m, line[i].y2) - y;
            update(1, 1, m, l + 1, r, line[i].flag);
            //l+1是点区间化段区间时长度需减1
            sum += len[1] * (line[i + 1].x - line[i].x);
        }
        printf("Test case #%d\nTotal explored area: %.2f\n\n", ++cas, sum);
    }
    return 0;
}

Atlantis

Problem Description

There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.
Input

The input file consists of several test cases. Each test case starts with a line containing a single integer n (1<=n<=100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0<=x1<x2<=100000;0<=y1<y2<=100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
The input file is terminated by a line containing a single 0. Don’t process it.
Output

For each test case, your program should output one section. The first line of each section must be “Test case /#k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.
Output a blank line after each test case.
Sample Input

2 10 10 20 20 15 15 25 25.5 0
Sample Output

Test case /#1 Total explored area: 180.00

0%