The 2014 ACM-ICPC Asia Regional Anshan Online

【A】无向图的双联通子图计数、DP+状态压缩

【B】计算几何（点的旋转）

【C】DP+状态压缩

【D】离散数学+DP （感觉可出）

【E】概率DP

【F】LCT模板题（-_-///LCT是啥！！！！）

【G】签到题

【H】染色+搜索

【I】阅读理解+记忆化搜索

【J】物理题，数论，高斯消元法（感觉可出）

---

B、Rotate

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Special Judge

Problem Description

Noting is more interesting than rotation!

Your little sister likes to rotate things. To put it easier to analyze, your sister makes n rotations. In the i-th time, she makes everything in the plane rotate counter-clockwisely around a point ai by a radian of pi.

Now she promises that the total effect of her rotations is a single rotation around a point A by radian P (this means the sum of pi is not a multiplier of 2π).

Of course, you should be able to figure out what is A and P :).

Input

The first line contains an integer T, denoting the number of the test cases.

For each test case, the first line contains an integer n denoting the number of the rotations. Then n lines follows, each containing 3 real numbers x, y and p, which means rotating around point (x, y) counter-clockwisely by a radian of p.

We promise that the sum of all p’s is differed at least 0.1 from the nearest multiplier of 2π.

T<=100. 1<=n<=10. 0<=x, y<=100. $0<=p<=2\pi$.

Output

For each test case, print 3 real numbers x, y, p, indicating that the overall rotation is around (x, y) counter-clockwisely by a radian of p. Note that you should print p where $0<=p<2\pi$.

Your answer will be considered correct if and only if for x, y and p, the absolute error is no larger than 1e-5.

Sample Input

1
3
0 0 1
1 1 1
2 2 1

Sample Output

1.8088715944 0.1911284056 3.0000000000

题意

对于每一组测试数据，给出一系列旋转命令，每次将整个平面空间绕着某一点逆时针旋转某一个弧度。而所有这些操作的最终结果可以等效为绕着A点旋转P弧度，题目的要求即求出这个坐标点A和弧度P。

分析

当时看到这题解析几何，第一反应就是不想去管它了，因为手头没有趁手的模板可用，本来就数学不好，算起来太过耗时，还容易错，无奈水平有限，能做的题目不多，还是回来写这个了。

既然题目确定了所有这些操作都可以等效为一个，那我们也不需呀去管这个结论是怎么证明出来的了。基本的思想是用一条线段去指代这个平面，每次将线段的两端点都进行一次旋转操作，就相当于整条线段都旋转了，更进一步地就代表平面旋转了。之后分析原始坐标与结果坐标之间的关系即可得出等效结果。

一、原坐标与起始坐标相连的线段必然是以旋转中心为圆心的圆上的一条弦。则根据两个点的旋转结果，取线段中垂线算出交点即可求出圆心，即旋转中心；

二、然后就是旋转角度了，画个三角形余弦定理求解即可。

注意

最开始一直WA是忽略了一个问题就是P的范围是0~2Pi，三角形余弦定理计算出的结果肯定是小于Pi的，就是最后必须判断一下旋转角度是否超过了Pi，超了则最终的输出结果应该是2Pi-P。这里要用到判断两点是否在一条直线的同一边。

没有好的模板……下面的代码看着各种乱啊：

/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : B1002
************************************************ */

#include <iostream>
#include <cstdio>
#include <cmath>

#define Pi 3.141592657

typedef struct poi
{
    double x,y;
} point;

using namespace std;

point rotate(point v,point p,double angle)
{
    point ret=p;
    v.x-=p.x,v.y-=p.y;
    p.x=cos(angle);
    p.y=sin(angle);
    ret.x+=v.x*p.x-v.y*p.y;
    ret.y+=v.x*p.y+v.y*p.x;
    return ret;
}

