A.ZOJ3726 Alice's Print Service
题解 here
这道题在HDU上要用I64d 在ZOJ上要用lld
几何题，分几种情况：和大圆相离、和大圆相交和小圆相离、和大圆相交小圆也相交。
还有一种情况需要考虑，它飞的方向远离圆则永远不相交。
借用土豪的神模板
#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
*/
感觉就是个简单的搜索，但是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成狗
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;
}