NOIP+2023年全国青少年信息学奥林匹克联赛真题

CCF全国青少年信息学奥林匹克联赛 CCF NOIP 2023 时间：2023年11月18日08：30~13：00 题目名称 词典 三值逻辑 双序列拓展 天天爱打卡 题目类型 传统型 传统型 传统型 传统型 目录 dict tribool expand run 可执行文件名 dict tribool expand run 输入文件名 dict.in tribool.in expand.in run.in 输出文件名 dict.out tribool.out expand.out run.out 每个测试点时限 1.0秒 1.0秒 1.0秒 2.0秒 内存限制 512 MiB 512 MiB 512 MiB 512 MiB 测试点数目 10 10 20 25 测试点是否等分 是 是 是 是 提交源程序文件名 对于C++语言 dict.cpp tribool.cpp expand.cpp run.cpp 编译选项 对于C++语言 -02-std=c++14-static 注意事项（请仔细阅读） 1.文件名（程序名和输入输出文件名）必须使用英文小写。 2.C/C++中函数main(0的返回值类型必须是int,程序正常结束时的返回值必须 是0. 3.提交的程序代码文件的放置位置请参考各省的具体要求。 4.因违反以上三点而出现的错误或问题，申诉时一律不予受理。 5.若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。 6.选手提交的程序源文件必须不大于100KB。 7.程序可使用的栈空间内存限制与题目的内存限制一致。 8.全国统一评测时采用的机器配置为：Intel(R)Core(TM)i7-8700KCPU@3.70GHz, 内存32GB。上述时限以此配置为准。 9.只提供Linux格式附加样例文件。 10.评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以此为准。 CCF全国青少年信息学奥林匹克联赛CCF NOIP2023 词典(dict) 词典(dict) 【题目描述】 小S的词典里有n个两两不同的、长度均为m的单词1,2，·，n。每个单词 都是一个小写字母构成的字符串。 小S可以做以下操作任意多次（可以不做）：选择词典中的任意一个单词，交换其 中任意两个字符。 对于每个1≤i≤n,小S想知道，是否可以通过以上操作得到新的n个单词 w,w吃，·，wn,使得对于每个j卡i,的字典序比四都要小。对于n=1的情况，我 们约定：上述性质是自然成立的。 对于两个同样长度的字符串s=s152…sL和t=tt2…t红，称字符串s字典序小 于字符串t,当且仅当以下条件成立：存在位置，在第i个字符之前s和t都相同，而 且s<t,即小写字母s:在英文字母顺序中先于。 【输入格式】 从文件dict.n中读入数据。 输入的第一行包含两个正整数n和m,分别表示单词个数和单词长度。 接下来n行，每行包含一个长度为m的小写字母字符串，表示一个单词。 【输出格式】 输出到文件dict.out中。 输出一行，其中包含一个长度为n的01字符串a:对于1≤i≤n,如果题目描述 中的性质成立，则a:=1,否则a4=0。 【样例1输入】 1 47 2 abandon 3 bananaa 4 baannaa 5 notnotn 【样例1输出】 1110 第2页共12页 CCF全国青少年信息学奥林匹克联赛CCF NOIP2023 词典(dict) 【样例1解释】 ·不做任何操作，第一个单词字典序最小，因此输出第一个字符为1； ·交换bananaa的前两个字符以及abandon的第三个和第六个字符，得到abondan, abnanaa,baannaa,notnotn,此时第二个单词字典序最小，因此输出第二个字 符为1： ·交换baannaa的第一个和最后一个字符得到aaannab,其余字符串不变，此时 第三个单词字典序最小，因此输出第三个字符为1： ·无论如何操作，第四个单词不会小于第二个单词，因此输出第四个字符为日。 【样例2】 见选手目录下的dict/dict2.in与dict/dict2.ans。 该组样例满足测试点4的限制。 【样例3】 见选手目录下的dict/dict3.n与dict/dict3.ans。 该组样例满足测试点7的限制。 【样例4】 见选手目录下的dict/dict4.in与dict/dict4.ans。 该组样例满足测试点10的限制。 【数据范围】 对于所有测试数据，保证：1≤n≤3,000,1≤m≤3,000，：为长度为m的小写 字母字符串且两两不同。 测试点编号 n≤ m≤ 1 1 1 2~4 26 57 15 2 8 300 300 9 103 103 10 3,000 3,000 第3页 共12页 CCF全国青少年