Chenfan Blog

Do cool things that matter.

0%

The 2014 ACMICPC Asia Regional Beijing Online

Posted on Edited on In

【A】极角排序+树状数组

【B】计算几何，凸包（队友已出）

【C】-_-///不懂

【D】数论，概率密度

【E】图的连通性+Floyed传递闭包+bitset

【F】贪心

【G】签到题

【H】区间维护+线段树+DFS序（可以看看）

【I】BFS地图题（当时好多人坑在摄像头上面了，现在有一点点思路，分层图，一会看看）

【J】-_-/////

貌似除了这两题巨坑的，剩下的都有能出的可能性

A、Always Cook Mushroom

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

Matt has a company, Always Cook Mushroom (ACM), which produces high-quality mushrooms.

ACM has a large field to grow their mushrooms. The field can be considered as a 1000 * 1000 grid where mushrooms are grown in grid points numbered from (1, 1) to (1000, 1000). Because of humidity and sunshine, the productions in different grid points are not the same. Further, the production in the grid points (x, y) is (x + A)(y + B) where A, B are two constant. Matt,the owner of ACM has some queries where he wants to know the sum of the productions in a given scope(include the mushroom growing on the boundary). In each query, the scope Matt asks is a right angled triangle whose apexes are (0, 0), (p, 0), (p, q) 1<=p, q<=1000. As the employee of ACM, can you answer Matt’s queries?

Input

The first line contains one integer T, indicating the number of test cases.

For each test case, the first line contains two integers:A, B(0<=A, B<=1000).

The second line contains one integer M(1<=M<=10^5), denoting the number of queries.

In the following M lines, the i-th line contains three integers a, b, x (1<=a, b<=10^6, 1<=x<=1000), denoting one apex of the given right angled triangle is (x, 0) and the slope of its base is (a, b). It is guaranteed that the gird points in the given right angled triangle are all in valid area, numbered from (1, 1) to (1000, 1000).

Output

For each test case, output M + 1 lines.

The first line contains “Case #x:”, where x is the case number (starting from 1)

In the following M lines, the i-th line contains one integer, denoting the answer of the i-th query.

Sample Input

2
0 0
3
3 5 8
2 4 7
1 2 3
1 2
3
3 5 8
2 4 7
1 2 3

Sample Output

Case #1:
1842
1708
86
Case #2:
2901
2688
200

题意

给出一张最大1000*1000的图，给出一些询问，每次询问给出一个斜率和x，要求三角内的所有点的和。

分析

题目意思比较裸，直观地想到这道题目的难度肯定不是在理解上，应该是数据比较大太裸的算法不可能卡过。

果然试了各种，唯一想到的树状数组也加上去了，还是一直TLE没能在比赛过程中出解。

赛后整理终于明白了，这道题目的关键在于如何把一张二维的图转化为一维来解决，本题给我的启发是：累加的题目如果要避免反复加引起的重复的话，树状数组是必须的，时间非常优秀，然而树状数组毕竟是一维的，必须想到办法解决二维压成一维之后的后效性等等问题才能发挥出最大的效果。

最后的算法：

二维转一维：将最大1000*1000个点按照斜率排序。对于每次的询问也是按照斜率排序。

想象有一根轴，从x轴的0°角开始逆时针扫整个平面，扫到的点按照x坐标加入树状数组，直到扫到与一条询问线重合，则对该次询问求sum(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
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
/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : HDU5032
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

long long c[1010];
int outp[100010];
long long ou[100010];

typedef struct poin
{
    int x,y;
    long long v;
    double ang;
} point;

point poi[1000010];
int totp;

typedef struct nod
{
    int a,b,x,src;
    double ang;
} node;

node lis[100010];

bool op1(point a,point b)
{
    if (a.ang==b.ang) return a.x<b.x;
    else return a.ang<b.ang;
}

bool op2(node a,node b)
{
    if (a.ang==b.ang) return a.a<b.a;
    else return a.ang<b.ang;
}

int lowbit(int s)
{
    return s&-s;
} 

void update(int s,long long x) 
{
    while (s<=1000)
    {
        c[s]+=x;
        s+=lowbit(s);
    }
}

long long sum(int s)
{
    long long t=0;
    while (s>0)
    {
        t+=c[s];
        s-=lowbit(s);
    }
    return t;
} 

int main()
{
    freopen("test.txt","r",stdin);
    
    int t;
    
    totp=0;
    for (int i=1;i<=1000;i++)
    for (int j=1;j<=1000;j++)
    {
        totp++;
        poi[totp].x=i;
        poi[totp].y=j;
        poi[totp].ang=(double)j/i;
    }
    sort(&poi[1],&poi[1+totp],op1);
    
    scanf("%d",&t);
    for (int tt=1;tt<=t;tt++)
    {
        int A,B;
        scanf("%d%d",&A,&B);
        memset(c,0,sizeof(c));

        for (int i=1;i<=totp;i++) poi[i].v=(poi[i].x+A)*(poi[i].y+B);
        
        printf("Case #%d:\n",tt);
        
        int m;
        scanf("%d",&m);
        for (int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&lis[i].a,&lis[i].b,&lis[i].x);
            lis[i].ang=(double)lis[i].b/lis[i].a;
            lis[i].src=i;
        }
        sort(&lis[1],&lis[1+m],op2);
        for (int i=1;i<=m;i++) outp[lis[i].src]=i;
        
        for (int i=1,j=1;i<=m;i++)
        {
            while (j<=totp&&lis[i].ang-poi[j].ang>=0)
            {
                update(poi[j].x,poi[j].v);
                j++;
            }
            ou[i]=sum(lis[i].x);
        }
        
        for (int i=1;i<=m;i++) printf("%lld\n",ou[outp[i]]);
    }
    
    return 0;
}

