【蒟蒻题解】SCOI2005(DAY 1)

昨天打了一下2005年的SCOI,虽然已经是十多年前的省选题了,但是很多题目还是不能一次AC(我太菜了QwQ),下面就让我来讲讲这套题的解法吧

T1 超级格雷码

题目描述:

Description:
著名的格雷码是指2n个不同n位二进制数(即0~2n-1,不足n位在前补零)的一个排列,这个排列满足相邻的两
个二进制数的n位数字中最多只有一个数字不同(例如003和001就有一个数位不同,而003和030有两个数位不同,
不符合条件)。例如n=2时,(00,01,11,10)就是一个满足条件的格雷码。 所谓超级格雷码就是指Bn个不同的n位B
进制数的排列满足上面的条件。 任务:给出n和B(2≤B≤36, 1≤Bn≤65535),求一个满足条件的格雷码。对于
大于9的数位用A~Z表示(10~35)。

Input
只有一行,为两个整数n和B。

Output
一共Bn个行,每行一个B进制数,表示你所求得的符合条件的排列

Sample Input
2 2

Sample Output
00
01
11
10

AC解法:
这道题的思路就是很经典的打表找规律,首先我们先可以打出一个3,3的表:

000
100
200
210
110
010
020
120
220
221
121
021
011
111
211
201
101
001
002
102
202
212
112
012
022
122
222


然后我们发现,对于从左往右数的任意第i位,在第i位不变的一个序列中(见下图),他的前一位(也就是i-1位)是按顺序或者逆序排列的,那么究竟是顺序还是逆序呢?

1.PNG

通过观察我们发现:
当从左往右数的任意第i位为偶数时,则第i-1位是相对于第i位的枚举顺序递增枚举的(比如第二列为0时,前一列为【0,1,2】(第一个绿色箭头)),即若第i位为顺序,则i-1位为顺序,若第i位为逆序,则i-1位为逆序;

反之当第i位为奇数时,则第i-1位是第i位的枚举顺序递减枚举的(比如第二列为2时,前一列为【2,1,0】(第二个绿色箭头)),即若第i位为顺序,则i-1位为逆序,若第i位为逆序,则i-1位为顺序。

所以程序就很显然了:

程序部分:

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n,b;
int a[1100];

int build(int k,int t)
{
    if(k==0)
    {
        for(int i=1;i<=n;i++)
        if(a[i]<10)printf("%d",a[i]);
        else printf("%c",a[i]-10+'A');

        printf("\n");
        return 0;
    }

    if(t==1)
    {
        for(int i=0;i<b;i++)
        {
            a[k]=i;
            if(i%2==1)build(k-1,0);
            else build(k-1,1);
        }
    }
    else
    {
         for(int i=b-1;i>=0;i--)
         {
            a[k]=i;
            if(i%2==1)build(k-1,1);
            else build(k-1,0);
         }
    }
}

int main()
{
    scanf("%d%d",&n,&b);
    memset(a,sizeof(a),0);
    build(n,1);
    return(0);
}

T2 栅栏

题目描述:

Description

农夫约翰打算建立一个栅栏将他的牧场给围起来,因此他需要一些特定规格的木材。于是农夫约翰到木材店购
买木材。可是木材店老板说他这里只剩下少部分大规格的木板了。不过约翰可以购买这些木板,然后切割成他所需
要的规格。而且约翰有一把神奇的锯子,用它来锯木板,不会产生任何损失,也就是说长度为10的木板可以切成长
度为8和2的两个木板。你的任务:给你约翰所需要的木板的规格,还有木材店老板能够给出的木材的规格,求约翰
最多能够得到多少他所需要的木板。

Input

 > 第一行为整数m(m<= 50)表示木材店老板可以提供多少块木材给约翰。紧跟着m行为老板提供的每一块木板的长
度。接下来一行(即第m+2行)为整数n(n <= 1000),表示约翰需要多少木材。接下来n行表示他所需要的每一块木板
的长度。木材的规格小于32767。(对于店老板提供的和约翰需要的每块木板,你只能使用一次)。

Output

 > 只有一行,为约翰最多能够得到的符合条件的木板的个数。

Sample Input

4
30
40
50
25
10
15
16
17
18
19
20
21
25
24
30

Sample Output
7

HINT
25切出 21 30切出 20 40切出 19、18 50切出 15、16、17

AC解法:

首先看到这道题,就觉得正着做很难做,所以我们就考虑能不能从侧面做?

当然是可以的,那么如何从侧面做呢?很经典的做法,我们可以二分我们能得到的符合条件的木板的个数,若当次二分到k,接下来就是如何判断能否满足前k小的需求了。

正常来说,我们的思路就是DFS枚举用第i块木板来满足第j个需求。但是若是裸的DFS,肯定超时。那么我们只要看能否满足前k小的全部所需木板就行了。

因为贪心的来想一下,对于任意一次需求的木棍,若能满足大的木板,就必定能满足小的木板,所以我们只需要判断小的木板能否满足就行了(若小的无法满足,大的也一定能满足)

所以DFS的时候是按照需要的木棍从大到小的顺序一层一层搜,每一层上是按照从小到大的顺序枚举提供的木棍。(当然枚举的时候已经不一定是从小到大了,有些木棍已经被截掉了一些。)

要使用两个有效的剪枝:

1)如果下一层的木棍和这一层的木棍等长,就从这一层木棍枚举到的提供的木棍开始枚举,因为前面的都是不可以的。

2)当一根木棍被截掉一段之后小于最小的需要的木棍,那么它就废掉了,记录当前废掉的木棍总长Rest,如果Rest + 1到mid所有木棍的总长 > 提供的所有木棍总长,那么就返回 false。

具体来看程序吧:

程序部分:

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1000],b[11000],c[11000];
int i,j,k,m,n,o,p,js,jl,l,r,mid,tot,w;

bool pd(int x,int last)//x表示木板个数,last表示从哪个木板开始考虑(切割)
{
    int i;bool fg;
    if(w>tot-c[mid])return(false);
    if(x==0)return(true);

    for(i=last;i<=m;i++)
    if(a[i]>=b[x])
    {
        a[i]=a[i]-b[x];//切掉这块
        if(a[i]<b[1])w=w+a[i];//如果比最小的一块还要小,则算作废料

        if(b[x-1]==b[x]) fg=pd(x-1,i);//回溯
        else fg=pd(x-1,1);

        if(a[i]<b[1])w=w+a[i];
        a[i]=a[i]+b[x];

        if(fg==true)return(true);
    }
    return(false);

}

int main()
{
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        tot=tot+a[i];
    }
    sort(a+1,a+m+1);

    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b[i]);

    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)c[i]=c[i-1]+b[i];

    while (c[n]>tot) n--;  
    l=0;r=n;
    while(r-l>1)
    {
        w=0;
        mid=(l+r)/2;
        if(pd(mid,1)==true)l=mid;
        else r=mid-1;
    }
    w=0;
    if(pd(r,1)==true)printf("%d",r);
    else printf("%d",l);
    return 0; 
}

T3 繁忙的都市

题目描述:

Description

城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道
路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连
接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这
个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的
要求: 1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来。 2. 在满足要求1的情况下,改造的
道路尽量少。 3. 在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。任务:作为市规划
局的你,应当作出最佳的决策,选择那些道路应当被修建。

Input

第一行有两个整数n,m表示城市有n个交叉路口,m条道路。接下来m行是对每条道路的描述,u, v, c表示交叉
路口u和v之间有道路相连,分值为c。(1≤n≤300,1≤c≤10000)

Output

两个整数s, max,表示你选出了几条道路,分值最大的那条道路的分值是多少。

Sample Input
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

Sample Output
3 6

AC解法:

这应该是这套题目最水的一道题目了吧,思路有两种:

首先,因为图一定是联通的,所以若要改造的道路尽量少,最后出来的路径一定是一棵树。想到树,想到最长边最短,想到什么?

二分!(划掉)当然是最小生成树啊,所以只要跑一遍裸的最小生成树就AC了。

当然,这当然不是最简单的解法了,因为我们知道路径条数是n-1,所以我们只要求出这颗最小生成树最长边就行了,所以就很简单了呀——我们对边从小到大排序,再一条条边加进去,直到整幅图联通就行了。至于图是否联通,只要写个并查集就行了(记得路径压缩!!!)

程序部分:

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
    int x,y,sum;
}a[100000];

int f[310],g[310],i,j,k,m,n,o,p,js,jl,x,y;

int comp(node x,node y)
{
    if(x.sum<y.sum)return(true);
    else return(false);
}

int find(int x)//并查集+路径压缩
{
    int p=x,t;  
    while(f[p]!=p)p=f[p];
    while(x!=p){t=f[x];f[x]=p;x=t;}//路径压缩 
    return x;  
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].sum);
    sort(a+1,a+m+1,comp);
    for(int i=1;i<=n;i++)
    {
        g[i]=1;
        f[i]=i;
    }
    printf("%d ",n-1);
    for(int i=1;i<=m;i++)
    {
        x=find(a[i].x);
        y=find(a[i].y);
        if(x!=y)
        {
            f[x]=y;
            g[y]=g[y]+g[x];
            if(g[y]==n)
            {
                printf("%d",a[i].sum);
                exit(0);
            }
        }
    }

    return 0;
}

