A
HDU 4510
直接模拟
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> using namespace std; #define inf 1000000007 #define MAXN 500010 #define ll __int64 int main() { int t; scanf("%d",&t); while(t--) { int a,b,c,d,e,f; scanf("%d:%d:%d %d:%d:%d",&a,&b,&c,&d,&e,&f); d=d%12; int a1=a*3600+b*60+c; int b1=d*3600+e*60+f; if(a1<b1) a1=a1+12*3600; int c1=a1-b1; int a2,b2,c2; a2=c1/3600; b2=c1%3600/60; c2=c1%60; printf("%02d:%02d:%02d ",a2,b2,c2); } return 0; }
B
HDU 4511
spfa 记录路径 判断最短路径上是否是不能走的
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> using namespace std; #define inf 1000000000000007 #define MAXN 500010 #define ll __int64 struct node { double x,y; }z[55]; int fa[55]; double dis[55]; int x[110][6]; int num[110]; bool vis[55]; deque<int>q1; int n,m; double dis1(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double spfa(int s,int t) { for(int i=1;i<=n;i++) dis[i]=inf; memset(vis,0,sizeof(vis)); dis[s]=0; q1.push_back(s); vis[s]=1; while(!q1.empty()) { int now=q1.front(); q1.pop_front(); vis[now]=0; for(int i=now+1;i<=n;i++) { double d1=dis1(z[now].x,z[now].y,z[i].x,z[i].y); if(dis[now]+d1<dis[i]) { int ok=1; int ok1=0; for(int j=1;j<=m;j++) { if(i==x[j][num[j]]) ok1=1; if(i==x[j][num[j]]) { int aa=0; int bb=now; //printf("%d %d ",i,x[j][num[j]]); for(int k=num[j]-1;k>=1;k--) { // printf("%d %d ",bb,x[j][k]); if(bb!=x[j][k]) { aa=1; break; } bb=fa[bb]; } if(aa==0) ok=0; } } if(ok==1||ok1==0) { fa[i]=now; dis[i]=dis[now]+d1; if(!vis[i]) { if(q1.empty()) q1.push_back(i); else { if(dis[i]<dis[q1.front()]) q1.push_front(i); else q1.push_back(i); } vis[i]=1; } } } } } if(dis[t]==inf) return -1.0; return dis[t]; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { if(n==m&&m==0) break; for(int i=1;i<=n;i++) scanf("%lf%lf",&z[i].x,&z[i].y); for(int i=1;i<=m;i++) { scanf("%d",&num[i]); for(int j=1;j<=num[i];j++) scanf("%d",&x[i][j]); } double ans=spfa(1,n); for(int i=1;i<=n;i++) { // printf("%d %d ",i,fa[i]); } if(ans==-1) printf("Can not be reached! "); else printf("%.2lf ",ans); } return 0; }
C
hdu 4512
LICS 注意第二个循环的范围 和下标
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> using namespace std; #define inf 1000000000000007 #define MAXN 210 #define ll __int64 int z[MAXN]; int x[MAXN]; int dp[MAXN]; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&z[i]); for(int i=1;i<=n;i++) x[i]=z[n-i+1]; int mx1=0; for(int i=1;i<=n;i++) { int mx=0; for(int j=1;j<=n-i+1;j++) { if(z[i]>x[j]) mx=max(mx,dp[j]); else if(z[i]==x[j]) dp[j]=mx+1; if(i==n-j+1) mx1=max(mx1,dp[j]*2-1); else mx1=max(mx1,dp[j]*2); } } printf("%d ",mx1); } return 0; }