首页 > 代码库 > 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;}
View Code

 

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 }
View Code

 

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;}
View Code

 

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;}
View Code

 

E 题目都还没看。。看心情补吧。。

Acdream手速赛7