2013腾讯编程马拉松初赛第一场（3月21日) 解题报告 (HDU 4505 HDU4506 HDU4507 HDU4508 HDU4509)

现在的位置: 首页 > 综合 > 正文

RSS

2013腾讯编程马拉松初赛第一场（3月21日) 解题报告 (HDU 4505 HDU4506 HDU4507 HDU4508 HDU4509)

2018年02月18日 ⁄ 综合 ⁄ 共 5091字 ⁄ 字号小中大 ⁄ 评论关闭

A题 (hdu 4505)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4505

解题思路: 一次遍历就可以，这道题可以推出公式 max*10+(k*5)+n

max最高楼层，k多少个楼层需要开门，n一共多少个人

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 400
int a[MAX];
int main()
{
    int t,n,i,j,m,k,max;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(a,0,sizeof(a));
        for(i=0,k=0,max=0;i<n;i++)
        {
            scanf("%d",&m);
            if(a[m]==0)
                k++;
            a[m]++;
            if(m>max)
                max=m;
        }
        printf("%d\n",max*10+(k*5)+n);
    }
    return 0;
}

B题 (hdu 4506)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4506

解题思路: 一个个求多少次方速度很慢，可以用快速幂

代码:

#include<stdio.h>
__int64 a[10005];
__int64 get_mi(__int64 a,__int64 b,int n)
{
    if(0 == a) return 0;
    if(0 == b)  return 1;
    __int64 r=1;
    while(b)
    {
        if(b&1)
            r=(r*a)%n;
        a=(a*a)%n;
        b>>=1;
    }
    return r;
}
int main()
{
    int T,i,y;
    __int64 n,t,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%I64d%I64d%I64d",&n,&t,&k);
        for(i=0;i<n;i++)
        {
            scanf("%I64d",&a[i]);
        }
        __int64 x;
        int mmm=1000000007;
        __int64 sum;
        sum=get_mi(k,t,mmm);
        t%=n;
        for(i=0;i<n-1;i++)
        {
            if(i<t)
                y=i+n-t;
            else
                y=i-t;
            x=(a[y]*sum)%mmm;
            printf("%I64d ",x);
        }
        if(i<t)        y=i+n-t;
        else y=i-t;
        x=(a[y]*sum)%mmm;
        printf("%I64d\n",x);
    }
    return 0;
}

D题 (hdu 4508)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4508

解题思路: 经典DP，完全背包的模版题，不一定要把背包装满

代码:

#include <stdio.h>
#include <string.h>
#define MAX_N 100001
#define MAX_V 100001
#define _MAX -0x3f3f3f3f
int n,m,f[MAX_V],c[MAX_N],w[MAX_N];
int DP(int full)
{
    int i,v;
    if(full) //如果是恰好放满，则除f[0][0]外都初始化为无穷小
    {
        memset(f,_MAX,sizeof(f));
        f[0]=0;
    }
    else  memset(f,0,sizeof(f)); //如果不一定要放满，则初始化为0
    for(i=1;i<=n;i++)
    {
        for(v=c[i];v<=m;v++)
        {
            f[v]=(f[v-c[i]]+w[i]>f[v])?f[v-c[i]]+w[i]:f[v];  // ****状态转移方程****
        }
    }
    return f[m];
}
int main ()
{
    int i;
    while(scanf("%d",&n)!=EOF)
    {
       for(i=1;i<=n;i++)
       {
            scanf("%d%d",&w[i],&c[i]);
       }
         scanf("%d",&m);
        printf("%d\n",DP(0)); //0为非满，1非恰好满
    }
    return 0;
}

E题(hdu 4509)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4509

解题思路: 开始没有考虑到时间会有交叉的情况，WA了两次

把分钟转换成数字，那么24小时就有24*60=1440

构建数组a[1440]，初始化为-1

每行给出的两个时间都可以转换成一个区间存不存在

如 01:00 02:00，转换成a[60]到a[120]所有的元素都为0

这道题可以用线段树优化，但是数组不大，效果不那么明显

可以用memset代替for，效率高一点

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 2000
int time[MAX];
int main()
{
    int n,i,t,a,b,c,d,s,k;
    while(scanf("%d",&n)!=EOF)
    {
        memset(time,-1,sizeof(time));  //-1代表空闲
        for(i=0;i<n;i++)
        {
            scanf("%d:%d %d:%d",&a,&b,&c,&d);
            s=a*60+b;
            t=c*60+d;
            memset(time+s,0,(t-s)*sizeof(time[0]));  //memset代替for循环
        }                                            //0代表忙碌
        for(i=0,k=0;i<1440;i++)
            if(time[i]==-1)
                k++;
        printf("%d\n",k);
    }
    return 0;
}

C题(hdu 4507)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4507

解题思路: 位DP的思想，转载一下大牛的思路

典型的按位dp。一开始想会不会是数学结论题，但是很快觉得数学一点不靠谱，然后发现按位dp可做。

求出区间[0, N]中满足条件的数的平方和，这样可以不用卡下界。

定义数组dp[ d ][ u ][ i ][ j ]，d表示dp到第d位，u表示是否卡上界（按惯例，0表示卡上界），i表示前缀的各位数字和模7为i，j表示前缀表示的整数模7为j。每个元素存num、sum、ssum三个值。num表示满足条件的前缀数量，sum则是这些前缀表示的整数的和，ssum是这些前缀表示的整数的平方和。

dp从最高位到最低位枚举p，再枚举当前位的数字d，并枚举上一位p+1位的dp数组最后两维i：0~6，j：0~6。计算出转移到p位时的余数值：

