NOIP2001-2005 题解

发表于 | 分类于 |
字数统计: 2,941 字

本文包含了NOIP2001-2005题目的题解。

NOIP2001

普及T1 数的计算

题目地址

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <cstdio>
#include <cstring>
#include <cstdlib>
typedef long long ll;
int dp[1005]={0},n;
int main(){
    dp[2]=2,dp[1]=1;
    scanf("%d",&n);
    int i,j;
    for(i=3;i<=n;i++){
        for(j=i/2;j>=1;j--)
            dp[i]+=dp[j];
        dp[i]++;
    }
    printf("%d\n",dp[n]);
    return 0;
}

普及T2 最大公约数与最小公倍数问题

题目地址

我们知道$\mathcal x_0$必须是$\mathcal y_0$的约数。
所以记$\mathcal t=\frac{y_0}{x_0}$，则$\mathcal 2^u$（$\mathcal u$为$\mathcal t$不同质因子的个数）即为答案。（集合划分）
很巧妙的数学方法。
爆搜会TLE来着。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int isP(int a){for(int i=2;i*i<=a;i++)if(a%i==0)return 0;return 1;}
int main(){
    int x0,y0,i,ans=1;
    scanf("%d%d",&x0,&y0);
    if(y0%x0){printf("0\n");return 0;}
    for(i=2,y0/=x0;i<=y0;i++)
        if(y0%i==0&&isP(i))ans<<=1;
    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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
char s1[30], s2[30];
int root, lc[250], rc[250];
int get(int il, int ir, int pl, int pr){
    if(ir - il < 0)
        return 0;
    int id = s2[pr], i;
    for(i = il; i <= ir; ++i)
        if(s1[i] == id) break;
    int len = i - il;
    lc[id] = get(il, i - 1, pl, pl + len - 1);
    rc[id] = get(i + 1, ir, pl + len, pr - 1);
    return id;
}
void getP(int id){
    printf("%c", id);
    if(lc[id]) getP(lc[id]);
    if(rc[id]) getP(rc[id]);
}
void solve(){
    int len = strlen(s1);
    root = get(0, len - 1, 0, len - 1);
    getP(root);
}
int main(){
    scanf("%s%s", s1, s2);
    solve();
    return 0;
}

普及T4 装箱问题

题目地址

一个简单的背包问题。
不过稍微要做一些处理，只要考虑状态的合法性即可。初始合法的状态就是箱子为空，随后按照01背包扩展到其他状态。

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
#include <cstdio>
#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; 
}
int V, n, f[20005] = {0}, v[35];
void init(){
    V = read(), n = read();
    for(int i = 0; i < n; ++i)
        v[i] = read();
}
void solve(){
    f[0] = 1;
    for(int i = 0; i < n; ++i)  
        for(int j = V; j >= v[i]; --j)
            f[j] |= f[j - v[i]];
    int ans;
    for(ans = V; !f[ans]; --ans)
        ;
    printf("%d\n", V - ans);
}
int main(){
    init();
    solve();
    return 0;
}

提高T1 一元三次方程求解

题目地址

有4种方法：

  1. 暴力，按$0.01$步长枚举
  2. 二分，按照单调性求解
  3. 数学公式
  4. 导数

这里用的是二分，感觉还不错。

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
#include <stdio.h>     
#include <stdlib.h> 
#include <string.h>   
typedef double D;
D a,b,c,d,t1,t2,epi=0.01;
D get(D k){
    return k*a*k*k+b*k*k+c*k+d;
}
D C(int ll,int rr){
    D tmp,mid,l=(D)ll,r=(D)rr;
    int i=(get(l)>get(r))?1:0;
    for(;;){
        mid=(l+r)/2.0;
        tmp=get(mid);
        if(r-l<epi&&r-l>-epi)break;
        if(tmp>0){
            if(i)l=mid;
            else r=mid;
        }else{
            if(i)r=mid;
            else l=mid;
        }
    }
    printf("%.2lf ",mid);
}
int main(){   
    scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
    int i;for(i=-100;i<=100;i++){
        t1=(D)i,t2=t1+0.99;
        t1=get(t1),t2=get(t2);
        if(t1*t2<0)C(i,i+1);
        else if(t1<epi&&t1>-epi)printf("%.2lf ",(D)i);
    }
    return 0;     
}

提高T2 数的划分

题目地址

一个经典的递推问题。

方法一

我的方法是设$f(n, m, k)$为数$n$划分为$k$个小于或等于$m$的数的方法数。
那么有

这么做是$O(n ^2 k)$的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
#include <algorithm>
using namespace std;
int f[205][7]={0},n,k;
int main(){
    f[0][0]=1;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=k;j++)
            for(int p=1;p<=n;p++)
                if(p-i>=0)f[p][j]+=f[p-i][j-1];
    printf("%d\n",f[n][k]);
    return 0;
}

