2025年CCF全国青少年信息学奥林匹克联赛 CCF NOIP 2025

CCF全国青少年信息学奥林匹克联赛 CCF NOIP 2025 时间：2025年11月29日08：30~13：00 题目名称 糖果店 清仓甩卖 树的价值 序列询问 题目类型 传统型 传统型 传统型 传统型 目录 candy sale tree query 可执行文件名 candy sale tree query 输入文件名 candy.in sale.in tree.in query.in 输出文件名 candy.out sale.out tree.out query.out 每个测试点时限 1.0秒 1.0秒 2.0秒 2.0秒 内存限制 512 MiB 512 MiB 512 MiB 512 MiB 测试点数目 20 25 25 20 测试点是否等分 是 是 是 是 提交源程序文件名 对于C++语言 candy.cpp sale.cpp tree.cpp query.cpp 编译选项 对于C++语言 -02 -std=c++14 -static 注意事项（请仔细阅读） 1.文件名（程序名和输入输出文件名）必须使用英文小写。 2.main函数的返回值类型必须是int,程序正常结束时的返回值必须是0。 3.若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末换行）。 4.选手提交的程序源文件大小不得超过100KB。 5.提交的程序源文件的放置位置请参考各省的具体要求。 6.程序可使用的栈空间内存限制与题目的内存限制一致。 7.禁止在源代码中改变编译器参数（如使用pragma命令)，禁止使用系统结构相 关指令（如内联汇编）或其他可能造成不公平的方法。 8.因违反上述规定而出现的问题，申诉时一律不予受理。 9.只提供Linux格式附加样例文件。 10.全国统一评测时采用的机器配置为：Intel Core Ultra9285KCPU@3.70GHz (关闭睿频与能效核)，内存96GB。上述时限以此配置为准。 11.评测在当前最新公布的NOI Linux下进行，各语言的编译器版本以此为准。 第页共页 CCP全国青少年信息学奥林匹克联赛CCF NOIP2025 糖果店(candy) 糖果店(candy) 【题目描述】 小X开了一家糖果店，售卖种糖果，每种糖果均有无限颗。对于不同种类的糖 果，小X采用了不同的促销策略。具体地，对于第i(1≤i≤)种糖果，购买第一颗 的价格为x:元，第二颗为：元，第三颗又变回x:元，第四颗则为y:元，以此类推。 小R带了m元钱买糖果。小R不关心糖果的种类，只想得到数量尽可能多的糖 果。你需要帮助小R求出，m元钱能购买的糖果数量的最大值。 【输入格式】 从文件candy.in中读入数据。 输入的第一行包含两个正整数n,m,代表糖果的种类数和小R的钱数。 输入的第i+1(1≤i≤n)行包含两个正整数x,y,分别表示购买第i种糖果时第 奇数颗的价格和第偶数颗的价格。 【输出格式】 输出到文件candy.out中。 输出一行一个非负整数，表示m元钱能购买的糖果数量的最大值。 【样例1输入】 1 210 2 41 3 33 【样例1输出】 【样例1解释】 小R可以购买4颗第一种糖果，共花费4+1+4+1=10元。 第页共页 CCP全国青少年信息学奥林匹克联赛CCF NOIP2025 糖果店(candy) 【样例2输入】 1 315 217 3 23 31 【样例2输出】 小R可以购买1颗第一种糖果、1颗第二种糖果与6颗第三种糖果，共花费1+ 2+12=15元。 【样例3】 见选手目录下的candy,/candy3.in与candy,/candy3.ans。 该样例满足测试点6的约束条件。 【样例4】 见选手目录下的candy/candy.4.im与candy/candy4.ans。 该样例满足测试点8,9的约束条件。 【样例5】 见选手目录下的candy,/candy5.im与candy,/candy5.ans。 该样例满足测试点11,12的约束条件。 【样例6】 见选手目录下的candy/candy6.im与candy,/candy6.ans。 该样例满足测试点13的约束条件。 【样例7】 见选手目录下的candy,/candy'7.in与candy/candy7.ans。 该样例满足测试点17,18的约束条件。 第页共页 CCP全国青少年信息学奥林匹克联赛CCF NOIP2025 糖果店(candy) 【数据范围】 对于所有测试数据，均有： ·1≤n≤105； ·1≤m≤1018： 。对于所有1≤i≤n,均有1≤xi,班≤10°。 测试点编号 n≤ m≤ 特殊性质 1 1 10 2,3 2 无 20 4,5 10 6 A 7 102 102 B 8,9 无 10 A 11,12 103 104 B 13 无 14 A 15,16 109 B 105 17,18 无 19,20 1018 特殊性质A:对于所有1≤i≤n,均有=y。 特殊性质B:对于所有1≤i≤n,均有x:≥ 第页共页 CCP全国青少年信息学奥林匹克联赛CCF NOIP2025 清仓甩卖(sale) 清仓甩卖(sale) 【题目描述】 小X的糖果促销策略很成功，现在糖果店只剩下了n颗糖果，其中第i(1≤i≤n) 颗糖果的原价为α，元。小X计划将它们全部重新定价，清仓甩卖。具体地，小X会 将每颗糖果的清仓价格分别定为1元或2元。设第i(1≤i≤n)颗糖果的清仓价格为 ∈{1,2}元，则它的性价比被定义为原价与清仓价格的比值，即。 小R又带了m元钱买糖果。这一次，小R希望他购买到的糖果的原价总和最大， 于是他采用了以下购买策略：将所有糖果按照性价比从大到小排序，然后依次考虑每一 颗糖果。具体地，若小R在考虑第i(1≤i≤n)颗糖果时剩余的钱至少为w;元，则他 会购买这颗糖果，否则他会跳过这颗糖果，继续考虑下一颗。特别地，若存在两颗糖果 的性价比相同，则小R会先考虑原价较高的糖果；若存在两颗糖果的性价比与原价均 相同，则小R会先考虑编号较小的糖果。 例如，若小X的糖果商店剩余3颗糖果，原价分别为a1=1,2=3,a3=5,而 清仓价格分别为w1=2=1,3=2,则性价比分别为1,3，多。因此小R会先考虑第 2颗糖果，然后考虑第3颗糖果，最后考虑第1颗糖果。 小R想知道，在小X的所有2m种定价方案中，有多少种定价方案使得他按照上述 购买策略能购买到的糖果的原价总和最大。你需要帮助小R求出满足要求的定价方案 的数量。由于答案可能较大，你只需要求出答案对998,244,353取模后的结果。 【输入格式】 从文件sale.in中读入数据。 本题包含多组测试数据。 输入的第一行包含两个非负整数C,t,分别表示测试点编号与测试数据组数。c=0 表示该测试点为样例。 接下来依次输入每组测试数据，对于每组测试数据： ·第一行包含两个正整数n,m,分别表示糖果的数量与小R的钱数。 ·第二行包含n个正整数1，a2,.·,an,分别表示每颗糖果的原价。 【输出格式】 输出到文件sale.out中。 对于每组测试数据，输出一行一个非负整数，表示使得小R购买到的糖果的原价 总和达到最大值的定价方案数对998,244,353取模后的结果。 【样例1输入】 第页共页 CCP全国青少年信息学奥林匹克联赛CCF NOIP2025 清仓甩卖(sale) 1 01 2 32 3 135 【样例1输出】 【样例1解释】 该样例即为【题目描述】中的例子。共有以下6种定价方案使得小R购买到的糖 果原价总和最大，分别为： ·2w1=w2=w3=1,小R购买到的糖果原价总和为8； ·w1=w3=1,w2=2,小R购买到的糖果原价总和为6： ·w1=1,w2=3=2,小R购买到的糖果原价总和为5： ·w2=w3=1,w1=2,小R购买到的糖果原价总和为8： ·w3=1,w1=w2=2,小R购买到的糖果原价总和为5： ·w1=w2=w3=2,小R购买到的糖果原价总和为5。 注意：若1=w2=1,w3=2,则小R会依次购买第2颗和第1颗糖果，原价总 和为4，但小R可以只购买第3颗糖果，原价总和为5。因此该定价方案无法使小R购 买到的糖果的原价总和达到最大值。 【样例2】 见选手目录下的sale/sale2.im与sale/sale2.ans。 该样例满足测试点1~3的约束条件。 【样例3】 见选手目录下的sale/sale3.in与sale/sale3.ans。 该样例满足测试点4,5的约束条件。 【样例4】 见选手目录下的sale/sale4.im与sale/sale4.ans。 该样例满足测试点7~9的约束条件。 第页共页 CCP全国青少年信息学奥林匹克联赛CCF NOIP2025 清仓甩卖(sale) 【样例5】 见选手目录下的sale/sale5.im与sale/sale5.ans。 该样例满足测试点10~12的约束条件。 【样例6】 见选手目录下的sale/sale6.im与sale/sale6.ans。 该样例满足测试点13的约束条件。 【样例7】 见选手目录下的sale/sale7.im与sale/sale7.ans。 该样例满足测试点14,15的约束条件。 【样例8】 见选手目录下的sale/sale8.in与sale/sale8.ans。 该样例满足测试点17的约束条件。 【样例9】 见选手目录下的sale/sale9.im与sale/sale9.ams。 该样例满足测试点19,20的约束条件。 【样例10】 见选手目录下的sale/sale10.im与sale/sale10.ans。 该样例满足测试点2123的约束条件。 【样例11】 见选手目录下的sale/sale11.im与sale/sale11.ams。 该样例满足测试点24,25的约束条件。 【数据范围】 设N为单个测试点内所有测试数据的的和。对于所有测试数据，均有： ·1≤t≤5×104： ·1≤n≤5,000，N≤5×104,1≤m≤2m-1: ·对于所有1≤i≤n,均有1≤a;≤109。 第页共页 CCP全国青少年信息学奥林匹克联赛CCF NOIP2025 清仓甩卖(sale) 测试点编号 n≤ N≤ m 特殊性质 1~3 5 4,5 10 ≤2m-1 无 6 40 5,000 7~9 =2 10~12 300 B ≤2m-1 13 14,15 =2 无 16 =2m-1 17 =2m-2 103 104 18 A 19,20 B ≤2m-1 21~23 无 24,25 5,000 5×104 特殊性质A:a1=a2=··=an 特殊性质B:对于所有1≤i≤n,均有a;>5×10。 第页共页 CCP全国青少年信息学奥林匹克联赛CCF NOIP2025 树的价值(tee) 树的价值（tree) 【题目描述】 给定一棵n个结点的有根树，其中结点1为根，结点i(2≤i≤n)的父亲结点为 结点P 对于1≤i≤n,定义结点i的深度d山：为结点1到结点i的简单路径的边数，也就 是说，d山1=0，d:=dp+1(2≤i≤n)。定义有根树的高度h为所有结点的深度的最大 值，即h=max1d。 给定高度的上界m。在本题中，给定的有根树的高度不超过m。 你需要给每个结点设置一个非负整数作为它的权值。对于1≤i≤，若结点i的权 值为，令S,表示结点i的子树中结点权值构成的集合。对于每一种权值设置方案，定 义树的价值为∑mex(S),其中mex(S)表示不在集合S中的最小非负整数。例如，在 下图中，若设置a1=3,a2=2,ag=a4=0,a5=1,则S1={0,1,2,3},S2={0,1,2, S3={0},S4={0},S5={1},树的价值为4+3+1+1+0=9。 3 你需要求出，在所有权值设置方案中，树的价值的最大值。 【输入格式】 从文件tree.in中读入数据。 本题包含多组测试数据。 输入的第一行包含一个正整数，表示测试数据组数。 接下来依次输入每组测试数据，对于每组测试数据： ·第一行包含两个正整数n,m,分别表示结点数量与高度的上界。 ·第二行包含n-1个正整数p2,P仍，·，Pn,分别表示每个结点的父亲结点。 【输出格式】 输出到文件tree.out中。 第页共页 CCP全国青少年信息学奥林匹克联赛CCF NOIP2025 树的价值(tee) 对于每组测试数据，输出一行一个非负整数，表示树的价值的最大值。 【样例1输入】 1 2 52 31122 4 72 112223 【样例1输出】 9 13 【样例1解释】 该样例共包含两组测试数据。 对于第一组测试数据，可以设置a1=3,a2=2,a3=a4=0,a5=1,则树的价值 为4+3+1+1+0=9。 对于第二组测试数据，可以设置a1=4,a2=3,a4=2,ag=a6=1,a5=a7=0, 则树的价值为5+4+2+0+1+0+1=13。 【样例2】 见选手目录下的tree/tree2.im与tree/tree2.ams。 该样例满足测试点3,4的约束条件。 【样例3】 见选手目录下的tree/tree3.im与tree/tree3.ans。 该样例满足测试点7,8的约束条件。 【样例4】 见选手目录下的tree/tree4.im与tree/tree4.ans。 该样例满足测试点13,14的约束条件。 第页共页