首页 > 代码库 > 2013腾讯编程马拉松初赛第4,5场
2013腾讯编程马拉松初赛第4,5场
HDU 4520
A
直接模拟
#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 100010 #define ll __int64 double z[50]; int main() { int n; while(scanf("%d",&n)!=EOF) { if(n==0) break; double sum=0,mx=0,mi=10; for(int i=1;i<=n;i++) { scanf("%lf",&z[i]); sum=sum+z[i]; mx=max(mx,z[i]); mi=min(mi,z[i]); } sum=sum-mx-mi; sum=sum/(n-2); int ind; double mx1=10; for(int i=1;i<=n;i++) { if(fabs(z[i]-sum)<mx1) { mx1=fabs(z[i]-sum); ind=i; } } printf("%d\n",ind); } return 0; }
HDU 4521
B
维护一个 i-d的LIS
#include <cstdlib> #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int N = 100005; int n, d; int seq[N]; int alen[N]; void solve() { vector<int>vt; vector<int>::iterator it; int ret = 0; for (int i = 1; i <= n; ++i) { it = lower_bound(vt.begin(), vt.end(), seq[i]); if (it == vt.end()) alen[i] = vt.size()+1; else alen[i] = it-vt.begin()+1; if (i-d >= 1) { if (vt.size() == alen[i-d]-1) vt.push_back(seq[i-d]); else if (vt[alen[i-d]-1] > seq[i-d]) vt[alen[i-d]-1] = seq[i-d]; } ret = max(ret, alen[i]); } printf("%d\n", ret); } int main() { while (scanf("%d %d", &n, &d) != EOF) { for (int i = 1; i <= n; ++i) { scanf("%d", &seq[i]); } solve(); } return 0; }
HDU 4522
C
2遍SPFA
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> using namespace std; #define inf 1000000007 #define MAXN 210 #define ll __int64 int head[MAXN]; bool vis[MAXN]; struct node { int v,next,ok; }edge[10000010]; int cnt; char s[10010]; int d0,d1; int S,T,n,m; int d[MAXN]; deque<int>q1; void add(int u,int v,int ty) { edge[cnt].ok=ty; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } ll spfa1() //硬 { memset(vis,0,sizeof(vis)); vis[S]=1; q1.push_back(S); for(int i=1;i<=n;i++) d[i]=inf; d[S]=0; while(!q1.empty()) { int now=q1.front(); q1.pop_front(); vis[now]=0; for(int i=head[now];i!=-1;i=edge[i].next) { int v=edge[i].v; if(d[v]>d[now]+1) { d[v]=d[now]+1; if(!vis[v]) { if(q1.empty()) q1.push_back(v); else { if(d[v]<d[q1.front()]) q1.push_front(v); else q1.push_back(v); } vis[v]=1; } } } } if(d[T]==inf) return -1; return (ll)d[T]*d0; } ll spfa2() //软 { memset(vis,0,sizeof(vis)); vis[S]=1; q1.push_back(S); for(int i=1;i<=n;i++) d[i]=inf; d[S]=0; while(!q1.empty()) { int now=q1.front(); q1.pop_front(); vis[now]=0; for(int i=head[now];i!=-1;i=edge[i].next) { int v=edge[i].v; if(edge[i].ok==1) { if(d[v]>d[now]+1) { d[v]=d[now]+1; if(!vis[v]) { if(q1.empty()) q1.push_back(v); else { if(d[v]<d[q1.front()]) q1.push_front(v); else q1.push_back(v); } vis[v]=1; } } } } } if(d[T]==inf) return -1; return (ll)d[T]*d1; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); cnt=0; for(int i=1;i<=m;i++) { int ty; scanf("%s %d",s,&ty); int len=strlen(s); int a; a=0; int j; // printf("%s\n",s); for(j=0;j<len;j++) { if(s[j]==‘+‘) break; a=a*10+s[j]-‘0‘; } int b=0; for(j++;j<len;j++) { if(s[j]==‘+‘) { // printf("%d %d\n",a,b); add(a,b,ty); a=b; b=0; } else { b=b*10+s[j]-‘0‘; } } add(a,b,ty); } scanf("%d%d",&d0,&d1); scanf("%d%d",&S,&T); //printf("111\n"); /* for(int i=0;i<cnt;i++) printf("%d %d\n",edge[i].v,edge[i].ok); */ ll ans1=spfa1(); ll ans2=spfa2(); ll ans; if(ans1!=-1&&ans2!=-1) ans=min(ans1,ans2); else ans=max(ans1,ans2); printf("%I64d\n",ans); } return 0; }
HDU 4523
D
3<=m<=n+p
其实可以用double 高精度 java
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> using namespace std; #define inf 1000000007 #define MAXN 210 #define ll __int64 int main() { double n,m,p; while(scanf("%lf%lf%lf",&n,&m,&p)!=EOF) { if(m<=2) printf("NO\n"); else { if(p==0) { if(n==m) printf("YES\n"); else printf("NO\n"); } else if(n+p>=m) printf("YES\n"); else printf("NO\n"); } } return 0; }
HDU 4524
E
模拟
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> using namespace std; #define inf 1000000007 #define MAXN 1000010 #define ll __int64 int z[MAXN]; int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&z[i]); int ok=0; for(int i=n-1;i>=1;i--) { if(z[i]>=z[i+1]) { z[i]-=z[i+1]; z[i+1]=0; } } for(int i=1;i<=n;i++) if(z[i]) ok=1; if(ok==1) printf("I will never go out T_T\n"); else printf("yeah~ I escaped ^_^\n"); } return 0; }
HDU 4525
F
sum(n) = sum(n-1)*(k1+k2)
然后判断下 double ll 会炸
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> using namespace std; #define inf 1000000007 #define MAXN 210 #define ll __int64 int main() { int t,ca; scanf("%d",&t); ca=1; while(t--) { int n,k1,k2; ll k; scanf("%d%d%d%I64d",&n,&k1,&k2,&k); double sum=0; for(int i=1;i<=n;i++) { int a; scanf("%d",&a); sum=sum+a; } ll ans=0; if(sum>k) ans=0; else { if(sum==0) ans=inf; else if(k1+k2>=-1&&k1+k2<=1) ans=inf; else { while(sum<=k) { sum=sum*(k1+k2); ans++; } } } if(ans==inf) printf("Case #%d: inf\n",ca++); else printf("Case #%d: %I64d\n",ca++,ans); } return 0; }
HDU 4526
G
dp[i][j] 到第i辆车为止上了j 个人
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<deque> using namespace std; #define inf 1000000007 #define MAXN 210 #define ll __int64 struct node { int t,num; }z[MAXN]; int dp[110][110]; int main() { int t; scanf("%d",&t); while(t--) { int n,k,d,s; scanf("%d%d%d%d",&n,&k,&d,&s); for(int i=1;i<=k;i++) scanf("%d %d",&z[i].t,&z[i].num); for(int i=0;i<=k;i++) { for(int j=0;j<=n;j++) dp[i][j]=inf; } dp[0][0]=0; for(int i=1;i<=k;i++) { for(int j=0;j<=n;j++) { for(int k=0;k<=z[i].num;k++) { dp[i][j]=min(dp[i][j],dp[i-1][j]); if(j<k) { dp[i][j]=min(dp[i][j],j*z[i].t+d); } else { dp[i][j]=min(dp[i][j],dp[i-1][j-k]+k*z[i].t+d); } } } } if(dp[k][n]==inf) printf("impossible\n"); else printf("%d\n",dp[k][n]); } return 0; }
HDU 4527
BFS
加一个时间
#include <iostream> #include <cstdio> #include <cmath> #include <map> #include <algorithm> #include <cstring> #include <string> #include<set> #include<queue> using namespace std; #define inf 1000000007 #define MAXN 10 #define ll __int64 int z[MAXN][MAXN]; struct node { int x,y,a,b,step; }; queue<node>q1; int s1[4]={1,0,-1,0}; int s2[4]={0,1,0,-1}; int main() { while(scanf("%d",&z[1][1])!=EOF) { for(int i=2;i<=6;i++) scanf("%d",&z[1][i]); for(int i=2;i<=6;i++) { for(int j=1;j<=6;j++) scanf("%d",&z[i][j]); } int m; scanf("%d",&m); while(m--) { int a,b; scanf("%d%d",&a,&b); z[a][b]++; if(z[a][b]>4) { int time=0; z[a][b]=0; node p; p.x=a; p.y=b; for(int i=0;i<4;i++) { p.a=s1[i]; p.b=s2[i]; p.step=0; q1.push(p); } while(!q1.empty()) { while(!q1.empty()&&q1.front().step==time) { node p1=q1.front(); q1.pop(); int x,y; x=p1.x+p1.a; y=p1.y+p1.b; if(x<1||x>6||y<1||y>6) continue; // printf("time %d x %d y %d\n",p1.step,x,y); if(z[x][y]) z[x][y]++; else { node p2; p2.x=x; p2.y=y; p2.a=p1.a; p2.b=p1.b; p2.step=p1.step+1; q1.push(p2); } } for(int i=1;i<=6;i++) { for(int j=1;j<=6;j++) { if(z[i][j]>4) { z[i][j]=0; node p1; p1.x=i; p1.y=j; p1.step=time+1; for(int k=0;k<4;k++) { p1.a=s1[k]; p1.b=s2[k]; q1.push(p1); } } } } time++; } } } for(int i=1;i<=6;i++) { for(int j=1;j<6;j++) printf("%d ",z[i][j]); printf("%d\n",z[i][6]); } printf("\n"); } return 0; }
2013腾讯编程马拉松初赛第4,5场
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。