蓝桥ACM培训-实战1

前言：

  今天老师没讲课，只让我们做了一下几道题目。

正文：

Problem:A 小蓝与操作序列：

#include<bits/stdc++.h>
using namespace std;
stack<int> a;
int main(){int n,flag=1,ans;string cz;cin>>n;for(int i=1;i<=n;i++){cin>>cz;if(cz=="push"){a.push(1);}if(cz=="pop"){if(a.empty()){ans=i;flag=0;break;}else a.pop();}if(cz=="top"){if(a.empty()){ans=i;flag=0;break;}}if(cz=="clear"){while(!a.empty())a.pop();}}if(flag){cout<<"Yes"<<endl;cout<<a.size()<<endl;}else{cout<<"No"<<endl;cout<<ans<<endl;}return 0;
}

自己开一个stack模拟即可，注意c++的stack是没有clear操作的，让他循环弹出即可。

Problem:B 小兰与角谷猜想：

#include<bits/stdc++.h>
using namespace std;
int cnt;
long long jg(long long x){cnt=0;while(x>1){if(x%2==0)x/=2;else x=x*3+1;cnt++;}return cnt;
}
int main(){long long l,r,ans=0,step=0;cin>>l>>r;for(long long i=l;i<=r;i++){if(step<jg(i))ans=i;step=max(step,jg(i));}cout<<ans<<endl;
}

数据范围不大，直接暴力找（注意答案要用longlong）。

Problem:C 小兰与名氏距离：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int x[100009],y[100009];
int main(){ll n,ans=0;cin>>n;for(int i=1;i<=n;i++){cin>>x[i]>>y[i];}sort(x+1,x+1+n);sort(y+1,y+1+n);for(int i=1;i<=n;i++){ll cnt=1,fi=i;while(x[++i]==x[fi])cnt++;i--;ans+=(cnt*(cnt-1))/2;}for(int i=1;i<=n;i++){ll cnt=1,fi=i;while(y[++i]==y[fi])cnt++;i--;ans+=(cnt*(cnt-1))/2;}cout<<ans<<endl;
}

满足条件的两个点一定有x或y相等，我们将x,y分开考虑，对于每a个相同的x和y，一定有a*（a-1）/2个点对满足条件，总加和即可。

Problem:D 小兰与线段：

#include <bits/stdc++.h>
using namespace std;
int mp[1009][1009],dp[1009][1009][2],n,m,cnt,ans=0;
int main(){cin>>n>>m;for(int i=1;i<=n;i++)for(int o=1;o<=m;o++)cin>>mp[i][o];for(int i=1;i<=n;i++){for(int o=1;o<=m;o++){cnt=1;if(dp[i][o][0]==0){dp[i][o][0]=1;for(int p=o+1;p<=m;p++){if(mp[i][p]==mp[i][o]){cnt++;dp[i][p][0]=1;ans=max(cnt,ans);}else break;}}cnt=1;if(dp[i][o][1]==0){dp[i][o][1]=1;for(int p=i+1;p<=n;p++){if(mp[p][o]==mp[i][o]){cnt++;dp[p][o][1]=1;ans=max(cnt,ans);}else break;}}//cout<<dp[i][o][1]<<" ";}//cout<<endl;}cout<<ans<<endl;
}

一开始想用dfs,这道题好像用dfs有点麻烦，我自己刚好前不久了解了一点动态规划，写这题时灵感暴发，于是就尝试了一下，没想到竟然可行，这题好像暴力也能过。在这里讲讲我的思路吧，我们将每个点都设置好两个状态，分别是已扫过本行和已扫过本列，我们从第一行第一列开始遍历，先检验他的状态看看有没有被扫过（行列都要）。如果有就跳过，没有就更新状态后向下一行或列的点继续操作，这样就可以排除已考虑的点，直到遍历到末尾，最后输出答案。

Problem:E 小兰与子数组：

#include <bits/stdc++.h>
using namespace std;
int main()
{int n,a[100000];scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&a[i]);sort(a,a+n);cout<<a[n-1]-a[0]<<" "<<max(a[n-2]-a[0],a[n-1]-a[1]);return 0;
}

排序后直接输出最大值减最小值与子序列最大值减最小值。

后记：

  开学前最后一次训练，不知道之后的训练在什么时候。