算法题目优选（蓝桥杯备战）--2

前言

这些题目摘录于洛谷，好题，典型的题，考察各类算法运用，可用于蓝桥杯及各类算法比赛备战，算法题目练习，提高算法能力，补充知识，提升思维。
锻炼解题思路，从学会算法模板后，会分析，用到具体的题目上。

分享

试想一下多年以后，你真的成为自己最喜欢的样子，那么此刻如果身处低谷，你真的不再为自己努力尝试一下吗？每个人的起点不同，不要为此感到愤恨不公，把握有限的时间，让自己变的更好，用更扎实的学识拖住你的犹豫，用更坚毅的品质挡住你的迷茫。当一切实现，你也许会觉得努力不是独自的成长，也不是突然的蜕变，而是你面对理想的自己，日复一日的靠近。

题目清单

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。

代码：

#include<iostream>usingnamespacestd;constintN=5e5+10;typedeflonglongLL;LL n,a,b;LL w[N];//判断boolcheck(LL x){intcnt=0;for(inti=1;i<=n;i++){if(w[i]<=a*x)continue;intd=w[i]-a*x;cnt+=d/b+(d%b==0?0:1);}returncnt<=x;}intmain(){cin>>n>>a>>b;for(inti=1;i<=n;i++)cin>>w[i];//二分答案LL l=1,r=5e5;while(l<r){LL mid=(l+r)/2;if(check(mid))r=mid;elsel=mid+1;}cout<<l<<endl;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.

代码：

#include<iostream>usingnamespacestd;constintN=1010;intw[]={0,1,2,3,5,10,20};inta[10];intf[N];//f[i][j]从前i个物品中挑选，能否凑出重量为jintmain(){for(inti=1;i<=6;i++)cin>>a[i];//初始化f[0]=1;//多重背包for(inti=1;i<=6;i++){for(intj=1000;j>=0;j--)//优化一维，逆序处理{for(intk=0;k<=a[i]&&k*w[i]<=j;k++){f[j]=f[j]||f[j-k*w[i]];//有一个成立即可}}}intret=0;for(inti=1;i<=1000;i++){if(f[i])ret++;}cout<<"Total="<<ret<<endl;return0;}

3.螺旋矩阵

题目：P2239 [NOIP 2014 普及组] 螺旋矩阵

解法：找规律 + 分情况讨论 + 递归
1.暴力模拟：直接按顺序填数，O（n ^ 2）时间复杂度还在范围内，但是空间超了。

2.发现：会出现在边缘和不在边缘两种情况；那么可以一层一层的分析，在边缘（属于边界条件，可以直接数学计算），当 (i, j) 的位置不在边缘的时候，接下来去：将主问题（边长为 n 的矩形，从 0 开始累加，找出 (i, j) 位置的值；）分割为子问题（边长为 n - 2 的矩形，从 4 * (n - 1) 开始累加，找出 (i -1, j - 1) 位置的值。） 注意：此时要查找的位置是i - 1， j - 1。相同子问题，可以用递归来解决。

3.边界处理：

细节： 每一圈的开始位置不同，用一个begin标记每一圈的开始位置

i=1， 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。

代码：

#include<iostream>usingnamespacestd;intn,i,j;//递归intdfs(intn,intbegin,inti,intj){//边界，递归出口if(i==1)returnbegin+j;if(j==n)returnbegin+i+n-1;if(i==n)returnbegin+3*n-j-1;if(j==1)returnbegin+4*n-i-2;//下一层returndfs(n-2,begin+4*(n-1),i-1,j-1);}intmain(){cin>>n>>i>>j;cout<<dfs(n,0,i,j)<<endl;return0;}

4.“非常男女”计划

题目：P1114 “非常男女”计划

解法：正负抵消 + 前缀和 + 哈希表
找一个区间内男女个数相等，1，0； sum * 2 = len; 但是这样判断很麻烦。

提供思路：要确定一个区间的两种东西数量是否相等，可以用1，-1表示，看区间和是否为0，正负抵消。

再学会用前缀和（思路） + 哈希表 维护区间的值。 思维转化：要找一个区间和为0的最长区间， 区间为sum,那么用前缀和维护区间和，利用哈希表找第一个出现sum的位置，两者区间的差部分的那个区间为0区间，且满足最长，就找第一个，用mp.count(sum)。

细节：要初始化mp[0] = 0, 因为本身区间可能sum = 0，但是之前没有0， 就算不到这种情况区间的长度。

代码：

