校招全国统一模拟笔试2020年2月场编程题参考代码

变换次数

分析

暴力计算即可.

参考code

#include

using namespace std;

int n, ans, tmp;

int main() {

cin >> n;

while(n > 9) {

tmp = 1;

for(; n; n /= 10) tmp *= n % 10;

n = tmp;

ans++;

}

cout << ans << endl;

}

神奇数

分析

枚举区间内的数,然后check一下要求的性质即可。

参考code

#include

using namespace std;

bool isprime(int x) {

for(int i = 2; i * i <= x; i++) {

if(x % i == 0) return false;

}

return true;

}

bool check(int x) {

int cnt[10];

memset(cnt, 0, sizeof(cnt));

while(x) {

cnt[x % 10]++;

x /= 10;

}

for(int i = 1; i < 10; i++) {

for(int j = 1; j < 10; j++) {

if(i != j && cnt[i] && cnt[j]) {

if(isprime(i * 10 + j)) return true;

}else if(i == j && cnt[i] >= 2) {

if(isprime(i * 10 + j)) return true;

}

}

}

return false;

}

int main() {

int a, b, ans = 0;;

cin >> a >> b;

for(int i = a; i <= b; i++) {

if(check(i)) ans++;

}

cout << ans << endl;

return 0;

}

添加字符

分析

分为A长度小于B的情况和等于的情况。

小于就枚举B串的一个偏移量,然后枚举维护最小的不相等的位数。

等于就直接对比就好了。

参考code

#include

using namespace std;

int main() {

string a, b;

cin >> a >> b;

int la = a.size(), lb = b.size();

if(la < lb) {

int ans = 1e9;

for(int i = 0; i + la <= lb; i++) {

int cnt = 0;

for(int j = 0; j < la; j++) {

if(a[j] != b[i + j]) cnt++;

}

if(cnt < ans) {

ans = cnt;

}

}

cout << ans << endl;

return 0;

} else {

int cnt = 0;

for(int j = 0; j < la; j++) {

if(a[j] != b[j]) ++cnt;

}

cout << cnt << endl;

}

return 0;

}

数组变换

分析

对于每个数一直除2,然后最后check是否相等即可。

参考code

#include

using namespace std;

int a[55];

int main() {

int n;

cin >> n;

for(int i = 0; i < n; i++) cin >> a[i];

string res = "YES";

for(int i = 0; i < n; i++) {

while(!(a[i] & 1)) a[i] >>= 1;

}

for(int i = 1; i < n; i++) {

if(a[i] != a[0]) res = "NO";

}

cout << res << endl;

}

排序子序列

分析

考虑序列A_1, A_2, . . . , A_i是一个单调的序列.显然如果对于j < i把序列分为A_1, A_2. . . A_j 和 A_j+1, A_j+2, . . . , A_i 两个部分不会使问题变得更优.

于是我们可以贪心的去重复下面过程:

1、 从序列中找出最长的单调连续子序列

2、 删除找出的最长的单调连续子序列

这里的单调序列包括非递增和非递减,而判断子序列是否单调的时候,注意处理等于的情况。

参考code

#include

using namespace std;

int main() {

int n;

cin >> n;

vector A;

int ans = 1;

for(int i = 0; i < n; ++i) {

int x;

cin >> x;

if(A.size() <= 1)

A.push_back(x);

else {

if(A[0] <= A.back() && A.back() <= x)

A.push_back(x);

else if(A[0] >= A.back() && A.back() >= x)

A.push_back(x);

else {

ans++;

A.clear();

A.push_back(x);

}

}

}

cout << ans << endl;

return 0;

}

组队竞赛

分析

对于所有参赛队员,我们把他们的水平值进行逆序排序,然后逐一挨着安排每个队伍,然后计算出队伍水平值总和,即为所求。对于a1 >= a_2 >= a_3... >= a{3N}, 我们可以容易观察出答案就是a2 + a_4 + a_6 +...+ a{2N}

参考code

#include

using namespace std;

const int maxn = 300100;

int a[maxn];

int main() {

int n; scanf("%d", &n);

for(int i = 0; i < 3 * n; i++) scanf("%d", &a[i]);

sort(a, a + 3 * n);

long long ans = 0;

for(int i = 0; i < n; i++) ans += a[n + 2 * i];

printf("%lld\n", ans);

return 0;

}

训练部队

分析

可以考虑把新兵分为两种类型。

一种战斗型(战斗值大于潜力值的),一种潜力型(相当于打了他可以获得潜力值),对潜力型的新兵进行战斗力值排序。

然后一种情况是潜力型中战斗值最高的牛牛去打完剩余的潜力型,因为战斗力值会越大越多,另一种情况考虑打完所有潜力型获得值是固定的,那么在攻击型中找一个能打完所有的潜力型的牛牛,并且战斗力值和潜力值要最大。

实现就是用的前缀和和二分

参考code

#include

using namespace std;

typedef long long LL;

const int maxn = 100005;

int n;

int goodn,badn;

LL sum[maxn],MAX[maxn];

struct Node {

LL x,y;

Node() {}

Node (const LL &_x,const LL &_y) { x=_x; y=_y; }

bool operator < (const Node &t) const {

if(x ^ t.x) return x < t.x;

return y < t.y;

}

}good[maxn],bad[maxn];

int search(int L, int R, LL x) {

while(L < R) {

int mid = (L + R + 1) >> 1;

if(MAX[mid] < x) L = mid;

else R = mid - 1;

}

return L;

}

LL solve() {

LL ans = 0;

ans = max(ans, sum[search(0, goodn - 1, good[goodn].x)] + good[goodn].x + good[goodn].y);

for(int i = 1; i <= badn; i++) {

int pos = search(0, goodn, bad[i].x);

ans = max(ans, sum[pos] + bad[i].x + bad[i].y);

}

return ans;

}

int main() {

scanf("%d", &n);

for(int i = 1; i <= n; i++) {

LL x, y;

scanf("%lld%lld",&x, &y);

if(x < y) good[++goodn] = Node(x,y);

else bad[++badn] = Node(x,y);

}

sort(good + 1, good + goodn + 1);

MAX[0] = 0; sum[0] = 0;

for(int i = 1; i <= goodn; i++) {

sum[i] = sum[i-1] + good[i].y - good[i].x;

MAX[i] = max(MAX[i-1], good[i].x - sum[i-1]);

}

LL ans = solve();

printf("%lld\n", ans);

return 0;

}

牛牛的数列

分析

正着枚举记录一下当前位置的连续上升子序列长度,倒着也做一遍。

最后枚举一个连接点即可。

参考code

#include

using namespace std;

const int maxn = 100000 + 5;

const int INF = 0x3f3f3f3f;

int a[maxn], n;

int pre[maxn], suf[maxn];

int main() {

scanf("%d", &n);

for(int i = 1; i <= n; i++) scanf("%d", a + i);

a[0] = INF, a[n + 1] = INF;

for(int i = 1; i <= n; i++) pre[i] = a[i - 1] < a[i] ? pre[i - 1] + 1 : 1;

for(int i = n; i >= 1; i--) suf[i] = a[i] < a[i + 1] ? suf[i + 1] + 1 : 1;

int ans = 1;

for(int i = 1; i <= n; i++) {

ans = max(ans, pre[i - 1] + 1);

ans = max(ans, suf[i + 1] + 1);

if(a[i + 1] - a[i - 1] >= 2) ans = max(ans, pre[i - 1] + suf[i + 1] + 1);

}

printf("%d\n", ans);

return 0;

}