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

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

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

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

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

 

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

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

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

 

2013腾讯编程马拉松初赛第4,5场