Nowcoder Girl 参考题解

题目练习地址： https://www.nowcoder.com/test/8527168/summary

平方数

分析

签到题。sqrt的枚举或者直接算都可以。

复杂度

O(n^(1/2))

参考代码

#include <bits/stdc++.h>
using namespace std;

int n;
int main() {
    cin >> n;
    int ans = 0;
    for(int i = 0; i <= sqrt(n); i++) ans = i * i;
    printf("%d\n",ans);
    return 0;
 }

勇气获得机

分析

仔细观察会发现，每一步的按键方案由奇偶性确定，于是分类确定即可。

复杂度

O(logn)

参考代码

#include <bits/stdc++.h>

using namespace std;

int n;
stack<char> s;
int main() {
    cin >> n;
    while(n) {
        if(n % 2 == 0) {
            n = (n - 2) / 2;
            s.push('G');
        } else {
            n = (n - 1) / 2;
            s.push('N');
        }
    }
    while(!s.empty()) {
        printf("%c", s.top());
        s.pop();
    }
    printf("\n");
    return 0;
}

打车

分析

注意到n很小，直接枚举子集判断是否合法，在所有合法的方案中找size最大。

复杂度

O(2^n)

参考代码

#include <bits/stdc++.h>

using namespace std;

int n, s, p[15];
int main() {
    scanf("%d%d", &n, &s);
    for(int i = 0; i < n; i++) scanf("%d", &p[i]);
    int ans = 0;
    for (int x = 0; x < (1 << n); x++) {
        int mi = 10000000;
        int sum = 0;
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if ((x & (1 << i)) != 0 ) {
                mi = min(mi, p[i]);
                sum += p[i];
                cnt++;
            }
        }
        if (sum >= s && sum - mi < s) {
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;

}

排列

分析

如果某个数没有满足错排要求，直接和相邻的位置swap一下，统计次数即可。

复杂度

O(n)

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 5;

int a[maxn], n;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    int res = 0;
    for(int i = 0; i < n - 1; i++) {
        if(a[i] == i + 1) {
            swap(a[i], a[i + 1]);
            res++;
        }
    }
    if(a[n - 1] == n) res++;
    cout << res << endl;
    return 0;
}

美丽的项链

分析

可以通过母函数求解。
比较直接的就直接用背包dp算就行了。

复杂度

O(nmr)

参考代码

#include <bits/stdc++.h>
using namespace std;

long long f[2][105];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(f, 0, sizeof(f));
    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        memset(f[i & 1], 0, sizeof(f[i & 1]));
        int l, r;
        scanf("%d%d", &l, &r);
        for (int k = l; k <= r; k++)
            for (int j = m; j >= k; j--)
                f[i & 1][j] += f[i + 1 & 1][j - k];
    }
    printf("%lld\n", f[n & 1][m]);
    return 0;
}

勇敢的妞妞

分析

当k >= 5的时，每一维属性都取最大求和即可。
对于k < 5的时，预处理31种情况可能得到的最大的和。然后dfs枚举子集维护最大的答案即可。

复杂度

O(31 5 n)

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4 + 5;

int mx[10];
int num[maxn][10];
int N, K;
int sta[32];
int dfs(int s, int cur) {
    if(cur == K) return 0;
    int tmp = 0;
    for(int i = s; i; i = (i - 1) & s) tmp = max(tmp, sta[i] + dfs(s ^ i, cur + 1));
    return tmp;
}
int main() {
    scanf("%d%d", &N, &K);
    memset(sta, 0, sizeof(sta));
    memset(mx, 0, sizeof(mx));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < 5; j++) {
            scanf("%d", &num[i][j]);
            mx[j] = max(mx[j], num[i][j]);
        }
        for(int j = 0; j < 32; j++) {
            int res = 0;
            for(int k = 0; k < 5; k++) {
                if(j & (1 << k)) {
                    res += num[i][k];
                }
            }
            sta[j] = max(sta[j], res);
        }
    }
    if(K >= 5) {
        int ans = 0;
        for(int i = 0; i < 5; i++) ans += mx[i];
        printf("%d\n", ans);
    } else {
        printf("%d\n", dfs(31, 0));
    }
    return 0;
}

#google#