int main()
{
    int t;
    scanf("%d",&t);
    for (int tt=1;tt<=t;tt++)
    {
        int n;
        scanf("%d",&n);
        point p1={20.123,6.678},p2={3.414,10.123};
        point p0={(p1.x+p2.x)/2,(p1.y+p2.y)/2};
        for (int i=1;i<=n;i++)
        {
            point now;
            double p;
            scanf("%lf%lf%lf",&now.x,&now.y,&p);
            p1=rotate(p1,now,p);
            p2=rotate(p2,now,p);
        }
        
        point p10;
        p10.x=(p1.x+20.123)/2;
        p10.y=(p1.y+6.678)/2;
        double k1=(p1.y-p10.y)/(p1.x-p10.x);
        k1=-1/k1;
        double b1=p10.y-k1*p10.x;
        
        point p20;
        p20.x=(p2.x+3.414)/2;
        p20.y=(p2.y+10.123)/2;
        double k2=(p2.y-p20.y)/(p2.x-p20.x);
        k2=-1/k2;
        double b2=p20.y-k2*p20.x;
        
        double xx=(b2-b1)/(k1-k2);
        double yy=k1*xx+b1;
        
        double bb=(xx-3.414)*(xx-3.414)+(yy-10.123)*(yy-10.123);
        double cc=(xx-p2.x)*(xx-p2.x)+(yy-p2.y)*(yy-p2.y);
        double aa=(p2.x-3.414)*(p2.x-3.414)+(p2.y-10.123)*(p2.y-10.123);
        double ct=(bb+cc-aa)/(2*sqrt(bb)*sqrt(cc));
        
        point p3={2*xx-p0.x,2*yy-p0.y};
        point p4={(p1.x+p2.x)/2,(p1.y+p2.y)/2};
        
        double k3=(p3.y-p0.y)/(p3.x-p0.x);
        double b3=p3.y-k3*p3.x;
        
        point pp={xx,yy};
        point p5=rotate(p0,pp,1);
        
        if ((p4.x*k3+b3-p4.y)*(p5.x*k3+b3-p5.y)>0) printf("%.10lf %.10lf %.10lf\n",xx,yy,acos(ct));
        else printf("%.10lf %.10lf %.10lf\n",xx,yy,2*Pi-acos(ct));
    }
    
    return 0;
}

启发

对于计算几何的东西，真的需要提前准备下模板，主要的几何思想要看数学能力。

---

E、Walk

Time Limit: 30000/15000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Problem Description

I used to think I could be anything, but now I know that I couldn’t do anything. So I started traveling.

The nation looks like a connected bidirectional graph, and I am randomly walking on it. It means when I am at node i, I will travel to an adjacent node with the same probability in the next step. I will pick up the start node randomly (each node in the graph has the same probability.), and travel for d steps, noting that I may go through some nodes multiple times.

If I miss some sights at a node, it will make me unhappy. So I wonder for each node, what is the probability that my path doesn’t contain it.

Input

The first line contains an integer T, denoting the number of the test cases.

For each test case, the first line contains 3 integers n, m and d, denoting the number of vertices, the number of edges and the number of steps respectively. Then m lines follows, each containing two integers a and b, denoting there is an edge between node a and node b.

T<=20, n<=50, n-1<=m<=n*(n-1)/2, 1<=d<=10000. There is no self-loops or multiple edges in the graph, and the graph is connected. The nodes are indexed from 1.

Output

For each test cases, output n lines, the i-th line containing the desired probability for the i-th node.

Your answer will be accepted if its absolute error doesn’t exceed 1e-5.

Sample Input

2
5 10 100
1 2
2 3
3 4
4 5
1 5
2 4
3 5
2 5
1 4
1 3
10 10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
4 9

Sample Output

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.6993317967
0.5864284952
0.4440860821
0.2275896991
0.4294074591
0.4851048742
0.4896018842
0.4525044250
0.3406567483
0.6421630037

题意

随机随机随机！！…在一张无向图中，随机选定一个起点出发，之后的每一步都是等概率的。有一些点不能被到达，这里要求的就是每一个点不能被到达的概率。

分析

