第一屆C語言比賽答案

01-09

第一次C語言比賽完美落幕

嵌入式Linux：第一屆「C語言比賽」?

zhuanlan.zhihu.com

題目鏈接

提示 - C語言網?

www.dotcpp.com

密碼 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 != )

	{

		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

", 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==	) ++p;

    while (*q++=*p++);

    q -= 2;

    while (*q==  || *q==	) --q;

    *(q+1) =;

    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 ",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);

	while (n--)

	{

		root = 0;

		while (

 != (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 == 	 || 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 = ;

	printf("%s", target);

	return 0;

}
/*
2

Love

sylu

I love ShenYang,and love sylu more
output:

I l*** ShenYang,and l*** s*** more

*/

覺得對你有幫助，請關注微信公眾號-嵌入式Linux