蓝桥杯第二十场小白入门赛

2.黛玉泡茶

我的思路代码：（但我不知道哪有错误）

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int main(){int n,m,k,res=1;cin>>n>>m>>k;vector<int>num(n+1,0);for(int i=1;i<=n;i++) cin>>num[i];sort(num.begin()+1,num.end());int sum=m;for(int i=1;i<=k;i++){sum-=num[i];if(sum<0){sum+=m;res++;}}cout<<res<<endl;return 0;
}

正确的思路代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;int main(){int n,m,k,res=0;cin>>n>>m>>k;vector<int>num(n+1,0);for(int i=1;i<=n;i++) cin>>num[i];sort(num.begin(),num.end());for(int i=1;i<=k;i++) res+=num[i];if(res%m==0)cout<<res/m<<endl;else cout<<res/m+1<<endl;return 0;
}

反思：我知道了。查看了测试用例后，我才明白，可能茶壶容量远小于一杯茶的容量，也就是说，你要倒满一杯茶，需要接好几次水壶，而我的代码中循环一次res最多也加一。后果就是，对于这类测试用例，我的循环结束了，我的sum还远远小于0，还没加成正值。

3.宝玉请安

我的错误思路代码：

#include <iostream>
#include<cmath>
using namespace std;
int main()
{int t,x1,x2,x3;int res=0;//需走的步数cin>>t;while(t--){cin>>x1>>x2>>x3;if((x2<x1&&x3<x1)||(x2>x1&&x3>x1)){if(x2>x3) res=abs(x2-x1);else res=abs(x3-x1);}else if((x2<x1&&x3>x1)||(x2>x1&&x3<x1)){if(abs(x1-x3)<abs(x1-x2)){res=abs(x1-x3)+abs(x2-x3);}else res=abs(x1-x2)+abs(x3-x2);}cout<<res<<endl;}// 请在此输入您的代码return 0;
}

正确思路代码：

#include <iostream>
#include<cmath>
using namespace std;
int main()
{int t,x1,x2,x3;int res=0;//需走的步数cin>>t;while(t--){cin>>x1>>x2>>x3;res=min(abs(x1-x2),abs(x1-x3))+abs(x2-x3);cout<<res<<endl;}// 请在此输入您的代码return 0;
}

反思：思考了好长时间，不知道自己为什么错，就是觉得自己的思路很正确，难受死了。最后看了看别人的和我相似的思路，才发现原来自己思路有漏洞，我把可能情况分两部分，一是两个目标地点在同一侧，二是不在同一侧。在同一侧的步数统计有问题，我直接判断两点谁更大，实际上应该判断两点谁离x1更远。

还学到了别人的直触本质的思路。本质上是x1到x2或x3其中一个，让后再在x2,x3之间行走。

4.贾母祝寿

我的思路代码：

#include <iostream>
#include<cmath>
#include<vector>
using namespace std;
int main()
{int n,q;long long res=0;cin>>n>>q;vector<long long>stone(n,0);while(q--){int t,x,y;cin>>t>>x>>y;if(t==1){for(int i=0;i<x;i++){stone[i]+=y;}}else {for(int i=n-1;i>=n-x;i--){stone[i]-=y;}}}for(int i=0;i<n;i++){stone[i]=abs(stone[i]);res=max(res,stone[i]);}cout<<res<<endl;// 请在此输入您的代码return 0;
}

正确思路代码：

#include <iostream>
#include<cmath>
#include<vector>
using namespace std;
int main()
{int n,q;long long res=0;cin>>n>>q;long long num1=0,num2=0;while(q--){int t,x,y;cin>>t>>x>>y;if(t==1){num1+=y;if(x==n)num2+=y;}else {num2-=y;if(x==n) num1-=y;}}res=max(abs(num1),abs(num2));cout<<res<<endl;// 请在此输入您的代码return 0;
}

反思：我的思路时间复杂度太高，O(n*m),n的数据范围是10^5,m的数据范围是10^9。

 5.清洁客房

我根本没想到用dp数组，我想用排列组合做一下，没做出来。

#include <iostream>
#include<vector>
using namespace std;
int N = 1e5+1;
int mod = 1e9 + 7;
int main()
{vector<vector<long>> dp(N, vector<long>(4,0));//前i个房间选择j种的方案类型for(int i=1;i<N;i++)dp[i][1]=9;for (int i = 2; i <N; i++) {for (int j = 2; j <= 3; j++) {dp[i][j] = (dp[i - 1][j - 1] * (10 - (j - 1))%mod  + dp[i - 1][j] * j%mod ) % mod;}}int t, n;cin >> t;while (t--) {cin >> n;cout << dp[n][3] << endl;}// 请在此输入您的代码return 0;
}

dp数组含义：dp[i][j]前i个房间选择j种等级的方案数 (i,j均从0开始)

6.宝玉与黛玉的考验

正确代码

#include<iostream>
#include<string>
using namespace std;int n, m, k;
string a, b;
long get(long a, long b) {return k * a + k * b - 2 * a * b;
}int main() {cin >> n >> m >> k >> a >> b;int mxa = 0, mxb = 0, mna = k, mnb = k, sum = 0;//滑动窗口，找出4个值、for (int i = 0; i < n; i++) {sum += a[i] - '0';if (i >= k) {sum -= a[i - k] - '0';mxa = max(sum, mxa);mna = min(sum, mna);}}sum = 0;for (int i = 0; i < m; i++) {sum += b[i] - '0';if (i >= k) {sum -= b[i - k] - '0';mxb = max(sum, mxb);mnb = min(sum, mnb);}}cout << max(max(get(mxa, mxb), get(mxa, mnb)), max(get(mna, mxb), get(mna, mnb))) << endl;return 0;
}

思路：这题看来是和数学思维相关。开始我想了遍历整个二维数组，但是很明显超时。

用数学思维来分析：设k*k区间中分别有a行，b列被选中，即长度为n的字符串中有a个1，长度为m的字符串中有b个1。那么这个区间的价值为ka-ab+kb-ab=-2（a-k/2）(b-k/2)+k^2/2。（k是常量，a,b是变量）a,b单独变化，这个表达式 的最值在a,b取到端点的时候取到最值。那么就求a,b的最大小值。求的过程用到滑动窗口。