企业官网建设流程全解析

网站建设需要注意什么问题,做分享衣服网站的初衷是什么,安装wordpress php,网站的信息容量2023年12月GESP真题及题解(C七级): 商品交易 题目描述 市场上共有 N N N 种商品#xff0c;编号从 0 0 0 至 N − 1 N-1 N−1 #xff0c;其中#xff0c;第 i i i 种商品价值 v i v_i vi​ 元。 现在共有 M M M 个商人#xff0c;编号从 0 0 0 至 M − 1 M-1 M−…2023年12月GESP真题及题解(C七级): 商品交易题目描述市场上共有N NN种商品编号从0 00至N − 1 N-1N−1其中第i ii种商品价值v i v_ivi​元。现在共有M MM个商人编号从0 00至M − 1 M-1M−1。在第j jj个商人这你可以使用你手上的第x j x_jxj​种商品交换商人手上的第y j y_jyj​种商品。每个商人都会按照商品价值进行交易具体来说如果v x j v y j v_{x_j}v_{y_j}vxj​​vyj​​他将会付给你v x j − v y j v_{x_j}-v_{y_j}vxj​​−vyj​​元钱否则那么你需要付给商人v y j − v x j v_{y_j}-v_{x_j}vyj​​−vxj​​元钱。除此之外每次交易商人还会收取1 11元作为手续费不论交易商品的价值孰高孰低。你现在拥有商品a aa并希望通过一些交换来获得商品b bb。请问你至少要花费多少钱当然这个最小花费也可能是负数这表示你可以在完成目标的同时赚取一些钱。输入格式第一行四个整数N , M , a , b N , M , a , bN,M,a,b分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证0 ≤ a , b N 0 \le a,b N0≤a,bN保证a ≠ b a \ne bab。第二行N NN个用单个空格隔开的正整数v 0 , v 1 , … , v N − 1 v_0,v_1,…,v_{N-1}v0​,v1​,…,vN−1​依次表示每种商品的价值。保证1 ≤ v i ≤ 10 9 1≤v_i≤10^91≤vi​≤109。接下来M MM行每行两个整数x j , y j x_j,y_jxj​,yj​表示在第j jj个商人这你可以使用第x j x_jxj​种商品交换第y j y_jyj​种商品。保证0 ≤ x j , y j N 0≤x_j,y_jN0≤xj​,yj​N保证x j ≠ y j x_j≠y_jxj​yj​。输出格式输出一行一个整数表示最少的花费。特别地如果无法通过交换换取商品b bb请输出No solution。输入输出样例 1输入 13 5 0 2 1 2 4 1 0 2 0 0 1 2 1 1 2输出 15输入输出样例 2输入 23 3 0 2 100 2 4 0 1 1 2 0 2输出 2-95输入输出样例 3输入 34 4 3 0 1 2 3 4 1 0 0 1 3 2 2 3输出 3No solution说明/提示数据范围对于30%的测试点保证N ≤ 10 N ≤ 10N≤10M ≤ 20 M ≤ 20M≤20。对于70%的测试点保证N ≤ 10 3 N ≤10^3N≤103M ≤ 10 4 M≤10^4M≤104。对于100%的测试点保证N ≤ 10 5 N≤10^5N≤105M ≤ 2 × 10 5 M≤2×10^5M≤2×105。思路分析这个问题可以转化为图论中的最短路径问题。核心思路是1. 问题建模将每种商品看作图中的节点将商人提供的交换关系看作有向图的边边的权重花费 abs(v[x] - v[y]) 1abs(v[x] - v[y])商品差价1固定的手续费2. 特殊处理负权边由于交易可能赚钱即花费为负所以图中存在负权边。因此不能使用普通的Dijkstra算法需要使用能处理负权的最短路径算法。3. 算法选择SPFA算法适用于有负权边的图最坏时间复杂度O(VE)但实际运行较快Bellman-Ford算法更稳定但时间复杂度O(VE)在本题数据范围下可能超时本题选择SPFA并加入负环检测4. 负环处理如果图中存在负环且起点a能到达负环且从负环能到达终点b那么理论上可以通过无限次交易赚取无限多的钱最小花费是负无穷。但题目未明确说明这种情况我们按常规处理如果检测到负环且能到达b则输出No solution因为这种情况在实际中不可能实现无限次交易。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;// 使用long long防止数据溢出constll INF1e18;// 定义无穷大值constintMAXN1e510;// 最大商品数量intn,m,a,b;// n:商品数, m:商人数, a:起点商品, b:目标商品ll v[MAXN];// v[i]:第i种商品的价值vectorpairint,llg[MAXN];// 邻接表存储图g[u] {(v, w)}表示从u到v的边权重为w/** * SPFA算法求最短路径 * ans 输出参数存储计算得到的最小花费 * 返回值true:找到解false:无解不可达或存在负环 */boolspfa(llans){// d[i]:从起点a到商品i的最小花费vectorlld(n,INF);// cnt[i]:节点i入队次数用于检测负环vectorintcnt(n,0);// inq[i]:节点i是否在队列中vectorboolinq(n,false);// 队列用于存储待处理的节点queueintq;// 初始化起点d[a]0;q.push(a);inq[a]true;cnt[a]1;// SPFA主循环while(!q.empty()){intuq.front();// 取出队首节点q.pop();inq[u]false;// 标记为不在队列中// 遍历节点u的所有出边for(autoe:g[u]){inttoe.first;// 目标节点ll we.second;// 边权交易花费// 松弛操作如果通过u到达to的距离更短则更新if(d[u]wd[to]){d[to]d[u]w;// 更新最短距离// 如果to不在队列中加入队列if(!inq[to]){q.push(to);inq[to]true;cnt[to];// 入队次数1// 负环检测如果一个节点入队超过n次说明存在负环// 在负环中可以无限减少花费这种情况视为无解if(cnt[to]n){returnfalse;// 存在负环返回无解}}}}}// 检查是否可达目标商品bif(d[b]INF){returnfalse;// 不可达返回无解}// 将结果赋值给输出参数ansd[b];returntrue;// 成功找到最短路径}intmain(){// 加速输入输出ios::sync_with_stdio(false);cin.tie(0);// 读入基本参数cinnmab;// 读入商品价值for(inti0;in;i){cinv[i];}// 建立交易关系图for(inti0;im;i){intx,y;cinxy;// 计算交易花费v[y] - v[x] 1// 公式推导// 1. 如果v[x] v[y]我们得到(v[x]-v[y])元差价支付1元手续费// 总花费 -(v[x]-v[y]) 1 v[y] - v[x] 1负花费表示赚钱// 2. 如果v[x] v[y]我们支付(v[y]-v[x])元差价支付1元手续费// 总花费 v[y] - v[x] 1// 两种情况统一为花费 v[y] - v[x] 1ll costv[y]-v[x]1;// 添加有向边从商品x到商品y权重为cost// 注意交易是单向的只能使用x交换yg[x].push_back({y,cost});}// 调用SPFA算法计算最小花费ll ans;if(spfa(ans)){coutans\n;// 输出最小花费}else{coutNo solution\n;// 无解输出}return0;}功能分析1. 算法设计思路图建模将每种商品视为图中的节点将商人提供的交易关系视为有向边边的权重计算公式v[y] - v[x] 1v[y] - v[x]: 商品价值差1: 固定手续费算法选择由于存在负权边当v[y] v[x]时不能使用Dijkstra算法选择SPFA (Shortest Path Faster Algorithm)算法本质是Bellman-Ford算法的队列优化版本能处理负权边平均时间复杂度优于Bellman-Ford2. 核心功能模块数据结构邻接表 (g[MAXN]):存储图结构每个元素为pairint, ll表示(目标节点, 边权重)空间复杂度: O(NM)距离数组 (d[n]):存储从起点a到每个节点的最短距离初始值为INF无穷大辅助数组:cnt[n]: 记录节点入队次数用于负环检测inq[n]: 标记节点是否在队列中避免重复入队SPFA算法流程初始化: 起点距离为0加入队列循环处理队列:取出队首节点u遍历u的所有出边尝试松弛操作如果通过u到达邻居的距离更短则更新如果邻居被更新且不在队列中则加入队列负环检测: 如果一个节点入队超过n次说明存在负环结果判断: 如果目标节点b的距离仍为INF说明不可达3. 关键点说明负权边处理边权公式v[y] - v[x] 1可能为负值负权边表示交易可以赚钱获得差价大于手续费SPFA算法能正确处理负权边负环检测负环: 环上所有边的权重之和为负数影响: 在负环上可以无限循环交易无限减少花费处理: 检测到负环则视为无解返回No solution不可达判断初始化所有节点距离为INF如果经过算法后b的距离仍为INF说明从a无法到达b返回No solution4. 时间复杂度分析理论复杂度最坏情况: O(VE) O(2×10^10)平均情况: 远好于最坏情况实际表现: 在本题数据范围内通常可以接受优化特点队列优化: 只处理距离发生变化的节点避免冗余: 使用inq数组防止重复入队提前终止: 检测到负环时提前返回5. 空间复杂度分析邻接表: O(NM) ≈ 3×10^5辅助数组: O(N) ≈ 10^5总空间: 约1.6MB远小于内存限制6. 边界情况处理数据类型使用long long存储距离防止溢出商品价值最大109 ^99M最大2×105 ^55最坏情况下总花费可能超过int范围特殊输入无解情况:不可达无交易路径存在负环且能到达目标零花费/赚钱情况:最小花费为负数表示交易赚钱算法能正确处理负距离完整GESP C考级真题题解专栏GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html更多csp信奥赛C学习资料汇总1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}