回文数 构造

题目	难度
866. 回文素数	中等
906. 超级回文数	困难
2217. 找到指定长度的回文数	中等
2967. 使数组成为等数数组的最小代价	中等
CF1673C	rating 1500

模板

    for (int L = 1; L <= 5; L++) {
        int low = (int) Math.pow(10, L - 1);
        int high = (int) Math.pow(10, L);
        // Check for odd-length palindromes
        for (int root = low; root < high; root++) {
            long p = root;
            for (int x = root / 10; x > 0; x /= 10) {
                p = p * 10 + x % 10;
            }
            pal.add(p);
        }
        // Check for even-length palindromes
        for (int root = low; root < high; root++) {
            long p = root;
            for (int x = root; x > 0; x /= 10) {
                p = p * 10 + x % 10;
            }
            pal.add(p);
        }
    }

866. 回文素数

public class Solution866 {
    public int primePalindrome(int n) {
        for (int L = 1; L <= 5; L++) {
            int low = (int) Math.pow(10, L - 1);
            int high = (int) Math.pow(10, L);
            // Check for odd-length palindromes
            for (int root = low; root < high; root++) {
                int p = root;
                for (int x = root / 10; x > 0; x /= 10) {
                    p = p * 10 + x % 10;
                }
                if (p >= n && isPrime(p)) {
                    return p;
                }
            }
            // Check for even-length palindromes
            for (int root = low; root < high; root++) {
                int p = root;
                for (int x = root; x > 0; x /= 10) {
                    p = p * 10 + x % 10;
                }
                if (p >= n && isPrime(p)) {
                    return p;
                }
            }
        }
        return -1;
    }

    // 判断素数
    private static boolean isPrime(long num) {
        if (num < 2) {
            return false;
        }
        for (long i = 2; i * i <= num; ++i) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}

906. 超级回文数

import java.util.ArrayList;
import java.util.List;

public class Solution906 {
    static List<Long> pal;

    static {
        pal = new ArrayList<>();
        for (int i = 1; i < 1e5; i++) {
            // odd len
            long p = i;
            for (int x = i / 10; x > 0; x /= 10) {
                p = p * 10 + x % 10;
            }
            p *= p;
            if (isPal(p)) pal.add(p);
            // even len
            p = i;
            for (int x = i; x > 0; x /= 10) {
                p = p * 10 + x % 10;
            }
            p *= p;
            if (isPal(p)) pal.add(p);
        }
        pal.sort(null);
    }

    public int superpalindromesInRange(String left, String right) {
        long L = Long.parseLong(left);
        long R = Long.parseLong(right);
        return lowerBound(pal, R) - lowerBound(pal, L - 1);
    }

    private int lowerBound(List<Long> a, long key) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a.get(m) >= key) r = m;
            else l = m + 1;
        }
        return l;
    }

    private static boolean isPal(long x) {
        return x == reverse(x);
    }

    private static long reverse(long x) {
        long res = 0;
        while (x > 0) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}

2217. 找到指定长度的回文数

import java.util.Arrays;

public class Solution2217 {
    public long[] kthPalindrome(int[] queries, int intLength) {
        int L = (intLength + 1) / 2;
        int low = (int) Math.pow(10, L - 1);
        int high = (int) Math.pow(10, L);

        int q = queries.length;
        long[] ans = new long[q];
        Arrays.fill(ans, -1);
        for (int i = 0; i < q; i++) {
            int root = low + queries[i] - 1;
            if (root < high) {
                long p = root;
                if (L * 2 > intLength) {
                    // Check for odd-length palindromes
                    for (long x = p / 10; x > 0; x /= 10) {
                        p = p * 10 + x % 10;
                    }
                } else {
                    // Check for even-length palindromes
                    for (long x = p; x > 0; x /= 10) {
                        p = p * 10 + x % 10;
                    }
                }
                ans[i] = p;
            }
        }
        return ans;
    }
}

2967. 使数组成为等数数组的最小代价

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution2967 {
    static List<Long> pal;

    static {
        // size = 199998, max = 9999999999
        pal = new ArrayList<>();
        for (int L = 1; L <= 5; L++) {
            int low = (int) Math.pow(10, L - 1);
            int high = (int) Math.pow(10, L);
            // Check for odd-length palindromes
            for (int root = low; root < high; root++) {
                long p = root;
                for (int x = root / 10; x > 0; x /= 10) {
                    p = p * 10 + x % 10;
                }
                pal.add(p);
            }
            // Check for even-length palindromes
            for (int root = low; root < high; root++) {
                long p = root;
                for (int x = root; x > 0; x /= 10) {
                    p = p * 10 + x % 10;
                }
                pal.add(p);
            }
        }
        pal.sort(null);
    }

    public long minimumCost(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        long median = nums[n / 2];
        int i = lowerBound(pal, median);
        long ans = Long.MAX_VALUE;
        for (int j = Math.max(0, i - 1); j <= i + 1; j++) {
            long y = pal.get(j);
            ans = Math.min(ans, getCost(nums, y));
        }
        return ans;
    }

    private long getCost(int[] nums, long y) {
        long cost = 0;
        for (int v : nums) {
            cost += Math.abs(y - v);
        }
        return cost;
    }

    private int lowerBound(List<Long> a, long key) {
        int l = 0, r = a.size();
        while (l < r) {
            int m = l + (r - l) / 2;
            if (a.get(m) >= key) r = m;
            else l = m + 1;
        }
        return l;
    }
}

CF1673C

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class CF1673C {
    static int n;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            n = scanner.nextInt();
            System.out.println(solve());
        }
    }

    static final int MAX_N = (int) (4e4 + 5);
    static final int MOD = (int) (1e9 + 7);
    static List<Integer> pal;
    static long[] f;

    static {
        pal = new ArrayList<>();
        for (int i = 1; i < 400; i++) {
            int p = i;
            for (int x = i / 10; x > 0; x /= 10) {
                p = p * 10 + x % 10;
            }
            pal.add(p);
            if (i < 100) {
                p = i;
                for (int x = i; x > 0; x /= 10) {
                    p = p * 10 + x % 10;
                }
                pal.add(p);
            }
        }
        // 完全背包
        f = new long[MAX_N];
        f[0] = 1;
        for (Integer v : pal) {
            for (int j = v; j < MAX_N; j++) {
                f[j] = (f[j] + f[j - v]) % MOD;
            }
        }
    }

    private static String solve() {
        return String.valueOf(f[n]);
    }
}

（全文完）