Section 2.3

 

         这一节做得很郁闷,题目以动态规划为主,而本人的动规很弱,做的很勉强。。。

 

Longest Prefix

问题描述:

         给定一堆短字符串,和一条长字符串,求用短字符串组成的长字符串的最长前缀长度。

分析:

         看完题目首先想到的是DFS,写完提交上去后到第三组数据就超时了。。。看了别人的题解,原来要用动规,用dp[i]表示当前能拼到的最长前缀,然后在短字符里面寻找最长的能和长字符串继续匹配的,然后i+1!本来想第一次试试Hash,但写到一半觉得函数写得不够好,先记住了,有空了用Hash优化一遍。

 

Cow Pedigrees

问题描述:

      给定一颗树的节点数和度,问其能构成多少种不同的数。

分析

      这题虽然明知道要用动规,但想了一下午都没想出状态转移方程来,囧~。看了网上的官方题解,一颗树显然要由一颗小树(根节点)构成,可以是左子树,也可以是右子树,分三种情况,左长,右长,左右同长。状态转移方程如下:

table[i][j] += smalltrees[i-2][k]*table[i-1][j-1-k];

                  // 左子树深度小于i-1,右子树深度为i-1

table[i][j] += table[i-1][k]*smalltrees[i-2][j-1-k];

                  // 左子树深度为i-1,右子树深度小于i-1

table[i][j] += table[i-1][k]*table[i-1][j-1-k];

                  // 左右子树深度都为i-1

 

Zero Sum

问题描述:

      请考虑一个由1NN=3, 4, 5 ... 9)的数字组成的递增数列:1 2 3 ... N。现在请在数列中插入“+”表示加,或者“-”表示减,“ ”表示空白(例如1-2 3就等于1-23),来将每一对数字组合在一起(请不在第一个数字前插入符号)。计算该表达式的结果并判断其值是否为0。请你写一个程序找出所有产生和为零的长度为N的数列。

分析:

       这题在培训的时候讲过,创建一个字符串“1 2 3 4 5 6 7 8 9 ”数字间隔着空格,然后在空格位置枚举写入‘ ’,‘+’,‘-’递归(其实也就是简单的DFS)。把字符串转成数字运算,若结果为0则输出。

 

Money Systems

问题描述:

      给出一套钱币的面值,求组成某数N有多少种方案。

分析:

       这是个简单的动规,用dp[ i ] [ j ]表示仅用前i种钱币拼成j的方案数,那么仅用前i-1种钱币拼成j的方案dp[i-1][j]也满足,如果用了一枚面值为i的钱币,则dp[i][j]+=dp[i-1][j-v[i]]其中v[i]i的面值,同理,用了两枚dp[i][j]+=dp[i-1][j-2*v[i]],一直到j-k*v[i]<=0为止。

注意,当j可以被v[i]整除时,dp[i][j]++;初始化dp[1][k*v[1]]=1,(k*v[i]<=N)

状态转移方程为:

dp[i][j] =dp[i-1][j-k*v[i]];k=1..j/v[i]

 

Controlling Companies

问题描述:

      有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。如果至少满足了以下三个条件之一,公司A就可以控制公司B了:

1.公司A = 公司B

2.公司A拥有大于50%的公司B的股票。

3.公司A控制K(K >= 1)个公司,记为C1, ..., CK,每个公司Ci拥有xi%的公司B的股票,并且x1+ .... + xK > 50%

给你一个表,每行包括三个数(i,j,p);表明公司i享有公司jp%的股票。计算所有的数对(h,s),表明公司h控制公司s。至多有100个公司。

 

写一个程序读入三对数(i,j,p)i,jp是都在范围(1..100)的正整数,并且找出所有的数对(h,s),使得公司h控制公司s

分析:

       这题似乎很麻烦,当你控制了一家新公司后,新公司又有可能控制着另一家公司,构成一层接一层的迭代关系。。。刚开始用DFS的时候思路就比较混乱,结果只通过了前六个测试,而且效率很低,后来细细分析了一下,其实这有点类似图的结构,题目给出的表可以看做邻接矩阵。问题就转化为,以某点作为原点出发,如果原点到某点s的距离超过50,那么把s纳入原点所在集合P,找与s距离超过50的点,再次纳入P,不断更新原点到这些点的距离。最后列出所有到原点距离超过50的点。

int Own[101][101]={0};
int current[101];
bool visit[101],flag;
int N,MAX=0,MIN=1<<30;

void Search(int n)
{   int i,j;
    
for(j=MIN;j<=MAX;j++)
    
{   current[j]+=Own[n][j];
        
if(current[j]>50&&!visit[j])
        
{   visit[j]=true;
            Search(j);
        }
  
    }
         
}


int main()
{   memset(visit,false,sizeof(visit));
    fin
>>N;
    
int  t=N,i,j,p;
    
while(t--)
    
{   fin>>i>>j>>p;
        Own[i][j]
+=p;
        
if(i>MAX)
            MAX
=i;
        
if(i<MIN)
            MIN
=i;
        
if(j<MIN)
            MIN
=j;
        
if(j>MAX)
            MAX
=j;
    }

    
for(i=MIN;i<=MAX;i++)        
    
{   memset(current,0,sizeof(current));
        memset(visit,
false,sizeof(visit));
        Search(i);
        
for(j=MIN;j<=MAX;j++)
            
if(current[j]>50&&j!=i)
                fout
<<i<<" "<<j<<endl;
    }

    
return 0;
}

posted on 2010-05-26 13:07 ZAKIR 阅读(317) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年7月>
30123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

常用链接

留言簿

随笔档案

文章分类

文章档案

大牛们

搜索

最新评论

阅读排行榜

评论排行榜