【蒟蒻题解】SCOI 2006(DAY 1)

这几天可能都会做各地省选题,所以这段时间就先放下新算法的讲解,重点讲解这些经典套题,那么几天就让我们走进SCOI 2006 DAY 1的奇幻旅程吧!

T1 zh_tree

题目描述:

Description

张老师根据自己工作的需要,设计了一种特殊的二叉搜索树。他把这种二叉树起名为zh_tree,对于具有n个结点的zh_tree,其中序遍历恰好为(1,2,3,…,n),其中数字1,2,3,…,n 是每个结点的编号。n个结点恰好对应于一组学术论文中出现的n个不同的单词。第j个单词在该组论文中出现的次数记为dj,例如,d2=10表示第2个结点所对应的单词在该组论文中出现了10次。设该组论文中出现的单词总数为S,显然,S=d1+d2+…+dn。记fj=dj/S为第j个单词在该组论文中出现的概率(频率)。 张老师把根结点深度规定为0,如果第j个结点的深度为r,则访问该结点的代价hj为hj=k(r+1)+c,其中k,c为已知的不超过100的正常数。 则zh_tree是满足以下条件的一棵二叉树:它使 h1f1+h2f2+…+hnfn 达到最小。我们称上式为访问zh_tree的平均代价。 请你根据已知数据为张老师设计一棵zh_tree。
Input

第1行:3个用空格隔开的正数: n k c 其中n<30,为整数,k,c为不超过100的正实数。 第2行:n个用空格隔开的正整数,为每个单词出现的次数(次数<200)。
Output

第1行:(5分)一个正实数,保留3位小数,为访问Zh_tree的最小平均代价。 第2行:(5分)n个用空格隔开的整数,为该树的前序遍历。一般地,作为最优解的前序遍历不一定唯一,只输出一个解。

Sample Input
4 2 3.5
20 30 50 20

Sample Output
7.000

AC解法:

这道题字里行间都透露出一种DP的芳香,没错,这就是一道很经典的区间DP(其实也可以说是记忆化搜索)。

我们定义数组dp【l】【r】【k】表示区间l,r的根节点在深度k时的最小代价;所以很显然的就可以分为三种情况:

1.l为这一层层的根节点,【i+1,r】的根节点在k+1层;
2.r为这一层的根节点,【i,r-1】的根节点在k+1层;
3.在(l,r)中有一个点i为根节点,【l,i-1】和【i+1,r】的根节点在k+1层

所以动态规划方程就很显然了:

double maxx=1000000000.0000;
        maxx=my_min(maxx,find(l+1,r,dep+1)+f[l]*(k*dep+c));
        maxx=my_min(maxx,find(l,r-1,dep+1)+f[r]*(k*dep+c));
        for(int i=l+1;i<r;i++)
        {
            maxx=my_min(maxx,find(l,i-1,dep+1)+find(i+1,r,dep+1)+f[i]*(k*dep+c));
        }
        dp[l][r][dep]=maxx;

接下来我们只需要从(1,n,1)出发(dep从1开始是为了解决题目中r+1的问题),逐层DP,加以记忆化,就可以很轻松的在时限内完成这道题了。

程序部分:

#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
double f[110],dp[110][110][110],c,k;
int a[110],i,j,m,n,o,p,js,visit[110][110][110]={0},jl,tot;
double my_min(double x,double y)
{
    if(x<y)return(x);
    else return(y);
}
double find(int l,int r,int dep)
{
    if(visit[l][r][dep]==1)return(dp[l][r][dep]);
    visit[l][r][dep]=1;
    if(l==r)
    {
        dp[l][r][dep]=f[l]*(dep*k+c);
        return(dp[l][r][dep]);
    }
    else
    {
        double maxx=1000000000.0000;
        maxx=my_min(maxx,find(l+1,r,dep+1)+f[l]*(k*dep+c));
        maxx=my_min(maxx,find(l,r-1,dep+1)+f[r]*(k*dep+c));
        for(int i=l+1;i<r;i++)
        {
            maxx=my_min(maxx,find(l,i-1,dep+1)+find(i+1,r,dep+1)+f[i]*(k*dep+c));
        }
        dp[l][r][dep]=maxx;
        return(dp[l][r][dep]);
    }
}

int main()
{
    scanf("%d%lf%lf",&n,&k,&c);
    tot=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        tot=tot+a[i];
    }
    for(int i=1;i<=n;i++)f[i]=double(a[i])/double(tot);
    find(1,n,1);
    printf("%0.3lf",dp[1][n][1]);
    return 0;
}

T2 k进制集合的映射

题目描述:
1.gif2.gif

AC解法:
这道题整个网站通过的人数少之又少,而且貌似找不到题解,这里就讲一下出题人的想法吧:

2_1.PNG2_2.PNG2_3.PNG2_4.PNG

程序部分(不知道为什么不能直接贴,所以附上下载文件【后缀改为c就可用】):
cx.PNG
AC.txt

T3 整数划分

题目描述:

Description

从文件中读入一个正整数n(10≤n≤31000)。要求将n写成若干个正整数之和,并且使这些正整数的乘积最大。 例如,n=13,则当n表示为4+3+3+3(或2+2+3+3+3)时,乘积=108为最大。

Input
只有一个正整数: n (10≤n≤31000)

Output
第1行输出一个整数,为最大乘积的位数。 第2行输出最大乘积的前100位,如果不足100位,则按实际位数输出最大乘积。 (提示:在给定的范围内,最大乘积的位数不超过5000位)。

Sample Input
13

Sample Output
3
108

这道题就是很经典的结论题,可能很多人之前都想到过这个问题——将n写成若干个正整数之和,并且使这些正整数的乘积最大,那么怎么拆才最大呢?

没错,就是尽量拆成3相乘:那么为什么是这样呢?我们发现,当n=12时,可以写成2^6=64,3^4=81,4^3=64,然后我们就猜测这会不会是一个先递增再递减的图像?结果证明确实是这样。

所以我们就把n尽量拆成3,最后一个拆不了3就拆成2或者4,一定不要出现拆成1的情况!!!

由于要求输出前100位,再加之一共不超过5000位,裸的高精度乘法就好了。

程序部分:

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int i,j,k,m,n,o,p,js,jl;
int a[11000];
int matrix(int last,int x)
{
    for(int i=1;i<=last;i++)
    {
        a[i]=a[i]*x+a[i-1]/10;
        a[i-1]=a[i-1]%10;
    }
    if(a[last]>=10)
    {
        jl++;
        a[jl]=a[jl-1]/10;
        a[jl-1]=a[jl-1]%10;
    }
}
int main()
{
    scanf("%d",&n);
    a[1]=1;
    if(n<=4)
    {
        printf("1\n%d",n);
        exit (0);
    }
    jl=1;
    while(n>4)
    {
        n=n-3;
        matrix(jl,3);
    }
    matrix(jl,n);
    printf("%d\n",jl);
    if(jl<=100)for(int i=jl;i>=1;i--)printf("%d",a[i]);
    else for(int i=jl;i>=jl-99;i--)printf("%d",a[i]);
    return 0;
}

结语

对比2005年的SCOI DAY1,2006年难度得到了一定的提升,都是一些非常经典的题目,还是很值得一做的,希望你喜欢这篇题解。
zj.PNG

Last modification:July 12th, 2018 at 09:26 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment