The 2014 ACM-ICPC Asia Mudanjiang Regional

继续复盘之前的Regional……出题者说这一套题太简单，对当时没有AK很不满……真是醉了，弱校没法活了

【A】签到题

【B】树结构，树的中心

【C】-_-///

【D】概率DP

【E】-_-///

【F】树结构填数

【G】-_-///

【H】模拟

【I】签到题

【J】-_-///

【K】贪心，构造后缀表达式

---

A、ZOJ 3819 Average Score

Time Limit: 2 Seconds
Memory Limit: 65536 KB

Description

Bob is a freshman in Marjar University. He is clever and diligent. However, he is not good at math, especially in Mathematical Analysis.

After a mid-term exam, Bob was anxious about his grade. He went to the professor asking about the result of the exam. The professor said:

“Too bad! You made me so disappointed.”
“Hummm… I am giving lessons to two classes. If you were in the other class, the average scores of both classes will increase.”

Now, you are given the scores of all students in the two classes, except for the Bob’s. Please calculate the possible range of Bob’s score. All scores shall be integers within [0, 100].

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains two integers N (2 <= N <= 50) and M (1 <= M <= 50) indicating the number of students in Bob’s class and the number of students in the other class respectively.

The next line contains N - 1 integers A1, A2, .., AN-1 representing the scores of other students in Bob’s class.

The last line contains M integers B1, B2, .., BM representing the scores of students in the other class.

Output

For each test case, output two integers representing the minimal possible score and the maximal possible score of Bob.

It is guaranteed that the solution always exists.

Sample Input

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

Sample Output

4 4
2 4

分析

签到，写个方程稍微推一下即可得到区间

---

B、ZOJ 3820 Building Fire Stations

Time Limit: 5 Seconds
Memory Limit: 131072 KB
Special Judge

Description

Marjar University is a beautiful and peaceful place. There are N buildings and N - 1 bidirectional roads in the campus. These buildings are connected by roads in such a way that there is exactly one path between any two buildings. By coincidence, the length of each road is 1 unit.

To ensure the campus security, Edward, the headmaster of Marjar University, plans to setup two fire stations in two different buildings so that firefighters are able to arrive at the scene of the fire as soon as possible whenever fires occur. That means the longest distance between a building and its nearest fire station should be as short as possible.

As a clever and diligent student in Marjar University, you are asked to write a program to complete the plan. Please find out two proper buildings to setup the fire stations.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains an integer N (2 <= N <= 200000).

For the next N - 1 lines, each line contains two integers Xi and Yi. That means there is a road connecting building Xi and building Yi (indexes are 1-based).

Output

For each test case, output three integers. The first one is the minimal longest distance between a building and its nearest fire station. The next two integers are the indexes of the two buildings selected to build the fire stations.

If there are multiple solutions, any one will be acceptable.

Sample Input

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

Sample Output

1 1 2
1 2 4

题意

题目给出一棵树作为一个城镇的地图，现在要在地图中设置两个救火点，使得最后任意一点发生火灾，救火都能及时到达，即使得救火点到达每个城镇的最大距离最小。

分析

首先比较明显的能想到基于树的直径做一些文章。

浙大的出题者在他的人人日志中给出了本题结论的证明：

http://blog.renren.com/blog/240107793/937020122?bfrom=01020100200

最终得出的结论是，两个点a、b必然都在树的直径上。（结论1）

之后的思路有两种：

1. 作者的正解是扫出直径之后对每一个点向外扩展一次，得到每个点外延的最大距离，然后将其转化为一个一维的RMQ问题，二分一下区间即可。

2. 第一次得到树的直径之后，从直径的中点切开，对两侧的两棵子树分别再做一次树的直径，找到的两个直径的中点就是最终的a和b。

关于思路2的证明：

1）子树的直径的中点距离这棵子树剩余的点一定是最远的，则这个点满足作为a、b点的条件。

2）然后简单推测一下，子树的直径中点一定在原树的直径上。这一点与结论1相吻合。

这个简单地举几个例子试一下就好，跟上面那个结论一样，能简单地想到大概是这样，但是原谅我数学不好……写不出证明。

3）上面两个结论组合一下，最后的交点就是a、b的最终位置了。

然后需要注意的是根据树的直径的结点个数，要分奇数和偶数分别讨论。偶数个结点只要从中间一条边切开即可，但是奇数个结点的情况就要继续分成两种情况，考虑中点分别切给左边那个子树和切给右边那棵子树的结果，取距离最小的那一个。

/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : ZOJ 3820
************************************************ */

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

using namespace std;

typedef struct nod
{
    int a,b;
} node;

node edge[400010];
int start[200010],num[200010],front[200010],list[200010];
int listn;

bitset<200010> flag;

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