#include<iostream>#include<unordered_map>usingnamespacestd;intn;unordered_map<int,int>mp;// 1.前缀和sum 2.对应下标intmain(){cin>>n;intsum=0,ret=0;mp[0]=0;//注意要初始化，sum = 0, i = 0for(inti=1;i<=n;i++){intx;cin>>x;x=(x==0?-1:1);sum+=x;if(mp.count(sum))ret=max(ret,i-mp[sum]);//count,第一次出现sum的值（位置），区间长度elsemp[sum]=i;//第一次出现sum}cout<<ret<<endl;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]

在这两种情况中取最大值即可。

代码：

#include<iostream>#include<algorithm>usingnamespacestd;constintN=2e5+10;intn;inta[N];intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);n=unique(a+1,a+1+n)-(a+1);if(n==1)cout<<-1<<endl;elseif(n==2)cout<<a[2]%a[1]<<endl;elsecout<<max(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])。

代码：

#include<iostream>usingnamespacestd;constintN=30;intret,n;string s[N];intcnt[N];//同bool的作用，标记字符串用了几次，用于剪枝（非法）voiddfs(string path){if(path.size()>ret)ret=path.size();//记得更新长度for(inti=1;i<=n;i++){if(cnt[i]>=2)continue;//剪枝intcur1=path.size()-1,cur2=0;while(cur1>=1&&cur2<path.size()-1){if(path.substr(cur1)==s[i].substr(0,cur2+1))//长度为 cur2 + 1{cnt[i]++;dfs(path+s[i].substr(cur2+1));//拼接cnt[i]--;//恢复现场，回溯}cur1--;cur2++;}}}intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>s[i];charch;cin>>ch;for(inti=1;i<=n;i++){if(s[i][0]==ch){cnt[i]++;dfs(s[i]);cnt[i]--;//恢复现场，回溯}}cout<<ret<<endl;return0;}

7.瑞士轮

题目：P1309 [NOIP 2011 普及组] 瑞士轮

解法：模拟 + 归并排序
直接模拟时间复杂度会超。

创建两个数组，胜者组和败者组。要降序排序，因为要输出分数最大的人的id,因为每个人有id,实力值，分数3个数据，排序时要对应，用struct存储。 O（n * r + nlogm)

每一轮：

1.先按分数排序；（降序）

2.模拟一轮比赛过程，比赛结果放入胜者组和败者组。 （降序）

3.用归并排序的逻辑合并有序数组。

代码：

#include<iostream>#include<algorithm>usingnamespacestd;constintN=2e5+10;//开2倍空间intn,r,q;structnode{ints,id,w;}a[N];node x[N],y[N];//胜者组和败者组//升序boolcmp(node&x,node&y){if(x.s==y.s)returnx.id<y.id;elsereturnx.s>y.s;}//归并排序合并有序数组逻辑voidmerge(){intcur1=1,cur2=1,i=1;while(cur1<=n&&cur2<=n){if(x[cur1].s>y[cur2].s||(x[cur1].s==y[cur2].s&&x[cur1].id<y[cur2].id)){a[i++]=x[cur1++];}else{a[i++]=y[cur2++];}}//其中必有一个剩余，处理剩下的while(cur1<=n)a[i++]=x[cur1++];while(cur2<=n)a[i++]=y[cur2++];}intmain(){cin>>n>>r>>q;for(inti=1;i<=n+n;i++){cin>>a[i].s;a[i].id=i;}for(inti=1;i<=n+n;i++){cin>>a[i].w;}sort(a+1,a+1+n+n,cmp);while(r--){intpos=1;for(inti=1;i<=n+n;i+=2)//一次两个比较，注意这里 i += 2{if(a[i].w>a[i+1].w){a[i].s++;x[pos]=a[i];y[pos]=a[i+1];}else{a[i+1].s++;x[pos]=a[i+1];y[pos]=a[i];}pos++;}merge();}cout<<a[q].id<<endl;return0;}

8. 奶酪

题目：P3958 [NOIP 2017 提高组] 奶酪

解法：并查集（妙解）
判断是否联通，联通的话放入一个集合，在最上表面n+1和最下表面0各增加一块，最后判断这两块是否连通。

代码：

#include<iostream>usingnamespacestd;typedeflonglongLL;constintN=1e3+10;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]);returnd<=4*r*r;}intmain(){intT;cin>>T;while(T--){cin>>n>>h>>r;//初始化for(inti=0;i<=n+1;i++)fa[i]=i;for(inti=1;i<=n;i++){cin>>x[i]>>y[i]>>z[i];//判断下表面if(z[i]<=r)merge(i,0);//判断上表面if(z[i]+r>=h)merge(i,n+1);//判断其余的球for(intj=1;j<i;j++){if(check(i,j))merge(i,j);}}if(find(0)==find(n+1))cout<<"Yes"<<endl;elsecout<<"No"<<endl;}return0;}

让我们保持好奇，保持耐心，在纷繁的数据结构中寻找秩序，在复杂的逻辑中构建桥梁。共勉！”