CCF NOIP 2024 真题

CCF全国青少年信息学奥林匹克联赛 CCF NOIP 2024 时间：2024年11月30日08:30!13:00 题目名称 编辑字符串 遗失的赋值 树的遍历 树上查询 题目类型 传统型 传统型 传统型 传统型 目录 edit assign traverse query 可执行文件名 edit assign traverse query 输入文件名 edit.in assign.in traverse.inquery.in 输出文件名 edit.out assign.out traverse.outquery.out 每个测试点时限 1.0秒 1.0秒 1.0秒 2.0秒 内存限制 512 MiB 512 MiB 512 MiB 1024 MiB 测试点数目 20 20 25 25 测试点是否等分 是 是 是 是 交源程序文件名 对于C++语言 edit.cpp assign.cpp traverse.cppquery.cpp 编译选项 对于C++语言 ‐O2 ‐std=c++14 ‐static . 注 . 意 . 事 . 项（ . 请 . 仔 . 细 . 阅 . 读） 1.文件名（程序名和输入输出文件名）必须使用英文小写。 2.main函数的返回值类型必须是 int，程序正常结束时的返回值必须是 0。 3.交的程序代码文件的放置位置请参考各省的具体要求。 4.因违反以上三点而出现的错误或问题，申诉时一律不予受理。 5.若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。 6.选手交的程序源文件必须不大于 100KB。 7.程序可使用的栈空间内存限制与题目的内存限制一致。 8.全国统一评测时采用的机器配置为： Intel(R) Core(TM) i7-8700K CPU @3.70GHz， 内存32GB。上述时限以此配置为准。 9.只供Linux格式附加样例文件。 10.评测在当前最新公布的 NOI Linux下进行，各语言的编译器版本以此为准。 CCF全国青少年信息学奥林匹克联赛 CCF NOIP 2024 编辑字符串（ edit） 编辑字符串（ edit） 【题目描述】 小M有两个长度为 n且字符集为 {0,1}的字符串 s1,s2。 小M希望两个字符串中对应位置字符相同的出现次数尽可能多，即满足 s1,i=s2,i 的i(1"i"n)尽可能多。为此小 M有一个字符串编辑工具，这个工具供的基本操 作是在一个字符串中交换两个 . 相 . 邻的字符。为了保持字符串的可辨识性，规定两个字符 串中的部分字符不能参与交换。小 M可以用工具对 s1或s2进行多次字符交换，其中 可以参与交换的字符能够交换任意多次。 现在小M想知道，在使用编辑工具后，两个字符串中对应位置字符相同的出现次 数最多能有多少。 【输入格式】 从文件edit.in中读入数据。 . 本 . 题 . 包 . 含 . 多 . 组 . 测 . 试 . 数 . 据。 输入的第一行包含一个整数 T，表示测试数据的组数。 接下来包含 T组数据，每组数据的格式如下： •第一行包