当前位置：首页 > article >正文

蓝桥杯真题——洛谷 day 9 枚举、贪心、找规律

article 2025/3/17 9:19:35

P8615 [蓝桥杯 2014 国 C] 拼接平方数

拼接平方数：本身是平方数，并且可以拆分为平方数

时间复杂度分析：枚举每个数O(n)=1e6，判断是否为平方数
1s可以跑1e8次，能过
后面判断是否是拼接平方数需要用常数级别

怎么判断：先判断本身是否是平方数，再判断拆分是否是平方数
枚举拆分，n位数最多可以有n-1种，拆出来

sqrt函数返回是double，转换为int后可将所有开平方后有小数点的数略去
如sqrt(3)=1.732，int-->1，1*1=1！=3
sqrt(4)=2，int-->2，2^2==4

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stdio.h>
#include<cmath>
using namespace std;

int a,b;

bool check1(string s)
{
   int sum=0;
   for(int i=0;i<s.size();i++)//将字符串s转换为数
   {
       sum*=10;
       sum+=s[i]-'0';
   }

   if(sum==0)//特判，0，00，000不是平方数
       return 0;

   int temp=(int)sqrt(sum);//进行强制类型转换，实现判断是否为平方数
   return temp*temp==sum;
}

bool check2(string s)
{
   for(int i=1;i<s.size();i++)
   {
       string s1=s.substr(0,i);//取出从0开始的有i个字符的子串
       string s2=s.substr(i);//从i开始到结尾的子串，因为i从1开始
       if(check1(s1)&&check1(s2))
           return true;
   }
   return false;
}
int main()
{
   cin>>a>>b;
   for(int i=a;i<=b;i++)
   {
       string s=to_string(i);
       if(check1(s)&&check2(s))
           cout<<i<<endl;
   }
   return 0;
}

P8682 [蓝桥杯 2019 省 B] 等差数列

思路：
由公式可知，在等差数列成立的时候公差越大越好
排完序后要保证相邻两项的差是公差，取min是因为要保证每一项都是等差数列
注意：因为求项公式使用了除法，当都为1时公差是0，需要特判

#include<iostream>
#include<algorithm>

using namespace std;

const int N=2e5+10;
long long int a[N];

int main()
{
   int n;
   cin>>n;
   for(int i=0;i<n;i++)
       cin>>a[i];

   sort(a,a+n);

   long long int sub=1e18;//公差越大越好，先定义为最大值
   for(int i=1;i<n;i++)
       sub=min(sub,a[i]-a[i-1]);

   if(sub==0)//注意：当公差为0时需要特判
       cout<<n<<endl;
   else
       cout<<(a[n-1]-a[0])/sub+1<<endl;
   return 0;
}

为什么有一个WA???

P8720 [蓝桥杯 2020 省 B2] 平面切分

规律：新生成x个交点，就多了x+1个面

特判：重合的线不计入贡献

交点公式

注意：ans的初始化为1

更加具体的思路：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<set>
#include<vector>

#define PII pair<double,double>

using namespace std;
int n;

int main()
{
   cin>>n;
   set<PII> st;
   for(int i=1;i<=n;i++)
   {
       double k,b;
       cin>>k>>b;
       st.insert({k,b});//使用set去重
   }
   //去重后取出，存入vector
   vector<double> k,b;
   for(auto i:st)
   {
       k.push_back(i.first);
       b.push_back(i.second);
   }

   //枚举每一条线，求交点数
   //去完重后有a.size()条线
   set<PII> pos;
   //最开始是有一个面（0条线时）
   int ans=1;
   for(int i=0;i<k.size();i++)
   {
       for(int j=i+1;j<k.size();j++)//取出两条线，不能重复取，则j=i+1
       {
           //平行的情况，没有交点
           if(k[i]==k[j])
               continue;
           //求新增加的交点，不能重复
           double x=(b[j]-b[i])/(k[i]-k[j]);
//           double y=k[i]*((b[j]-b[i])/(k[i]-k[j]))+b[j];
           double y=k[i]*x+b[i];
           //去交点重
           pos.insert({x,y});
       }
       ans+=pos.size()+1;
       pos.clear();//清空交点
   }
   cout<<ans<<endl;
   return 0;
}