直接暴力跑
k2每次前进两步
k1每次前进一步
k2一定能追上k1
这样空间复杂度降到1,没用stl时间也缩短了
AC代码如下:
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; int next( int n, int k ){ int num[20], cnt = 0; long long ne = ( long long ) k * k; while( ne ){ num[cnt++] = ne % 10; ne /= 10; } int ans = 0, temp; temp = min( n, cnt ); while( temp-- ){ ans = ans * 10 + num[--cnt]; } return ans; } int main(){ int N, K, T, ans; scanf( "%d", &T ); while( T-- ){ scanf( "%d%d", &N, &K ); int k1, k2; k1 = k2 = K; ans = K; do{ k1 = next( N, k1 ); k2 = next( N, k2 ); ans = max( ans, k2 ); k2 = next( N, k2 ); ans = max( ans, k2 ); }while( k1 != k2 ); printf( "%d\n", ans ); } return 0; }