ii = （i + d）%7 jj = （j * 10 + d）%7

最基本的转移方程是：

dp[ p ][ 1 ][ ii ][ jj ].num += dp[ p + 1][ 1 ][ i ][ j ];

dp[ p ][ 1 ][ ii ][ jj ].sum += dp[ p + 1 ][ 1 ][ i ][ j ].sum * 10

+ dp[ p + 1 ][ 1 ][ i ][ j ].num * d;

dp[ p ][ 1 ][ ii ][ jj ].ssum += dp[ p + 1 ][ 1 ][ i ][ j ].ssum * 100

+ dp[ p + 1 ][ 1 ][ i ][ j ].sum * 20 * d

+ d * d * dp[ p + 1 ][ 1 ][ i ][ j ].num;

代码:

//zzy.2013.3.21AC
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

#define ll long long
#define MOD (1000000007LL)

typedef struct
{
    ll num,sum,ssum;
}node;

ll digits[21];
node dp[21][2][7][7];

void ini(ll len)
{
    for(ll i = 1; i <= len + 1; ++i){
        for(ll j = 0; j < 2; ++j){
            for(ll k = 0; k < 7; ++k){
                for(ll m = 0; m < 7; ++m){
                    dp[i][j][k][m].num = 0;
                    dp[i][j][k][m].sum = 0;
                    dp[i][j][k][m].ssum = 0;
                }
            }
        }
    }
}

ll Len(ll N)
{
    ll ret = 0;
    while(N){
        ret ++;
        digits[ret] = N % 10;
        N = N / 10;
    }
    return ret;
}

void DP(ll len)
{
    for(ll p = len; p > 0; p--)
    {
        for(ll d = 0; d <= 9; d++)
        {
            if(d == 7) continue;
            for(ll i=0; i<7; i++)
            {
                for(ll j=0; j<7; j++)
                {
                    ll ii,jj;
                    ii = (i+d)%7;
                    jj = (j*10+d)%7;
                    dp[p][1][ii][jj].sum += dp[p+1][1][i][j].sum*10
                    + dp[p+1][1][i][j].num*d;
                    if(d < digits[p])
                        dp[p][1][ii][jj].sum += dp[p+1][0][i][j].sum*10
                        + dp[p+1][0][i][j].num*d;
                    dp[p][1][ii][jj].sum %= MOD;
                    
                    dp[p][1][ii][jj].num += dp[p+1][1][i][j].num;
                    if(d < digits[p])
                        dp[p][1][ii][jj].num += dp[p+1][0][i][j].num;
                    dp[p][1][ii][jj].num %= MOD;
                    
                    dp[p][1][ii][jj].ssum += dp[p+1][1][i][j].ssum * 100LL
                    + 20LL * d * dp[p+1][1][i][j].sum + d*d * dp[p+1][1][i][j].num;
                    if(d < digits[p])
                        dp[p][1][ii][jj].ssum += dp[p+1][0][i][j].ssum * 100LL
                        + 20LL * d * dp[p+1][0][i][j].sum + d*d * dp[p+1][0][i][j].num;
                    dp[p][1][ii][jj].ssum %= MOD;
                }
            }
        }
        ll d = digits[p];
        if(d == 7) continue;
        for(ll i=0; i<7; i++)
        {
            for(ll j=0; j<7; j++)if(dp[p+1][0][i][j].num)
            {
                ll ii,jj;
                ii = (i+d)%7;
                jj = (j*10+d)%7;
                dp[p][0][ii][jj].sum += dp[p+1][0][i][j].sum*10 + dp[p+1][0][i][j].num*d;
                dp[p][0][ii][jj].sum %= MOD;
                
                dp[p][0][ii][jj].num += dp[p+1][0][i][j].num;
                dp[p][0][ii][jj].num %= MOD;
                
                dp[p][0][ii][jj].ssum += dp[p+1][0][i][j].ssum * 100LL
                + 20LL * d * dp[p+1][0][i][j].sum + d*d * dp[p+1][0][i][j].num;
                dp[p][0][ii][jj].ssum %= MOD;
            }
        }
    }
}

ll calcu(ll N)
{
    ll len = Len(N);
    ini(len);
    dp[len+1][0][0][0].num = 1;
    DP(len);
    ll ret = 0;
    for(ll i=1; i<7; i++){
        for(ll j=1; j<7; j++){
            ret += dp[1][0][i][j].ssum;
            ret += dp[1][1][i][j].ssum;
        }
    }
    ret %= MOD;
    return ret;
}

int main()
{
    ll T;
    cin >> T;
    while(T--){
        ll A,B;
        cin >> A >> B;
        ll ans = 0;
        ans = calcu(B) - calcu(A - 1);
        ans = (ans + MOD) % MOD;
        cout << ans << endl;
    }
    return 0;
}

注：原创文章，转载请注明出处: http://blog.csdn.net/qq7366020

作者: quiniela

该日志由 quiniela 于6年前发表在综合分类下，最后更新于 2018年02月18日.
转载请注明: 2013腾讯编程马拉松初赛第一场（3月21日) 解题报告 (HDU 4505 HDU4506 HDU4507 HDU4508 HDU4509) | 学步园 +复制链接

抱歉!评论已关闭.

学步园

2013腾讯编程马拉松初赛第一场（3月21日) 解题报告 (HDU 4505 HDU4506 HDU4507 HDU4508 HDU4509)

作者: quiniela

书签

最新文章New

本站推荐

返回首页