蓝桥杯第二十场小白入门赛
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的最大小值。求的过程用到滑动窗口。