方法二

设$f(n, k)$为题意所求，那么：

  1. 划分里面有$1$，那么包含$f(n - 1, k - 1)$>
  2. 划分里面没有$1$，那么给划分里面所有的数添上一个$1$，即包含$f(n - k, k)$。
    因此得到时间复杂度$O(nk)$。

提高T3 统计单词个数

题目地址

提高T4 Car的旅行路线

题目地址

非常简单的最短路，非常难的建图。
出发地和到达地每个机场间道路权值设为0即可。
建图就是暴力用勾股求矩形顶点。
在下面的代码中，我将顶点拆成了4个。

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define rep(e) for(e=0;e<4;e++)
using namespace std;
typedef double db;
int T,s,t,A,B,rec[405][2],pr[105],vis[405];
db ds[405][405],d[405][405],l[405];
db dis(int a,int b){
    return (rec[a][0]-rec[b][0])*(rec[a][0]-rec[b][0])+
    (rec[a][1]-rec[b][1])*(rec[a][1]-rec[b][1]);
}
bool eq(db a,db b){return a-b>(-1e-6)&&a-b<(1e-6);}
void make(int i){
    db q1=dis(i,i+2),q2=dis(i,i+1),q3=dis(i+1,i+2);
    if(eq(q1+q2,q3))rec[i+3][0]=rec[i+2][0]+rec[i+1][0]-rec[i][0],
    rec[i+3][1]=rec[i+2][1]+rec[i+1][1]-rec[i][1];
    else if(eq(q2+q3,q1))rec[i+3][0]=rec[i+2][0]+rec[i][0]-rec[i+1][0],
    rec[i+3][1]=rec[i+2][1]+rec[i][1]-rec[i+1][1];
    else if(eq(q1+q3,q2))rec[i+3][0]=rec[i+1][0]+rec[i][0]-rec[i+2][0],
    rec[i+3][1]=rec[i+1][1]+rec[i][1]-rec[i+2][1];
}
void dijkstra(){
    int at,i=A<<2,j;db lst;
    fill(l,l+s,1e10);
    fill(vis,vis+s,0);
    l[i]=l[i+1]=l[i+2]=l[i+3]=0.0;
    for(i=0;i<s;i++){
        for(lst=1e10,j=0;j<s;j++)
            if(!vis[j]&&l[j]<lst)at=j,lst=l[j];
        vis[at]=1;
        for(j=0;j<s;j++)
            l[j]=min(l[at]+d[at][j],l[j]);
    }
}
int main(){
    scanf("%d",&T);
    int i,j,u,v;db price;
    while(T--){
        scanf("%d%d%d%d",&s,&t,&A,&B);
        A--,B--,s<<=2;
        for(i=0;i<s;i+=4){
            scanf("%d%d%d%d%d%d%d",&rec[i][0],&rec[i][1],&
            rec[i+1][0],&rec[i+1][1],&rec[i+2][0],&
            rec[i+2][1],&pr[i]),make(i);
            if(i/4==A||i/4==B)pr[i]=0;
        }
        for(i=0;i<s;i+=4){
            for(j=0;j<s;j+=4){
                price=(i!=j)?t:pr[i];
                rep(u)rep(v)
                    ds[i+u][j+v]=sqrt(dis(i+u,j+v)),
                    d[i+u][j+v]=price*ds[i+u][j+v];
            }
        }
        dijkstra();
        printf("%.1lf\n",l[B<<2]);
    }
    return 0;
}

NOIP2002

普及T2 选数

题目地址

