例79 女孩節
問題描述
在女孩節，我們班上男生和女生聚在一起，在這個場合，每個男孩都會為女孩許愿，男孩想知道女孩對他們愿望的反應，
如果一個愿望包含一個或多個女孩的名字，它被認為是與她們特別交談，否則它就是在和所有的女孩說話，當然，一個愿望可以同時與幾個女孩交談，
如果愿望最多包含9個單詞，女孩會說“oh”，
如果愿望至少包含10個單詞，并且愿望中包括“beautiful”、“pretty”或“lovely”等單詞，女孩會說“xixi”，
如果愿望至少包含10個單詞，但愿望中沒有出現上面提到的3個單詞，女孩會說“hehe”，
一個愿望中不會包含所有的女孩的名字，
輸入
輸入的第一行包含兩個整數g和w（1<=g<=5，1<=w<=30），分別是女孩數量和愿望數量，接下來的g行中，每行是一個只含小寫單詞的單詞，代表一個女孩的名字，接下來的w行中，每行是一個愿望，一個愿望最多包含200個字符，字符只包括字母、空格和“！”，每個愿望包含一個或多個句子，每個句子以“！”結尾，每個句子的第一個字母都是大寫的，其他字母總是小寫的，你可以假設每個愿望在語法上都是正確的，
輸出
對于輸入的每個愿望，給出女孩的回答，如果它正在與所有女孩交談，輸出“All”，或者按照女孩在姓名串列中出現的順序，輸出該愿望涉及的女孩串列（姓名之間用一個空格分隔），然后輸出一個分號，后面跟一個空格，以及諸如“hehe”、“xixi”、“oh”之類的反應，
輸入樣例
5 5
answer
baiqingr
cedar
juleo
seven
Happy girls day to all of you!
Happy girls day to all of you!Wish you happy forever!
Happy girls day for answer mm!
Congratulations for cedar mm and seven mm!Wish you more and more beautiful hehe!
Hello answer hello baiqingr hello juleo would you mind having dinner together!
輸出樣例
All: oh
All: hehe
answer: oh
cedar seven: xixi
answer baiqingr juleo: hehe
（1）編程思路，
因為要檢查“beautiful”、“pretty”或“lovely”等單詞在愿望中的出現情況，撰寫函式int find(char *a,char *b)檢查作為單詞b的字串是否在字串a中出現，與一般字串匹配略有不同的是，若b在a中出現，還需看匹配的前后是否有1個空格，或匹配之前有空格，之后有“!”符號，
撰寫好函式后，直接按題意進行模擬處理即可，
（2）源程式，
#include<stdio.h> #include <string.h> int find(char *a,char *b) { int alen=strlen(a); int blen=strlen(b); int i,j; for (i=0;i<alen;i++) { for (j=0;j<blen && (i+j)<alen; j++) { if (b[j]!=a[i+j]) break; } if (i!=0 && j==blen && (a[i-1]==' '||a[i-1]=='!') && (a[i+j]==' '||a[i+j]=='!')) return 1; if (i==0 && j==blen && (a[i+j]==' '||a[i+j]=='!')) return 1; } return 0; } int main() { int n,m; scanf("%d%d",&n,&m); char name[6][25]; int i; for (i=0;i<n;i++) scanf("%s",name[i]); getchar(); while (m--) { char wish[205]; gets(wish); int wordnum=0; // 單詞數 for (i=0;wish[i]!='\0';i++) { if (wish[i]>='A' && wish[i]<='Z') // 大寫變小寫 wish[i]=wish[i]-'A'+'a'; if (wish[i]>='a'&& wish[i]<='z' && (wish[i+1]==' '||wish[i+1]=='!')) wordnum++; } int h[6]; memset(h,0,sizeof(h)); int cnt=0; for (i=0;i<n;i++) { if (find(wish,name[i]) && h[i]==0) { h[i]=1; cnt++; } } if (cnt==0) printf("All: "); else { int f=0; for (i=0;i<n;i++) { if (h[i]==1) { if (f==0) { printf("%s",name[i]); f=1; } else { printf(" %s",name[i]); } } } printf(": "); } if (wordnum<=9) printf("oh\n"); else { if (find(wish,"beautiful") || find(wish,"pretty") || find(wish,"lovely")) printf("xixi\n"); else printf("hehe\n"); } } return 0; }
將此源程式提交給北大OJ題庫 POJ 1677 Girls' Day（http://poj.org/problem?id=1677）可以Accepted，
習題79
79-1 拼寫檢查
問題描述
現在有一些英語單詞需要做拼寫檢查，你的工具是一本詞典，需要檢查的單詞，有的是詞典中的單詞，有的與詞典中的單詞相似，你的任務是發現這兩種情況，單詞A與單詞B相似的情況有三種：
1、洗掉單詞A的一個字母后得到單詞B；
2、用任意一個字母替換單詞A的一個字母后得到單詞B；
3、在單詞A的任意位置增加一個字母后得到單詞B，
你的任務是發現詞典中與給定單詞相同或相似的單詞，
輸入
第一部分是詞典中的單詞，從第一行開始每行一個單詞，以"#"結束，詞典中的單詞保證不重復，最多有10000個，
第二部分是需要查詢的單詞，每行一個，以"#"結束，最多有50個需要查詢的單詞，
詞典中的單詞和需要查詢的單詞均由小寫字母組成，最多包含15個字符，
輸出
按照輸入的順序，為每個需要檢查的單詞輸出一行，如果需要檢查的單詞出現在詞典中，輸出“?x is correct"，?x代表需要檢查的單詞，如果需要檢查的單詞沒有出現在詞典中，則輸出"?x: ?x1 ?x2 ...?xn"，其中?x代表需要檢查的單詞，?x1...?xn代表詞典中與需要檢查的單詞相似的單詞，這些單詞中間以空格隔開，如果沒有相似的單詞，輸出"?x:"即可，
輸入樣例
i
is
has
have
be
my
more
contest
me
too
if
award
#
me
aware
m
contest
hav
oo
or
i
fi
mre
#
輸出樣例
me is correct
aware: award
m: i my me
contest is correct
hav: has have
oo: too
or:
i is correct
fi: i
mre: more me
（1）編程思路，
設給定單詞的長度為len，則詞典中與給定單詞相同或相似的單詞的長度只可能為len-1、len或len+1，分別對詞典中字串長度為這三種情況的單詞進行處理，
（2）源程式，
#include <stdio.h> #include <string.h> int main() { int i,j,x,k; char s[10001][18]; for(i=0; ;i++) { scanf("%s",s[i]); if (strcmp(s[i],"#")==0) break; } int n=i; char str[18],ans[10001][18]; while (scanf("%s",str) && strcmp(str,"#")!=0) { int f=0; int cnt=0; for (i=0; i<n; i++) { if (strcmp(s[i],str)==0) { printf("%s is correct\n",str); break; } } if (i<n) continue; for (i=0; i<n; i++) { if((strlen(s[i])-strlen(str))==1) { x=0; for(j=0,k=0; j<strlen(s[i])&& k<strlen(str); k++,j++) { while(s[i][j]!=str[k]&&(k<strlen(str))&&(j<strlen(s[i]))) { if(x==0) j++; if(x!=0) k++; x++; } } if(x<=1) { f=1; strcpy(ans[cnt++],s[i]); } } if((strlen(s[i])-strlen(str))==-1) { x=0; for(j=0,k=0; j<strlen(s[i])&& k<strlen(str); k++,j++) { while(s[i][j]!=str[k]&&(k<strlen(str))&&(j<strlen(s[i]))) { if(x==0) k++; if(x!=0) j++; x++; } } if(x<=1) { f=1; strcpy(ans[cnt++],s[i]); } } if((strlen(s[i])-strlen(str))==0) { x=0; for(j=0; j<strlen(str); j++) { if(s[i][j]!=str[j]) { x++; } } if(x==1) { f=1; strcpy(ans[cnt++],s[i]); } } } printf("%s:",str); if (f) for(i=0; i<cnt; i++) { printf(" "); printf("%s",ans[i]); } printf("\n"); } return 0; }
將此源程式提交給北大OJ題庫 POJ 1035 Spell checker（http://poj.org/problem?id=1035）可以Accepted，
79-2 字謎組
問題描述
給定一個文本，找出其中5個最大的字謎組，
文本中包括一系列單詞，一個單詞w是一個單詞v的一個變位詞，當且僅當將w中的一些字符位置重新排列得到v，我們稱w和v在同一個字謎組中，字謎組的大小是該組中的單詞數，
輸入
輸入包含由小寫字母組成的單詞，由空格（或新行）分隔，它由EOF終止，你可以假設不超過30000個單詞，
輸出
輸出5個最大的字謎組，如果少于5組，則將其全部輸出，按大小對組進行排序，組內單詞按字典順序進行排序，相同的單詞只輸出一個，組間也按第1個單詞的字典順序排列，
輸入樣例
undisplayed
trace
tea
singleton
eta
eat
displayed
crate
cater
carte
caret
beta
beat
bate
ate
abet
輸出樣例
Group of size 5: caret carte cater crate trace .
Group of size 4: abet bate beat beta .
Group of size 4: ate eat eta tea .
Group of size 1: displayed .
Group of size 1: singleton .
（1）編程思路，
定義結構體陣列word來保存輸入的各個單詞，
struct WordNode
{
char org[80];
char ord[80];
}word[30005];
其中，成員分量org保存輸入的單詞的原始字串，ord保存將輸入的單詞按小寫字母從小到大排列后的字串，若單詞w和v在同一個字謎組中，則單詞w和v的成員分量ord字串一定相同，
再定義結構體陣列group保存各字謎組，
struct GroupNode
{
int num;
int start;
}group[30005];
其中，成員分量num保存字謎組中單詞個數，start保存字謎組中第1個單詞在排好序后的word陣列中的下標位置，
程式中主要進行3個排序，輸入一個單詞后，將每個單詞按小寫字母從小到大排列后的保存到成員分量ord字串中，
全部單詞輸入完后，將單詞陣列word按成員分量ord字典序升序排列，這樣同一字謎組中的單詞一定排在一起，若成員分量ord相同，則按單詞的原始形式org按字典序升序排列，這樣，word陣列按字謎組排列，組內單詞也按字典序排列，
對word陣列進行回圈遍歷，將每個字謎組的情況統計并保存到group陣列中，之后將group陣列按成員分量num降序排列，這樣字謎組中單詞個數多的排在前面，若成員分量num相同，則按start升序排列，從而保證組間也按第1個單詞的字典順序排列，
（2）源程式，
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; struct WordNode { char org[80]; char ord[80]; }word[30005]; struct GroupNode { int num; int start; }group[30005]; int cmp1(struct WordNode a, struct WordNode b) { if (strcmp(a.ord, b.ord) != 0) return strcmp(a.ord, b.ord) < 0; return strcmp(a.org, b.org) <= 0; } int cmp2(struct GroupNode a, struct GroupNode b) { if (a.num != b.num) return a.num > b.num; return strcmp(word[a.start].org, word[b.start].org)<=0; } int main() { int n=0; // 單詞個數 int i,j; while(scanf("%s", word[n].org) != EOF) { strcpy(word[n].ord, word[n].org); int len = strlen(word[n].ord); sort(word[n].ord, word[n].ord + len); n++; } sort(word, word+n,cmp1); int cnt=1; // 當前組數 group[0].start = 0; // 第1個單詞肯定在第1組中 group[0].num = 1; for (i=1; i<n; i++) { if (strcmp(word[i].ord, word[group[cnt-1].start].ord)==0) { group[cnt-1].num++; } else { group[cnt].start = i; group[cnt].num = 1; cnt++; } } sort(group, group + cnt, cmp2); for (i=0; i<5; i++) { printf("Group of size %d: ",group[i].num); int p=group[i].start; printf("%s ", word[p].org); for (j=1; j<group[i].num; j++) { if(strcmp(word[p+j].org,word[p+j-1].org)!=0) { printf("%s ", word[p+j].org); } } printf(".\n"); } return 0; }
將此源程式提交給北大OJ題庫 POJ 2408 Anagram Groups（http://poj.org/problem?id=2408）可以Accepted，
79-3 單詞翻譯
問題描述
你剛從倫敦搬到一個大城市，這里的人說一種難以理解的外語方言，幸運的是，你有一本字典來幫助你理解它們，
輸入
輸入由多達100000個字典條目組成，后面是一個空行，后面是多達100000個單詞的訊息，每個字典條目都是一行，包含一個英語單詞，后跟一個空格和一個外語單詞，在字典中，外語單詞不會出現一次以上，輸入中的每個單詞最多由10個小寫字母組成，
輸出
將輸入的外語單詞翻譯成英語單詞，每行一個單詞，字典里沒有的外語單詞應該翻譯成“eh”，
輸入樣例
dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay
atcay
ittenkay
oopslay
輸出樣例
cat
eh
loops
（1）編程思路，
定義結構體陣列word來保存字典，
struct Dictionary
{
char e[15];
char s[15];
} word[100001];
其中，成員分量e保存英文單詞，s保存外語單詞，
將字典word按外語單詞升序排列，
之后，對于每個查找的外語單詞，采用二分法對陣列word進行查找，若查找成功，輸出對應的英語單詞，若不成功，輸出字串“eh”，
（2）源程式，
#include <stdio.h> #include <string.h> #include <algorithm> using namespace std; int n; struct Dictionary { char e[15]; char s[15]; }; struct Dictionary word[100001]; int cmp(struct Dictionary a,struct Dictionary b) { return strcmp(a.s,b.s)<0; } int judge(char *s) { int left=0,right=n-1; while (left<=right) { int mid=(left+right)/2; if (strcmp(word[mid].s,s)==0) return mid; else if (strcmp(word[mid].s,s)>0) right=mid-1; else left=mid+1; } return -1; } int main() { n=0; char c; char s[15]; while(scanf("%s%c",word[n].e,&c)!=EOF) { if(c=='\n') { strcpy(s,word[n].e); break; } scanf("%s",word[n].s); n++; } sort(word,word+n,cmp); int k=judge(s); if(k>=0) printf("%s\n",word[k].e); else printf("eh\n"); while(scanf("%s",s)!=EOF) { k=judge(s); if (k>=0) printf("%s\n",word[k].e); else printf("eh\n"); } return 0; }
將此源程式提交給北大OJ題庫 POJ 2503 Babelfish（http://poj.org/problem?id=2503）可以Accepted，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/442859.html
標籤：其他