第十二届蓝桥杯大赛软件赛省赛第二场C/C++大学B组 题解(大部分)
A 求余
code
#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)void solve(){cout<<2021%20<<endl;}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}//答案:1
B 双阶乘
Code:
#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)void solve(){int ans=1;for(int i=1;i<=2021;i+=2){ans=ans*i%100000;}cout<<ans<<endl;}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}/*59375*/
C 格点
code:
#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)void solve(){int ans=0;for(int i=1;i<=2021;i++){for(int j=1;j<=2021;j++){if(i*j<=2021) ans++;}}cout<<ans<<endl;}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}/*15698*/
其实是可以优化的,但没必要,暴力跑的也快也准
D 整数分解
很常见的背包DP。
code:
#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)void solve(){ll dp[6][2022]; memset(dp, 0, sizeof dp); for(int i = 1;i<2022;i++) dp[1][i] = 1; for(int i =2;i<=5;i++) for(int j =1; j<2022;j++) for(int k = 1;k<2022;k++){ if(j-k > 0) dp[i][j] += dp[i-1][j-k]; } cout<< dp[5][2021];}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}/*691677274345*/
E 城邦
看题一眼就知道这是一道的最小生成树的板子题。
最小生成树有两种算法,一个是Prim算法 O ( n 2 ) O(n^2) O(n2)和克鲁斯卡尔算法 O ( m l o g m ) O(mlogm) O(mlogm)。
这个题用Prim算法就行了,暴力杯,暴力就是了。
Prim算法
适用于稠密图,时间复杂度 O ( n 2 ) O(n^2) O(n2)。
核心思想:每次挑一条与当前集合相连的最短边。
C++ 代码
// st[i] 表示点i是否在当前生成树集合中// dist[i] 表示点i到当前集合的最短边的长度// g[i][j] 表示点i和点j之间边的长度// 返回值:最小生成树中所有边的总长度int Prim(){ int res = 0; for (int i = 1; i <= n; i ++ ) { dist[i] = INF; st[i] = false; } dist[1] = 0; for (int i = 1; i <= n; i ++ ) { int id = -1, min_dist = INF; // 寻找最短边 for (int j = 1; j <= n; j ++ ) if (!st[j] && dist[j] < min_dist) { id = j; min_dist = dist[j]; } st[id] = true; res += dist[id]; // 用新加入的点更新其余点到生成树的最短边 for (int j = 1; j <= n; j ++ ) if (!st[j]) dist[j] = min(dist[j], g[id][j]); } return res;}
Kruskal算法
适用于稀疏图,时间复杂度 O ( m l o g m ) O(mlogm) O(mlogm).
核心思想:从小到大挑不多余的边。
C++ 代码
// 边的信息struct Edge{ int a, b, v; bool operator< (const Edge &W) const { return v < W.v; }};// 并查集——寻找当前集合的代表元素int find(int x){ if (father[x] != x) father[x] = find(father[x]); return father[x];}// 所有边存储在 Edge edges[M]; // 函数返回最小生成树中所有边的总长度int Kruskal(){ int res = 0; // 初始化并查集代表元素 for (int i = 1; i <= n; i ++ ) father[i] = i; sort(edge, edge + m); for (int i = 0; i < m; i ++ ) { int a = edge[i].a, b = edge[i].b; if (find(a) != find(b)) { res += edge[i].v; father[find(a)] = find(b); } } return res;}
代码:
#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)int st[N],dist[N],g[2030][2030],n;// st[i] 表示点i是否在当前生成树集合中// dist[i] 表示点i到当前集合的最短边的长度// g[i][j] 表示点i和点j之间边的长度// 返回值:最小生成树中所有边的总长度int Prim(){ int res = 0; for (int i = 1; i <= n; i ++ ) { dist[i] = INT_MAX; st[i] = false; } dist[1] = 0; for (int i = 1; i <= n; i ++ ) { int id = -1, min_dist = INT_MAX; // 寻找最短边 for (int j = 1; j <= n; j ++ ) if (!st[j] && dist[j] < min_dist) { id = j; min_dist = dist[j]; } st[id] = true; res += dist[id]; // 用新加入的点更新其余点到生成树的最短边 for (int j = 1; j <= n; j ++ ) if (!st[j]) dist[j] = min(dist[j], g[id][j]); } return res;}int get(int i,int j){int ans=0;while(i||j){if(i%10!=j%10) ans+=i%10+j%10;i/=10;j/=10;}return ans;}void solve(){n=2020;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){g[i][j]=get(i,j);//cout<<g[i][j]<<" ";}}cout<<Prim()<<endl;}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}/*4045*/
H 完全平方数
思路:
要使得一个数是完全平方数,那么他所有的质因子都应该是偶数次幂。这样才能开根号,幂次除以 2 能整除。
所以我们把n分解质因数,所有质因子奇数次幂的相乘就是答案,奇数多加一次就变成偶数。
代码:
#includeusing namespace std;typedef long long ll;const int N = 2e6 + 7;const int mod = 1e9 + 7;const int MOD = 998244353;#define sc(x) scanf("%lld", &(x))#define pr(x) printf("%lld\n", (x))#define int long long#define rep(i, l, r) for (int i = l; i <= r; ++i)int a[N],n,m;void solve(){cin>>n;int ans=1;for(int i=2;i*i<=n;i++){if(n%i==0){int cnt=0;while(n%i==0) cnt++,n/=i;if(cnt&1) ans*=i;}}if(n>1) ans*=n;cout<<ans<<endl;}signed main(){int _=1;//cin>>_;while(_--) solve();return 0;}
与50位技术专家面对面 20年技术见证,附赠技术全景图