NOIP2007 题解

发表于 | 分类于 |
字数统计: 1,008 字

本文包含了NOIP2007八道题目的题解。

普及T1 奖学金

题目链接

按照题意排序即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
struct Stu{
    int all, chi, id;
};
struct cmp{
    inline bool operator()(const Stu& s1, const Stu& s2){
        if(s1.all != s2.all)return s1.all > s2.all;
        if(s1.chi != s2.chi)return s1.chi > s2.chi;
        return s1.id < s2.id;
    }
};
Stu s[505];
int n;
void init(){
    n = read();
    for(int i = 0; i < n; ++i)
        s[i].id = i + 1,
        s[i].all = s[i].chi = read(),
        s[i].all += read() + read();
    sort(s, s + n, cmp());
}
void solve(){
    for(int i = 0; i < 5; ++i)
        printf("%d %d\n", s[i].id, s[i].all);
}
int main(){
    init();
    solve();
    return 0;
}

普及T2 纪念品分组

题目链接

排序后大的尽量和小的组合，无法组合则直接退出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <algorithm>
int limit,n,k[30005],ans=0;
int main(){
    scanf("%d%d",&limit,&n); 
    int i,at,o=0;
    for(i=0;i<n;i++)scanf("%d",&k[i]);
    std::sort(k,k+n);
    for(i=0;i<n;i++){
        for(o=0,at=n-1;at>i;at--)
            if(k[at]<=limit-k[i]){o=1;break;}
        if(o){ans+=n-at;n=at;}else{ans+=n-i;break;}
    }printf("%d\n",ans); 
    return 0;
}

普及T3 守望者的逃离

题目链接

方法一

分类讨论。。
尽量采取最优的策略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
int m, s, t, ts, lim;
int get(){
    if((10 - m) % 4) 
        return (10 - m) / 4 + 1;
    return (10 - m) / 4;
}
int main(){ 
    scanf("%d%d%d", &m, &s, &t);
    for(int i = t, ts = s; i > 0; ){
        if(ts <= 0) break;
        if(m >= 10)
            m -= 10, ts -= 60, i--;
        else{
            if(ts <= 17)
                i--, ts=0;//跑一下就跑的到
            else{
                if((lim = get()) < 3){
                    if(i >= lim + 1){
                        if(ts <= 34){
                            i -= ts / 17;
                            if(ts % 17) i--;
                            ts = 0;//跑完全程
                        }else
                            i = i - (lim + 1), ts -= 60, m -= 10, m += lim * 4;
                    }else {
                        if(ts <= i * 17){
                            i -= ts / 17;
                            if(ts % 17) i--;
                            ts = 0;//跑完全程
                        }else 
                            ts -= i * 17, i = 0;//尽量跑
                    }
                }else{
                    if(i >= 7){
                        if(ts <= 7 * 17){
                            i -= ts / 17;
                            if(ts % 17) i--;
                            ts = 0;//跑完全程
                        }else
                            i -= 7, ts -= 120;
                    }else {
                        if(ts <= i * 17){
                            i -= ts / 17;
                            if(ts % 17) i--;
                            ts = 0;//跑完全程
                        }else
                            ts -= i * 17, i = 0;//尽量跑
                }
            }
        }
    }
    if(ts > 0)
        printf("No\n%d\n", s - ts);
    else 
        printf("Yes\n%d\n", t - i);
    return 0;    
}

方法二

我们将法术和跑步分开来，跑一遍DP。
一开始只有法术，然后修改决策为跑步。
（来自洛谷上的神奇方法）
该方法之所以成立，就在于恢复完全是为了放出法术，而和跑步无关。因此可以将两者视为不同的决策。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dp[300005];
void solve(){
    int m = read(), s = read(), T = read();
    dp[0] = 0;
    for(int i = 1; i <= T; ++i){
        if(m >= 10)
            dp[i] = dp[i - 1] + 60, m -= 10;
        else
            dp[i] = dp[i - 1], m += 4;
    }
    for(int i = 1; i <= T; ++i){
        dp[i] = max(dp[i], dp[i - 1] + 17);
        if(dp[i] >= s){
            printf("Yes\n%d\n", i);
            break;
        }
    }
    printf("No\n%d\n", dp[T]);
}

普及T4 Hanoi双塔问题

题目链接

可以证明最短的次数一定是原汉诺塔问题的答案的两倍。
（因为最优情况下就是每一次要移动2个同样大小的盘子）
所以…加个高精度就完了。

提高T1 统计数字

题目链接

模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>
#include <algorithm>
using namespace std; 
int n,k[200005],tot=1,last;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&k[i]);
    sort(k,k+n);
    last=k[0];
    for(int i=1;i<n;i++){
        if(last!=k[i])
            printf("%d %d\n",last,tot),tot=1,last=k[i];
        else tot++;
    }
    printf("%d %d\n",last,tot);
    return 0;
}

Powered By Valine
v1.5.2