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