第十四届蓝桥杯c++研究生组
A 混乘数字
关键思路是求每个十进制数的数字以及怎么在一个数组中让判断所有的数字次数相等。
求每个十进制的数字
while(n!=0){
int x = n%10;//x获取了n的每一个位数字
n/=10;
}
扩展：求二进制的每位数字 （注意：进制转换、1的个数、位运算）
x >> k & 1//k代表第几个位置
判断几个数中的数字次数相等
下面是判断3个数中的数字次数相等
bool swap(int n,int i,int j){
int a[]={0,0,0,0,0,0,0,0,0,0};
while(n!=0){
int x = n%10;
a[x]++;
n/=10;
}
while(i!=0){
int x = i%10;
a[x]--;
i/=10;
}
while(j!=0){
int x = j%10;
a[x]--;
j/=10;
}
for(int i=0;i<=9;i++){
if(a[i]!=0){
return false;
}
}
return true;
}
完整代码：
#include <iostream>
#include <cmath>
using namespace std;
bool swap(int n,int i,int j){
int a[]={0,0,0,0,0,0,0,0,0,0};
while(n!=0){
int x = n%10;
a[x]++;
n/=10;
}
while(i!=0){
int x = i%10;
a[x]--;
i/=10;
}
while(j!=0){
int x = j%10;
a[x]--;
j/=10;
}
for(int i=0;i<=9;i++){
if(a[i]!=0){
return false;
}
}
return true;
}
bool is(int n){
for(int i=2;i<=sqrt(n)+1;i++){
if(n%i==0){
int j = n/i;
if(swap(n,i,j)){
return true;
}
}
}
return false;
}
int main(){
int sum=0;
for(int i=1;i<=1000000;i++){
if(is(i)){
sum++;
}
}
cout << sum << endl;
return 0;
}
B 钉板上的正方形
爆搜
#include <bits/stdc++.h>
using namespace std;
int a[][20]={
{1,1,0,1,0,1,1,1,1,1},
{1,1,1,0,0,1,1,1,1,0},
{1,1,0,0,1,0,1,1,1,1},
{1,0,1,1,0,1,1,1,1,0},
{1,0,1,0,1,1,1,1,0,0},
{1,0,0,1,0,1,0,1,0,1},
{1,1,1,1,1,1,1,1,1,0},
{0,1,1,1,1,1,1,1,1,0},
{0,1,1,0,1,0,1,1,1,1},
{1,0,1,0,0,1,0,1,0,0},
};
map<int, int> mp;
int ans;
int main(){
for(int i=0;i<10;i++){
for(int j=0;j<10;j++){
if(a[i][j]==0){
continue;
}
for(int k=i+1;k<10;k++){
for(int p=0;p<=j;p++){
if(a[k][p]==0){
continue;
}
if (a[k + j - p][p + k - i] == 1 && a[i + j - p][j + k - i] == 1){
int len = (j - p) * (j - p) + (k - i) * (k - i);
if (mp[len] == 0) {
ans++;
mp[len] = 1;
}
}
}
}
}
}
cout << ans;
return 0;
}
扩展map的用法
map容器是一个键值对key—value的映射，其内部实现是一颗以key为关键吗的红黑树。map的key和value可以是任意类型，其中key必须定义小于号运算符。
map的声明
map<key_type,value_type> name;
//列子
map<int int> mp;
map<string,int> mp;
方法
size/empty/clear/begin/end/insert/erase/find/[]
C 整数变换
求每个数的位的数字。详细见A题。注意数据范围
#include <iostream>
#include <algorithm>
using namespace std;
long long n,sum;
int main(){
cin >> n;
while(n>0){
long long x=n;
while(x!=0){
int aa=x%10;
n-=aa;
x/=10;
}
sum++;
}
cout << sum <<endl;
return 0;
}
D 躲炮弹
**最初思路：**遍历从L到R，但是如果随机遍历每个L到R中的每个数，最后得到的最小移动数是不一样。即行不通。
解题思路：
分三种情况：
- 当n<l时。不用移动，输出0.
- 当n>=l&&n<=r时。即考虑移动l-1的步数和移动到r右边的符合条件之间的最小数。
- 当n>r时。即往左右移动找符合最小移动的步数。
完整代码
#include <bits/stdc++.h>
using namespace std;
long long n,l,r;
long long ans;
bool check(int x){
for(int i=1;i<=sqrt(x);i++){
if(x%i==0){
int t = x/i;
if(i>=l && i<=r){
return true;
}
if(t>=l && t<=r){
return true;
}
}
}
return false;
}
int main(){
cin >> n >> l >> r;
if(n<l){
cout << 0 << endl;
return 0;
}
if(n>=l&&n<=r){
ans = n-(l-1);
for(int i=1;i<=2000;i++){
if(!check(r+i)){
ans = min(r+i-n,ans);
break;
}
}
cout << ans <<endl;
return 0;
}
for(int i=1;i<=2000;i++){
if(!check(n+i) || !check(n-i)){
cout << i << endl;
return 0;
}
}
return 0;
}
E 最大区间
单调栈对两个方向上各使用使用一次单调栈求得距离i位置最近的比它小的数。
完整代码：
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
long long a[N],l[N];
int main(){
long long n,ans=0;
cin >> n;
for(int i=0;i<n;i++){
cin >> a[i];
}
stack<pair<int,int>> s;
stack<pair<int,int>> ss;
s.push({-1,-1});
ss.push({-1,-1});
for(int i=0;i<n;i++)
{
while(s.size()&&a[i]<=s.top().first)
s.pop();
l[i]=a[i]*(i-s.top().second);
s.push({a[i],i});
}
for(int i=n-1;i>=0;i--)
{
while(ss.size()&&a[i]<=ss.top().first)
ss.pop();
ans=max(ans,(long long)l[i]+a[i]*(ss.top().second-i-1));
ss.push({a[i],i});
}
cout<<ans;
return 0;
}
扩展 栈的使用先进后出
声明
stack<int> s;
stack<pair<int,int>> ss;
s.push();
s.pop();
选段排序
思路：主要利用大顶堆和小顶堆进行扩展区间。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define int long long
#define endl '\n'
#define INF 0x3f3f3f3f3f3f3f3f
const int N=2e5+10;
priority_queue<int,vector<int>,less<int>> q1;//大顶堆
priority_queue<int,vector<int>,greater<int>> q2;//小顶堆
int a[N];
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n,p,q;
cin>>n>>p>>q;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+p,a+q+1);
int minn=a[p],maxx=a[q];
int sub=maxx-minn;
for(int i=p;i<=q;i++)
{
q1.push(a[i]);
q2.push(a[i]);
}
for(int i=q+1;i<=n;i++)//[p,q]拓展右边界[L,q]
{
int t=q1.top();
if(a[i]<minn) minn=a[i];
if(a[i]<t){
q1.pop();
q1.push(a[i]);
sub=max(sub,q1.top()-minn);
}
}
for(int i=p-1;i>=1;i--)//[p,q]拓展左边界[p,R]
{
int t=q2.top();
if(a[i]>maxx) maxx=a[i];
if(a[i]>t){
q2.pop();
q2.push(a[i]);
sub=max(sub,maxx-q2.top());
}
}
cout<<sub;
return 0;
}