NOIP2008 题解

发表于 | 分类于 |
字数统计: 3,504 字

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

普及T1 ISBN号码

题目地址

模拟即可。

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
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;
char isbn[20];
int last,sum=0,cnt=1;
int main(){
    scanf("%s",isbn);
    for(int i=0;i<13;i++){
        if(isdigit(isbn[i])&&i!=12)
            sum+=(isbn[i]-'0')*cnt,cnt++;
        else if(isdigit(isbn[i])&&i==12)
            sum%=11,last=isbn[i]-'0';
        else
            sum%=11,last=10;
    }
    if(last==sum){
        printf("Right");
    }else{
    	for(int i=0;i<12;i++)
        	putchar(isbn[i]);
        printf("%c\n",sum==10?'X':sum+'0');
    }
    return 0;
}

普及T2 排座椅

题目地址

算一下选每一行或者每一列可以阻断的人数，然后排序贪心即可。
注意行号和列号都要排序再输出。
时间复杂度：$\mathcal O(nlogn+mlogm)$

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
#include <bits/stdc++.h>
using namespace std;
struct Seat{
    int id,tot;
};
Seat line[1005],row[1005];
bool cmp(const Seat &sa,const Seat &sb){
    return sa.tot>sb.tot;
}
bool cmp2(const Seat &sa,const Seat &sb){
    return sa.id<sb.id;
}
int n,m,K,L,D;
int main(){
    scanf("%d%d%d%d%d",&n,&m,&K,&L,&D);
    int x1,y1,x2,y2;
    for(int i=1;i<=n;i++)
        line[i].tot=0,line[i].id=i;//该行上面 
    for(int i=1;i<=m;i++)
        row[i].tot=0,row[i].id=i;//该列右边 
    for(int i=1;i<=D;i++){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(x1==x2)
            row[min(y1,y2)].tot++; //同行记录列 
        else if(y1==y2)
            line[min(x1,x2)].tot++;
    }
    sort(line+1,line+1+n,cmp),sort(line+1,line+K+1,cmp2);
    sort(row+1,row+1+m,cmp),sort(row+1,row+1+L,cmp2);
    for(int i=1;i<K;i++)
        printf("%d ",line[i].id);
    printf("%d\n",line[K].id);
    for(int i=1;i<L;i++)
        printf("%d ",row[i].id);
    printf("%d\n",row[L].id);
    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 <stdio.h>  
#include <string.h>  
#include <stdlib.h>  
#include <math.h>
int q[28][28]={{2,6,10,22,42,86,170,342,682,1366,2730,5462,10922,21846,43690,87382,174762,349526,699050,1398102,2796202,5592406,11184810,22369622,44739242,89478486,178956970,357913942},
{0,8,0,32,0,128,0,512,0,2048,0,8192,0,32768,0,131072,0,524288,0,2097152,0,8388608,0,33554432,0,134217728,0,536870912},
{0,6,2,20,14,70,72,254,330,948,1430,3614,6008,13990,24786,54740,101118,215766,409640,854702,1652090,3396916,6643782,13530350,26667864,53971350,106914242,215492564},
{0,6,0,22,0,86,0,342,0,1366,0,5462,0,21846,0,87382,0,349526,0,1398102,0,5592406,0,22369622,0,89478486,0,357913942},
{0,6,0,20,2,70,18,252,110,924,572,3434,2730,12902,12376,48926,54264,187036,232562,720062,980674,2789164,4086550,10861060,16878420,42484682,69242082,166823430},
{0,6,0,20,0,72,0,272,0,1056,0,4160,0,16512,0,65792,0,262656,0,1049600,0,4196352,0,16781312,0,67117056,0,268451840},
{0,6,0,20,0,70,2,252,22,924,156,3432,910,12870,4760,48622,23256,184796,108528,705894,490314,2708204,2163150,10430500,9373652,40313160,40060078,156305070},
{0,6,0,20,0,70,0,254,0,948,0,3614,0,13990,0,54740,0,215766,0,854702,0,3396916,0,13530350,0,53971350,0,215492564},
{0,6,0,20,0,70,0,252,2,924,26,3432,210,12870,1360,48620,7752,184756,40698,705434,201894,2704204,961400,10401250,4440150,40123152,20030010,155172330},
{0,6,0,20,0,70,0,252,0,926,0,3460,0,13110,0,50252,0,194446,0,758100,0,2973350,0,11716252,0,46333566,0,183739940},
{0,6,0,20,0,70,0,252,0,924,2,3432,30,12870,272,48620,1938,184756,11970,705432,67298,2704156,354200,10400602,1776060,40116656,8584290,155118390},
{0,6,0,20,0,70,0,252,0,924,0,3434,0,12902,0,48926,0,187036,0,720062,0,2789164,0,10861060,0,42484682,0,166823430},
{0,6,0,20,0,70,0,252,0,924,0,3432,2,12870,34,48620,342,184756,2660,705432,17710,2704156,106260,10400600,592020,40116600,3121560,155117522},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12872,0,48656,0,185136,0,708512,0,2725408,0,10532160,0,40870080,0,159189120},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,2,48620,38,184756,420,705432,3542,2704156,25300,10400600,161460,40116600,950040,155117520},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48622,0,184796,0,705894,0,2708204,0,10430500,0,40313160,0,156305070},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,2,184756,42,705432,506,2704156,4600,10400600,35100,40116600,237510,155117520},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184758,0,705476,0,2704708,0,10405800,0,40157550,0,155402532},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184756,2,705432,46,2704156,600,10400600,5850,40116600,47502,155117520},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184756,0,705434,0,2704204,0,10401250,0,40123152,0,155172330},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184756,0,705432,2,2704156,50,10400600,702,40116600,7308,155117520},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184756,0,705432,0,2704158,0,10400652,0,40117356,0,155125640},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184756,0,705432,0,2704156,2,10400600,54,40116600,812,155117520},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184756,0,705432,0,2704156,0,10400602,0,40116656,0,155118390},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184756,0,705432,0,2704156,0,10400600,2,40116600,58,155117520},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184756,0,705432,0,2704156,0,10400600,0,40116602,0,155117580},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184756,0,705432,0,2704156,0,10400600,0,40116600,2,155117520},
{0,6,0,20,0,70,0,252,0,924,0,3432,0,12870,0,48620,0,184756,0,705432,0,2704156,0,10400600,0,40116600,0,155117522}};
int main(){ 
    int n,m;scanf("%d%d",&n,&m);printf("%d\n",q[n-3][m-3]);
    return 0;  
}

