P8615题解

· · 题解

（upd：2023.9.9 增添常数更小的取模分割法）

题目大意

找出一段区间的“拼接平方数”，“拼接平方数”指一个数是平方数，而且它能拆成两部分，那两个部分也是平方数，但是不能包括 0。

思路

由于数据范围较小，可以预处理一下所有的平方数，再枚举区间内的每一个平方数的所有分割方式，判断是否能由两个平方数组成。

时间复杂度为：O(r)。

实现过程

一、判断是否为平方数，为预处理平方数及“拼接平方数”做准备。

因为平方数的平方根为整数，所以将一个平方数的平方根转化为整数并不会导致精度丢失，而非平方数的平方根转化为整数则会丢失小数部分的精度。

时间复杂度：O(1)。

可以写出如下代码：

bool pfs(int x) { //判断平方数函数
    return (int)sqrt(x) == sqrt(x);
}

二、预处理出范围内的所有平方数。

直接从 1 开始 for 循环到 r，判断每一个数是否为平方数，如果是就将其标记下来。

时间复杂度：O(r)。

代码如下：

bool f[1000005];
for (int i = 1; i <= r; i++) {//预处理1到r之间的所有平方数
    if (pfs(i))
        f[i] = 1;
}

三、判断所有的“拼接平方数”。

从 l 枚举到 r，判断区间内每一个数是否为“拼接平方数”，如果是将其输出。

判断方法：先判断是否为平方数，如果是枚举每一种分割方式，判断是否为两个平方数组成，如果是就是“拼接平方数”。

利用 STL 的字符串与数字转化函数或模运算和除法的性质，可以轻松完分割操作。

时间复杂度：O(r-l)。

代码如下：

字符串：

    for (int i = l; i <= r; i++)//判断l到r的所有“拼接平方数”并输出
        if (f[i]) {
            s = to_string(i);
            int sl = s.size();
            for (int j = 1; j < sl; j++) {
                int x = stoi(s.substr(0, j));
                int y = stoi(s.substr(j));
                if (f[x] && f[y]) {
                    printf("%d\n", i);
                    break;
                }
            }
        }

模运算和除法（常数更小）：

    for (int i = l; i <= r; i++)//判断l到r的所有“拼接平方数”并输出
        if (f[i]) {
            int k = 10;
            for (int j = 1; j <= 5; j++) {
                int x = i % k;
                int y = i / k;
                k *= 10;
                if (f[x] && f[y]) {
                    printf("%d\n", i);
                    break;
                }
            }
        }

至此，此题已经基本完成。将各部分代码整理一下，就可以得到完整的 AC 代码。

AC 代码如下：

字符串分割法：

#include<bits/stdc++.h>
using namespace std;
bool f[1000005];
int l, r;
string s;
bool pfs(int x) {
    return (int)sqrt(x) == sqrt(x);
}
int main() {
    cin >> l >> r;
    for (int i = 1; i <= r; i++) {
        if (pfs(i))
            f[i] = 1;
    }
    for (int i = l; i <= r; i++)
        if (f[i]) {
            s = to_string(i);
            int sl = s.size();
            for (int j = 1; j < sl; j++) {
                int x = stoi(s.substr(0, j));
                int y = stoi(s.substr(j));
                if (f[x] && f[y]) {
                    printf("%d\n", i);
                    break;
                }
            }
        }
    return 0;
}

取模分割法：

#include<bits/stdc++.h>
using namespace std;
bool f[1000005];
int l, r;
string s;
bool pfs(int x) {
    return (int)sqrt(x) == sqrt(x);
}
int main() {
    cin >> l >> r;
    for (int i = 1; i <= r; i++) {
        if (pfs(i))
            f[i] = 1;
    }
    for (int i = l; i <= r; i++)
        if (f[i]) {
            int k = 10;
            for (int j = 1; j <= 5; j++) {
                int x = i % k;
                int y = i / k;
                k *= 10;
                if (f[x] && f[y]) {
                    printf("%d\n", i);
                    break;
                }
            }
        }
    return 0;
}

如有错误，请各位多多指教。
另附打表代码