资源简介

2025全国青少年信息学奥林匹克竞赛
2025.11.29
第一题糖果店/candy
题目描述
小X开了一家糖果店，售卖种糖果，每种糖果均有无限颗。对于不同种类的糖果，小X采用了不同
的促销策略。具体地，对于第i(1≤i≤)种糖果，购买第一颗的价格为x;元，第二颗为班元，第
三颗又变回c:元，第四颗则为斯元，以此类推。
小R带了m元钱买糖果。小R不关心糖果的种类，只想到得到数量尽可能多的糖果。你需要帮助小R
求出，m元钱能购买的糖果数量的最大值。
输入格式
输入的第一行包含两个正整数n,m,代表糖果的种类数和小R的钱数。
输入的第i+1(1≤i≤n)行包含两个正整数x,,分别表示购买第i种糖果时第奇数颗的价格和
第偶数颗的价格。
输出格式
输出一行一个非负整数，表示m元钱能购买的糖果数星的最大值。
【数据范围】
对于所有测试数据，均有：
·1≤n≤105：
·1≤m<1018:
·对于所有1≤i≤n,均有1≤x,班≤10°。
测试点编号
n<
m≤
特殊性质
1
1
10
2,3
2
20
4,5
10
6
A
102
102
B
8,9
无
10
A
11.12
103
103
8
13
无
14
9
15.16
109
105
17.18
无
19,20
1018
特殊性质A:对于所有1≤i≤n,均有：一i。
特殊性质B:对于所有1≤i≤n,均有x:之i。
第二题清仓甩卖/sale
小X的糖果促销策略很成功，现在糖果店只剩下了n颗糖果，其中第i(1≤i≤)颗糖果的原价为a:
元。小X计划将它们全部重新定价，清仓甩卖。具体地，小X会将每颗糖果的清仓价格分别定为1元或
2元。设第i(1≤i≤)颗糖果的清仓价格为：∈{1,2}元，则它的性价比被定义为原价与清仓价
格的比值，即票
小R又带了m元钱买糖果。这一次，小R希望他购买到的糖果的原价总和最大，于是他采用了以下购
买策略：将所有糖果按照性价比从大到小排序，然后依次考虑每一颗糖果。具体地，若小R在考虑第(
1≤i≤)颗糖果时剩余的钱至少为心：元，则他会购买这颗糖果；否则他会跳过这颗糖果，继续考虑
下一颗。特别地，若存在两颗糖果的性价比相同，则小R会先考虑原价较高的糖果；若存在两颗糖果的
性价比与原价均相同，则小R会先考虑编号较小的糖果。
例如，若小X的糖果商店剩余3颗糖果，原价分别为a1=1,a2=3,a3=5,而清仓价格分别为
w1=心2=1，D3=2,则性价比分别为1,3，号。因此小R会先考虑第2颗糖果，然后考虑第3颗
糖果，最后考虑第1颗糖果。
小想知道，在小X的所有2”种定价方案中，有多少种定价方案使得他按照上述购买策略能购买到的
糖果的原价总和最大。你需要帮助小R求出满足要求的定价方案的数量。由于答案可能较大，你只需要
求出答案对998,244,353取模后的结果。
输入格式
本题包含多组测试数据。
输入的第一行包含两个非负整数℃，t,分别表示测试点编号与测试数据组数。c一0表示该测试点为样
例。
接下来依次输入每组测试数据，对于每组测试数据：
·第一行包含两个正整数n,m,分别表示糖果的数量与小R的钱数：
·第二行包含n个正整数a1,a2,.·,an,分别表示每颗糖果的原价。
输出格式
对于每组测试数据，输出一行一个非负整数，表示使得小购买到的糖果的原价总和达到最大值的定价
方案数对998.244.353取模后的结果。
【数据范围】
设N为单个测试点内所有测试数据的的和。对于所有测试数据，均有：
·1≤t≤5×104：
·1≤n≤5,000，N≤5×104,1≤m≤2n-1:
·对于所有1≤i≤n,均有1≤a≤10°.

展开更多......

收起↑