第十四届蓝桥杯大赛软件赛国赛C/C++研究生组

题一：混乘数字

有一点像哈希表：
首先定义两个数组，拆分ab和n
然后令n = a*b 查看两个表对应的十进制位数和个数是否相同
还需要定义一个set，用于验证当前的n是否已经被计算过了
是因为2 * 8== 4 * 4 == 16

#include<bits/stdc++.h>
using namespace std;
set<int> s;//
int StoredAB[10],StoredN[10];//0-9一共10个珠子
int ans;
//验证
bool test(int n,int a,int b){//初始化两个数组memset(StoredAB,0,sizeof(StoredAB));memset(StoredN,0,sizeof(StoredN));while(n){StoredN[n%10]++;n/=10;}while(a) StoredAB[a%10]++,a/=10;while(b) StoredAB[b%10]++,b/=10;for(int i=0;i<=9;i++){if(StoredAB[i]!=StoredN[i]) return false;}return true;
}
int main()
{for(int a=1;a<1000000;a++){for(int b = 1;b<1000000;b++){int n = a*b;if(n>1000000) break;if(test(n,a,b)){if(s.find(n)==s.end()){ //没有set集合当中的话ans++;s.insert(n);}}}}cout<<ans<<endl;return 0;
}

题二：钉板上的正方形

下面给出的代码在表示其他正方形定点时用到了三角形的旋转

下面给出代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;int a[10][10] = 
{{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}
};struct edge {int x, y;bool operator <(const edge &e) const {return x * x + y * y < e.x * e.x + e.y * e.y;}
};int main() {set<edge> st;auto test = [&](int i, int j) {if(i < 0 || i >= 10 || j < 0 || j >= 10) return false;return a[i][j] == 1;};for(int i = 0;i < 10;i++) {for(int j = 0;j < 10;j++) {if(a[i][j] != 1) continue;for(int x = i;x < 10;x++) {for(int y = j;y < 10;y++) {if(x == i && y == j) continue;if(a[x][y] != 1) continue;int dx = x - i, dy = y - j;if(test(i + dy, j - dx) && test(i + dx + dy, j + dy - dx)) {st.insert(edge{dx, dy});}}}}}cout << st.size() << endl;
}

题三：整数变换

这道题比较简单 直接给代码嗷：

#include <iostream>
using namespace std;
int main()
{// 请在此输入您的代码int n;cin>>n;int mintues = 0;while(n>0){int temp = n;int sum=0;while(temp>0){sum+=temp%10;temp/=10;}n-=sum;mintues++;}cout<<mintues;return 0;
}

题四：躲炮弹

本题有一个点就是他给的距离n是基于数轴上的原点的距离，题意没有说的很清楚
其他的就是需要向左向右寻找能够躲避炮弹的点

#include <iostream>
#include <algorithm>
using namespace std;// 判断m是否安全：不被任何x∈[L, R]整除
bool is_safe(int m, int L, int R) {if (m < L) return true;           // m小于L时安全if (L <= m && m <= R) return false; // m在区间内则不安全for (int d = 1; d * d <= m; ++d) {if (m % d != 0) continue;int a = d;int b = m / d;// 检查因数对是否在区间内，因数都在区间内，则一定不安全if ((a >= L && a <= R) || (b >= L && b <= R)) {return false;}}return true;
}int main() {int n, L, R;cin >> n >> L >> R;// 检查原始位置是否安全bool original_safe = true;if (L <= n && n <= R) { // 在区间内，一定不安全original_safe = false;} else {  // 在区间外，通过遍历因数是否在区间内判断原始位置是否安全original_safe = true;for (int d = 1; d * d <= n; ++d) {if (n % d == 0) {int a = d, b = n / d;if ((a >= L && a <= R) || (b >= L && b <= R)) {original_safe = false;break;}}}}if (original_safe) {cout << 0 << endl;return 0;}// 候选解A：向左移动到最近的安全位置int candidateA = -1;for (int m = n - 1; m >= 0; --m) {if (is_safe(m, L, R)) {candidateA = n - m;break;}}// 候选解B：向右移动到最近的安全位置int candidateB = -1;for (int m = n + 1; ; ++m) {if (is_safe(m, L, R)) {candidateB = m - n;break;}}// 如果候选解A不存在，则只考虑候选解Bif (candidateA == -1) {cout << candidateB << endl;} else if (candidateB == -1) {cout << candidateA << endl;} else {cout << min(candidateA, candidateB) << endl;}return 0;
}

题五：最大区间

/*
使用单调栈求解左右边界
1.列表项找到左边界：找到第一个比当前元素小的位置left[i],则Ai能够作为最小值扩展到left[i]+1位置
2.列表找到右边界：找出第一个比当前元素小的位置right[i],则Ai能够作为最小值扩展到right[i]-1位置
这样Ai作为最小值的最大子数组长度为right[i]-left[i]-1;
*/
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
long long n,a[N],minn;
stack <long long>st;//栈int main( )
{//根据题面得（R-L+1)*a[i]要尽可能大,所以我们可以从l[i]和r[i]下手//我们要求都要比他的区间要r[i]-l[i]-1+1//即可以完成第31行的代码scanf("%lld",&n);vector <int> l(n,-1);//答案数组1for(int i=0;i<n;i++)scanf("%lld",&a[i]);for(int i=0;i<n;i++){while(!st.empty() && a[st.top()]>=a[i])st.pop( );if(!st.empty())l[i]=st.top( );st.push(i);}//找左边第一个比他小的元素的下标（注意是下标）while(!st.empty())st.pop( ); //清空栈，避免干扰。vector <int> r(n,n);//答案数组2for(int i=n-1;i>=0;i--){while(!st.empty() && a[st.top()]>=a[i])st.pop( );if(!st.empty())r[i]=st.top( );st.push(i);}//找右边第一个比他小的元素的下标（注意是下标）for(int i=0;i<n;i++){minn=max(minn,(r[i]-l[i]-1)*a[i]);}printf("%lld",minn);
}