NOIP2010 题解

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

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

普及T1 数字统计

题目地址

某一道普及的弱化版。
模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
#include <bits/stdc++.h>
using namespace std;
int l,r,ans=0;
int main(){
    scanf("%d%d",&l,&r);
    for(int i=l;i<=r;i++){
        int t=i;
        while(t)ans+=(t%10==2),t/=10;
    }
    printf("%d\n",ans);
    return 0;
}

普及T2 接水问题

题目地址

模拟即可。
可以用堆加速，但我的代码里没用。
不用堆的时间复杂度是$O(nm)$，用的话是$O(nlogm)$。

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
#include <bits/stdc++.h>
#define INF 1000000000
using namespace std;
int n,m,at[105],w[10005],f=0,ans=0; 
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)
        scanf("%d",&at[i]);
    for(int i=m;i<n;i++)
        scanf("%d",&w[i-m]);
    for(;;){
        int mini=INF;
        for(int i=0;i<m;i++)
            if(at[i]>0&&at[i]<mini)mini=at[i];
        if(mini==INF)break;
        ans+=mini;
        for(int i=0;i<m;i++)
            if(at[i]>0){
                at[i]-=mini;
                if(!at[i]){
                    if(f!=n-m)at[i]=w[f++];
                    else at[i]=-1;
                }
            }
    }
    printf("%d\n",ans);
    return 0;
}

普及T3 导弹拦截

题目地址

此题致敬了11年前的那道经典题目。
我们希望这个工作半径最小，直觉上就要让这两个系统都被充分利用。也就是让第一套拦截一部分，第二套拦截另一部分。
我们先对所有导弹到第一套系统的距离从近到远排一个序，企图把这个序列切成$2$份，将前半部分给第一个系统，将后半部分（远的）给第二个系统。
枚举切开的部位，找到第二套系统应该有的工作半径，也就是分配给第二套系统的最远导弹到他的距离。这里用各种方法实现，我用的是对所有导弹到第二套系统的距离从远到近排一个序，然后用一个指针扫的方法。
综上，解决本题的时间复杂度为$O(nlogn)$。

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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct{
    int id,dis;
}Mis;
Mis mis[200005];
bool operator<(Mis a,Mis b){return a.dis<b.dis;}
int p1[2],p2[2],n,at;//p1 x  p2 y
bool vis[100005]={0};
int ask(){//找第二套应该有的工作半径
    while(vis[mis[at].id]&&at<2*n)
        at++;
    if(at==2*n)return 0;
    else return mis[at].dis;
}
int main(){
    scanf("%d%d%d%d%d",&p1[0],&p2[0],&p1[1],&p2[1],&n);
    int i,j,l1,l2,ans=2000000000;
    for(i=0;i<n;i++)
        scanf("%d%d",&l1,&l2),
        mis[i].dis=(p1[0]-l1)*(p1[0]-l1)+
        (p2[0]-l2)*(p2[0]-l2),
        mis[i+n].dis=-(p1[1]-l1)*(p1[1]-l1)-
        (p2[1]-l2)*(p2[1]-l2),
        mis[i].id=mis[i+n].id=i;
    sort(mis,mis+n),
    sort(mis+n,mis+n+n),
    at=n;
    ans=min(ans,-ask());//全部分配给第二套
    for(i=0;i<n;i++)
        vis[mis[i].id]=1,
        ans=min(ans,(mis[i].dis-ask()));
    printf("%d\n",ans);
    return 0;
}

普及T4 三国游戏

题目地址

这个人肯定不会输给电脑。
因为计算机的选将是完全根据这个人的选法来的，也就是说，这个人自己是一定有把握选中更好的策略的。
然后具体选法，非常简单：
最大的一定被拆，所以我们矮子里拔高个儿，选默契值排第二且是所有第二中最高的一对将。
这样就做完了。
时间复杂度：$O(n^2)$。

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>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
typedef long long ll;
int n,mat[505][505]={0};
void init(){
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
        for(int j=i+1;j<n;j++)
            scanf("%d",&mat[i][j]),
            mat[j][i]=mat[i][j];
}
void solve(){
    int max1=0,max2=0,ans=0;
    for(int i=0;i<n;i++){
        max1=max2=0;
        for(int j=0;j<n;j++){
            if(mat[i][j]>max1)max2=max1,max1=mat[i][j];
            else if(mat[i][j]>max2)max2=mat[i][j];
        }
        ans=max(ans,max2);
    }
    printf("1\n%d\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}

提高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
#include <bits/stdc++.h>
#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; 
}
bool vis[1005];
int w,m,n,que[100005],f=0,r=0;
void init(){
    m=read(),n=read();
}
void solve(){
    int ans=0;
    while(n--){
        w=read();
        if(!vis[w]){
            vis[w]=1,que[r++]=w,ans++;
            if(r-f==m+1)vis[que[f++]]=0;
        }
    }
    printf("%d\n",ans);
}
int main(){
    init();
    solve();
    return 0;
}

提高T2 乌龟棋

题目地址

按卡片数$DP$即可。只要知道每一种卡片的使用情况就可以推知当前所处位置，从而进行状态转移。
设$f(i,j,k,l)$表示用了$i$张$1$，$j$张$2$，$k$张$3$，$l$张$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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define dis(a,b,c,d) score[1+a+(b<<1)+(d<<2)+(c<<2)-c]
#define fep(a,b) for(a=0;a<=cnt[b];a++)
using namespace std;
int dp[41][41][41][41]={0},n,m,cnt[4]={0},score[353];
int main(){
    scanf("%d%d",&n,&m);
    int i,j,u,v,d;
    for(i=1;i<=n;i++)
        scanf("%d",&score[i]);
    for(i=0;i<m;i++)
        scanf("%d",&j),cnt[j-1]++;
    dp[0][0][0][0]=score[1];
    fep(i,0)fep(j,1)fep(u,2)fep(v,3){
        d=dis(i,j,u,v);
        if(i)dp[i][j][u][v]=max(dp[i-1][j][u][v]+d,dp[i][j][u][v]);
        if(j)dp[i][j][u][v]=max(dp[i][j-1][u][v]+d,dp[i][j][u][v]);
        if(u)dp[i][j][u][v]=max(dp[i][j][u-1][v]+d,dp[i][j][u][v]);
        if(v)dp[i][j][u][v]=max(dp[i][j][u][v-1]+d,dp[i][j][u][v]);
    }
    printf("%d\n",dp[cnt[0]][cnt[1]][cnt[2]][cnt[3]]);
    return 0;
}

提高T3 关押罪犯（待考察）

题目地址

贪心。
将仇恨值从大到小排序，从仇恨最大的一对人开始处理起。记录每一个人的“对手”，看作是这个人和“对手”必须处在不同监狱。如果两人所处监狱相同那就表示分配到此为止，输出答案。
然后分类讨论，假设两人都还没有对手就互相记为对手，表示两人不会在一个监狱；只有一个人有对手，那就另一个人把这个人记为对手，并且把这个人的对手收为己方（用并查集实现）；两个人都有，那就收各自的对手为己方。
讨论完之后，处理下一对罪犯，如此反复。
这样就可以在$O(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
38
39
40
41
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int parent[20005],riv[20005]={0},m,n,re[100005][3];
int cmp(const void *a,const void *b){
    return *(int*)b-*(int*)a;
}
void init(int k){
    for(int i=1;i<=k;i++)parent[i]=i;
}
int Find(int a){
    if(parent[a]==a)return a;
    return (parent[a]=Find(parent[a]));
}
void joint(int x,int y){
    int a=Find(x),b=Find(y);
    if(a==b)return;
    parent[b]=a;
}
int main(){
    scanf("%d%d",&n,&m);
    init(n);int i,k1,k2,t1,t2;
    for(int i=0;i<m;i++)
        scanf("%d%d%d",&re[i][1],&re[i][2],&re[i][0]);
    qsort(re,m,sizeof(re[0]),cmp);
    for(i=0;i<m;i++){
        t1=re[i][1],t2=re[i][2];
        if(Find(t1)==Find(t2))break;
        if(riv[t2]&&!riv[t1])swap(t1,t2);
        if(!riv[t2]){
            if(!riv[t1])riv[t1]=t2,riv[t2]=t1;
            else riv[t2]=t1,joint(t2,riv[t1]);
        }else
            joint(t2,riv[t1]),joint(t1,riv[t2]);
    }
    if(i==m)printf("0\n");
    else printf("%d\n",re[i][0]);
    return 0;
}

提高T4 引水入城

题目地址

先搜索，搜出每一个出水站能最多支援几个国家。
然后会发现每一个国家能支援到的国家一定是一段一段存在的。
如果不是，那么会形成一些国家无法被到达的局面，就输出$0$，然后统计。
否则对每段区间排序后贪心选择即可。
可以用一些手段加速，如对在第一行的国家，只选取相对周围的国家更高一些的国家来搜索，因为这个国家肯定可以向两侧扩展。
时间复杂度：$O(nm)$（近似）

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
bool dp[505][505],able[505][505]={0};
int n,m,h[505][505],par[505],res,ans,dx[]={-1,0,0,1},dy[]={0,-1,1,0};
int stack[250005][2],top=0;
void dfs(int x,int y){
    int nx,ny,i;
    stack[top][0]=x,stack[top++][1]=y;
    while(top){
        x=stack[--top][0],y=stack[top][1];
        for(i=0;i<4;i++){
            nx=x+dx[i],ny=y+dy[i];
            if(nx>=0&&ny>=0&&nx<n&&ny<m&&
            h[nx][ny]<h[x][y]&&!dp[nx][ny])
                dp[nx][ny]=1,stack[top][0]=nx,stack[top++][1]=ny;
        }
    }
}
void _solve(){
    int i,j,p,k,rec[505][2],tot=0,l,r;
    for(ans=1,i=j=0;j<m;j++){
        while(i<m&&par[i]==par[j])i++;
        p=par[i-1],k=0;
        while(k<m&&!able[p][k])k++;
        rec[tot][0]=k;
        if(tot&&rec[tot-1][0]==k)tot--;
        while(k<m&&able[p][k])k++;
        rec[tot++][1]=k-1;
        if(k-1<rec[tot-1][0])tot--;
        j=i-1;
    }
    for(l=rec[0][0],r=rec[0][1],i=1;i<tot;i++){
        while(i<tot&&rec[i][0]<=r+1)i++;
        if(r==m-1)break;
        i--,r=rec[i][1],ans++;
    }
}
void solve(){
    int i,j,k;
    for(i=j=0;j<m;j++){
        while(i<m&&par[i]==par[j])i++;
        memset(dp,0,sizeof(dp));
        dp[0][par[i-1]]=1,dfs(0,par[i-1]);
        memcpy(able[par[i-1]],dp[n-1],sizeof(bool)*m);
        j=i-1;
    }
    bool cnt[505]={0};
    for(k=i=0;i<m;i++)
        for(j=0;j<m;j++)
            if(able[par[i]][j]&&!cnt[j])cnt[j]=1,k++;
    res=(k==m)?1:0;
    if(res)_solve();
    else ans=m-k;
    printf("%d\n%d\n",res,ans);
}
int main(){
    scanf("%d%d",&n,&m);
    int i,j,maxi,lst;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            scanf("%d",&h[i][j]);
    for(i=0;i<m;i++){
        while(i<m-1&&h[0][i+1]>h[0][i])i++;
        for(j=i-1;j>=0&&h[0][j]<h[0][j+1];j--)
            par[j]=i;
        par[i]=i;
        for(j=i+1;j<m&&h[0][j]<h[0][j-1];j++)
            par[j]=i;
        while(i<m-1&&h[0][i+1]<h[0][i])i++;
    }
    solve();
    return 0;
}

Powered By Valine
v1.5.2