大意略。
思路:可以发现有循环节,之后在循环节中找最大的即可,可过STL或者哈希表来判重,另一种巧妙的方法是通过Floyd判圈算法来实现。
通过这题熟悉了C++的stringstream和Floyd判圈算法。
哈希表:
#include <iostream> #include <sstream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <stack> #include <algorithm> #include <cctype> using namespace std; const int maxn = 100003; const int INF = 0x3f3f3f3f; typedef long long LL; int st[maxn]; int rear; struct Hash { int first[maxn], next[maxn]; int hash(int s) { return (s & 0x7fffffff) % maxn; } void init() { memset(first, -1, sizeof(first)); } void insert(int s) { int h = hash(st[s]); next[s] = first[h]; first[h] = s; } int find(int s) { int h = hash(s); for(int v = first[h]; v != -1; v = next[v]) { if(s == st[v]) return 1; } return 0; } }; Hash hash; int n, k; void read_case() { hash.init(); scanf("%d%d", &n, &k); } int next(int n, int k) { stringstream ss; ss << (LL) k*k; string s = ss.str(); if(s.length() > n) s = s.substr(0, n); int ans; stringstream ss2(s); ss2 >> ans; return ans; } void solve() { rear = 0; read_case(); int ans = -INF; while(!hash.find(k)) { st[rear] = k; hash.insert(rear); rear++; if(ans < k) ans = k; k = next(n, k); } printf("%d\n", ans); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }
Floyd判圈:
#include <iostream> #include <sstream> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <cmath> #include <vector> #include <queue> #include <stack> #include <algorithm> #include <cctype> using namespace std; typedef long long LL; int n, k; /*int next(int n, int k) { stringstream ss; ss << (LL) k*k; string s = ss.str(); if(s.length() > n) s = s.substr(0, n); int ans; stringstream ss2(s); ss2 >> ans; return ans; }*/ /*int next(int n, int k) { if(!k) return 0; LL k2 = (LL)k*k; int L = 0; while(k2) { buf[L++] = k2%10; k2 /= 10; } if(n > L) n = L; int ans = 0; for(int i = 0; i < n; i++) ans = ans*10 + buf[--L]; return ans; }*/ int next(int n, int k) { char buf[100], s1[100]; sprintf(buf, "%lld", (LL)k*k); if(n > strlen(buf)) n = strlen(buf); strncpy(s1, buf, n), s1[n] = '\0'; int ans = 0; for(int i = 0; i < n; i++) ans = ans*10 + s1[i]-'0'; return ans; } void read_case() { scanf("%d%d", &n, &k); } void solve() { read_case(); int ans = k; int count = 0; int k1 = k, k2 = k; do { k1 = next(n, k1); k2 = next(n, k2); if(k2 > ans) ans = k2; k2 = next(n, k2); if(k2 > ans) ans = k2; //count++; //算出循环节 }while(k1 != k2); printf("%d\n", ans); //printf("%d\n", count); } int main() { int T; scanf("%d", &T); while(T--) { solve(); } return 0; }