2013腾讯编程马拉松初赛第1场（3月21）（HDU 4505 HDU4506 HDU4507 HDU4508 HDU4509）

A题 (hdu 4505)

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

解题思路:    水题没啥好说的，一般10分钟就能出来这道题。。。。1a

代码:

[cpp] view plaincopy

1. #include <iostream>  
2. #include <algorithm>  
3. using namespace std;  
4. const int maxn = 20;  
5. int main()  
6. {  
7.     int t, n, a[maxn];  
8.     scanf("%d", &t);  
9.     while (t--)  
10.     {  
11.         scanf("%d", &n);  
12.         int i;  
13.         for (i=0; i<n; i++)  
14.         {  
15.             scanf("%d", &a[i]);  
16.         }  
17.         sort(a, a+n);  
18.         int ans = 0;  
19.         int now = 0;  
20.         for (i=0; i<n; i++, ans++)  
21.         {  
22.             if (a[i]<=now)continue;  
23.             ans += 6 * (a[i] - now);  
24.             ans += 5;  
25.             now = a[i];  
26.         }  
27.         ans += now * 4;  
28.         printf("%d\n", ans);  
29.     }  
30.     return 0;  
31. }  

B题 (hdu 4506)

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

解题思路:   这道题真晕。。我没做，最后发现其实我应该做这道题，不用啥技巧。。用了个快速幂。。。1a。。。

快速幂请参见：http://blog.csdn.net/liuqiyao_01/article/details/8478402

代码:

[cpp] view plaincopy
#include <iostream>  
using namespace std;  
  
#define max(a,b)    ((a)>(b)?(a):(b))  
const int maxn = 105;  
  
int main()  
{  
    int n, m;  
    int a[maxn], b[maxn], dp[100005];  
    while (scanf("%d", &n) != EOF)  
    {  
        int i, j;  
        for (i=1; i<=n; i++)  
            scanf("%d %d", &a[i], &b[i]);  
        scanf("%d", &m);  
        memset(dp, 0, sizeof(dp));  
        for (i=1; i<=n; i++)  
        {  
            for (j=0; j<=m; j++)  
            {  
                if (b[i] > j) continue;  
                dp[j] = max(dp[j], dp[j-b[i]] + a[i]);  
            }  
        }  
        printf("%d\n", dp[m]);  
    }  
    return 0;  
}  


E题(hdu 4509)
题目链接:    http://acm.hdu.edu.cn/showproblem.php?pid=4509
解题思路:    一开始xindoo和我说穷举。。我一看输入量，觉得穷举肯定没戏，但是想不出别的方法，于是穷举，思路乱七八糟的wa了3次。。郁闷啊。。直到他们出了这道题，我就没做。。22号看网上大牛用memset，很好用。。。第一次学。。以后一定能用上。
代码:
[cpp] view plaincopy
#include <iostream>  
#include <algorithm>  
using namespace std;  
  
const int maxn = 500005;  
int n;  
  
int main()  
{  
    int flag[1440];  
    while (scanf("%d", &n) != EOF)  
    {  
        int sh, sm, eh, em;  
        memset(flag, -1, sizeof(flag));  
  
        int i;  
        int ans = 0;  
        for (i=0; i<n; i++)  
        {  
            scanf("%d:%d %d:%d", &sh, &sm, &eh, &em);  
            int s = sh * 60 + sm;  
            int e = eh * 60 + em;  
            memset(flag + s, 0, (e-s)*sizeof(flag[0]));  
        }  
        for (i=0; i<1440; i++)  
            if (flag[i])  
                ans++;  
        printf("%d\n", ans);  
    }   
    return 0;  
}  
1楼xindoo3天前 12:43
你的E题太暴力了，看我的代码，耗时耗内存都少，而且代码短。nn[code=cpp]n#include <cstdio>n#include <cstring>nint s[1445];nint main()n{n    int n;n    while (scanf("%d",&n) != EOF)n    {n        memset(s,0,sizeof(s));n        int a,b,c,d;n        while (n--)n        {n            scanf("%d:%d %d:%d",&a,&b,&c,&d);n            s[a*60+b] += 1;n            s[c*60+d] -= 1;n        }n        int ans = 0;n        int ss = 0;n        for (int i = 0;i < 1440;i++)n        {n            ss += s[i];n            if (!ss)n                ans++;n        }n        printf("%d\n",ans);n    }n}n[/code]
Re: liuqiyao_013天前 13:10
回复xindoon不暴力非man