启发

既然已经想到了树状数组，就应该多想想树状数组的性质，本题是利用了极角的特性二维化一维，思维上非常地巧妙。

树状数组这一块另外再补补，尤其是多维的情况

B、Building

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Special Judge

Problem Description

Once upon a time Matt went to a small town. The town was so small and narrow that he can regard the town as a pivot. There were some skyscrapers in the town, each located at position xi with its height hi. All skyscrapers located in different place. The skyscrapers had no width, to make it simple. As the skyscrapers were so high, Matt could hardly see the sky.Given the position Matt was at, he wanted to know how large the angle range was where he could see the sky. Assume that Matt’s height is 0. It’s guaranteed that for each query, there is at least one building on both Matt’s left and right, and no building locate at his position.

Input

The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow. Each test case begins with a number N(1<=N<=10^5), the number of buildings. In the following N lines, each line contains two numbers, xi(1<=xi<=10^7) and hi(1<=hi<=10^7).

After that, there’s a number Q(1<=Q<=10^5) for the number of queries.

In the following Q lines, each line contains one number qi, which is the position Matt was at.

Output

For each test case, first output one line “Case #x:”, where x is the case number (starting from 1).

Then for each query, you should output the angle range Matt could see the sky in degrees. The relative error of the answer should be no more than 10^(-4).

Sample Input

3
3
1 2
2 1
5 1
1
4
3
1 3
2 2
5 1
1
4
3
1 4
2 3
5 1
1
4

Sample Output

Case #1:
101.3099324740
Case #2:
90.0000000000
Case #3:
78.6900675260

说明

不太擅长几何题，好在队友给力能解决，日后慢慢看……0.0，嘿嘿

http://www.cnblogs.com/AOQNRMGYXLMV/p/3987173.html

E、Explosion

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others) Total

Problem Description

Everyone knows Matt enjoys playing games very much. Now, he is playing such a game. There are N rooms, each with one door. There are some keys(could be none) in each room corresponding to some doors among these N doors. Every key can open only one door. Matt has some bombs, each of which can destroy a door. He will uniformly choose a door that can not be opened with the keys in his hand to destroy when there are no doors that can be opened with keys in his hand. Now, he wants to ask you, what is the expected number of bombs he will use to open or destroy all the doors. Rooms are numbered from 1 to N.

Input

The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.

In the first line of each test case, there is an integer N (N<=1000) indicating the number of rooms.

The following N lines corresponde to the rooms from 1 to N. Each line begins with an integer k (0<=k<=N) indicating the number of keys behind the door. Then k integers follow corresponding to the rooms these keys can open.

Output

For each test case, output one line “Case #x: y”, where x is the case number (starting from 1), y is the answer which should be rounded to 5 decimal places.

Sample Input

2
3
1 2
1 3
1 1
3
0
0
0

Sample Output

Case #1: 1.00000
Case #2: 3.00000

题意

有N个房间，每个房间都是被门锁上，而打开的方式有两种，找到这扇门的钥匙或者用炸弹炸开。每个房间中都可能存在一些钥匙，即打开这个房门之后可以获得其他一些房间的钥匙。本题求的是最终为了打开所有房门，所有点需要被炸开的数学期望值。

分析

这里房间和钥匙的关系可以作为结点之间的连边条件，用于构造一张图。若1号房间有2号、3号房的钥匙，可用单向边连接1->2和1->3，表示如果能够进入1号房，那么2、3号房也能接着进入。最终将本题转化为传递闭包连通性的问题。

