第十二届蓝桥杯 2021年省赛B组c++部分题解
发布时间
阅读量：
阅读量
第一题：空间
解析：1mb=1024kb=1024*1024b，1b（字节）=8bit（位）
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long a=pow(2,20);
a=a/4;
cout<<a*256;
return 0;
}第二题：卡片
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n=2021041820210418;
ll a[10000];
int main()
{
int cnt=0;
for(ll i=1;i*i<=n;i++)
{
if(n%i==0)
{
a[cnt++]=i;
if(i!=n/i) a[cnt++]=n/i;
}
}
int ans=0;
for(int i=0;i<cnt;i++)
{
for(int j=0;j<cnt;j++)
{
if(a[i]*a[j]>n) continue;
for(int k=0;k<cnt;k++)
{
if(a[i]*a[j]*a[k]==n) ans++;
}
}
}
cout<<ans;
return 0;
}第三题：直线
#include<bits/stdc++.h>
using namespace std;
struct node{
double x,y;
};
map<pair<double,double>,int>mp;
node p[500];
int main()
{
int cnt=0;
int ans=0;
for(int i=0;i<20;i++)
{
for(int j=0;j<21;j++)
{
p[cnt].x=i;
p[cnt].y=j;
cnt++;
}
}
for(int i=0;i<cnt;i++)
{
for(int j=0;j<cnt;j++)
{
if((p[i].x==p[j].x)||(p[i].y==p[j].y)) continue;
double k=(p[j].y-p[i].y)/(p[j].x-p[i].x);
double b=(p[j].y*(p[j].x-p[i].x)-p[j].x*(p[j].y-p[i].y))/(p[j].x-p[i].x);
//double b = p[j].y - k * p[j].x; 不用这种方法，避免k造成精度爆炸
if(mp[{k,b}]==0)
{
mp[{k,b}]=1;
ans++;
}
}
}
ans+=20+21;//直线
cout<<ans;
return 0;
}第四题：货物摆放
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n=2021041820210418;
ll a[10000];
int main()
{
int cnt=0;
for(ll i=1;i*i<=n;i++)
{
if(n%i==0)
{
a[cnt++]=i;
if(i!=n/i) a[cnt++]=n/i;
}
}
int ans=0;
for(int i=0;i<cnt;i++)
{
for(int j=0;j<cnt;j++)
{
if(a[i]*a[j]>n) continue;
for(int k=0;k<cnt;k++)
{
if(a[i]*a[j]*a[k]==n) ans++;
}
}
}
cout<<ans;
return 0;
}第五题：路径
解法一：Floyd（运行时间较长）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll INF=1e9;
ll a[2050][2050];
int gcd(int a,int b)
{
if(a%b==0) return b;
return gcd(b,a%b);
}
int main()
{
for(int i=1;i<=2021;i++)
{
for(int j=1;j<=2021;j++)
{
if(i==j) a[i][j]=0;
else if(abs(j-i)>21) a[i][j]=INF;
else{
a[i][j]=(i*j)/gcd(j,i);
}
}
}
for(int k=1;k<=2021;k++)
{
for(int i=1;i<=2021;i++)
{
for(int j=1;j<=2021;j++)
{
a[i][j]=min(a[i][k]+a[k][j],a[i][j]);
}
}
}
cout<<a[1][2021];
return 0;
}解法二：Dijkstra
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int INF=1e9;
int a[2050][2050];
int vis[2050];
int d[2050];
int gcd(int a,int b)
{
if(a%b==0) return b;
return gcd(b,a%b);
}
void dijk(int s)
{
fill(d,d+2050,INF);
d[s]=0;
for(int i=1;i<=2021;i++)
{
int u=-1,mind=INF;
for(int j=1;j<=2021;j++)
{
if(!vis[j]&&d[j]<mind)
{
u=j;
mind=d[j];
}
}
if(u==-1) return;
vis[u]=1;
for(int v=1;v<=2021;v++)
{
if(!vis[v]&&a[u][v]!=INF&&d[v]>d[u]+a[u][v])
{
d[v]=d[u]+a[u][v];
}
}
}
}
int main()
{
for(int i=1;i<=2021;i++)
{
for(int j=1;j<=2021;j++)
{
if(i==j) a[i][j]=0;
else if(abs(j-i)>21) a[i][j]=INF;
else{
a[i][j]=(i*j)/gcd(j,i);
}
}
}
dijk(1);
cout<<d[2021];
return 0;
}第六题：时间显示
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll n;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
ll d=24*60*60*1000;
n=n%d;
n=n/1000;
int hh=n/3600;
int mm=(n/60)%60;
int ss=n%60;
printf("%02d:%02d:%02d\n",hh,mm,ss);
}
return 0;
}第七题：砝码称重
解法一（50%）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6;
int vis[maxn];//记录每种称重是否出现过
int a[maxn];//N个砝码的重量
int N;//砝码的数量
void dfs(int sum, int i)//sum：当前已选用砝码的总重量 i：下一个将要选用砝码的序号
{
if (i == N)
{
if (sum >= 0)
vis[sum] = 1;
return;
}
dfs(sum + a[i], i + 1);//把a[i]放在右边
dfs(sum, i + 1); //不选a[i]
dfs(sum - a[i], i + 1);//把a[i]放在左边
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++) cin >> a[i];
dfs(0, 0);
int ans = 0;
for (int i = 1; i < maxn; i++)
{
if (vis[i]) ans++;
}
cout << ans << endl;
return 0;
}解法二：（100%）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[100005];//表示重量为j的称重能不能实现，取值为1或0
ll w[105];//N个砝码的重量
int main()
{
ll N;
cin >> N;
for (ll i = 1; i <= N; i++) cin >> w[i];
dp[0] = 1;
for (ll i = 1; i <= N; i++) {//考虑每个砝码
//从大到小考虑每个称重j，j>=w[i]
//如果从小到大，则意味着w[i]可以加很多次
for (ll j = 100000; j >= w[i]; j--)//此前没有加w[i]，现在考虑加
//如果此前dp[j - w[i]]为1，则加上w[i]的重量，能达到j，所以dp[j]为1
dp[j] = max(dp[j], dp[j - w[i]]);
}
for (ll i = 1; i <= N; i++) {
ll siz = 100000 - w[i];
for (ll j = 1; j <= siz; j++)//此前不放w[i]或放，现在减，相当于放左边和不放
//如果此前dp[j + w[i]]为1，则减去w[i]的重量，能达到j，所以dp[j]为1
dp[j] = max(dp[j], dp[j + w[i]]);
}
ll ans = 0;
for (ll i = 1; i <= 100000; i++)
ans += dp[i];
cout << ans << endl;
return 0;
}第八题：杨辉三角形
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll N;
ll C(int a, int b)
{
ll res = 1;
for (ll i = a, j = 1; j <= b; i--, j++)
{
res = res * i / j;
if (res > N)
return res;
}
return res;
}
int main()
{
cin >> N;
for (int k = 16; k >= 0; k--)
{
ll l = 2 * k, r = max(N, l), mid;
while (l <= r) {
mid = l + (r - l) / 2;
ll CC = C(mid, k);
if (CC == N)
break;
else if (CC > N)
r = mid - 1;
else
l = mid + 1;
}
if (C(mid, k) == N)
{
cout << (mid + 1) * mid / 2 + k + 1 << endl;
break;
}
}
return 0;
}全部评论 (0)
还没有任何评论哟~