2026/3/29 13:27:02
网站建设
项目流程
个人网站建设法律规定,wordpress更换域名图片不显示,wordpress ftp密码,网站建设和优欢迎大家订阅我的专栏#xff1a;算法题解#xff1a;C与Python实现#xff01; 本专栏旨在帮助大家从基础到进阶 #xff0c;逐步提升编程能力#xff0c;助力信息学竞赛备战#xff01;
专栏特色 1.经典算法练习#xff1a;根据信息学竞赛大纲#xff0c;精心挑选…欢迎大家订阅我的专栏算法题解C与Python实现本专栏旨在帮助大家从基础到进阶 逐步提升编程能力助力信息学竞赛备战专栏特色1.经典算法练习根据信息学竞赛大纲精心挑选经典算法题目提供清晰的代码实现与详细指导帮助您夯实算法基础。2.系统化学习路径按照算法类别和难度分级从基础到进阶循序渐进帮助您全面提升编程能力与算法思维。适合人群准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生希望系统学习C/Python编程的初学者想要提升算法与编程能力的编程爱好者附上汇总贴历年CSP-S复赛真题解析 | 汇总【题目来源】洛谷[P1311 NOIP 2011 提高组] 选择客栈 - 洛谷【题目描述】丽江河边有n nn家很有特色的客栈客栈按照其位置顺序从1 11到n nn编号。每家客栈都按照某一种色调进行装饰总共k kk种用整数0 ∼ k − 1 0 \sim k-10∼k−1表示且每家客栈都设有一家咖啡店每家咖啡店均有各自的最低消费。两位游客一起去丽江旅游他们喜欢相同的色调又想尝试两个不同的客栈因此决定分别住在色调相同的两家客栈中。晚上他们打算选择一家咖啡店喝咖啡要求咖啡店位于两人住的两家客栈之间包括他们住的客栈且咖啡店的最低消费不超过p pp。他们想知道总共有多少种选择住宿的方案保证晚上可以找到一家最低消费不超过p pp元的咖啡店小聚。【输入】共n 1 n1n1行。第一行三个整数n , k , p n, k, pn,k,p每两个整数之间用一个空格隔开分别表示客栈的个数色调的数目和能接受的最低消费的最高值接下来的n nn行第i 1 i1i1行两个整数之间用一个空格隔开分别表示 $i $ 号客栈的装饰色调a i a_iai和i ii号客栈的咖啡店的最低消费b i b_ibi。【输出】一个整数表示可选的住宿方案的总数。【输入样例】5 2 3 0 5 1 3 0 2 1 4 1 5【输出样例】3【算法标签】《洛谷 P1311 选择客栈》 #递推# #NOIP提高组# #2011#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 使用长整型防止溢出constintN200005;// 定义最大数组长度intn,k,p;// n:酒店数量, k:颜色种类, p:最大预算inta[N];// a[i]:第i个酒店的颜色intb[N];// b[i]:第i个酒店的费用intnum[55][N];// num[j][i]:前i个酒店中颜色为j的酒店数量intpos[N];// pos[i]:从i向前找第一个费用p的酒店位置intans;// 最终答案满足条件的方案数signedmain(){// 输入酒店数量、颜色种类和最大预算cinnkp;// 输入每个酒店的颜色和费用for(inti1;in;i){cina[i]b[i];// 计算前缀和统计每种颜色出现的次数for(intj0;jk;j){if(ja[i]){// 当前酒店颜色为j数量加1num[j][i]num[j][i-1]1;}else{// 其他颜色保持不变num[j][i]num[j][i-1];}}// 记录费用p的最近位置if(b[i]p){// 当前酒店费用p记录当前位置pos[i]i;}else{// 当前酒店费用p继承前一个位置pos[i]pos[i-1];}}// 统计满足条件的方案数for(inti2;in;i){// 找到从i向前第一个费用p的酒店位置inttpos[i];// 当前酒店的颜色intca[i];// 累加在位置t之前颜色与当前酒店相同的酒店数量ansnum[c][t];// 如果当前酒店本身费用p需要减去自身避免重复计算if(pos[i]i){ans--;}}// 输出最终答案coutansendl;return0;}【运行结果】5 2 3 0 5 1 3 0 2 1 4 1 5 3