当时做题的时候想到的是用类似并查集的方法处理，但是想半天还是没想出方案来，最后用了BFS+DFS双向扩展，结果就TLE到死都没解决。

考虑我们已经通过某种方法得到了所有点对之间的到达关系，假设存在x个点都能够到达i号点，则为了到达i点，所有这x个房间需要被炸开的概率为1/x，因为任意炸开一个都能够到达i点，则为了到达i点需要的数学期望值为1*1/x=1/x。根据这种思路，容易看出来每一个点的数学期望值都是独立的。则可以单独求取到达每一个点需要的期望值，最终求和即可。

主要的时间复杂度都花在遍历得到所有点对上了，最基本的是用一个Floyed直接传递闭包，O(n^3)

然后从大神们的题解中发现了一种以前我从来没见过的新东西————位集。这货简直是黑科技……时空条件都非常优秀，直接用在Floyed上，复杂度可以降到O(n^3/64)（不要问我这个是怎么来的，，，我不知道）

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
/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : HDU5036
************************************************ */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <bitset>

using namespace std;

bitset<1010> a[1010];

int main()
{
    int t;
    scanf("%d",&t);
    for (int tt=1;tt<=t;tt++)
    {
        int n;
        scanf("%d",&n);
        for (int i=1;i<=n;i++)
        {
            a[i].reset();
            a[i][i]=true;
        }
        
        for (int i=1;i<=n;i++)
        {
            int m;
            scanf("%d",&m);
            for (int j=1;j<=m;j++)
            {
                int k;
                scanf("%d",&k);
                a[i][k]=true;
            }
        }
        
        for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        if (a[j][i]) a[j]|=a[i];
        
        double ans=0;
        for (int i=1;i<=n;i++)
        {
            int tot=0;
            for (int j=1;j<=n;j++) 
            if (a[j][i]) tot++;
            ans+=1.0/tot;
        }
        
        printf("Case #%d: %.5lf\n",tt,ans);
    }
    
    return 0;
}

有关bitset的用法，详见另外整理的一篇博文：

F、Frog

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Problem Description

Once upon a time, there is a little frog called Matt. One day, he came to a river.

The river could be considered as an axis.Matt is standing on the left bank now (at position 0). He wants to cross the river, reach the right bank (at position M). But Matt could only jump for at most L units, for example from 0 to L.

As the God of Nature, you must save this poor frog.There are N rocks lying in the river initially. The size of the rock is negligible. So it can be indicated by a point in the axis. Matt can jump to or from a rock as well as the bank.

You don’t want to make the things that easy. So you will put some new rocks into the river such that Matt could jump over the river in maximal steps.And you don’t care the number of rocks you add since you are the God.

Note that Matt is so clever that he always choose the optimal way after you put down all the rocks.

Input

The first line contains only one integer T, which indicates the number of test cases.

For each test case, the first line contains N, M, L (0<=N<=2*10^5,1<=M<=10^9, 1<=L<=10^9).

And in the following N lines, each line contains one integer within (0, M) indicating the position of rock.

Output

For each test case, just output one line “Case #x: y”, where x is the case number (starting from 1) and y is the maximal number of steps Matt should jump.

Sample Input

2
1 10 5
5
2 10 3
3
6

Sample Output

Case #1: 2
Case #2: 4

G、Grade

Time Limit: 3000/1500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)

Problem Description

Ted is a employee of Always Cook Mushroom (ACM). His boss Matt gives him a pack of mushrooms and ask him to grade each mushroom according to its weight. Suppose the weight of a mushroom is w, then it’s grade s is

s = 10000 - (100 - w)^2

What’s more, Ted also has to report the mode of the grade of these mushrooms. The mode is the value that appears most often. Mode may not be unique. If not all the value are the same but the frequencies of them are the same, there is no mode.

Input

The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.

The first line of each test cases contains one integers N (1<=N<=10^6),denoting the number of the mushroom.

The second line contains N integers, denoting the weight of each mushroom. The weight is greater than 0, and less than 200.

Output

For each test case, output 2 lines.

The first line contains “Case #x:”, where x is the case number (starting from 1)

The second line contains the mode of the grade of the given mushrooms. If there exists multiple modes, output them in ascending order. If there exists no mode, output “Bad Mushroom”.

Sample Input

3
6
100 100 100 99 98 101
6
100 100 100 99 99 101
6
100 100 98 99 99 97

Sample Output

Case #1:
10000
Case #2:
Bad Mushroom
Case #3:
9999 10000

分析

排序+判断，有些细节上的小问题要多注意一下

Related Posts