第一次C语言比赛完美落幕
嵌入式Linux：第一届“C语言比赛”
题目链接
提示 - 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
答案提供者
参考代码
#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 = 0; /* 字典树当前分配的节点编号 */
void build_trie(char *s, int val) /* 插入单词S到字典树中 */
{
int root = 0;
char *p = s;
int num = 0;
while (*p != '\0')
{
num = *p - 'a';
if (g_trie[root][num] == 0)
{
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 = 0;
memset(g_trie, 0, sizeof(int) * MAX_TRIE_NODE * MAX_ALPHA);
memset(trie_vals, 0, sizeof(int) * MAX_TRIE_NODE);
for (i = 0; i < n; i++)
{
scanf("%s %d", trie_entry, &v);
build_trie(trie_entry, v);
}
memset(dp, 0, sizeof(int) * MAX_STR_LEN); /* dp[i]表示target字符串长度为i时的最优解 */
/* 在字典树中查找target从i-j的子串 */
for (i = 0; i < len; i++)
{
kroot = 0;
if (0 != i && 0 == dp[i]) /* 如果dp[i]是0，即target 0-i的子串没有解，没必要再查找i-j子串的权值 */
{
continue;
}
for (j = i; j < (i + MAX_TRIE_ENTRY_LEN - 1) && j < len; j++)
{
if (0 == (kroot = g_trie[kroot][target[j] - 'a'])) /* 第j个字母没有在字典树上找到，即i-j字串没在字符串上找到 */
{
break;
}
/* 如果trie_vals[kroot]是0，即子串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] == 0)
dp[len]--;
printf("%d\n", dp[len]);
}
return 0;
}
/*
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相对简单，但是坑也比较多，写答案的时候要特别注意
答案提供者
参考代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
/*****************************************************************************
函 数 名 : strtrim
功能描述 : 去掉行首行尾空格符
输入参数 : char *s
输出参数 : 无
返 回 值 : char *
调用函数 :
被调函数 :
修改历史 :
1.日 期 : 2018年11月14日
作 者 : 韦启发
修改内容 : 新生成函数
*****************************************************************************/
char * strtrim(char *s) {
char *p = s;
char *q = s;
while (*p==' ' || *p=='\t') ++p;
while (*q++=*p++);
q -= 2;
while (*q==' ' || *q=='\t') --q;
*(q+1) ='\0';
return s;
}
#define Long_Input_Str
#define Short_Input_Str
#define Out_Str
/*****************************************************************************
函 数 名 : strfind
功能描述 : 字符串查找函数
输入参数 : Long_Input_Str const char *pcString1
Short_Input_Str const char *pcString2
输出参数 : 无
返 回 值 : Out_Str char*
调用函数 :
被调函数 :
修改历史 :
1.日 期 : 2018年11月14日
作 者 : 韦启发
修改内容 : 新生成函数
*****************************************************************************/
Out_Str char* strfind(Long_Input_Str const char *pcString1, Short_Input_Str const char *pcString2)
{
char *pCompareStart = (char *)pcString1;
char *pCursor_S1, *pCursor_S2;
char cSrc, cDst;
//判断是否是空，如果是空直接退出
if (!pcString1)
return NULL;
if (!*pcString2)
return NULL;
//循环比较
while (*pCompareStart)
{
//两个字符串赋值
pCursor_S1 = pCompareStart;
pCursor_S2 = (char *)pcString2;
//扫描两个字符串
while (*pCursor_S1 && *pCursor_S2)
{
cSrc = *pCursor_S1;
cDst = *pCursor_S2;
//转换成小写
if ((cSrc >= 'A') && (cSrc <= 'Z'))
cSrc -= ('A' - 'a');
if ((cDst >= 'A') && (cDst <= 'Z'))
cDst -= ('A' - 'a');
if (cSrc != cDst)
break;
pCursor_S1++;
pCursor_S2++;
}
//如果不是空，则找到字符串
if (!*pCursor_S2)
return(pCompareStart);
//地址偏移，比较下一个
pCompareStart++;
}
return NULL;
}
/*****************************************************************************
函 数 名 : main
功能描述 : main函数
输入参数 : void
输出参数 : 无
返 回 值 : int
调用函数 :
被调函数 :
修改历史 :
1.日 期 : 2018年11月14日
作 者 : 韦启发
修改内容 : 新生成函数
*****************************************************************************/
int main(void)
{
int N;
scanf("%d%*c",&N);
char * p[N];
char * pc;
char * pch;
if(N > 1000)
N = 1000;
/*01 开始输入短字符串*/
for(int i=0;i<N;i++)
{
p[i]=(char*)malloc(21*sizeof(char));
gets(p[i]);
/*去掉字符串空格*/
p[i] = strtrim(p[i]);
}
pc = (char*)malloc(10001*sizeof(char));
/*02 循环获取长字符串*/
while(gets(pc)!=NULL)
{
/*03 循环比较N个子字符串*/
for(int i = 0; i<N; i++)
{
/*04 循环查找字符串 直到找不到为止*/
while (strfind(pc,p[i]) != NULL)
{
/*05 获取匹配的长字符串*/
pch = strfind(pc,p[i]);
/*06 get指针有点重复 ，可以修改，懒得动了*/
char * get = (char*)malloc(strlen(p[i]));
strncpy(get,p[i],strlen(p[i]));
for(int j=1;j < strlen(get);j++)
{
*(get +j) = '*';
}
/*07 加上*后再赋值给pch*/
strncpy(pch+1,get+1,strlen(get)-1);
free(get);
}
}
printf("%s\n",pc);
}
free(pc);
return 0;
}
输出结果
第二题的另一个小伙伴提供 答案
#include<stdio.h>
#include<string.h>
#define MAX_NODE_NUM 10000
#define MAX_ALPHA_NUM 26
int curr_node = 0;
int trie[MAX_NODE_NUM][MAX_ALPHA_NUM];
int kword[MAX_NODE_NUM];
int find(char* start, char* end)
{
int root = 0;
int num;
while (start < end)
{
if (*start >= 'A' && *start <= 'Z')
{
num = *start - 'A';
}
else
{
num = *start - 'a';
}
if (trie[root][num] == 0)
{
return -1;
}
root = trie[root][num];
start++;
}
if (kword[root] != 1)
{
return -1;
}
return 0;
}
int main()
{
int n, root, num;
char target[10001];
char c;
char *p1, *p2, *p, *tmp;
curr_node = 0;
memset(trie, 0, sizeof(int) * MAX_NODE_NUM * MAX_ALPHA_NUM);
memset(kword, 0, sizeof(int) * MAX_NODE_NUM);
scanf("%d\n", &n);
while (n--)
{
root = 0;
while ('\n' != (c = getchar()))
{
if (c >= 'A' && c <= 'Z')
{
num = c - 'A';
}
else
{
num = c - 'a';
}
if (0 == trie[root][num])
{
trie[root][num] = ++curr_node;
}
root = trie[root][num];
}
kword[root] = 1;
}
p1 = p2 = target;
while (EOF != (c = getchar()))
{
//if (c == ' ' || c == '\t' || c == '.' || c == ',')
if (!(c >= 'A' && c <= 'Z' || c >= 'a' && c <= 'z'))
{
if (0 == find(p1, p2))
{
while (++p1 != p2)
{
*p1 = '*';
}
}
*p2++ = c;
p1 = p2;
}
else
{
*p2++ = c;
}
}
*p2 = '\0';
printf("%s", target);
return 0;
}
/*
2
Love
sylu
I love ShenYang,and love sylu more
output:
I l*** ShenYang,and l*** s*** more
*/
觉得对你有帮助，请关注微信公众号-嵌入式Linux
原文作者：；如有侵权，请联系管理员删除。