int bfs(int s)
{
    queue<int> q;
    while (!q.empty()) q.pop();
    int dist[200010];

    memset(dist,0,sizeof(dist));
    flag[s]=1;
    q.push(s);
    int ma=0,out=s;
    while (!q.empty())
    {
        int now=q.front();
        q.pop();
        for (int i=0;i<num[now];i++)
        {
            int next=edge[start[now]+i].b;
            if (!flag[next])
            {
                flag[next]=1;
                front[next]=now;
                q.push(next);
                dist[next]=dist[now]+1;
                if (ma<dist[next])
                {
                    ma=dist[next];
                    out=next;
                }
            }
        }
    }

    return out;
}

void getlist(int s)
{
    if (!front[s])
    {
        listn=1;
        list[1]=s;
        return ;
    }
    while (front[s]!=0)
    {
        listn++;
        list[listn]=s;
        s=front[s];
    }
    listn++;
    list[listn]=s;
}

int main()
{
    freopen("3820.txt","r",stdin);

    int t;
    scanf("%d",&t);
    for (int tt=1;tt<=t;tt++)
    {
        int n;
        scanf("%d",&n);
        for (int i=1;i<n;i++)
        {
            scanf("%d%d",&edge[i*2].a,&edge[i*2].b);
            edge[i*2-1].a=edge[i*2].b;
            edge[i*2-1].b=edge[i*2].a;
        }
        int m=n*2-2;
        sort(&edge[1],&edge[m+1],op);
        int o=0;
        memset(num,0,sizeof(num));
        for (int i=1;i<=m;i++)
        {
            if (o!=edge[i].a)
            {
                o=edge[i].a;
                start[o]=i;
            }
            num[o]++;
        }

        flag.reset();
        int p1=bfs(1);
        flag.reset();
        memset(front,0,sizeof(front));
        int p2=bfs(p1);

        listn=0;
        memset(list,0,sizeof(list));
        getlist(p2);
        
        if (listn&1)
        {
            int a=list[listn/2],b=list[listn/2+1],c=list[listn/2+2];

            flag.reset();
            flag[b]=1;
            p1=bfs(a);
            flag.reset();
            flag[b]=1;
            memset(front,0,sizeof(front));
            p2=bfs(p1);

            listn=0;
            memset(list,0,sizeof(list));
            getlist(p2);

            int ans1=listn/2;
            int ansa1=list[listn/2+1];

            flag.reset();
            flag[a]=1;
            p1=bfs(b);
            flag.reset();
            flag[a]=1;
            memset(front,0,sizeof(front));
            p2=bfs(p1);

            listn=0;
            memset(list,0,sizeof(list));
            getlist(p2);

            ans1=max(ans1,listn/2);
            int ansb1=list[listn/2+1];

            flag.reset();
            flag[b]=1;
            p1=bfs(c);
            flag.reset();
            flag[b]=1;
            memset(front,0,sizeof(front));
            p2=bfs(p1);

            listn=0;
            memset(list,0,sizeof(list));
            getlist(p2);

            int ans2=listn/2;
            int ansa2=list[listn/2+1];

            flag.reset();
            flag[c]=1;
            p1=bfs(b);
            flag.reset();
            flag[c]=1;
            memset(front,0,sizeof(front));
            p2=bfs(p1);

            listn=0;
            memset(list,0,sizeof(list));
            getlist(p2);

            ans2=max(ans2,listn/2);
            int ansb2=list[listn/2+1];

            if (ans1<ans2) printf("%d %d %d\n",ans1,ansa1,ansb1);
            else printf("%d %d %d\n",ans2,ansa2,ansb2);
        } else 
        {
            int a=list[listn/2],b=list[listn/2+1];

            flag.reset();
            flag[b]=1;
            p1=bfs(a);
            flag.reset();
            flag[b]=1;
            memset(front,0,sizeof(front));
            p2=bfs(p1);

            listn=0;
            memset(list,0,sizeof(list));
            getlist(p2);

            int ans1=listn/2;
            int ansa1=list[listn/2+1];

            flag.reset();
            flag[a]=1;
            p1=bfs(b);
            flag.reset();
            flag[a]=1;
            memset(front,0,sizeof(front));
            p2=bfs(p1);

            listn=0;
            memset(list,0,sizeof(list));
            getlist(p2);

            ans1=max(ans1,listn/2);
            int ansb1=list[listn/2+1];

            printf("%d %d %d\n",ans1,ansa1,ansb1);
        }
    }

    return 0;
}

---

D、ZOJ 3822 Domination

Time Limit: 8 Seconds
Memory Limit: 131072 KB
Special Judge

Description

Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays chess with his friends. What’s more, he bought a large decorative chessboard with N rows and M columns.

Every day after work, Edward will place a chess piece on a random empty cell. A few days later, he found the chessboard was dominated by the chess pieces. That means there is at least one chess piece in every row. Also, there is at least one chess piece in every column.

“That’s interesting!” Edward said. He wants to know the expectation number of days to make an empty chessboard of N × M dominated. Please write a program to help him.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

There are only two integers N and M (1 <= N, M <= 50).

Output

For each test case, output the expectation number of days.

Any solution with a relative or absolute error of at most 10-8 will be accepted.

Sample Input

2
1 3
2 2

Sample Output

3.000000000000
2.666666666667

题意

有一个棋盘，目标是在棋盘中摆放棋子，使得最终每一个格子都能够被控制，这里控制的意思是满足这个格子的同行和同列上都有棋子存在。最终需要求出的是达成这种条件的期望。

分析

比较裸的概率DP…原谅我看到的第一眼居然没想到…还是做题太少啊

f(i,j,k)表示使用k个棋子，控制完n行中的任意i行，m列中的任意j列所需要的概率。则最后的期望就是求一个f(n,m,k)*k的总和即可。

简单的方程如下：

f(i,j,k) = Sum
{
    f(i,j,k+1)*(i*j-k)/(n*m-k),
    f(i+1,j,k+1)*(n-i)*j/(n*m-k),
    f(i,j+1,k+1)*i*(m-j)/(n*m-k),
    f(i+1,j+1,k+1)*(n-i)*(m-j)/(n*m-k)
}

方程中需要尤其注意的是当达成n行m列全部被控制之后，就可以结束了，即转移中f(n,m,k)->f(n,m,k+1)是不存在的！！！！因为这个原因悲剧了好久，后来对比其他人的代码才发现这个重大的问题。。。

/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : ZOJ 3822
************************************************ */
/* ***********************************************
f(i,j,k) = Sum
{
    f(i,j,k+1)*(i*j-k)/(n*m-k),
    f(i+1,j,k+1)*(n-i)*j/(n*m-k),
    f(i,j+1,k+1)*i*(m-j)/(n*m-k),
    f(i+1,j+1,k+1)*(n-i)*(m-j)/(n*m-k)
}
************************************************ */

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

using namespace std;

double f[60][60][4000];

int main()
{
    int t;
    scanf("%d",&t);
    for (int tt=1;tt<=t;tt++)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(f,0,sizeof(f));
        
        f[1][1][1]=1;
        for (int k=1;k<=m*n;k++)
        for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
        {
            if (k<max(i,j)) continue;
            if (k+1<=i*j&&i!=n||j!=m)
            f[i][j][k+1]+=f[i][j][k]*(i*j-k)/(n*m-k);
            if (k+1<=(i+1)*j)
            f[i+1][j][k+1]+=f[i][j][k]*(n-i)*j/(n*m-k);
            if (k+1<=i*(j+1))
            f[i][j+1][k+1]+=f[i][j][k]*i*(m-j)/(n*m-k);
            if (k+1<=(i+1)*(j+1))
            f[i+1][j+1][k+1]+=f[i][j][k]*(n-i)*(m-j)/(n*m-k);
        }

        double ans=0;
        for (int i=max(n,m);i<=m*n;i++) ans+=f[n][m][i]*i;

        printf("%.10f\n",ans);
    }

    return 0;
}

---

I、ZOJ 3827 Information Entropy

Time Limit: 2 Seconds
Memory Limit: 65536 KB
Special Judge

Description

Information Theory is one of the most popular courses in Marjar University. In this course, there is an important chapter about information entropy.

Entropy is the average amount of information contained in each message received. Here, a message stands for an event, or a sample or a character drawn from a distribution or a data stream. Entropy thus characterizes our uncertainty about our source of information. The source is also characterized by the probability distribution of the samples drawn from it. The idea here is that the less likely an event is, the more information it provides when it occurs.

Generally, “entropy” stands for “disorder” or uncertainty. The entropy we talk about here was introduced by Claude E. Shannon in his 1948 paper “A Mathematical Theory of Communication”. We also call it Shannon entropy or information entropy to distinguish from other occurrences of the term, which appears in various parts of physics in different forms.

Named after Boltzmann’s H-theorem, Shannon defined the entropy Η (Greek letter Η, η) of a discrete random variable X with possible values {x1, x2, …, xn} and probability mass function P(X) as:

H(X)=E(−ln(P(x)))

Here E is the expected value operator. When taken from a finite sample, the entropy can explicitly be written as

H(X)=−∑i=1nP(xi)log b(P(xi))

Where b is the base of the logarithm used. Common values of b are 2, Euler’s number e, and 10. The unit of entropy is bit for b = 2, nat for b = e, and dit (or digit) for b = 10 respectively.

In the case of P(xi) = 0 for some i, the value of the corresponding summand 0 logb(0) is taken to be a well-known limit:

0log b(0)=limp→0+plog b(p)

Your task is to calculate the entropy of a finite sample with N values.

Input

There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:

The first line contains an integer N (1 <= N <= 100) and a string S. The string S is one of “bit”, “nat” or “dit”, indicating the unit of entropy.

In the next line, there are N non-negative integers P1, P2, .., PN. Pi means the probability of the i-th value in percentage and the sum of Pi will be 100.

Output

For each test case, output the entropy in the corresponding unit.

Any solution with a relative or absolute error of at most 10-8 will be accepted.

Sample Input

3
3 bit
25 25 50
7 nat
1 2 4 8 16 32 37
10 dit
10 10 10 10 10 10 10 10 10 10

Sample Output

1.500000000000
1.480810832465
1.000000000000

分析

签到题，难点可能是在题面上，学过信息论的话看到样例就能直接打代码了。