第一题 好数 https://www.dotcpp.com/oj/problem3209.html、
考试的时候用的to_string 考完试发现会超时…以后还是老老实实取每一位吧(哭)
#include<iostream>
using namespace std;
const int N=1e7+10;
int q[N];
int n,cnt;
/*
bool check(int x)
{
int j=1;
string s=to_string(x);
for(int i=s.size()-1;i>=0;i--)
{
int t=s[i]-'0';
if(j%2)
{
if(t%2==0) return false;
}
else
{
if(t%2) return false;
}
j++;
}
return true;
}
*/
bool check(int x)
{
int j=1;
while(x)
{
int t=x%10;
if(j%2)
{
if(t%2==0) return false;
}
else
{
if(t%2) return false;
}
x/=10;
j++;
}
return true;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
if(check(i)) cnt++;
}
cout<<cnt<<endl;
return 0;
}
第二题 R格式 https://www.dotcpp.com/oj/problem3210.html
考试只会暴力 可以拿50%
#include<iostream>
#include<cmath>
using namespace std;
const int N=1e7+10;
int q[N];
int n,cnt;
int main()
{
int n;
double d;
cin>>n>>d;
int x=(int)(d*pow(2,n)+0.5);
cout<<x<<endl;
return 0;
}
第三题 宝石组合 https://www.dotcpp.com/oj/problem3211.html
只会暴力 考完后测试能拿30%
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=2010;
typedef long long LL;
int q[N];
int n;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int lcm(int a,int b)
{
return (LL)(a*b)/gcd(a,b);
}
int main()
{
cin>>n;
for(int i=0;i<n;i++) cin>>q[i];
sort(q,q+n);
int res=0;
int x,y,z;
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++)
for(int k=j+1;k<n;k++)
{
int a=q[i],b=q[j],c=q[k];
int tmp=a*b*c*lcm(lcm(a,b),c)/(lcm(a,b)*lcm(b,c)*lcm(a,c));
//cout<<a<<" "<<b<<" "<<c<<endl;
//cout<<tmp<<endl;
if(tmp>res)
{
res=tmp;
x=a,y=b,z=c;
}
}
cout<<x<<" "<<y<<" "<<z<<endl;
return 0;
}
第四题 数字接龙 https://www.dotcpp.com/oj/problem3212.html
当时因为check的参数问题 调试了一个小时,最后调出来以为写对了,结果考完试发现最后一个点不一定是k-1,但是考试的时候当成必须是k-1做的(呜呜呜),考完去网站上一测试就算没有特判也只能过70%,不知道哪里出问题了
但是这个网站我特判k-1和不特判k-1都是73%,可能是因为这个网站光-1就有55%,蓝桥杯官方测试点应该不会这样,能能拿个30%我就满足了
#include<iostream>
using namespace std;
const int N=15;
int g[N][N];
bool st[N][N];
int n,k;
int res[N];
int dx[8]={-1,-1,0,1,1,1,0,-1},dy[8]={0,1,1,1,0,-1,-1,-1};
bool check(int a,int b,int x)
{
if(x==1)
{
if(st[a-1][b]&&st[a][b+1]) return false;
}
if(x==3)
{
if(st[a+1][b]&&st[a][b+1]) return false;
}
if(x==5)
{
if(st[a][b-1]&&st[a+1][b]) return false;
}
if(x==7)
{
if(st[a][b-1]&&st[a-1][b]) return false;
}
return true;
}
bool dfs(int u,int a,int b,int last)
{
if(u<n*n&&(a==n-1&&b==n-1)) return false;
if(u==n*n)
{
if(a==n-1&&b==n-1)
{
return true;
}
return false;
}
st[a][b]=true;
//cout<<u<<" "<<a<<" "<<b<<" "<<last<<endl;
for(int i=0;i<8;i++)
{
int x=a+dx[i];
int y=b+dy[i];
if(x>=0&&x<n&&y>=0&&y<n&&!st[x][y])
{
if(last!=k-1&&last+1!=g[x][y]) continue;
if(last==k-1&&g[x][y]!=0) continue;
if(!check(a,b,i)) continue;
res[u]=i;
if(dfs(u+1,x,y,g[x][y])) return true;
}
}
st[a][b]=false;
return false;
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
cin>>g[i][j];
}
if(g[0][0]!=0&&g[n-1][n-1]!=k-1)
{
cout<<-1<<endl;
return 0;
}
else
{
if(dfs(1,0,0,0))
{
for(int i=1;i<n*n;i++)
{
cout<<res[i];
}
}
else cout<<-1<<endl;
}
return 0;
}
第五题 爬山 https://www.dotcpp.com/oj/problem3213.html
优先队列+贪心,唯一一道比较乐观的题了,虽说赛后有人hack了这个做法,但是蓝桥杯官方也是给的这个做法,自己去测只有一个测试点没过,所以还是能拿大部分分的 92%
#include<iostream>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
const int N=1e5+10;
typedef long long LL;
int n,k1,k2;
int main()
{
cin>>n>>k1>>k2;
priority_queue<int>heap;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
heap.push(x);
}
int k=k1+k2;
while(k)
{
int t=heap.top();
heap.pop();
if(t==1&&k2>0)
{
t=t/2;
heap.push(t);
k2--;
k--;
continue;
}
if(k1>0)
{
t=sqrt(t);
heap.push(t);
k1--;
k--;
continue;
}
else
{
t=t/2;
heap.push(t);
k2--;
k--;
}
}
LL res=0;
while(heap.size())
{
int t=heap.top();
heap.pop();
res+=t;
}
cout<<res<<endl;
return 0;
}
第六题 拔河 https://www.dotcpp.com/oj/problem3214.html
看错题意了,考试的时候首先以为是从数组中任意选组成俩队,后来又仔细看题目好像说的是必须连续选,想了半天就按连续选做的,但我一想连续选这不就是前缀和么,一个数组分成两个,那我枚举两个区间的分界点不就得了么,写完后其实也觉得不太对,因为这样的话也太简单了吧,果然,考完后才知道题目没说数组里的数必须全部选完。。可以只选一部分
10%
#include<iostream>
#include<cmath>
using namespace std;
const int N=1e3+10;
typedef long long LL;
int q[N];
LL s[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>q[i];
s[i]=s[i-1]+q[i];
}
LL res=1e15;
for(int i=1;i<=n-1;i++)
{
LL a=s[n]-s[i];
LL b=s[i];
res=min(res,abs(a-b));
}
cout<<res<<endl;
return 0;
}
2024.4.15晚 估分蓝桥杯45左右 省一没希望了