P6040 「ACOI2020」课后期末考试滑溜滑溜补习班题目背景潮田 渚Shiota Nagisa因为理科不大好自然会被仔细观察学生的杀老师发现于是渚同学只得加入杀老师举办的课后期末考试滑溜滑溜补习班。至于为什么叫这个名字额你不能问我啊。题目描述在补习班上因为多个学生会同时有需求所以杀老师会制造分身用音速移动来回回答问题。补习班上有nnn个同学他们每一个人都有一个问题。杀老师为了有序回答学生的问题把所有学生排成了一列。第iii个学生的问题有一个困难值aia_iai杀老师回答第iii个学生的问题需要花费aia_iai的精力。杀老师到了哪里它就要解决那个学生的问题。杀老师最开始会解决序列中第一个同学的问题他最后会去解决最后一个同学的问题。杀老师每次解决完一个同学的问题到下一个同学的座位上就要花费kkk点精力值。特殊的如果杀老师想让自己轻松一点可以不移动到下一个可以直接到下两个下三个就不用解决跳过的同学的问题了。对应的它会被学生调侃。受到打击的杀老师自然会花费格外的精力花费的精力为k(q−p−1)×dk(q-p-1) \times dk(q−p−1)×d当前位置为ppp跳到的位置为qqq。当然的杀老师也是有速度的啊并且它想解决学生的一些问题所以说杀老师最多只会跳过x−1x-1x−1个学生去解决下xxx个学生的问题。输入格式第一行五个整数n,k,d,x,tpn,k,d,x,tpn,k,d,x,tp表示有nnn个学生只按顺序去到下一个学生的座位需要花费kkk点精力每多跳过一个学生就要多花费ddd点精力值每一次最多只能跳过x−1x-1x−1个学生是否是特殊数据。tp0tp0tp0第二行nnn个整数a1…na_{1\dots n}a1…naia_iai表示第iii个学生的问题的困难值为aia_iai。tp1tp1tp1第二行一个整数SeedSeedSeed作为种子然后调用rndrndrnd函数依次生成nnn个整数作为aaa数组aia_iai表示第iii个学生的问题的困难值为aia_iai。inlineintrnd(){staticconstintMOD1e9;returnSeed(1LL*Seed*0x66CCFF%MOD20120712)%MOD;}输出格式一行一个整数表示杀老师解决完最后一个同学的问题最少需要花费多少精力。输入输出样例 #1输入 #15 3 4 1 0 1 2 3 4 5输出 #127输入输出样例 #2输入 #210 30630 56910 2 0 7484 99194 86969 17540 29184 68691 91892 81564 93999 74280输出 #2717318输入输出样例 #3输入 #310000000 899999999 923456655 213111 1 1314520输出 #39231813656566921说明/提示样例解释 #1杀老师每次不能跳过学生因此他必须依次移动并解决所有问题故答案为解决问题所需的精力123451512345151234515与移动所需的精力4×3124 \times 3124×312所以花费精力之和为272727。数据范围本题采用捆绑测试。Subtask 120 points学生们学习认真听话留下来的同学也会更少tp0tp0tp0n≤103n \leq 10^3n≤103。Subtask 230 points杀老师的速度快极了并且学生们没时间吐槽它tp0tp0tp0n≤106n \leq 10^6n≤106。Subtask 350 pointstp1tp1tp1其余无特殊限制。对于100%100\%100%的数据1≤n≤1071 \leq n \leq 10^71≤n≤1070≤k,d,ai≤1090 \leq k,d,a_i \leq 10^90≤k,d,ai≤1091≤x≤n−11 \leq x \leq n-11≤x≤n−1。提示对于tp1tp1tp1的数据rndrndrnd函数只用于减小输入量标准算法不依赖该数据生成方式。.C实现#includeiostream#includedeque//deque的头文件#includecstdio#define_for(i,a,b)for(inti(a);i(b);i)usingnamespacestd;typedeflonglongLL;constintMAXN1e710;intn,tp,x;LL a[MAXN],k,d,Seed,f[MAXN];dequeintq;inlineintrnd(){staticconstintMOD1e9;returnSeed(1LL*Seed*0x66CCFF%MOD20120712)%MOD;}//数据生成函数intmain(){cinnkdxtp;if(tp0){_for(i,1,n)scanf(%lld,a[i]);}else{scanf(%lld,Seed);_for(i,1,n)a[i]rnd();}f[1]a[1];q.push_back(1);//初始化莫忘掉_for(i,2,n){while(!q.empty()i-q.front()x)q.pop_front();//第1步“过期的弹出f[i]f[q.front()]a[i]k(i-q.front()-1)*d;//第2步更新f[i]while(!q.empty()f[i]-i*df[q.back()]-q.back()*d)q.pop_back();//第3步较大的弹出q.push_back(i);//第4步入队}printf(%lld\n,f[n]);return0;//完结撒花}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（2979）用C++实现信奥题 P6040 「ACOI2020」课后期末考试滑溜滑溜补习班
发布时间：2026/7/8 20:13:05
P6040 「ACOI2020」课后期末考试滑溜滑溜补习班题目背景潮田 渚Shiota Nagisa因为理科不大好自然会被仔细观察学生的杀老师发现于是渚同学只得加入杀老师举办的课后期末考试滑溜滑溜补习班。至于为什么叫这个名字额你不能问我啊。题目描述在补习班上因为多个学生会同时有需求所以杀老师会制造分身用音速移动来回回答问题。补习班上有nnn个同学他们每一个人都有一个问题。杀老师为了有序回答学生的问题把所有学生排成了一列。第iii个学生的问题有一个困难值aia_iai杀老师回答第iii个学生的问题需要花费aia_iai的精力。杀老师到了哪里它就要解决那个学生的问题。杀老师最开始会解决序列中第一个同学的问题他最后会去解决最后一个同学的问题。杀老师每次解决完一个同学的问题到下一个同学的座位上就要花费kkk点精力值。特殊的如果杀老师想让自己轻松一点可以不移动到下一个可以直接到下两个下三个就不用解决跳过的同学的问题了。对应的它会被学生调侃。受到打击的杀老师自然会花费格外的精力花费的精力为k(q−p−1)×dk(q-p-1) \times dk(q−p−1)×d当前位置为ppp跳到的位置为qqq。当然的杀老师也是有速度的啊并且它想解决学生的一些问题所以说杀老师最多只会跳过x−1x-1x−1个学生去解决下xxx个学生的问题。输入格式第一行五个整数n,k,d,x,tpn,k,d,x,tpn,k,d,x,tp表示有nnn个学生只按顺序去到下一个学生的座位需要花费kkk点精力每多跳过一个学生就要多花费ddd点精力值每一次最多只能跳过x−1x-1x−1个学生是否是特殊数据。tp0tp0tp0第二行nnn个整数a1…na_{1\dots n}a1…naia_iai表示第iii个学生的问题的困难值为aia_iai。tp1tp1tp1第二行一个整数SeedSeedSeed作为种子然后调用rndrndrnd函数依次生成nnn个整数作为aaa数组aia_iai表示第iii个学生的问题的困难值为aia_iai。inlineintrnd(){staticconstintMOD1e9;returnSeed(1LL*Seed*0x66CCFF%MOD20120712)%MOD;}输出格式一行一个整数表示杀老师解决完最后一个同学的问题最少需要花费多少精力。输入输出样例 #1输入 #15 3 4 1 0 1 2 3 4 5输出 #127输入输出样例 #2输入 #210 30630 56910 2 0 7484 99194 86969 17540 29184 68691 91892 81564 93999 74280输出 #2717318输入输出样例 #3输入 #310000000 899999999 923456655 213111 1 1314520输出 #39231813656566921说明/提示样例解释 #1杀老师每次不能跳过学生因此他必须依次移动并解决所有问题故答案为解决问题所需的精力123451512345151234515与移动所需的精力4×3124 \times 3124×312所以花费精力之和为272727。数据范围本题采用捆绑测试。Subtask 120 points学生们学习认真听话留下来的同学也会更少tp0tp0tp0n≤103n \leq 10^3n≤103。Subtask 230 points杀老师的速度快极了并且学生们没时间吐槽它tp0tp0tp0n≤106n \leq 10^6n≤106。Subtask 350 pointstp1tp1tp1其余无特殊限制。对于100%100\%100%的数据1≤n≤1071 \leq n \leq 10^71≤n≤1070≤k,d,ai≤1090 \leq k,d,a_i \leq 10^90≤k,d,ai≤1091≤x≤n−11 \leq x \leq n-11≤x≤n−1。提示对于tp1tp1tp1的数据rndrndrnd函数只用于减小输入量标准算法不依赖该数据生成方式。.C实现#includeiostream#includedeque//deque的头文件#includecstdio#define_for(i,a,b)for(inti(a);i(b);i)usingnamespacestd;typedeflonglongLL;constintMAXN1e710;intn,tp,x;LL a[MAXN],k,d,Seed,f[MAXN];dequeintq;inlineintrnd(){staticconstintMOD1e9;returnSeed(1LL*Seed*0x66CCFF%MOD20120712)%MOD;}//数据生成函数intmain(){cinnkdxtp;if(tp0){_for(i,1,n)scanf(%lld,a[i]);}else{scanf(%lld,Seed);_for(i,1,n)a[i]rnd();}f[1]a[1];q.push_back(1);//初始化莫忘掉_for(i,2,n){while(!q.empty()i-q.front()x)q.pop_front();//第1步“过期的弹出f[i]f[q.front()]a[i]k(i-q.front()-1)*d;//第2步更新f[i]while(!q.empty()f[i]-i*df[q.back()]-q.back()*d)q.pop_back();//第3步较大的弹出q.push_back(i);//第4步入队}printf(%lld\n,f[n]);return0;//完结撒花}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
