首页 > 代码库 > Acdream手速赛7
Acdream手速赛7
蛋疼啊,本次只做出了一道题目。。。渣爆了。。。
妈蛋,,卡题之夜。。比赛结果是1道题,比赛完哗啦哗啦出4道题。。
A acdream1191 Dragon Maze
题意: 给一个迷宫,给出入口坐标和出口坐标,要求从入口到出口的步数尽可能少,如果有多种方案,则要求获得的分数尽可能多,获得的分数为经过的方格的数字之和
思路: bfs求最小步数,每走一步更新一下走到这个格子的最大权值
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int> pii;const int INF = 1e9;const double eps = 1e-6;const int N = 110;int cas = 1;const int dx[] = {0,0,-1,1};const int dy[] = {-1,1,0,0};int g[N][N],w[N][N];int dep[N][N],exitdep;bool vis[N][N];int n,m;int enx,eny,exx,exy;int ans;inline bool inside(int x,int y){ return x>=0 && x<n && y>=0 && y<m;}void bfs(){ exitdep = INF; ans = 0; memset(vis,0,sizeof(vis)); memset(w,0,sizeof(w)); queue<pii> que; vis[enx][eny]=1; que.push(make_pair(enx,eny)); dep[enx][eny]=0; w[enx][eny]=g[enx][eny]; while(!que.empty()) { int x = que.front().first; int y = que.front().second; que.pop(); if(dep[x][y]>exitdep) continue; if(x==exx && y==exy) { //ans = max(ans,w[x][y]); exitdep = dep[x][y]; } for(int i=0;i<4;i++) { int nx = x+dx[i]; int ny = y+dy[i]; if(!vis[nx][ny] || dep[nx][ny]==dep[x][y]+1) w[nx][ny]=max(w[nx][ny],w[x][y]+g[nx][ny]); if(vis[nx][ny] || g[nx][ny]==-1 || !inside(nx,ny)) continue; vis[nx][ny]=1; dep[nx][ny]=dep[x][y]+1; que.push(make_pair(nx,ny)); } }}void run(){ scanf("%d%d",&n,&m); int i,j; scanf("%d%d%d%d",&enx,&eny,&exx,&exy); for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("%d",&g[i][j]); bfs(); printf("Case #%d: ",cas++); if(exitdep==INF) puts("Mission Impossible."); else printf("%d\n",w[exx][exy]);}int main(){ #ifdef LOCAL freopen("case.txt","r",stdin); #endif int _; scanf("%d",&_); while(_--) run(); return 0;}
B acdream1207 qj的寻找爱情之旅
题意:有一个数量为n的序列,给出第一项,求第n项最小的时候是多少,要求满足
① H[i] = (H[i−1] + H[i+1])/2 − 1, 其中 1 < i < N
② Hi ≥ 0
思路: 容易推出 H[i] = 2*H[i-1] - H[i-2] + 2 由于H[1] 题目给出,所以只要知道H[2]就可以一个个推到H[n],我开始的时候暴力了一下,发现规律,当H[2]小的时候,后面会有某一个数不满足Hi>=0的条件,当H[2]大于某个界限的时候,就会满足Hi>=0而且H[2]越大H[n]就越大,所以只要当H[2]=界限的时候H[n]就是所求最小值 , 然后就容易想到二分H[2]
坑点: 18行那里,如果我写成h[i]<-eps就wa,写成h[i]<0就AC了,浮点数一直很蛋疼啊。。 以后涉及浮点的话就多尝试一下吧。。
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef pair<int,int> pii; 5 const int INF = 1e9; 6 const double eps = 1e-8; 7 const int N = 1010; 8 int cas = 1; 9 10 double h[N],ans;11 int n;12 13 bool solve()14 {15 for(int i=3;i<=n;i++)16 {17 h[i]=2*h[i-1]-h[i-2]+2;18 if(h[i]<0)19 return 0;20 }21 return 1;22 }23 24 void bs()25 {26 double l,r;27 l=0.0;28 r=h[1];29 while(r-l>eps)30 {31 h[2] = (l+r)/2.0;32 if(solve())33 {34 r=h[2];35 ans = min(ans,h[n]);36 }37 else38 l=h[2];39 }40 }41 42 int main()43 {44 #ifdef LOCAL45 // freopen("case.txt","r",stdin);46 #endif47 cin>>n>>h[1];48 ans = 2e9;49 bs();50 printf("%.2lf\n",ans);51 return 0;52 }
C acdream1208 qj的奇怪宝具
题意:有一串环形柱子,每个柱子有两个值,左边和右边两个值,而且相邻的两个柱子,前面一个柱子的右值是后面一个珠子的左值,两个珠子聚合的时候会获得能量,获得的能力如下计算:设前一个珠子的左值为a,右值(也是后一个珠子的左值)为b,后一个珠子的右值为c,则这两个聚合后获得能量为a*b*c。求能获得的最大能量。
思路:典型的区间dp,矩阵连乘模型,不过这里是环状。解决方法也不难想:把链子复制一份到后面,求一次区间dp,然后答案就是dp[i][i+n-1], 1<=i<=n中的最大值
坑点:OJ问题,如果用多case输入模式就wa,单case就AC
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int> pii;const int INF = 1e9;const double eps = 1e-6;const int N = 500;int cas = 1;int dp[N][N];int ans;int a[N],n;void next(){ int i; int t=a[1]; for(i=1;i<n;i++) a[i]=a[i+1]; a[n]=t; a[n+1]=a[1];}void get_dp(){ memset(dp,0,sizeof(dp)); for(int i=1;i+2<=2*n+1;i++) dp[i][i+1]=a[i]*a[i+1]*a[i+2]; int t; for(int len=2;len<=n;len++) { for(int i=1;i<=2*n;i++) { int j=i+len; for(int k=i;k<j;k++) { t=dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1]; if(t>dp[i][j]) dp[i][j]=t; } } }}void run(){ int i; for(i=1;i<=n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; } ans = 0; a[2*n+1]=a[1]; get_dp(); for(i=1;i+n-1<=2*n;i++) ans = max(ans,dp[i][i+n-1]); printf("%d\n",ans);}int main(){ #ifdef LOCAL freopen("case.txt","r",stdin); #endif// while(scanf("%d",&n)!=EOF) scanf("%d",&n); run(); return 0;}
D acdream1209 qj的招待会
题意:有一些点,用大写字母或者小写字母表示,大写字母表示这个点上有人,小写表示没人。再给出一些有权边,题目求有人的点到qj所在的点的最短距离是多少
思路:改造一下dij就过了吧,在dij的循环里,如果当前点是一个有人点,直接就可以输出答案了
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int,int> pii;const int INF = 1e9;const double eps = 1e-6;const int N = 100;int cas = 1;// http://acm.zju.edu.cn/mdj2014/contestInfo.do?contestId=2int id[128];void pre(){ char c; for(c=30;c<127;c++) if(c>=‘A‘ && c<=‘Z‘) id[c]=c-‘A‘; else id[c]=c-‘a‘+30;}int n=id[‘z‘]+1;int m;int first[N];int d[N];bool done[N];int g[N][N];void dij(int s){ for(int i=0;i<n;i++) d[i]=INF; d[s]=0; priority_queue<pii,vector<pii>,greater<pii> > q; memset(done,0,sizeof(done)); q.push(make_pair(d[s],s)); while(!q.empty()) { pii u=q.top(); q.pop(); int x = u.second;// cout<<x<<endl; if(x<29 && x!=id[‘Z‘]) { printf("%c %d\n",x+‘A‘,d[x]); return; } if(done[x]) continue; done[x]=1; for(int v=0;v<n;v++) { if(g[x][v]==-1 || x==v) continue; if(d[v]>d[x]+g[x][v]) { d[v]=d[x]+g[x][v]; q.push(make_pair(d[v],v)); } } }}int cnt;void run(){ char s1[10],s2[10]; int i,a,b,c; cnt=0; memset(g,-1,sizeof(g)); for(i=0;i<m;i++) { scanf("%s%s%d",s1,s2,&c); a=id[s1[0]]; b=id[s2[0]]; if(g[a][b]==-1 || g[a][b]>c) { g[a][b]=g[b][a]=c; } } dij(id[‘Z‘]);}int main(){ #ifdef LOCAL freopen("case.txt","r",stdin); #endif pre(); n=id[‘z‘]+1;// cout<<"n="<<n<<endl; while(scanf("%d",&m)!=EOF) run(); return 0;}
E 题目都还没看。。看心情补吧。。
Acdream手速赛7