做网站 什么语言洛阳网站建设价格

做网站 什么语言,洛阳网站建设价格,怎么做一个赚钱得网站,建设模式有哪些文章目录前言分享题目清单1.奶牛晒衣服2.砝码称重3.螺旋矩阵4.“非常男女”计划5.次大值6.单词接龙7.瑞士轮8. 奶酪前言 这些题目摘录于洛谷#xff0c;好题#xff0c;典型的题#xff0c;考察各类算法运用#xff0c;可用于蓝桥杯及各类算法比赛备战#xff0c;算法题目…文章目录前言分享题目清单1.奶牛晒衣服2.砝码称重3.螺旋矩阵4.“非常男女”计划5.次大值6.单词接龙7.瑞士轮8. 奶酪前言这些题目摘录于洛谷好题典型的题考察各类算法运用可用于蓝桥杯及各类算法比赛备战算法题目练习提高算法能力补充知识提升思维。锻炼解题思路从学会算法模板后会分析用到具体的题目上。分享试想一下多年以后你真的成为自己最喜欢的样子那么此刻如果身处低谷你真的不再为自己努力尝试一下吗每个人的起点不同不要为此感到愤恨不公把握有限的时间让自己变的更好用更扎实的学识拖住你的犹豫用更坚毅的品质挡住你的迷茫。当一切实现你也许会觉得努力不是独自的成长也不是突然的蜕变而是你面对理想的自己日复一日的靠近。题目清单1.奶牛晒衣服题目P1843 奶牛晒衣服解法二分答案首先大概率会想到贪心算法就是优先选择湿度最大的衣服进行烘干然后选择次之但是这样的贪心策略是错误的可以举出反例w [10, 8], a 1, b 1; 如果选10 算出来时间是7s, 但最优解是用烘干机烘干10 选择烘干4s, 8烘干1s 结果是6是。为什么会错 因为把自然干看成为每个都有烘干能力为a/s的烘干机而这种贪心策略在最后浪费了其它烘干机在的烘干湿度。所以最好让最后衣服一起可以烘干。可以发现烘干机在中途要不断改变烘干的衣服。 这种是很难直接找的。枚举答案设经过的时间是 x 。根据题意我们可以发现如下性质经过的时间如果是 x 的话烘干机的「使⽤次数」最多也是 x x 与能弄干的衣服在呈正相关那么在整个解空间里面设弄干所有衣服的最少时间是 ret 于是有当 x ≥ ret 时我们能弄干所有衣服 满足要求合法当 x ret 时我们不能弄干所有衣服。在解空间中根据ret 的位置可以将解集分成两部分具有「⼆段性」那么我们就可以⼆分答案。不满足要求不合法接下来的重点就是给定⼀个时间 x判断「是否能把所有的衣服全部弄干」。当时间为 x时所有衣服能够自然蒸发a * x的湿度于是如果 w[i] ≤ a ⋅ x 让它自然蒸发如果 需要⽤烘⼲机烘干的湿度次数为w[i] a ⋅ x t w[i] − a ⋅ x t / b (t % b 0 ? 0 : 1) //优先级算术 逻辑那么我们可以遍历所有的衣服计算烘干机的「使用次数」与 x进行判断。如果使用次数「大于」给定的时间 x 说明不能全部弄干如果使用次数「小于等于」给定的时间 x 说明能全部弄干。注意虽然这里int也能全部通过这里数据范围是到 5e5 ,但是拿不准还是开long long。代码#includeiostreamusingnamespacestd;constintN5e510;typedeflonglongLL;LL n,a,b;LL w[N];//判断boolcheck(LL x){intcnt0;for(inti1;in;i){if(w[i]a*x)continue;intdw[i]-a*x;cntd/b(d%b0?0:1);}returncntx;}intmain(){cinnab;for(inti1;in;i)cinw[i];//二分答案LL l1,r5e5;while(lr){LL mid(lr)/2;if(check(mid))rmid;elselmid1;}coutlendl;return0;}2.砝码称重题目P2347 [NOIP 1996 提高组] 砝码称重解法多重背包求得是可以凑出得重量种数首先想到暴力枚举排列组合等方法但难以找到枚举或排列的方法且时间复杂度大过于复杂。重量 w:[1, 2, 3, 5, 10, 20]数量 a[] :[a1, a2, a3, a4, a5, a6]思路转化设选的 w总 j,这道题就转化为从前i种物品中选物品总重量为j的所有选法。这样题目就转化为多重背包问题物品个数有限制。执行多重背包的逻辑1.状态表式表示从前 i 种砝码中挑选是否能凑成总质量为 j 。最终结果就是 f 表里面最后⼀⾏为 true 的个数。f[n] [j]里面找 f[n] [0] 不算。2.状态转移⽅程根据第 i 个砝码选的个数能分成 a[i] 1 种情况设选了0,1, …… k 个。此时重量为 w[i] × k 那么就应该去前⾯看看能不能凑成 j − w[i] × k 即f[i - 1] [j - w[i] * k]在所有的情况里面只要有⼀个为真 f[i] [j] 就为真。3.初始化f[0] [0] 1起始状态也是为了后续填表有意义且正确。4.填表顺序从上往下每一行每一行从左往右。数据范围 可知 j 1000,用于循环更新所有选的情况。细节优化一维第二层for要逆序处理 0 k a[i], k * w[i] j.代码#includeiostreamusingnamespacestd;constintN1010;intw[]{0,1,2,3,5,10,20};inta[10];intf[N];//f[i][j]从前i个物品中挑选能否凑出重量为jintmain(){for(inti1;i6;i)cina[i];//初始化f[0]1;//多重背包for(inti1;i6;i){for(intj1000;j0;j--)//优化一维逆序处理{for(intk0;ka[i]k*w[i]j;k){f[j]f[j]||f[j-k*w[i]];//有一个成立即可}}}intret0;for(inti1;i1000;i){if(f[i])ret;}coutTotalretendl;return0;}3.螺旋矩阵题目P2239 [NOIP 2014 普及组] 螺旋矩阵解法找规律 分情况讨论 递归1.暴力模拟直接按顺序填数On ^ 2时间复杂度还在范围内但是空间超了。2.发现会出现在边缘和不在边缘两种情况那么可以一层一层的分析在边缘属于边界条件可以直接数学计算当 (i, j) 的位置不在边缘的时候接下来去将主问题边长为 n 的矩形从 0 开始累加找出 (i, j) 位置的值分割为子问题边长为 n - 2 的矩形从 4 * (n - 1) 开始累加找出 (i -1, j - 1) 位置的值。 注意此时要查找的位置是i - 1 j - 1。相同子问题可以用递归来解决。3.边界处理细节 每一圈的开始位置不同用一个begin标记每一圈的开始位置i1 begin j;j n, begin i n - 1;i n, begin 2 * (n - 1) (n - j) 1;j 1, begin 3 * (n - 1) (n - i) 1。代码#includeiostreamusingnamespacestd;intn,i,j;//递归intdfs(intn,intbegin,inti,intj){//边界递归出口if(i1)returnbeginj;if(jn)returnbeginin-1;if(in)returnbegin3*n-j-1;if(j1)returnbegin4*n-i-2;//下一层returndfs(n-2,begin4*(n-1),i-1,j-1);}intmain(){cinnij;coutdfs(n,0,i,j)endl;return0;}4.“非常男女”计划题目P1114 “非常男女”计划解法正负抵消 前缀和 哈希表找一个区间内男女个数相等10 sum * 2 len; 但是这样判断很麻烦。提供思路要确定一个区间的两种东西数量是否相等可以用1-1表示看区间和是否为0正负抵消。再学会用前缀和思路 哈希表 维护区间的值。 思维转化要找一个区间和为0的最长区间 区间为sum,那么用前缀和维护区间和利用哈希表找第一个出现sum的位置两者区间的差部分的那个区间为0区间且满足最长就找第一个用mp.count(sum)。细节要初始化mp[0] 0, 因为本身区间可能sum 0但是之前没有0 就算不到这种情况区间的长度。代码#includeiostream#includeunordered_mapusingnamespacestd;intn;unordered_mapint,intmp;// 1.前缀和sum 2.对应下标intmain(){cinn;intsum0,ret0;mp[0]0;//注意要初始化sum 0, i 0for(inti1;in;i){intx;cinx;x(x0?-1:1);sumx;if(mp.count(sum))retmax(ret,i-mp[sum]);//count,第一次出现sum的值位置区间长度elsemp[sum]i;//第一次出现sum}coutretendl;return0;}5.次大值题目P5682 [CSP-J 2019 江西] 次大值解法数学严格次大值可以对所有的数据排序 去重。细节虽然排序后去重取模后也会有重复的数但是这个算法原理不考虑。排序数组a最大值分为两种情况因为大数 % 小数 小数 a[n - 1], 小数 % 大数 max a[n - 1]最大值⼀定是 a[n - 1] % a[n]。同理次大值可以分为两种情况1.小数 % 大数那就只能是 a[n - 2] % a[n - 1] a[n - 2], a[n - 2]不考虑2.大数 % 小数只能是 a[n] % a[n - 1] 。 a[n - 1]在这两种情况中取最大值即可。代码#includeiostream#includealgorithmusingnamespacestd;constintN2e510;intn;inta[N];intmain(){cinn;for(inti1;in;i)cina[i];sort(a1,a1n);nunique(a1,a1n)-(a1);if(n1)cout-1endl;elseif(n2)couta[2]%a[1]endl;elsecoutmax(a[n-2],a[n]%a[n-1])endl;return0;}6.单词接龙题目P1019 [NOIP 2000 提高组] 单词接龙解法dfs暴搜 剪枝因为这道题的数据范围很小 n 20, dfs时间复杂度是呈指数级别的。大致思路从开头开始暴力搜索出所有的连接情况加入大量判断与更新剪枝找出最长的。这道题有大量的细节问题要处理用字符串数组s[i]存储所有字符串进行暴力搜索dfs。1.不能用常规的做法用全局的path标记当前路径因为不能“清理恢复现场”就是恢复回到上一步递归回溯会找不到上一条路的情况因为以往做的都是操作简单可以 - 一个数或字符pop_back() push_back() 回到上一步但是这里涉及到拼接就会改变很多很乱处理起来很复杂。 这里设计dfs(string path) 参数对应就保留了每一步的路径字符串的连接情况。2.如何拼接用双指针和substr拼接字符串函数判断path.substr(cur1 s[i].substr(0, cur2 1) substr()传1个参数是用这个及后面的字符传两个参数是开始和切的长度。 然后双指针同时移动cur1–, cur, 拼接path s[i].substr(cur2 1)。3.处理不能包含的问题给指针限定移动范围cur1 1 cur2 s[i].size() - 1。4.因为处理了不能包含的情况但是单词接龙的龙头是包含的情况要特殊处理就用一个for循环遍历字符串数组s[i] [0] ch; (这里可以看成一个二维数组遍历) dfs(s[i])。代码#includeiostreamusingnamespacestd;constintN30;intret,n;string s[N];intcnt[N];//同bool的作用标记字符串用了几次用于剪枝非法voiddfs(string path){if(path.size()ret)retpath.size();//记得更新长度for(inti1;in;i){if(cnt[i]2)continue;//剪枝intcur1path.size()-1,cur20;while(cur11cur2path.size()-1){if(path.substr(cur1)s[i].substr(0,cur21))//长度为 cur2 1{cnt[i];dfs(paths[i].substr(cur21));//拼接cnt[i]--;//恢复现场回溯}cur1--;cur2;}}}intmain(){cinn;for(inti1;in;i)cins[i];charch;cinch;for(inti1;in;i){if(s[i][0]ch){cnt[i];dfs(s[i]);cnt[i]--;//恢复现场回溯}}coutretendl;return0;}7.瑞士轮题目P1309 [NOIP 2011 普及组] 瑞士轮解法模拟 归并排序直接模拟时间复杂度会超。创建两个数组胜者组和败者组。要降序排序因为要输出分数最大的人的id,因为每个人有id,实力值分数3个数据排序时要对应用struct存储。 On * r nlogm)每一轮1.先按分数排序降序2.模拟一轮比赛过程比赛结果放入胜者组和败者组。 降序3.用归并排序的逻辑合并有序数组。代码#includeiostream#includealgorithmusingnamespacestd;constintN2e510;//开2倍空间intn,r,q;structnode{ints,id,w;}a[N];node x[N],y[N];//胜者组和败者组//升序boolcmp(nodex,nodey){if(x.sy.s)returnx.idy.id;elsereturnx.sy.s;}//归并排序合并有序数组逻辑voidmerge(){intcur11,cur21,i1;while(cur1ncur2n){if(x[cur1].sy[cur2].s||(x[cur1].sy[cur2].sx[cur1].idy[cur2].id)){a[i]x[cur1];}else{a[i]y[cur2];}}//其中必有一个剩余处理剩下的while(cur1n)a[i]x[cur1];while(cur2n)a[i]y[cur2];}intmain(){cinnrq;for(inti1;inn;i){cina[i].s;a[i].idi;}for(inti1;inn;i){cina[i].w;}sort(a1,a1nn,cmp);while(r--){intpos1;for(inti1;inn;i2)//一次两个比较注意这里 i 2{if(a[i].wa[i1].w){a[i].s;x[pos]a[i];y[pos]a[i1];}else{a[i1].s;x[pos]a[i1];y[pos]a[i];}pos;}merge();}couta[q].idendl;return0;}8. 奶酪题目P3958 [NOIP 2017 提高组] 奶酪解法并查集妙解判断是否联通联通的话放入一个集合在最上表面n1和最下表面0各增加一块最后判断这两块是否连通。代码#includeiostreamusingnamespacestd;typedeflonglongLL;constintN1e310;LL n,h,r;LL x[N],y[N],z[N];intfa[N];//并查集intfind(intx){returnfa[x]x?x:fa[x]find(fa[x]);}voidmerge(intx,inty){fa[find(x)]find(y);}boolcheck(inti,intj){LL d(x[i]-x[j])*(x[i]-x[j])(y[i]-y[j])*(y[i]-y[j])(z[i]-z[j])*(z[i]-z[j]);returnd4*r*r;}intmain(){intT;cinT;while(T--){cinnhr;//初始化for(inti0;in1;i)fa[i]i;for(inti1;in;i){cinx[i]y[i]z[i];//判断下表面if(z[i]r)merge(i,0);//判断上表面if(z[i]rh)merge(i,n1);//判断其余的球for(intj1;ji;j){if(check(i,j))merge(i,j);}}if(find(0)find(n1))coutYesendl;elsecoutNoendl;}return0;}让我们保持好奇保持耐心在纷繁的数据结构中寻找秩序在复杂的逻辑中构建桥梁。共勉”