用DFS构造出所有的组合即可。

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
#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; 
}
int n,k,x[24],ans=0;
bool isPrime(int t){
    if(t&1){
        if(t==1)return false;
        else{
            for(int i=3;i*i<=t;i+=2)
                if(t%i==0)return false;
            return true;
        }
    }else return t==2;
}
void dfs(int index,int used,int sum){
    sum+=x[index];
    if(used==k){
        if(isPrime(sum))ans++;
        return ;
    }
    for(int i=index+1;i<=n-k+used;i++)
        dfs(i,used+1,sum);
}
void init(){
    n=read(),k=read();
    for(int i=0;i<n;i++)
        x[i]=read();
}
void solve(){
    for(int i=0;i<=n-k;i++)
        dfs(i,1,0);
    printf("%d\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}

NOIP2003

提高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 <algorithm>
#include <cstring>
using namespace std;
int mp[105][105],c[105]={0},u[105],V,E,d[105]={0};
int que[105],f=0,r=0,vis[105]={0},mat[105][105]={0};
void topo(){
    int du[105]={0},i,j,o=0;
    for(i=1;i<=V;i++){
        for(j=1;j<=V;j++)
            if(mat[j][i])du[i]++,d[j]++;
        if(!du[i])vis[i]=1,que[r++]=i;
    }
    while(r-f){
        i=que[f++];
        if(du[i])c[i]-=u[i];
        if(c[i]>0){
            for(j=1;j<=V;j++)
                if(mat[i][j]){
                    c[j]+=mp[i][j]*c[i];
                    if(!vis[j])
                        vis[j]=1,que[r++]=j;
                }
        }
    }
    for(i=1;i<=V;i++)
        if(!d[i]&&c[i]>0)
            o=1,printf("%d %d\n",i,c[i]);
    if(!o)printf("NULL\n");
}
int main(){
    scanf("%d%d",&V,&E);
    int i,j,_u,v,_c;
    for(i=1;i<=V;i++)
        scanf("%d%d",&c[i],&u[i]);
    for(i=0;i<E;i++)
        scanf("%d%d%d",&_u,&v,&_c),
        mat[_u][v]=1,
        mp[_u][v]=_c;
    if(V==1&&c[1]>0)
        printf("%d %d\n",1,c[1]);
    else topo();
    return 0;
}

NOIP2004

提高T1 津津的储蓄计划

题目地址

模拟神题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
int saved = 0, cur = 0;
int main(){
    int flag = 1;
    for(int i = 1; i <= 12; ++i){
        cur += 300;
        int curm;
        scanf("%d", &curm);
        if(curm > cur){
            printf("-%d\n", i), flag = 0;
            break;
        }
        cur -= curm;
        saved += cur - (cur % 100);
        cur %= 100;
    }
    if(flag)
        printf("%d\n", cur + saved * 6 / 5);
    return 0;
}

NOIP2005

提高T4 等价表达式

题目地址

表达式求值。
然而数据可以很大，直接比较答案和原式的做法不大现实。
所以我们可以采用NOIP2014解方程的做法，把$a$带入一个数，再模一个质数，看结果是不是相同的。
实际上为了保证准确性是可以模多个质数的，但这题数据很水，就没有这么做。
最好还是多模几个质数。

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#define A 1189
using namespace std;
int stack[2][10005],top[2]={0},pro[300],lim,targ,M=10009;
char _exp[10000];
int poww(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=(res*a)%M;
        a=(a*a)%M,b>>=1;
    }
    return res; 
}
void opr(){
    int a1,a2,b;
    a2=stack[0][--top[0]],
    a1=stack[0][--top[0]],
    b=stack[1][--top[1]];
    if(b=='+')stack[0][top[0]++]=(a1+a2)%M;
    if(b=='-')stack[0][top[0]++]=(a1-a2+M)%M;
    if(b=='*')stack[0][top[0]++]=(a1*a2)%M;
    if(b=='^')stack[0][top[0]++]=poww(a1,a2);
}
void calc(){
    int i,j,t=-1,cnt=0;
    for(i=0;i<lim;i++){
        if(_exp[i]=='a')
            stack[0][top[0]++]=A;
        else if(isdigit(_exp[i])){
            if(t<0)t=_exp[i]-'0';
            else t=t*10+_exp[i]-'0';
        }else if(_exp[i]!=' '){
            if(t!=-1)
                stack[0][top[0]++]=t,
                t=-1;
            if(_exp[i]=='(')
                stack[1][top[1]++]='(',cnt++;
            else if(_exp[i]==')'){
                if(!cnt)continue;
                while(stack[1][top[1]-1]!='(')
                    opr();
                top[1]--,cnt--;
            }else{
                while(top[1]&&stack[1][top[1]-1]!='('&&
                pro[stack[1][top[1]-1]]>=pro[_exp[i]])
                    opr();
                stack[1][top[1]++]=_exp[i];
            }
        }
    }
}
void init(){
    pro['+']=pro['-']=1,
    pro['*']=2,
    pro['^']=3;
    fgets(&_exp[1],99,stdin);
    _exp[0]='(';
    lim=strlen(_exp);
    _exp[lim++]=')';
    calc();
    targ=stack[0][0];
}
void solve(){
    int m,i;
    fgets(_exp,99,stdin);
    sscanf(_exp,"%d",&m);
    for(i=0;i<m;i++){
        fgets(&_exp[1],99,stdin);
        _exp[0]='(';
        lim=strlen(_exp);
        _exp[lim++]=')';
        top[0]=top[1]=0;
        memset(stack,0,sizeof(stack));
        calc();
        if(stack[0][0]==targ)
            printf("%c",'A'+i);
    }
    printf("\n");
}
int main(){
    init();
    solve();
    return 0;
}