Gallagher's profileCAsH bACKPhotosBlogListsMore  |  Tools Help |
CAsH bACK |
|||||
|
see u when i see u.
Xredmanwrote:
这题并查集怎么做到的？
Apr. 14
|
Zju 3203/Zoj 3203 Light Bulb/* finished at 2009-06-29 18:11:28 555，省赛挂掉的题目，考研高数很尴尬。 分为两类情况：(1).影子不射到墙上;(2).影子射到墙上。 对第2种情况，x在闭区间内求最大值，求两端点 加 极值点（如果有）即可。 */ #include<iostream> #include<cmath> using namespace std; int main() { double H,h,D,x,left,right,ans; int t; cin>>t; while(t--) { cin>>H>>h>>D; x=sqrt(D*(H-h)); left=D*(1-h/H); right=D; if(x>=left && x<=right) { ans=H+D-2*x; x=D; ans=max(ans,H+D-x-D*(H-h)/x); x=D*(H-h)/H; ans=max(ans,H+D-x-D*(H-h)/x); } else { x=D; ans=H+D-x-D*(H-h)/x; x=D*(H-h)/H; ans=max(ans,H+D-x-D*(H-h)/x); } ans=max(ans,h*D/H);//阴影不在墙上 printf("%.3lf\n",ans); } return 0; } 80%完美的日子（暂时结束了，farewell）wuxinghe
(80%完美的日子)
AC Ratio: 357/1470 Plan:由我来重蹈你覆辙。
Pku 3736/Poj 3736 Snipe the Sniper /* finished at 2009-05-18 10:52:06 最优策略：所有敌人都沿直线往(100,0)走，将攻击集中于该点。 */ #include<iostream> #include<cmath> #include<algorithm> using namespace std; typedef struct { double d,x,y,r,hurt,time; }Enemy; Enemy e[105]; bool comp(Enemy a,Enemy b) { return a.d<b.d; } double dis(double a,double b,double c,double d) { return sqrt((a-c)*(a-c)+(b-d)*(b-d)); } int main() { int i,j,n,flag,mark; double HP,Stun_Time; while(cin>>n) { for(i=0;i<n;i++) { cin>>e[i].x>>e[i].y>>e[i].time>>e[i].r>>e[i].hurt; e[i].d=dis(100.0,0.0,e[i].x,e[i].y)-e[i].r;//d保存该敌人到(100,0)的距离（包括半径） } cin>>HP; sort(e+0,e+n,comp); i=flag=0; while(i<n&&flag==0) { Stun_Time=0; mark=0; for(;i<n;i++) { if(e[i].d<=100)//在攻击范围内 { mark=1; HP-=e[i].hurt; if(HP<=0) { flag=1; break; } Stun_Time+=e[i].time; } else { for(j=i;j<n;j++) { e[j].d-=Stun_Time; } break; } } if(mark==0) break; } if(flag==1) { cout<<"Danger!"<<endl; } else { cout<<"Safe!"<<endl; } } return 0; } Zju 2750/Zoj 2750 Idiomatic Phrases Game /* finished at 2009-05-07 19:58:01 Dijkstra 测模板（顺带）。满意。 */ #include<iostream> #include<cstring> using namespace std; const int MAX=100000000; int g[1005][1005]; int n,s[1005],dist[1005]; void dijkstra(int v) { int i,j,k,MIN; for(i=1;i<=n;i++) { s[i]=0; dist[i]=g[v][i]; } s[v]=1; dist[v]=MAX; for(i=2;i<=n;i++) { MIN=MAX; for(j=1;j<=n;j++) { if(j==v) { continue; } if(s[j]==0&&dist[j]<MIN) { MIN=dist[j]; k=j; } } if(MIN==MAX) break; s[k]=1; for(j=1;j<=n;j++) { if(s[j]==0&&dist[j]>dist[k]+g[k][j]) { dist[j]=dist[k]+g[k][j]; } } } } int main() { char idiom[100],head[1005][5],tail[1005][5]; int i,j,len,time[1005]; while(scanf("%d",&n)&&n) { for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { g[i][j]=MAX; } } for(i=1;i<=n;i++) { scanf("%d",&time[i]); scanf("%s",idiom); //head[i]=idiom.substr(0,4); head[i][0]=idiom[0]; head[i][1]=idiom[1]; head[i][2]=idiom[2]; head[i][3]=idiom[3]; head[i][4]='\0'; //tail[i]=idiom.substr(idiom.length()-4,4); len=strlen(idiom); tail[i][0]=idiom[len-4]; tail[i][1]=idiom[len-3]; tail[i][2]=idiom[len-2]; tail[i][3]=idiom[len-1]; tail[i][4]='\0'; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { if(strcmp(tail[i],head[j])==0) { g[i][j]=time[i]; } } } dijkstra(1); if(dist[n]==MAX) cout<<-1<<endl; else cout<<dist[n]<<endl; } return 0; } Zju 2158/Zoj 2158 Truck History /* finished at 2009-04-28 12:51:38 Prim模板测试。满意。 */ #include<iostream> #include<cstring> using namespace std; const int MAX=10000000; int n,length,g[2005][2005];//length记录最小生成树的总距离 char w[2005][100]; typedef struct { int dist;//候选顶点到已生成树的距离 int mark;//已选标记 }Vertex;//候选点集 Vertex v[2005]; int Get_Distance(int s,int t) { int i,len,sum; sum=0; len=strlen(w[s]); for(i=0;i<len;i++) { if(w[s][i]!=w[t][i]) sum++; } return sum; } void prim(int ori)//从点ori出发搜生成树 { int temp_min; int i,temp_v=0,sum=0;//sum记录已生成树中的顶点数 for(i=1;i<=n;i++)//initial { v[i].dist=g[i][ori]; v[i].mark=0; } v[ori].dist=0; v[ori].mark=1; sum++; while(sum<n)//选出n个点 { temp_min=MAX; for(i=1;i<=n;i++)//从候选顶点中选出距离已生成树最近的点 { if(v[i].mark==0)//未选 { if(temp_min>v[i].dist) { temp_min=v[i].dist; temp_v=i; } } } if(temp_min<MAX)//把选出的顶点加入树 { length+=v[temp_v].dist; v[temp_v].mark=1; sum++; } for(i=1;i<=n;i++)//调整候选顶点到已生成树的距离 { if(v[i].mark==0) { if(v[i].dist>g[i][temp_v]) { v[i].dist=g[i][temp_v]; } } } } } int main() { int i,j; while(scanf("%d",&n)&&n) { for(i=1;i<=n;i++) { scanf("%s",&w[i]); } for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { g[i][j]=Get_Distance(i,j); g[j][i]=g[i][j]; } } length=0; prim(1); printf("The highest possible quality is 1/%d.\n",length); } return 0; } Zju 2048/Zoj 2048 Highways /* finished at 2009-04-27 20:22:01 已建边权值赋0，Prim MST输出权值非0的边。 */ #include<iostream> using namespace std; const double MAX=100000000; int m,n; double g[755][755]; typedef struct { double x,y; }Point; Point p[755]; typedef struct { double dist; int s,mark;//s记录邻接端点 }Vertex; Vertex v[755]; double Get_Distance(int a,int b) { return (p[a].x-p[b].x)*(p[a].x-p[b].x)+(p[a].y-p[b].y)*(p[a].y-p[b].y); } void initial() { int i,j; for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) { g[i][j]=g[j][i]=Get_Distance(i,j); } } } void prim(int ori) { double temp_min; int i,temp_v=0,sum=0;//sum记录已生成树中的顶点数 for(i=1;i<=n;i++)//initial { v[i].dist=g[i][ori]; v[i].mark=0; v[i].s=ori; } v[ori].dist=0; v[ori].mark=1; sum++; while(sum<n) { temp_min=MAX; for(i=1;i<=n;i++)//从候选顶点中选出距离已生成树最近的点 { if(v[i].mark==0) { if(temp_min>v[i].dist) { temp_min=v[i].dist; temp_v=i; } } } if(temp_min<MAX)//把选出的顶点加入树 { if(temp_min!=0)//输出新生成树边 { cout<<v[temp_v].s<<" "<<temp_v<<endl; } v[temp_v].mark=1; sum++; } for(i=1;i<=n;i++)//调整候选顶点到已生成树的距离 { if(v[i].mark==0) { if(v[i].dist>g[i][temp_v]) { v[i].dist=g[i][temp_v]; v[i].s=temp_v; } } } } } int main() { int i,t,a,b; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%lf%lf",&p[i].x,&p[i].y); } initial(); scanf("%d",&m); for(i=1;i<=m;i++) { scanf("%d%d",&a,&b); g[a][b]=g[b][a]=0;//已建highway，边权值赋0 } prim(1); if(t!=0) cout<<endl; } return 0; } Hdu 2670/Hdoj 2670 Girl Love Value /* finished at 2009-04-27 13:44:16 把问题分为两个子问题： 1.选出哪k个boy； 2.按什么顺序选。 每个boy有两个属性：喜欢度 和 衰减速度。 其中衰减速度是关键。 我的感觉是：最好先选择衰减速度快的人（貌似贪心），好让总的衰减值最小。 因此先按衰减速度递减排序（解决子问题2），再DP（解决子问题1）。 其中f[i][j]表示：从前i个人中 按一定次序选出j个人 得到的最优喜欢度。 */ #include<iostream> #include<algorithm> using namespace std; int n,k,f[1005][1005]; typedef struct { int d,v; }Boy; Boy b[1005]; bool comp(Boy x,Boy y) { return x.d>y.d; } int main() { int i,j,MAX; while(scanf("%d%d",&n,&k)!=EOF) { for(i=1;i<=n;i++) { scanf("%d",&b[i].v); } for(i=1;i<=n;i++) { scanf("%d",&b[i].d); } sort(b+1,b+1+n,comp);//按衰减速度递减排序 MAX=0; for(i=1;i<=n;i++) { if(b[i].v>MAX) { MAX=b[i].v; } f[i][1]=MAX; } for(i=2;i<=n;i++) { for(j=2;j<=i;j++) { if(i-1<j) { f[i][j]=f[i-1][j-1]+b[i].v-(j-1)*b[i].d; } else { f[i][j]=max(f[i-1][j],f[i-1][j-1]+b[i].v-(j-1)*b[i].d); } } } cout<<f[n][k]<<endl; } return 0; } Zju 1825/Zoj 1825 Compound Words /* finished at 2009-04-26 20:14:46 STL水过... */ #include<iostream> #include<string> #include<set> using namespace std; int main() { set<string>::iterator p; set<string> dic; string s,t1,t2; int i,len; while(cin>>s) { dic.insert(s); } for(p=dic.begin();p!=dic.end();p++) { s=*p; len=s.length(); for(i=1;i<s.length();i++) { t1=s.substr(0,i); t2=s.substr(i,s.length()-i); if(dic.find(t1)!=dic.end() && dic.find(t2)!=dic.end()) { cout<<s<<endl; break; } } } return 0; } Zju 1953/Zoj 1953 Advanced Fruits/* finished at 2009-04-26 00:07:41 f[i][j]：x的前i个字符 和 y的前j个字符 合并的新串的最短长度。 “白杨树初长成，兔兔龙席地而坐，龙牛精越山而居。” 很久没有半夜工作了，555。由我来重蹈你覆辙。 */ #include<iostream> #include<string> using namespace std; int main() { int i,j,lx,ly,len,temp,f[105][105]; string x,y,z[105][105]; while(cin>>x>>y) { lx=x.length(); ly=y.length(); z[0][0]=""; f[0][0]=0; for(i=1;i<=lx;i++) { z[i][0]=z[i-1][0]+x[i-1]; f[i][0]=i; } for(j=1;j<=ly;j++) { z[0][j]=z[0][j-1]+y[j-1]; f[0][j]=j; } for(i=1;i<=lx;i++) { for(j=1;j<=ly;j++) { if(x[i-1]==y[j-1]) { temp=min(f[i-1][j]+1,f[i][j-1]+1); temp=min(temp,f[i-1][j-1]+1); } else { temp=min(f[i-1][j]+1,f[i][j-1]+1); temp=min(temp,f[i-1][j-1]+2); } if(temp==f[i-1][j]+1) { z[i][j]=z[i-1][j]+x[i-1]; } else if(temp==f[i][j-1]+1) { z[i][j]=z[i][j-1]+y[j-1]; } else if(temp==f[i-1][j-1]+1) { z[i][j]=z[i-1][j-1]+x[i-1]; } else if(temp==f[i-1][j-1]+2) { z[i][j]=f[i-1][j-1]+x[i-1]; z[i][j]+=y[j-1]; } f[i][j]=temp; } } //cout<<f[lx][ly]<<endl; cout<<z[lx][ly]<<endl; } return 0; } Zju 1648/Zoj 1648 Circuit Board /* finished at 2009-04-22 10:02:29 直接贴判直线相交的模板（LYS）就能过。 一个优化：按左端点横坐标排序所有线段，再做相应测试即可。 3 1 1 4 4 2 1 4 2 3 2 3 4 burned! */ #include<iostream> #include<algorithm> using namespace std; struct Point { double x; double y; }; struct Segment { Point left; Point right; }; Segment seg[2005]; bool comp(Segment a,Segment b) { if(a.left.x==b.left.x) return a.right.x<b.right.x; return a.left.x<b.left.x; } double direction(Point p0,Point p1,Point p2) { return (p2.x-p0.x)*(p1.y-p0.y)-(p1.x-p0.x)*(p2.y-p0.y); } bool on_segment(Point p0,Point p1,Point p2) { if((min(p0.x,p1.x)<=p2.x && p2.x<=max(p0.x,p1.x)) && (min(p0.y,p1.y)<=p2.y && p2.y<=max(p0.y,p1.y))) return true; return false; } bool Segment_intersect(Point p1,Point p2,Point p3,Point p4) { double d1,d2,d3,d4; d1 = direction(p3,p4,p1); d2 = direction(p3,p4,p2); d3 = direction(p1,p2,p3); d4 = direction(p1,p2,p4); if(((d1>0 && d2<0)||(d1<0 && d2>0)) && ((d3>0 && d4<0)||(d3<0&&d4>0))) return true; else if(d1==0 && on_segment(p3,p4,p1)) return true; else if(d2==0 && on_segment(p3,p4,p2)) return true; else if(d3==0 && on_segment(p1,p2,p3)) return true; else if(d4==0 && on_segment(p1,p2,p4)) return true; return false; } int main() { int i,j,n,flag; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) { scanf("%lf%lf%lf%lf",&seg[i].left.x,&seg[i].left.y,&seg[i].right.x,&seg[i].right.y); } sort(seg+0,seg+n,comp); flag=0; for(i=0;i<n-1;i++) { if(flag==1) { continue; } for(j=i+1;j<n;j++) { if(seg[j].left.x<=seg[i].right.x) { if(Segment_intersect(seg[i].left,seg[i].right,seg[j].left,seg[j].right)) { flag=1; break; } } else { break; } } } if(flag==0) cout<<"ok!"<<endl; else cout<<"burned!"<<endl; } return 0; } |
||||
|
|
