[蓝桥杯][2014年第五届真题]拼接平方数

题目链接：拼接平方数

解题思路：因为数据范围1e6，所有只需要先把1e3内的平方数求出来，然后再检查a~b的每一个数。从最后一位数开始把当前数分割，如果不合法，就从最后两位数开始分割，直到整个数分割完后，还是不合法那就不合法。

#include<bits/stdc++.h> #define x first #define y second #define mem(h) memset(h,-1,sizeof h) #define mcp(a,b) memcpy(a,b,sizeof b) using namespace std; typedef long long LL; typedef unsigned long long ull; typedef pair<int,int>PII; typedef pair<double,double>PDD; namespace IO{ inline LL read(){ LL o=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){o=o*10+c-'0';c=getchar();} return o*f; } }using namespace IO; //#############以上是自定义技巧（可忽略）########## const int N=1e3+7,M=2e5+7,INF=0x3f3f3f3f,mod=1e9+7,P=131; map<int,bool>st; int a,b; bool check(int num){ int k=10;//从最后一位开始分割 while(num/k){//直到整个数分割完 if(st[num%k]&&st[num/k])return true;//分割的位置前部分和后部分都要满足是平方数 k*=10;//分割位置往前推一位 } return false; } int main(){ cin>>a>>b; for(int i=1;i<N;i++)st[i*i]=1;//把这个平方数标记 for(int i=a;i<=b;i++){ if(st[i]){//如果这个数是平方数 if(check(i)){//检查这个数 cout<<i<<endl; } } } return 0; }