烟尘墨

01-12 23:23 已编辑嘉应学院 Web前端发布于广东

关注

牛客周赛 Round 76

小红出题

https://ac.nowcoder.com/acm/contest/99990/A

(补充说明：D题做法假了，仅作参考。)

小红出题

思路

先算有完整的多少周，每周可以出 $15$ 道题目，然后算剩下的有多少工作日，每天可以出 $3$ 道题目，加起来即为答案。

复杂度

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$

代码实现

// Problem: 小红出题
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/99990/A
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5;

void solve()
{
    int n;
    cin >> n;
    int ans = (n / 7 * 15) + (min(n % 7,5ll) * 3);
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

串串香

思路

显然，长度越小的子串出现次数可能越多，所以输出在字符串中出现次数最多的字符即可。

复杂度

时间复杂度 O(n) $，空间复杂度 O(n)$

代码实现

// Problem: 串串香
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/99990/B
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5;

int n;
string s;
int cnt[26];

void solve()
{
    cin >> n >> s;
    for (char c : s) {
        cnt[c - 'a']++;
    }
    int c = 0;
    for (int i = 0; i < 26; i++) {
        if (cnt[i] > cnt[c])
            c = i;
    }
    char ans = 'a' + c;
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

小红的gcd

思路

因为可以若干次任意选数组中的两个数，使它们变成它们的 $gcd$ ，最后必然会变成原先整个数组的 $gcd$ ，因此操作后可以得到的最小数组元素之和为整个数组的 $gcd$ 乘上 $n$

复杂度

时间复杂度 $O(n \log n)$ ，空间复杂度 $O(n)$

代码实现

// Problem: 小红的gcd
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/99990/C
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5;

int n, m;
int a[N];

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        m = __gcd(m, a[i]);
    }
    int ans = m * n;
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

奇偶调整

思路

很直接的可以想到，选择最大的偶数进行除二操作，可以减少很多，但不一定是减少最多的。

因为奇数异或一之后变成偶数，可能最大的奇数变成偶数后会大于当前最大的偶数，因此可以按以下思路进行决策。

用两个堆，一个存奇数，一个存偶数。

进行 $m$ 次除二操作，每次看是否还有异或次数，如果有，看当前的最大偶数（偶数堆的堆顶元素）是否小于当前的最大奇数。

如果当前的最大奇数大于最大偶数，则把最大奇数变成偶数，放入偶数堆中，此时最大偶数变成最大奇数-1。

对当前的最大偶数进行除二操作，然后根据最大偶数除二后的奇偶性把它放进相对应的堆中。

因为 $m$ 很大，所以代码实现中，结束不一定是执行 $m$ 次后，若当前最大偶数为 $0$ 也结束，这种情况表明当前没有奇数能转换为正偶数，而对 $0$ 进行除二操作没有意义，所以在这种情况下结束，这样确保了复杂度最多为 $O(n\log max(a_i))$ 。

按上面这样进行代码实现，也可能会有执行 $m$ 次后剩下异或次数的情况，所以最后还要检查是否剩下异或次数，如果有就用于剩下的奇数。

复杂度

时间复杂度 $O(n \log max(a_i))$ ，空间复杂度 $O(n)$

代码实现

// Problem: 奇偶调整
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/99990/D
// Memory Limit: 1024 MB
// Time Limit: 8000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5;

int n, m, k;
priority_queue<int> pq[2];

void solve()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        pq[x % 2].push(x);
    }
    for (int i = 1; i <= m; i++) {
        if (k > 0 && pq[1].size() && (!pq[0].size() || (pq[1].top() ^ 1) >= pq[0].top())) {
            pq[0].push(pq[1].top() ^ 1);
            pq[1].pop();
            k--;
        }
        if (!pq[0].size() || pq[0].top() == 0)
            break;
        int x = pq[0].top();
        pq[0].pop();
        pq[(x / 2) % 2].push(x / 2);
    }
    int ans = 0;
    while (pq[0].size()) {
        ans += pq[0].top();
        pq[0].pop();
    }
    while (pq[1].size()) {
        int x = pq[1].top();
        if (k > 0) {
            x ^= 1;
            k--;
        }
        ans += x;
        pq[1].pop();
    }
    cout << ans;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

幂次进近

思路

直接二分出满足 $m^k \le n$ 的最大的 $m$ ，和满足 $m^k \ge n$ 的最大的 $m$ ，然后比较两个哪个的 $k$ 次方离 $n$ 最近，如果一样近取较小的那个。

因为指数比较大，所以需要用快速幂求 $m^k$ ，并且可能爆数据类型，所以我的思路是在快速幂种判断是否超过 $2*10^{18}$ ，如果超过返回一个很大的值。

复杂度

时间复杂度 $O(\log n * \log k)$ ，空间复杂度 $O(1)$

代码实现

// Problem: 幂次进近
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/99990/E
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

typedef __int128 i128;

const int N = 1e6 + 5;
const i128 inf = 2e18 + 1e15;

int n, k;

__int128 qmi(__int128 a, int b)
{
    __int128 res = 1;
    while (b) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
        if (b && a >= inf)
            return inf * 3;
    }
    return res;
}

