A.ZOJ3726 Alice‘s Print Service

题解 here

这道题在HDU上要用I64d 在ZOJ上要用lld

C.ZOJ3728 Collision

几何题，分几种情况：和大圆相离、和大圆相交和小圆相离、和大圆相交小圆也相交。

还有一种情况需要考虑，它飞的方向远离圆则永远不相交。

借用土豪的神模板

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 1010
#define eps 1e-8
#define INF 0x7FFFFFFF
#define long long ll;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct point {
    double x,y;
};

double xmult(point p1,point p2,point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

double Distance(point p1,point p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}

double disptoline(point p,point l1,point l2)
{
    return fabs(xmult(p,l1,l2))/Distance(l1,l2);
}

point intersection(point u1,point u2,point v1,point v2)
{
    point ret=u1;
    double t=((u1.x-v1.x)*(v1.y-v2.y)-(u1.y-v1.y)*(v1.x-v2.x))
             /((u1.x-u2.x)*(v1.y-v2.y)-(u1.y-u2.y)*(v1.x-v2.x));
    ret.x+=(u2.x-u1.x)*t;
    ret.y+=(u2.y-u1.y)*t;
    return ret;
}

//判直线和圆相交,包括相切
int intersect_line_circle(point c,double r,point l1,point l2)
{
    if(disptoline(c,l1,l2)-r>-eps) {
        return 0;
    } else {
        return 1;
    }
}

//判线段和圆相交,包括端点和相切
int intersect_seg_circle(point c,double r,point l1,point l2)
{
    double t1=Distance(c,l1)-r,t2=Distance(c,l2)-r;
    point t=c;
    if (t1<eps||t2<eps) {
        return t1>-eps||t2>-eps;
    }
    t.x+=l1.y-l2.y;
    t.y+=l2.x-l1.x;
    return xmult(l1,c,t)*xmult(l2,c,t)<eps&&disptoline(c,l1,l2)-r<eps;
}

//判圆和圆相交,包括相切
int intersect_circle_circle(point c1,double r1,point c2,double r2)
{
    return Distance(c1,c2)<r1+r2+eps&&Distance(c1,c2)>fabs(r1-r2)-eps;
}

//计算圆上到点p最近点,如p与圆心重合,返回p本身
point dot_to_circle(point c,double r,point p)
{
    point u,v;
    if (Distance(p,c)<eps) {
        return p;
    }
    u.x=c.x+r*fabs(c.x-p.x)/Distance(c,p);
    u.y=c.y+r*fabs(c.y-p.y)/Distance(c,p)*((c.x-p.x)*(c.y-p.y)<0?-1:1);
    v.x=c.x-r*fabs(c.x-p.x)/Distance(c,p);
    v.y=c.y-r*fabs(c.y-p.y)/Distance(c,p)*((c.x-p.x)*(c.y-p.y)<0?-1:1);
    return Distance(u,p)<Distance(v,p)?u:v;
}

//计算直线与圆的交点,保证直线与圆有交点
//计算线段与圆的交点可用这个函数后判点是否在线段上
void intersection_line_circle(point c,double r,point l1,point l2,point& p1,point& p2)
{
    point p=c;
    double t;
    p.x+=l1.y-l2.y;
    p.y+=l2.x-l1.x;
    p=intersection(p,c,l1,l2);
    t=sqrt(r*r-Distance(p,c)*Distance(p,c))/Distance(l1,l2);
    p1.x=p.x+(l2.x-l1.x)*t;
    p1.y=p.y+(l2.y-l1.y)*t;
    p2.x=p.x-(l2.x-l1.x)*t;
    p2.y=p.y-(l2.y-l1.y)*t;
}

//计算圆与圆的交点,保证圆与圆有交点,圆心不重合
void intersection_circle_circle(point c1,double r1,point c2,double r2,point& p1,point& p2)
{
    point u,v;
    double t;
    t=(1+(r1*r1-r2*r2)/Distance(c1,c2)/Distance(c1,c2))/2;
    u.x=c1.x+(c2.x-c1.x)*t;
    u.y=c1.y+(c2.y-c1.y)*t;
    v.x=u.x+c1.y-c2.y;
    v.y=u.y-c1.x+c2.x;
    intersection_line_circle(c1,r1,u,v,p1,p2);
}
int main ()
{
    double Rm,R,r,x,y,vx,vy;
    while(~scanf("%lf %lf %lf %lf %lf %lf %lf",&Rm,&R,&r,&x,&y,&vx,&vy)) {
        point O;
        O.x=0;
        O.y=0;
        point P;
        P.x=x;
        P.y=y;
        point Pd;
        Pd.x=x+vx/10;
        Pd.y=y+vy/10;
        point p1,p2,p3,p4;
        if(Distance(O,P)<Distance(O,Pd))  {
            printf("0\n");
            continue;
        }

        if(intersect_line_circle(O,R+r,P,Pd)==0) {
            printf("0\n");    //与大圆相离
            continue;
        } else if(intersect_line_circle(O,Rm+r,P,Pd)==0) { //与小圆相离
            intersection_line_circle(O,R+r,P,Pd,p1,p2);
            if(p1.x!=p2.x) {
                printf("%.3lf\n",fabs((p1.x-p2.x)/vx));
            } else {
                printf("%.3lf\n",fabs((p1.y-p2.y)/vy));
            }
        } else {
            intersection_line_circle(O,R +r,P,Pd,p1,p2);
            intersection_line_circle(O,Rm+r,P,Pd,p3,p4);
            if(p1.x!=p2.x) {
                printf("%.3lf\n",2*fabs((max(p1.x,p2.x)-max(p3.x,p4.x))/vx));
            } else {
                printf("%.3lf\n",2*fabs((max(p1.y,p2.y)-max(p3.y,p4.y))/vy));
            }
        }
    }
}
/*
5 20 1 0 100 0 -1
5 20 1 30 15 -1 0
5 20 1 0 21  1  0
*/

F.ZOJ3731 Winter‘s Coming

感觉就是个简单的搜索，但是hdu、uva上都没有人过，目前uva上唯一的那一发submission是我华丽的WA，杭电上十几发submission一半是我交的。。。。zoj上有两个人过，我没过，而且还是坏习惯一直dfs在写迷宫，没T，WA成了狗。我的想法是用lw数组来存放每行最右端的W，用rl数组存放每行最左端的L，初始lw赋比0小，rl赋比m大，从第一行lw和rl之间开始枚举dfs，每一行把max（lw，0）当左边界，min（rl，m）当右边界，感觉还是挺简单的题。。。但是还是没AC

G.ZOJ3732 Graph Reconstruction

我之前刚好做过一个一样的题，点击这里，还是Havel-Hakimi定理，这题唯一的区别就是如果有多种可能就输出两组结果。我YY了一下，每次第二大的度数开始减一，减到最后一个数时将这个度和它的下一个度比较（如果存在的话），如果它们度一样，说明存在多组解，然后再用Havel-Hakimi定理扫一遍，第一回排序对度一样的情况按id从大到小排序，第二回对度一样的情况按id从小到大排序，这样就能产生两组解了，网上还有交换的方法， 不过交换起来相应的边都要改变，时间上都要进行两遍Havel-Hakimi扫描，我觉得我的方法更好想一些，不过缺点是我的方法只能找到两种解，如果题目需要输出三种解还是要用交换的方法。不过。。。可能我写的太挫，至今WA成狗

H.ZOJ3733 Skycity

J.ZOJ3735 Josephina and RPG

dp[i][j]: 和前i个队伍交战后所选队伍是j的最高胜率

状态转移方程：
dp[i][j] = max(dp[i][j],dp[i-1][j]*P[j][no[i]]); //代表不换
dp[i][no[i]] = max(dp[i][no[i]],dp[i-1][j]*P[j][no[i]]);//代表换战队

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 1010
#define eps 1e-11
#define INF 0x7FFFFFFF
#define long long ll;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

double a[150][150];
double dp[10010][150];
int r[10010];
int main(){
    int n,m,i,j;
    while(scanf("%d",&n)!=EOF){
        n = n*(n-1)*(n-2)/6;
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                scanf("%lf",&a[i][j]);
            }
        }
        scanf("%d",&m);
        for(i=0;i<n;i++){
            dp[0][i] = 1;
            for(j=1;j<=m;j++)
                dp[j][i] = 0;
        }
        for(i=1;i<=m;i++){
            scanf("%d",&r[i]);
        }
        for(i=1;i<=m;i++){
            for(j=0;j<n;j++){
                dp[i][j]=max(dp[i][j],dp[i-1][j]*a[j][r[i]]);
                dp[i][r[i]]=max(dp[i][r[i]],dp[i-1][j]*a[j][r[i]]);
            }
        }
        double ans = 0;
        for(i=0;i<n;i++){
            if(dp[m][i]>ans)    ans = dp[m][i];
        }
        printf("%.6lf\n",ans);
    }
    return 0;
}