概率DP的题目做得太少了，以至于当时最后的时间基本都花在这里了，还是没有什么想法。每次都是这样，比完之后才能想到最后的正解，唉。当时纠结的是怎么记录访问过的路径，然后判断每一次遍历完之后有哪些点是该次没有被访问过的。这个想法完全是不可行的。

既然是判断一个点不能到达的概率，则直接把这个点从图中去掉，依次递推其他所有点在走完d步之后到达的概率，结果的总和就是不能到达该点的概率。

概率DP的状态转移方程：f(i,j)=f(i-1,front[j])/num[front[j]]

求解的时候，依次枚举一个点，把这个点拿掉，然后递推DP结果，由于当前步的状态只与前一步有关，这里可以用滚动数组处理。

前向星是我的个人习惯，这里恰好需要一个计算的变量，前向星的结构恰好满足。

/* ***********************************************
MYID    : Chen Fan
LANG    : G++
PROG    : E1005
************************************************ */

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

using namespace std;

typedef struct nod
{
    int a,b;
} node;
node a[3000];
int start[60],num[60],n,m,d,tot;
bool ma[60][60];
double ans[60],temp[2][60];

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

int main()
{
    freopen("E1005.txt","r",stdin);
    
    int t;
    scanf("%d",&t);
    for (int tt=1;tt<=t;tt++)
    {
        scanf("%d%d%d",&n,&m,&d);
        memset(ma,0,sizeof(ma));
        int tail=0;
        for (int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if (!ma[x][y])
            {
                ma[x][y]=true;
                ma[y][x]=true;
                tail++;
                a[tail].a=x;
                a[tail].b=y;
                tail++;
                a[tail].a=y;
                a[tail].b=x;
            }
        }
        sort(&a[1],&a[tail+1],op);
        int o=0;
        memset(num,0,sizeof(num));
        for (int i=1;i<=tail;i++)
        {
            if (o!=a[i].a)
            {
                o=a[i].a;
                start[o]=i;
            }
            num[o]++;
        }
        
        memset(ans,0,sizeof(ans));
        for (int k=1;k<=n;k++)
        {
            memset(temp,0,sizeof(temp));
            int key=1;
            for (int i=1;i<=n;i++)
            if (i!=k) temp[0][i]=1.0/n;
            
            for (int i=1;i<=d;i++)
            {
                memset(temp[key],0,sizeof(temp[key]));
                for (int j=1;j<=n;j++)
                {
                    for (int o=0;o<num[j];o++)
                    if (a[start[j]+o].b!=k)
                    temp[key][a[start[j]+o].b]+=temp[1-key][j]/(double)num[j];
                }
                key=1-key;
            }
            key=1-key;
            
            for(int i=1;i<=n;i++)
            if (i!=k) ans[k]+=temp[key][i];
        }
        
        for (int i=1;i<=n;i++)
        printf("%.10lf\n",ans[i]);
    }
    
    return 0;
}

启发

题目中碰到一个点对前后状态影响较大，无法直接推算或者直接算需要涉及到大量复杂记录的情况，可以考虑先把这个点拿掉，完成之后再放上去，或者先把其变为普通点，完成后再恢复（后面有广州赛区的D题就是这种思想）

---

G、Osu!

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Special Judge

Problem Description

Osu! is a famous music game that attracts a lot of people. In osu!, there is a performance scoring system, which evaluates your performance. Each song you have played will have a score. And the system will sort all you scores in descending order. After that, the i-th song scored ai will add 0.95^(i-1)*ai to your total score.

Now you are given the task to write a calculator for this system.

Input

The first line contains an integer T, denoting the number of the test cases.

For each test case, the first line contains an integer n, denoting the number of songs you have played. The second line contains n integers a1, a2, …, an separated by a single space, denoting the score of each song.

T<=20, n<=50, 1<=ai<=500.

Output

For each test case, output one line for the answer.
Your answers will be considered correct if its absolute error is smaller than 1e-5.

Sample Input

1
2
530 478

Sample Output

984.1000000000

题意

排序+pow函数输出即可。