首页 > 代码库 > Noip2007提高组总结

Noip2007提高组总结

2024-07-03 19:28:15   226人阅读

　　两道基础题，后两题比较麻烦，算法想出来后，还是一些细枝末节的问题，需要特别注意，感觉Noip的题目质量还是挺高的，每做一套，都感觉会有大大小小不同的收获，就要月考了，最后把07年的题目总结一下，算是这两天的收获……

T1：统计数字

　　没有任何悬念的练习题，排序然后输出……

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

T2：字符串的展开

　　字符串处理的基础题，主要考察读题的仔细程度和编程的素质，尽量代码短一些，那么也好调试一点。

+ View Code?
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
#include <cstdio>
#include <cstring>
using namespace std;
#define rep() for(int j=0;j<p2;j++)
char s[1000000];
int p1,p2,p3;
void pr1(int b,int e){for(int i=b;i<=e;i++)rep()printf("%c",(char)i);}
void pr2(int b,int e){for(int i=e;i>=b;i--)rep()printf("%c",(char)i);}
void pr3(int b,int e){for(int i=b;i<=e;i++)rep()printf("%c",‘*‘);}
int main(){
    scanf("%d%d%d",&p1,&p2,&p3);
    scanf("%s",s); printf("%c",s[0]);
    for(int i=1;i<strlen(s);i++){
        if(s[i]!=‘-‘){printf("%c",s[i]);continue;}
        if(p3==1){
            if(s[i-1]>=‘0‘&&s[i+1]<=‘9‘&&s[i-1]<s[i+1]){
                if(p1==3)pr3(int(s[i-1])+1,int(s[i+1])-1);
                else pr1(int(s[i-1])+1,int(s[i+1])-1); continue;
            }
            if(s[i-1]>=‘a‘&&s[i+1]<=‘z‘&&s[i-1]<s[i+1]){
                if(p1==1)pr1(int(s[i-1])+1,int(s[i+1])-1);
                else if(p1==2)pr1(s[i-1]-‘a‘+‘A‘+1,s[i+1]-‘a‘+‘A‘-1);
                else pr3(int(s[i-1])+1,int(s[i+1])-1);
                continue;
            }
        }else{
            if(s[i-1]>=‘0‘&&s[i+1]<=‘9‘&&s[i-1]<s[i+1]){
                if(p1==3)pr3(int(s[i-1])+1,int(s[i+1])-1);
                else pr2(int(s[i-1])+1,int(s[i+1])-1); continue;
            }
            if(s[i-1]>=‘a‘&&s[i+1]<=‘z‘&&s[i-1]<s[i+1]){
                if(p1==1)pr2(int(s[i-1])+1,int(s[i+1])-1);
                else if(p1==2)pr2(s[i-1]-‘a‘+‘A‘+1,s[i+1]-‘a‘+‘A‘-1);
                else pr3(int(s[i-1])+1,int(s[i+1])-1);
                continue;
            }
        }printf("%c",s[i]);
    }
    return 0;
}

T3：矩阵取数游戏

　　这道题的Dp方程还是比较好推的，就是从中间向两端扩展，然后搜索进去层层外推即可，方程是f[i][j]=max{f[i][j-1]+a[j],f[i+1][j]+a[i]}，然后是2的幂次问题，因为直接算幂的话比较慢，所以用霍纳规则，每一次出栈时乘2，就可以了，没打高精度60分：

+ View Code?
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
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long LL;
LL ans,a[81],f[81][81];
LL getans(int s,int t){
    if(f[s][t])return f[s][t];
    if(s==t)return f[s][s]=2*a[s];
    LL t1,t2;
    t1=getans(s+1,t)+a[s];
    t2=getans(s,t-1)+a[t];
    if(t1>t2)return f[s][t]=2*t1;
    else return f[s][t]=2*t2;
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    while(n--){
        for(int i=1;i<=m;i++)scanf("%d",&a[i]);
        memset(f,0,sizeof f);
        ans+=getans(1,m);
    }
    cout<<ans;
    return 0;
}

　　之后粘上高精度的，重载运算符版本……

+ View Code?
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
59
60
61
62
63
64
65
66
67
68
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef struct bigint{
    int le,u[81];
    bigint(){le=0;memset(u,0,sizeof(u));}
    bigint operator+(const bigint &a){
        int l=max(le,a.le);
        bigint m;
        for(int i=0;i<=l;i++){
            m.u[i]+=u[i]+a.u[i];
            m.u[i+1]+=m.u[i]/10;
            m.u[i]%=10;
        }
        if(m.u[l+1]!=0)m.le=l+1;
        else m.le=l;
        return m;
    }
    bool operator>(const bigint &a){
        if(le>a.le)return true;
        if(le<a.le)return false;
        for(int i=le;i>=0;i--){
            if(u[i]>a.u[i])return true;
            if(u[i]<a.u[i])return false;
        }
        return false;
    }
    friend ostream& operator<<(ostream &cout,bigint a){
        for(int i=a.le;i>=0;i--)
        cout<<a.u[i];
        return cout;
    }
    friend istream& operator>>(istream &cin,bigint &a){
        int i,l;char b[82];
        cin>>b;
        memset(a.u,0,sizeof(a.u));
        a.le=l=strlen(b)-1;
        for(int i=0;i<=l;i++)a.u[l-i]=b[i]-‘0‘;
        return cin;
    }
    bool empty(){
        if(le==0&&u[0]==0)return true;
        else return false;
    }
};
bigint a[81],f[81][81];
int n,m;
bigint ans;
bigint getans(int s,int t){
    if(!f[s][t].empty())return f[s][t];
    if(s==t)return f[s][s]=a[s]+a[s];
    bigint t1,t2;
    t1=getans(s+1,t)+a[s];
    t2=getans(s,t-1)+a[t];
    if(t1>t2)return f[s][t]=t1+t1;
    else return f[s][t]=t2+t2;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        memset(f,0,sizeof(f));
        for(int j=1;j<=m;j++)cin>>a[j];
        ans=ans+getans(1,m);
    }
    cout<<ans;
    return 0;
}

T4：树网的核

　　对于这道题目首先要做到的是找树的直径，可以得出如果有多条直径的话，随便选取一条就可以了，因为越靠近核一定更优，选取链越长一定越优，（未完待续）


联系
我们