方法二

实际上这个递推是很水，设$\mathcal f\left(i,j\right)$为当前球到了第$i$个人的时候是第$j$次的情况下，传球的方法数，则可以递推得

其中$i-1$指$i$左边的人，$i+1$指$i$右边的人。
假设开始的人是￥0￥号即可。
时间复杂度：$\mathcal O\left(nm\right)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
int n,m,f[35][35];
int main(){
    scanf("%d%d",&n,&m);
    f[0][0]=1;
    for(int j=1;j<=m;j++){
        f[0][j]=f[n-1][j-1]+f[1][j-1];
        f[n-1][j]=f[0][j-1]+f[n-2][j-1];
        for(int i=1;i<n-1;i++)
            f[i][j]=f[i-1][j-1]+f[i+1][j-1];
    }
    printf("%d\n",f[0][m]);
    return 0;
}

普及T4 立体图

题目地址

这题目是不是一看就很恶劣啊？
是的！
但是只要知道构图的顺序就完成了一部分。
我的构图顺序是从最底层构起，每一层按列构成，从远到近，从左到右，从下到上，这样就解决了图形覆盖的问题。
然后就是坐标的计算以及图形具体元素坐标的计算，这里可以参考我的代码。
时间复杂度：画一个正方体的时间是常数，所以是$O($正方体数$)$。

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>
using namespace std;
char mp[20001][350];
int n,m,mp2[55][55],BOT=20000;
void lie(int x,int y){
    mp[x][y]=mp[x][y+4]='+',
    mp[x][y+1]=mp[x][y+2]=mp[x][y+3]='-';
}
void build(int x,int y,int z){
    int dx=BOT,dy=0;
    dx-=(z-1)*3+3+2*(m-x+1);//yuanlaiwei x
    dy+=(m-x+1)*2+(y-1)*4;
    lie(dx,dy),lie(dx+2,dy-2),lie(dx+5,dy-2);
    mp[dx+3][dy+4]='+',
    mp[dx+1][dy-1]=mp[dx+1][dy+3]=mp[dx+4][dy+3]='/';
    mp[dx+3][dy-2]=mp[dx+3][dy+2]=
    mp[dx+4][dy-2]=mp[dx+4][dy+2]=
    mp[dx+1][dy+4]=mp[dx+2][dy+4]='|',
    mp[dx+1][dy]=mp[dx+1][dy+1]=mp[dx+1][dy+2]=
    mp[dx+2][dy+3]=mp[dx+3][dy+3]=
    mp[dx+3][dy]=mp[dx+3][dy-1]=mp[dx+3][dy+1]=
    mp[dx+4][dy]=mp[dx+4][dy-1]=mp[dx+4][dy+1]=' ';
}
void output(){
    int s1=0,s2=0,i,j,ok;
    for(i=BOT;i>=0;i--){
        for(j=0,ok=0;j<350;j++)
            if(mp[i][j]!='.')ok=1;
        if(!ok)break;
    }
    s1=i+1;
    for(i=349;i>=0;i--){
        for(j=s1,ok=0;j<=BOT;j++)
            if(mp[j][i]!='.')ok=1;
        if(ok)break;
    }
    s2=i;
    //printf("%d %d\n",s1,s2);
    for(i=s1;i<=BOT;i++){
        for(j=0;j<=s2;j++)
            printf("%c",mp[i][j]);
        printf("\n");
    }
}
int main(){
    memset(mp,'.',sizeof(mp));
    scanf("%d%d",&m,&n);
    int i,j,k;
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            scanf("%d",&mp2[i][j]);
    for(i=1;i<=100;i++)
        for(k=0;k<n;k++)
            for(j=0;j<m;j++)
                if(mp2[j][k]>=i)
                    build(j+1,k+1,i);		
    output();
    return 0;
}

