20170307C++牛客笔试题

第一题： #include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> #include <string> #include <map> #include <vector> #include <set> #include <climits> #include <ctime> #include <cassert> #define IOS ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; typedef long long ll; #define mp make_pair #define fi first #define se second #define pb push_back const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3fll; const int MAX_N = 1001000; int prime_cnt; int vis[MAX_N], prime[MAX_N]; void Sieve() { memset(vis, 0, sizeof (vis)); prime_cnt = 0; for (int i = 2; i < MAX_N; ++i) { if (!vis[i]) prime[prime_cnt++] = i; for (int j = 0; j < prime_cnt && 1ll * i * prime[j] < MAX_N; ++j) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; } } } ll n; bool isPrime(ll x) { for (int i = 2; 1ll * i * i <= x; ++i) { if (x % i == 0) return false; } return true; } int main() { Sieve(); while (~scanf("%lld", &n)) { if (n > 10000) { ll q = (ll)sqrt(n + 0.5); if (isPrime(q) && q * q == n) { printf("%lld %d\n", q, 2); continue; } else if (isPrime(q + 1) && (q + 1) * (q + 1) == n) { printf("%lld %d\n", q + 1, 2); continue; } else if (isPrime(q - 1) && (q - 1) * (q - 1) == n) { printf("%lld %d\n", q - 1, 2); continue; } } int exp = 0, flag = 0; ll x = n, ret = 1; for (int i = 0; i < prime_cnt; ++i) { if (x % prime[i] == 0) { int cnt = 0; while (x % prime[i] == 0) cnt++, x /= prime[i]; ret = prime[i]; if (x == 1 && cnt > 1) exp = cnt, flag = 1; break; } } if (flag) printf("%lld %d\n", ret, exp); else printf("No\n"); } return 0; } 第二题： #include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> #include <string> #include <map> #include <vector> #include <set> #include <climits> #include <ctime> #include <cassert> #define IOS ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; typedef long long ll; #define mp make_pair #define fi first #define se second #define pb push_back const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3fll; const int MAX_N = 10010; int main() { int n, L; while (~scanf("%d%d", &n, &L)) { int find = 0, st = -1, len = 0; for (int i = L - 1; i <= 100; ++i) { if (2 * n % (i + 1)) continue; int p = 2 * n / (i + 1) - i; if (p < 0 || (p % 2)) continue; st = p / 2, len = i + 1, find = 1; break; } if (find == 0) puts("No"); else { for (int i = 0; i < len; ++i) { printf("%d", i + st); if (i < len - 1) printf(" "); else printf("\n"); } } } return 0; } 第三题： #include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <algorithm> #include <string> #include <map> #include <vector> #include <set> #include <climits> #include <ctime> #include <cassert> #define IOS ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; typedef long long ll; #define mp make_pair #define fi first #define se second #define pb push_back const double pi = acos(-1.0); const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3fll; const int MAX_N = 10010; int n; ll num[15], pw[15]; int main() { pw[0] = 1; for (int i = 1; i < 15; ++i) pw[i] = pw[i - 1] * 10; while (~scanf("%d", &n)) { int digit[15], len = 0, x = n; while (x) { digit[len++] = x % 10; x /= 10; } memset(num, 0, sizeof (num)); for (int i = 1; i < digit[len - 1]; ++i) num[i] += pw[len - 1]; num[digit[len - 1]] += (n % pw[len - 1] + 1); for (int i = len - 2; i >= 1; --i) { int former = n % pw[i + 1], latter = n / pw[i]; for (int j = digit[i] + 1; j < 10; ++j) num[j] += 1ll * former * pw[i]; num[digit[i]] += 1ll * former * pw[i]; if (digit[i] > 0) num[digit[i]] += latter + 1; for (int j = 1; j < digit[i]; ++j) num[j] += pw[i] * (former + 1); if (digit[i] > 0) num[0] += 1ll * former * pw[i]; } if (n > 9) { ll former = n / pw[1]; int k = digit[0]; for (int i = k + 1; i < 10; ++i) num[i] += former; for (int i = 0; i <= k; ++i) num[i] += (former + 1); } num[0] -= 1; for (int i = 0; i < 10; ++i) { printf("%lld", num[i]); if (i < 9) putchar(' '); else putchar('\n'); } } return 0; }

蒟蒻第一题用欧拉质数筛选虽然o(n),然而算幂的时候超时了，尴尬。 膜拜楼上一群数位dp随便干的daliao。

我怀疑碰到了个假人 我的也是 40 90 100 好巧~

第一题感觉是找最小质因数；= = 感觉怎么都会TLE所以就跳了。 第二题用等差数列求和公式，你逆向使用一下，= = 90%也是很费解。

第一题50%说超时了，求100%代码

第一题遍历都只40%，咋回事

这成绩还不错啊

第一题40%   后两题。。。。不说了 哎

第三题，感谢