基础算法(三)#蓝桥杯

文章目录

- 11、构造
- - 11.1、小浩的ABC
  - 11.2、小新的质数序列挑战
  - 11.3、小蓝找答案
  - 11.4、小蓝的无限集
- 12、高精度
- - 12.1、阶乘数码(高精度*单精度)

11、构造

11.1、小浩的ABC

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using ll = long long;int main(){IOS;int t;cin>>t;while(t--){ll x;cin>>x;// A B C  <=10^6if(x<2){cout<<"-1"<<'\n';continue;}if(x<=1000000){cout<<x-1<<" 1 1"<<'\n';continue;}ll a=1000000,c=x%a,b;if(c==0)c=a;b=(x-c)/a;cout<<a<<' '<<b<<' '<<c<<'\n';}return 0;
}

11.2、小新的质数序列挑战

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
using ll = long long;int main(){IOS;int T;cin>>T;while(T--){//质数序列，只能被1或本身整除的序列ll a,b;cin>>a>>b;if(a==1||b==1){cout<<"-1\n";continue;}auto gcd = [&](ll a,ll b){while(b!=0){ll t=a%b;a=b;b=t;}return a;};ll g=gcd(a,b);if(g==1){cout<<"1\n";}else{cout<<"0\n";}}return 0;
}

11.3、小蓝找答案

#include <bits/stdc++.h>using LL = long long;
using Pair = std::pair<int, int>;
#define inf 1'000'000'000void solve(const int &Case) {int n;std::cin >> n;std::vector<int> a(n);for (auto &x: a)std::cin >> x;auto ck = [&]() {for (int i = 1; i < n; i++) {if (a[i] <= a[i - 1])return false;}return true;};if (ck()) {std::cout << "1\n";return;}int l = 2, r = n, ret = n;while (l <= r) {int mid = (l + r) >> 1;std::vector<Pair> A;int flag = 0;std::function<void(int)> push = [&](int x) {if (x <= 0) {flag = 1;return;}while (!A.empty() && A.back().first > x)A.pop_back();if (A.empty()) {A.emplace_back(x, 1);return;}if (A.back().first == x) {A.back().second++;if (A.back().second == mid) {push(x - 1);A.emplace_back(x, 0);}}else {A.emplace_back(x, 1);}};A.emplace_back(a[0], 0);for (int i = 1; i < n; i++) {if (a[i] > a[i - 1])A.emplace_back(a[i], 0);else push(a[i]);if (flag)break;}if (flag)l = mid + 1;else {ret = mid;r = mid - 1;}}std::cout << ret << '\n';
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T = 1;
//    std::cin >> T;for (int Case = 1; Case <= T; Case++)solve(Case);return 0;
}

11.4、小蓝的无限集

#include <bits/stdc++.h>using LL = long long;
using Pair = std::pair<int, int>;
#define inf 1'000'000'000void solve(const int &Case) {int a, b, n;std::cin >> a >> b >> n;if (a == 1) {if (n % b == 1)std::cout << "Yes\n";else std::cout << "No\n";return;}// 枚举 a ^ iLL pw = 1;while (pw <= n) {if ((n - pw) % b == 0) {std::cout << "Yes\n";return;}pw *= a;}std::cout << "No\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int T = 1;std::cin >> T;for (int Case = 1; Case <= T; Case++)solve(Case);return 0;
}

12、高精度

12.1、阶乘数码(高精度*单精度)

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
void mult(vector<int>& a,int b){int d=0;for(int i=0;i<a.size();i++){int p=a[i]*b+d;a[i]=p%10;d=p/10;}while(d){a.push_back(d%10);d/=10;}
}
int main() {IOS;int t;cin>>t;while(t--){int n,a1;cin>>n>>a1;vector<int> ans(1,1);for(int i=2;i<=n;i++){mult(ans,i);//n的阶乘}int res=0;for(const auto &x:ans){if(x==a1)res++;}cout<<res<<"\n";}return 0;
}