提高T1 笨小猴

题目地址

模拟即可。
注意0和1都不是质数。

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
#include <bits/stdc++.h>
using namespace std;
bool judge(int x){
    if(!x||x==1)return 0;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)return 0;
    return 1;
}
char s[1005];
int cnt[27],len;
int main(){
    scanf("%s",s);
    len=strlen(s);
    for(int i=0;i<len;i++)
        cnt[s[i]-'a']++;
    int maxi=0,mini=1000;
    for(int i=0;i<26;i++){
        if(!cnt[i])continue;
        maxi=max(maxi,cnt[i]),mini=min(mini,cnt[i]);
    }
    if(judge(maxi-mini))
        printf("Lucky Word\n%d\n",maxi-mini);
    else printf("No Answer\n0\n");
    return 0;
}

提高T2 火柴棒等式

题目地址

方法一

大概划定一下加数的范围，然后暴力枚举即可。
1是最少的，所以以他为标准，大概左右两边的加数是在2000左右。
（实际上试验后发现在1000左右）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
int cnt[]={6,2,5,5,4,5,6,3,7,6},n,ans=0;
int table[2005];
int get(int a){
    int res=0;
    while(a)res+=cnt[a%10],a/=10;
    return res;
}
int main(){
    scanf("%d",&n),n-=4;
    table[0]=6;
    for(int i=1;i<=2000;i++)
        table[i]=get(i); 
    for(int i=0;i<=1000;i++)
        for(int j=0;j<=1000;j++)
            if(table[i]+table[j]+table[i+j]==n)ans++;
    printf("%d\n",ans);
    return 0;
}

方法二

题目是死的，人是活的。打表也是好手段。

1
int ans[]={0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,8,9,6,9,29,39,38,65,88,128};

提高T3 传纸条

题目地址

