E 好人hard

题意：输出1~n范围的所有回文数，\(1≤n≤10^{14}\).
大致思路如下。（用 dig 表示 n 的位数）代码片段 1 会按顺序输出\(0\sim\underbrace{99\dots 9}_{dig 个 9}\)范围内的回文数：

void rev(int n)
{
  int s=0;
  for (; n; n/=10) s = s*10 + n/10;
  return s;
}
int pow10[8] = {1, 10, 100, 1e3, 1e4, 1e5, 1e6, 1e7};
...
for (int d=1; d<dig; ++d)
{ 
  int half = d/2;
  int lb = pow10[half], ub = pow10[half+1] - 1;
  if (d%2==1)
    for (int i=lb; i<=ub; ++i)
      for (int j=0; j<=9; ++j)
        cout << i << j << rev(i) << endl;
  else
    for (int i=lb; i<=ub; ++i)
      cout << i << rev(i) << endl;
}

为了避免输出 0，可以单独处理 1 位数的回文数：

if (n<10)
{
  for (int i=1; i<=n; ++i)
    cout << i << endl;
  return 0;
}
for (int i=1; i<=9; ++i) cout << i << endl;
for (int d=2; d<dig; ++d)
{...下同代码片段 1

在 d 等于 n 的位数 dig 时，需要额外处理边界。
考虑到 ≤n 的最大的回文数，该回文数的前 \(\lceil\frac{n}{2}\rceil\) 位与 n 的前 \(\lceil\frac{n}{2}\rceil\) 位相同（代码中记作 nHalf），有一种简单的写法是：
当 dig 为偶数时，把 i 的上界设置为 nHalf；
当 dig 为奇数时略复杂，把 i*10+j 的上界设置为 nHalf，实际写成代码时是用 if 搞搞

for (int d=2; d<dig; ++d) {...} //类似代码片段 1，但是循环边界改了
int half = dig / 2;
int nHalf = n / pow[half];
int lb = pow10[half], ub = pow10[half+1] - 1;
if (dig%2==1)
  for (int i=lb; i<=ub; ++i)
    for (int j=0; j<=9; ++j)
    {
      if (i*10+j>n) return 0;
      cout << i << j << rev(i) << endl;
    }
else
  for (int i=lb; i<=nHalf; ++i)
    cout << i << rev(i) << endl;