ITPub博客

首页 > 应用开发 > C/C++ > 第一届C语言比赛答案

第一届C语言比赛答案

原创 C/C++ 作者:LinuxDevqqqqqq 时间:2018-11-22 16:17:00 0 删除 编辑

嵌入式Linux:第一届C语言比赛


题目链接

密码 2580

下面给出题目解析和答案

题目 1

题目描述

This English game is a simple English words connection game.

The rules are as follows: there are N English words in a dictionary, and every word has its own weight v. There is a weight if the corresponding word is used. Now there is a target string X. You have to pick some words in the dictionary, and then connect them to form X. At the same time, the sum weight of the words you picked must be the biggest.

输入

There are several test cases. For each test, N (1<=n<=1000) and X (the length of x is not bigger than 10000) are given at first. Then N rows follow. Each row contains a word wi (the length is not bigger than 30) and the weight of it. Every word is composed of lowercases. No two words in the dictionary are the same.

输出

For each test case, output the biggest sum weight, if you could not form the string X, output -1.

 

题目翻译

输入一个数字 N 和一个长字符串 XXXXXXXXXX

然后输入 N 个子字符串 TTTTT ,并给出每个子字符串的权值 Y

然后输出长字符串的最大权值 S

答案提供者

<img src=" data-caption="" data-size="normal" data-rawwidth="111" data-rawheight="92" width="111">

参考代码

#include <stdio.h>

#include <string.h>

 

#define MAX_STR_LEN 10001

#define MAX_TRIE_ENTRY_LEN 31

#define MAX_TRIE_NODE 300001

#define MAX_ALPHA 26

 

int g_trie[MAX_TRIE_NODE][MAX_ALPHA];     /*  字典树 */

int trie_vals[MAX_TRIE_NODE];             /*  字典树上关键字权值 */

int curr_node  = ;                            /*  字典树当前分配的节点编号 */

 

void build_trie ( char * s,  int val)         /*  插入单词 S 到字典树中 */

{

      int root  = ;

      char * = s;

      int num  = ;

      while ( * != '\0' )

     {

         num  = * - 'a' ;

          if (g_trie[root][num]  == )

         {

              g_trie[root][num]  = ++ curr_node;

         }

         root  = g_trie[root][num];

         p ++ ;

     }

     trie_vals[root]  = val;      /* 记录权值,也可以用来标记字典树中关键字结束(即叶子节点) */

      return ;

}

 

int main ()

{

      int n, v, len, num, i, j, kroot;

      int dp[MAX_STR_LEN];

      char target[MAX_STR_LEN];

      char trie_entry[MAX_TRIE_ENTRY_LEN];

     

      while ( ~ scanf( "%d %s" & n, target))

     {

         len  = strlen(target);

          /* 初始化叶子节点 */

         curr_node  = ;

         memset(g_trie,  sizeof ( int * MAX_TRIE_NODE  * MAX_ALPHA);

         memset(trie_vals,  sizeof ( int * MAX_TRIE_NODE);

          for (i  = ; i  < n; i ++ )

         {

              scanf( "%s %d" , trie_entry,  & v);

              build_trie(trie_entry, v);

         }

         

         memset(dp,  sizeof ( int * MAX_STR_LEN);     /* dp[i] 表示 target 字符串长度为 i 时的最优解 */

          /* 在字典树中查找 target i-j 的子串 */

          for (i  = ; i  < len; i ++ )

         {

              kroot  = ;

               if ( != && == dp[i])   /*  如果 dp[i] ,即 target 0-i 的子串没有解,没必要再查找 i-j 子串的权值 */

              {

                   continue ;

              }

               for (j  = i; j  < (i  + MAX_TRIE_ENTRY_LEN  - 1 && < len; j ++ )

              {

                   if ( == (kroot  = g_trie[kroot][target[j]  - 'a' ]))     /* j 个字母没有在字典树上找到,即 i-j 字串没在字符串上找到 */

                  {

                        break ;

                  }

                  

                   /* 如果 trie_vals[kroot] ,即子串 i-j 只匹配了某关键字的前缀,没有全词匹配得到 */

                   /* dp[j + 1] = max(dp[i] + trie_vals[kroot], dp[j + 1]) ,如果长度 i 的最优解加上 i-j 字串的权值更大,就取该值 */

                   if (trie_vals[kroot]  && dp[j  + 1 < dp[i]  + trie_vals[kroot])

                  {

                       dp[j  + 1 = dp[i]  + trie_vals[kroot];

                  }

              }

         }

         

          if (dp[len]  == )

              dp[len] -- ;

         printf( "%d\n" , dp[len]);

     }

      return ;

}

 

/*

 

1 aaaa

a 2

3 aaa

a 2

aa 5

aaa 6

4 abc

a 1

bc 2

ab 4

c 1

3 abcd

ab 10

bc 20

cd 30

3 abcd

cd 100

abc 1000

bcd 10000

 

output:

8

7

5

40

-1

 

*/

题目 2

题目描述

此刻你正在为沈阳理工开发一个 BBS ,为了网络文明并避免一些敏感词汇, BBS 的聊天中不能出现某些违禁用语。所以你的系统设计为由管理员输入若干的违禁词汇,对于帖子中的违禁词汇,系统只显示第一个字符,其他字符全部用 * 代替。注意查找违禁词汇时是不考虑大小写的,但修改时则要保留大小写。比如 love 是违禁词汇,则 Love love 都是违禁词语,而帖子中的 love 被输出为 l*** ,而 Love 输出 L*** 。现在就看你的啦!

输入

输入数据只有一组,第一行为一个正整数 n n<=1000 ),接下来有 n 行,每行有一个英文单词,由若干个英文字母组成,不含空格(单词长度不超过 20 )。

 

接下来有若干段需要处理的文字,处理到文件结束为止,字符个数不超过 10000 个。

输出

输出处理后的文字,除了违禁用语,其他文字和格式不变。

 

题目解析

这个题目相对题目 1 相对简单,但是坑也比较多,写答案的时候要特别注意

 


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/31561984/viewspace-2221176/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
微信公众号-嵌入式Linux 嵌入式开发有10余年,从刚开始的STC89C51单片机,STM32单片机,ARM,Linux ,Nordic ble ,Android系统开发,在学习和开发过程中,积累了很多经验,希望这些学习经验跟在码农路上一起奋斗的同学们一起分享。

注册时间:2018-11-13

  • 博文量
    60
  • 访问量
    68744