设$\mathcal f\left( k,i,j\right) \left( i \le j \right)$为走了$\mathcal k$步，第一条路径当前在第$\mathcal i$列，第二条在第$\mathcal j$列时的最大的爱心值。
则转移方程为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[105][51][51]={0},m,n,mat[51][51];
int main(){
    int i,j,k;scanf("%d%d",&m,&n);
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            scanf("%d",&mat[i][j]);
    for(k=1;k<m+n-1;k++)
        for(j=0;j<n;j++)
            for(i=0;i<=j;i++){
                if(k-i<0||k-i>=m||k-j<0||k-j>=m)continue;
                dp[k][i][j]=max(dp[k-1][i][j],dp[k][i][j]);
                if(i)dp[k][i][j]=max(dp[k-1][i-1][j],dp[k][i][j]);
                if(j)dp[k][i][j]=max(dp[k-1][i][j-1],dp[k][i][j]);
                if(i&&j)dp[k][i][j]=max(dp[k-1][i-1][j-1],dp[k][i][j]);
                dp[k][i][j]+=mat[k-i][i];
                if(i!=j)dp[k][i][j]+=mat[k-j][j];
            }
    printf("%d\n",dp[m+n-2][n-1][n-1]);
    return 0;
}

提高T4 双栈排序

题目地址

双栈排序=单栈排序*2。
那我们探究一下单栈排序吧！
显然，单栈排序中，如果有两个数$\mathcal a_i$和$\mathcal a_k$，其中$\mathcal a_k<a_i$，那么显然$\mathcal a_k$先弹出，$\mathcal a_i$后弹出。
什么时候一个序列无法被单栈排序呢？
如果因为某个原因，上面的事情做不到，就说明无法单栈排序。
换言之，我们假设$\mathcal i<k$且$\mathcal a_k<a_i$，那么如果两个数之间有一个碍事的：有元素$\mathcal i<j<k$，并且$\mathcal a_i<a_j$，那么显然在弹出$\mathcal a_k$后必须要先弹掉$\mathcal a_j$才能弹出$\mathcal a_i$，这不符合条件。所以无法单栈排序。
一个栈做不成，那就两个。
考虑把这些碍事的元素放到另一个栈里，这样就不矛盾了。问题是如何分配呢？
我们知道，根据上述条件，$\mathcal a_i$和$\mathcal a_j$必然无法在同一个栈中。根据这种”二分“的性质，我们想到了二分图。把下标看做结点，然后不能在一个栈里的点对间连一条边，判断这个图是否是二分图即可。这一步可以直接用DFS实现。
之后就比较简单了，输出排序过程即可。

还有一个瓶颈：怎么求这样的点对？直接枚举会带来$\mathcal O\left(n^3\right)$的时间复杂度，我们承受不住。
观察到$\mathcal a_k$具体是多少不重要，只要有一个$\mathcal k$满足且即可。所以我们可以用某一种类似后缀和的技巧：设、$\mathcal mx[i]$为序列$a$在下标为$i$~$n$时的最小值，则$\mathcal mx[i]=min(a[i],mx[i+1])$。
判断一个点对间是否有边，只要看是否有并且即可。
这样就可以在$\mathcal O\left(n^2\right)$的时间内求出点对了。
时间复杂度：$\mathcal O\left(n^2\right)$。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long ll;
int n,a[1005],mx[1005],mat[1005][1005]={0},col[1005]={0},ok=1;
int s1[1005],t1=0,s2[1005],t2=0;
void init(){
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    mx[n]=10000000;
    for(int i=n-1;i>=0;i--)
        mx[i]=min(mx[i+1],a[i]);
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n-1;j++)
            if(a[i]<a[j]&&mx[j+1]<a[i])
                mat[i][j]=mat[j][i]=1;
}
void dfs(int cur,int c){
    if(!col[cur])
        col[cur]=c;
    else{
        if(col[cur]!=c)ok=0;
        return ;
    }
    for(int i=0;i<n;i++)
        if(mat[cur][i])
            dfs(i,3-c);
}
void solve(){
    for(int i=0;i<n&&ok;i++)
        if(!col[i])
            dfs(i,1);
    if(!ok){
        printf("0\n");
        return ;
    }
    int val=0;
    for(int i=0;i<n;i++){
        if(col[i]==1)s1[t1++]=a[i],printf("a ");
        else s2[t2++]=a[i],printf("c ");
        for(;;){
            if(t1&&s1[t1-1]==val+1){
                t1--,printf("b ");
                val++;
            }else if(t2&&s2[t2-1]==val+1){
                t2--,printf("d ");
                val++;
            }else break;
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}