T4 最大子矩阵

题目描述:

Description

这里有一个n*m的矩阵,请你选出其中k个子矩阵,使得这个k个子矩阵分值之和最大。注意:选出的k个子矩阵
不能相互重叠。

Input

第一行为n,m,k(1≤n≤100,1≤m≤2,1≤k≤10),接下来n行描述矩阵每行中的每个元素的分值(每个元素的
分值的绝对值不超过32767)。

Output

只有一行为k个子矩阵分值之和最大为多少。

Sample Input
3 2 2
1 -3
2 3
-2 3

Sample Output
9

AC解法:

这道题咋一看,好像很高级,不会做,什么数据结构都用不上;再看一眼,呀!1≤m≤2!所以只要分类讨论就好了;

当m=1时,直接DP,设f【i】【k】为前i位分k个段可以到达的最大收益,g【i】为前i位的前缀和;那么动态规划方程就很显然了:
f[j][k]=my_max(f[j][k],f[i-1][k-1]+g[j]-g[i-1]);

当m=2时,设f【i】【j】【k】为第1列到第i位,第2列到第j位,分k个段可以到达的最大收益,g【i】【j】为第j列前i位的前缀和,我们考虑三种情况(如下图):

2.PNG

就是先对于每一个a【i】【j】【k】,可以从a【l】【j】【k-1】和a【i】【l】【k-1】转移过来(如图1,2);同理当i==j的时候,可以从a【l】【l】【k】转移过来。

所以动态规划的方程就呼之欲出了:

for(int ll=1;ll<=i;ll++)f[i][j][k]=my_max(f[i][j][k],f[ll-1][j][k-1]+g[i][1]-g[ll-1][1]);
            for(int ll=1;ll<=j;ll++)f[i][j][k]=my_max(f[i][j][k],f[i][ll-1][k-1]+g[j][2]-g[ll-1][2]);
            if(i==j)for(int ll=1;ll<=i;ll++)f[i][j][k]=my_max(f[i][j][k],f[ll-1][ll-1][k-1]+g[j][2]-g[ll-1][2]+g[i][1]-g[ll-1][1]);

程序部分

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int f[1100][1100][11];
int a[11000][10],g[11000][10];
int i,j,k,m,n,o,p,js,jl,jk,kk,ma,ll;
int my_max(int x,int y)
{
    if(x>y)return(x);
    else return(y);
}
int main()
{
    scanf("%d%d%d",&n,&m,&kk);
    memset(f,-63,sizeof(f));
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        scanf("%d",&a[i][j]);
        g[i][j]=g[i-1][j]+a[i][j];
    }

    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
    f[i][j][0]=0;
    if(m==1)
    {
        ma=-214748364;
        for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
        for(k=1;k<=kk;k++)
        {
            f[i][1][k]=my_max(f[i][1][k],f[i-1][1][k]);
            f[j][1][k]=my_max(f[j][1][k],f[i-1][1][k-1]+g[j][1]-g[i-1][1]);
            if(k==kk)if(f[j][1][k]>ma)ma=f[j][1][k];
        }
        printf("%d",ma);
    }

    else
    {
        ma=-214748364;
        for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        for(int k=1;k<=kk;k++)
        {
            f[i][j][k]=my_max(f[i-1][j][k],f[i][j-1][k]);
            for(int ll=1;ll<=i;ll++)f[i][j][k]=my_max(f[i][j][k],f[ll-1][j][k-1]+g[i][1]-g[ll-1][1]);
            for(int ll=1;ll<=j;ll++)f[i][j][k]=my_max(f[i][j][k],f[i][ll-1][k-1]+g[j][2]-g[ll-1][2]);
            if(i==j)for(int ll=1;ll<=i;ll++)f[i][j][k]=my_max(f[i][j][k],f[ll-1][ll-1][k-1]+g[j][2]-g[ll-1][2]+g[i][1]-g[ll-1][1]);
            if(k==kk)if(f[i][j][k]>ma)ma=f[i][j][k];
        }
        printf("%d",ma);
    }
    return 0;
}

结语

总的来说,这套题的难度就在普及组和提高组左右,细细想想还是可以AK的,希望你喜欢这篇题解!
3.PNG

Last modification:July 12th, 2018 at 05:27 pm
If you think my article is useful to you, please feel free to appreciate

One comment

  1. 黄液体

    我想打牌,黑桃2!

Leave a Comment