P9184 [USACO23OPEN] Moo Language B题目描述题目背景FJ 对与奶牛更好地互动感兴趣所以他决定学习 moo 语言moo 语言与英语相似但更为简单。单词只有四种类型名词、及物动词、不及物动词和连词每两个单词之间必须用空格隔开。标点符号仅包含逗号和句号它会跟在单词后面若该标点符号后面存在单词则需要隔一个空格再放单词。对于每个句子都需要遵循以下格式中的一条名词不及物动词。名词及物动词名词可以有多个。及物动词后面必须有至少一个名词。除及物动词后面的第一个名词外后面的每个名词前面都必须加一个逗号。也可以在两个句子之间加一个连词形成复合句复合句不能与其他句子用连词连接。每一个句子包括复合句都必须以句号结尾。FJ 的词库中有N NN个单词、C CC个逗号和P PP个句号。每个单词的使用次数不能超过这个单词在词库中出现的次数。现在你要帮他输出几个符合以上要求的句子使总单词数尽量多。每个输入文件中共包含T TT组样例。输入格式第一行输入T TT表示样例组数。对于每组样例格式如下第一行输入三个正整数N NN、C CC和P PP。在接下来的N NN行每行输入两个字符串。第一个字符串输入一个 FJ 可以用的单词全为小写字母长度为1 11至10 1010第二个字符串为以下字符串中的任意一个表示该单词的类型noun名词transitive-verb及物动词intransitive-verb不及物动词conjunction连词。同一个单词可能在词库中出现多次但是每次出现时它们的类型都相同。输出格式第一行输出组成符合以上要求的句子序列的最大单词数。在第二行中输出句子序列使单词数最多。本题开启 SPJ任何符合以上要求的句子序列均可通过。请不要输出多余的空格尤其是在每行末尾。输入输出样例 #1输入 #13 1 1 1 bessie noun 10 5 4 bessie noun taught transitive-verb flew intransitive-verb elsie noun farmer noun john noun and conjunction and conjunction nhoj noun mooed intransitive-verb 24 5 4 but conjunction bessie noun taught transitive-verb flew intransitive-verb elsie noun farmer noun john noun and conjunction and conjunction nhoj noun mooed intransitive-verb bob noun impressed transitive-verb cow noun impressed transitive-verb leaped intransitive-verb elsie noun bella noun buttercup noun pushed transitive-verb mooed intransitive-verb envy noun john noun nhoj noun输出 #10 9 nhoj mooed. farmer taught elsie, bessie and john flew. 23 nhoj mooed. nhoj impressed john, farmer, elsie, bessie and cow impressed bob. bella pushed elsie and buttercup flew. envy mooed but john leaped.说明/提示1 ≤ T ≤ 100 1 \leq T \leq 1001≤T≤1001 ≤ P , C ≤ N ≤ 10 3 1 \leq P, C \leq N \leq 10^31≤P,C≤N≤103。输入 2-6N ≤ 10 N \leq 10N≤10。输入 7-11N ≤ 100 N \leq 100N≤100。输入 12-16N ≤ 1000 N \leq 1000N≤1000。输入编号除以 5 余 2 的测试点没有及物动词。输入编号除以 5 余 3 的测试点没有不及物动词。输入编号除以 5 余 4 的测试点没有连词。C实现#includeiostream#includevectorusingnamespacestd;constintkMaxN2001;intt,n,c,p,s,m,l;vectorstringw[5],a[kMaxN];// 0 名词1 连词2 及物动词 3 不及物动词intmain(){for(cint;t;t--){cinncp;fill(w,w4,w[4]),sml0;// 初始化for(inti1;in;i){string s1,s2;cins1s2;w[(s2[0]t||s2[0]i)*2(s2[0]c||s2[0]i)].push_back(s1);// 分类存放单词}pmin(p,(int)w[1].size());// 连词增加句子数量for(;w[0].size()w[3].size()mp;s2){// 使用不及物动词构造新句a[m]w[4];// 创建新句a[m].push_back(w[0].back()),w[0].pop_back();// 加入名词a[m].push_back(w[3].back()),w[3].pop_back();// 加入不及物动词}for(lm;w[0].size()2w[2].size()mp;s3){// 使用及物动词构造新句a[m]w[4];// 创建新句a[m].push_back(w[0].back()),w[0].pop_back();// 加入名词a[m].push_back(w[2].back()),w[2].pop_back();// 加入及物动词a[m].push_back(w[0].back()),w[0].pop_back();// 加入名词}for(;lw[0].size()w[2].size();l--,s){// 将不及物动词句改造成及物动词句a[l].pop_back();// 去掉不及物动词a[l].push_back(w[2].back()),w[2].pop_back();// 加入及物动词a[l].push_back(w[0].back()),w[0].pop_back();// 加入名词}for(;l!mw[0].size()c;c--,s){// 加入多余的名词和逗号a[m].push_back(w[0].back()),w[0].pop_back();// 加入名词}coutsmin(m/2,(int)w[1].size())\n;// 累加连词数量for(inti1;im;i){// 枚举句子for(intj0;ja[i].size();j){// 枚举单词cout(j2?,:)(j? :)a[i][j];// 输出单词判断是否需要输出逗号和空格}if(im){// 之后还有句子if(i%2w[1].size()){// 可以使用连词cout w[1].back() ;w[1].pop_back();}else{cout. ;}}}cout(s?.:)\n;}return0;}translated by liyuanchen2021后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