void solve()
{
    cin >> n >> k;

    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (qmi(mid, k) >= n)
            r = mid;
        else
            l = mid + 1;
    }
    int ans = r;
    i128 val = qmi(r, k) - n;

    l = 1, r = n;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (qmi(mid, k) <= n)
            l = mid;
        else
            r = mid - 1;
    }
    if (n - qmi(r, k) < val) {
        ans = l;
    }
    cout << ans << '\n';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
}

同位序列

思路

对数组 $a$ 从小到大排序。

令 $f(x)$ 为以 $x$ 结尾的同位序列的最大长度。

因为 $b_j = g(b_{j-1})$ ，所以 $b_{j-1} < b_j$ 。

排序后，从左到右计算 $f(a_i)$ ，如果前面存在 $a_j$ 满足 $a_i = g(a_j)$ ，则可以使 $a_i$ 接在 $a_j$ 之后，即 $f(a_i) = f(a_j) 1$ ，否则的 $f(a_i) = 1$ 。

此时的问题就是要怎么算出对于 $a_i$ 来说，满足 $a_i = g(a_j)$ 的 $a_j$ 呢？

因为 $a_j$ 和 $a_i$ 二进制下 $1$ 的个数相同，所以 $a_j$ 是可以通过 $a_i$ 移动部分的 $1$ 得到。

显然，像 $1111111...$ 二进制下都是 $1$ 的数，是没有同位序列的上一项的，因为无论怎么移动其中的 $1$ ，这个数字都会变大不会变小。

如果是 $1100$ ，可以发现它的上一项是 $1010$ ，因为把次高位上的 $1$ 向下移动一位，这样减少的最少。

如果是 $10100$ ，它的上一项是 $10010$ ，可以发现把与从低位到高位，第一个下一位为 $0$ 的 $1$ 下移一位，这样是可以减少的尽可能少的。

如果是 $11001$ ，它的上一项是 $10101$ 吗？不是，它的上一项是 $10110$ ，因为最低位的 $1$ 可以上移，使得这个数增加，也就是使得减少的量再减小。

如果是 $1100011$ ，它的上一项是 $1011100$ 。

可以得到这样的规律，对于一个数 $x$ ，它在同位序列的上一项，是把与从低位到高位，第一个下一位为 $0$ 的 $1$ 下移一位，把更低位的所有 $1$ 的开头整体上移到它的此时下一位得到的。

就是像 $xxxxx10000...000011111$ ，变成 $xxxxx0111110000$ 这样子，前面这个 $1$ 向右移动一位，结尾部分的 $1$ 接到它的后面。

这样就可以求出 $a_i$ 在同位序列的上一项 $a_j$ 了。

至于要找具体的最长序列，只需要记录一下上一项，然后从最长序列的最后一项回溯到第一项即可。

复杂度

时间复杂度 $O(n\log n)$ ，空间复杂度 $O(n)$

代码实现

// Problem: 同位序列
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/99990/F
// Memory Limit: 512 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)

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

#define int long long

const int N = 1e6 + 5;

int n;
int a[N];
map<int, int> f;

int pre(int x)
{
    bitset<35> xb(x);
    for (int i = 0; i < 32; i++) {
        if (!xb[i] && xb[i + 1]) {
            xb[i] = 1, xb[i + 1] = 0;
            if (i) {
                int cnt = 0;
                for (int j = 0; j < i; j++) {
                    cnt += xb[j];
                    xb[j] = 0;
                }
                for (int j = 1; j <= cnt; j++) {
                    xb[i - j] = 1;
                }
            }
            return xb.to_ullong();
        }
    }
    return -1;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        int b = pre(a[i]);
        if (b != -1 && f.count(b)) {
            f[a[i]] = f[b] + 1;
        } else {
            f[a[i]] = 1;
        }
    }
    int last = 0;
    for (auto it : f) {
        if (it.second > f[last]) {
            last = it.first;
        }
    }
    vector<int> ans;
    while (1) {
        ans.push_back(last);
        int val = pre(last);
        if (!f.count(val))
            break;
        last = val;
    }
    cout << ans.size() << '\n';
    reverse(ans.begin(), ans.end());
    for (int x : ans)
        cout << x << ' ';
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

全部评论

推荐最新楼层

luxcfy

河北科技大学客户端其它

做一次好像也行

点赞回复分享

发布于 01-13 10:24 河北

luxcfy

河北科技大学客户端其它

e题有必要做两次二分吗

点赞回复分享

发布于 01-13 10:18 河北

烟尘墨

楼主

嘉应学院 Web前端

不太理解这个截断是什么意思，我这里的判断是 b && a>=2e18+1e15，就是 b 还有次数可以继续乘 a,乘上去的结果一定是不小于 2e18+1e15 的，而 n 最大为 1e18，这个算出来的结果与 n 最小距离必然是不小于 1e18+15 的，此时这个答案一定不会被取到，因为有更小的答案 n-1 存在，所以我觉得应该没什么问题？

点赞回复分享

发布于 01-12 21:13 广东

_轨迹_

北京邮电大学算法工程师

E题在快速幂的时候只判断a>=1e18真的可以吗，如果a已经被截断了怎么办

点赞回复分享

发布于 01-12 21:07 北京