网站前台模板 html常州建设安全员报名网站
张小明 2026/1/12 2:10:41
网站前台模板 html,常州建设安全员报名网站,企业管理公司介绍,在线平面图制作欢迎大家订阅我的专栏#xff1a;算法题解#xff1a;C与Python实现#xff01; 本专栏旨在帮助大家从基础到进阶 #xff0c;逐步提升编程能力#xff0c;助力信息学竞赛备战#xff01;
专栏特色 1.经典算法练习#xff1a;根据信息学竞赛大纲#xff0c;精心挑选…欢迎大家订阅我的专栏算法题解C与Python实现本专栏旨在帮助大家从基础到进阶 逐步提升编程能力助力信息学竞赛备战专栏特色1.经典算法练习根据信息学竞赛大纲精心挑选经典算法题目提供清晰的代码实现与详细指导帮助您夯实算法基础。2.系统化学习路径按照算法类别和难度分级从基础到进阶循序渐进帮助您全面提升编程能力与算法思维。适合人群准备参加蓝桥杯、GESP、CSP-J、CSP-S等信息学竞赛的学生希望系统学习C/Python编程的初学者想要提升算法与编程能力的编程爱好者附上汇总帖GESP认证C编程真题解析 | 汇总【题目来源】洛谷[B3874 GESP202309 六级] 小杨的握手问题 - 洛谷【题目描述】小杨的班级里共有N NN名同学学号从0 00至N − 1 N-1N−1。某节课上老师安排全班同学进行一次握手游戏具体规则如下老师安排了一个顺序让全班N NN名同学依次进入教室。每位同学进入教室时需要和已经在教室内且学号小于自己的同学握手。现在小杨想知道整个班级总共会进行多少次握手。提示可以考虑使用归并排序进行降序排序并在此过程中求解。【输入】输入包含2 22行。第一行一个整数N NN表示同学的个数第二行N NN个用单个空格隔开的整数依次描述同学们进入教室的顺序每个整数在0 ∼ N − 1 0 \sim N-10∼N−1之间表示该同学的学号。保证每位同学会且只会进入教室一次。【输出】输出一行一个整数表示全班握手的总次数。【输入样例】4 2 1 3 0【输出样例】2【算法标签】《洛谷 B3874 小杨的握手问题》 #树状数组# #递归# #排序# #GESP# #2023#【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglongconstintN300005;// 树状数组大小要大于最大可能的值intn;// 数组长度intans;// 逆序对总数inttr[N];// 树状数组/** * 计算lowbit返回x的二进制表示中最低位的1所对应的值 * 例如lowbit(6)2因为6的二进制是110最低位的1表示2 * param x 输入数字 * return lowbit值 */intlowbit(intx){returnx-x;// 利用补码性质x -x}/** * 树状数组更新操作 * 在位置x上增加c * param x 更新位置 * param c 增加的值 */voidadd(intx,intc){// 从x开始沿lowbit路径向上更新所有包含x的区间for(intix;iN;ilowbit(i)){tr[i]c;}}/** * 树状数组查询操作 * 查询前缀和[1, x] * param x 查询位置 * return 前缀和 */intquery(intx){intres0;// 从x开始沿lowbit路径向下累加for(intix;i;i-lowbit(i)){restr[i];}returnres;}signedmain()// 因为使用了#define int long long{// 输入数组长度cinn;// 从后向前遍历数组for(intin;i1;i--){intx;cinx;x;// 将数值从0-based转为1-based避免树状数组处理0// 查询在当前位置之前在原始顺序中有多少个比x小的数// 因为是从后向前遍历所以query(x)返回的是已经处理过的数中小于等于x的数量// 但我们需要的是严格小于x的数量所以这里有问题ansquery(x);// 将当前数加入树状数组add(x,1);}// 输出逆序对总数coutansendl;return0;}【运行结果】4 2 1 3 0 2