竞赛讨论区 > 牛客练习赛86题解
头像
DongResponse
发布于 2021-07-09 22:01
+ 关注

牛客练习赛86题解 精

A - 取因数

  • 偶数先手必胜，奇数后手必胜
  • 奇数取完之后一定会变成偶数，偶数的话拿掉 就会变成奇数
  • 这样回来还是偶数，总有一次会拿到 ，然后就游戏结束了 
#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    if (n & 1) puts("Bob");
    else puts("Alice");
    return 0;
}

B - A + B

  • 因为K只取「0」，「1」，「2」，N最大为「100」，所以完全可以先本地跑出来，然后交表。

  • 找到abcd型数字构造k=1型:abcd0abcd，如123401234，1230123等

  • 找到"(int)(aaa)"+"(int)(aa+a)" 构造k=2型:如11112，11111122，1111111122等

  • 找到"a","aa","aaa",构造k=0型:如1，11，111，1111，2，22，22222等

#include <bits/stdc++.h>

#define int long long
using namespace std;


vector<int> v[10];
vector<string> Ans[10];

signed main() {
    for (int j = 1; j < 10; j++) {
        int sum = 0;
        for (int i = 0; i < 16; i++) {
            sum = sum * 10 + j;
            Ans[0].push_back(to_string(sum));
            v[j].push_back(sum);
        }
    }
    for (int i = 12345; i <= 12468; i++)
        Ans[1].push_back(to_string(i) + "0" + to_string(i));
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j + 1 < v[i].size(); j++) {
            for (int k = j + 1; k < v[i].size(); k++) {
                if (to_string(v[i][j]).length() + to_string(v[i][k]).length() + to_string(v[i][k] + v[i][j]).length() < 30)
                    Ans[2].push_back(to_string(v[i][j]) + to_string(v[i][k]) + to_string(v[i][k] + v[i][j]));
            }
        }
    }
    int m, n;
    cin >> m >> n;
    for (int i = 0; i < n; i++)
        cout << Ans[m][i] << endl;
    return 0;
}

C - 取钱

  • 先处理出不超过当前钞票面额的最多钞票数
  • 对于每个输入，二分查找，然后加上差值这部分就好了 
#include <bits/stdc++.h>

using namespace std;


#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}
#define ALL(data)       data.begin(),data.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    const int64_t inf = TYPEMAX(int64_t) / 3;

    int n = input<int>();
    vector<int64_t> a(n);
    input_seq(ALL(a));
    a.push_back(inf);

    vector<int64_t> b(n + 1), btake(n + 1);
    b[0] = 0;
    btake[0] = 0;

    for (int i = 1; i <= n; ++i) {
        int64_t res = b[i - 1];
        int64_t can = (a[i] - 1 - res) / a[i - 1];
        b[i] = res + can * a[i - 1];
        btake[i] = btake[i - 1] + can;
    }

    for (int m = input<int>(); m != 0; --m) {
        int64_t s = input<int64_t>();
        int i = std::upper_bound(ALL(b), s) - b.begin() - 1;
        assert(0 <= i and i < n);
        int64_t res = b[i];
        int64_t take = btake[i];
        int64_t can = (a[i + 1] - 1 - res) / a[i];
        can = (s - res) / a[i];
        res += can * a[i];
        take += can;
        cout << res << " " << take << "\n";
    }
    return 0;
}

D - 翻转数列

  • 如果我们每次反转都多制造出两组要求的数对，效率就是最高的，当两组两组翻到无法再多制造出两组后，就不断多翻出一组直到不能再多为止
  • 假设 是出现最多的数字出现的次数，若 ，则最多可以有 组，否则最多可以有 组
  • 问题回到如何在一次反转多制造出两组？
  • 找到类似这样的区间 ，反转中间就可以得到
  • 因此我们可以对一开始的序列统计每种数字相邻且相同的数对个数
  • 之后问题就转化为了：给定一正整数序列，你每次可以挑两个大于零的数字同时减一，问最多可以进行几次操作？
  • 每次找最大的数字和随意的数字同时减一，就可以得到答案
  • 做完以上繁琐的操作之后，我们可以知道：
  • 原本有 组相邻且不同的数对，两组两组增加最多可以执行 次，最终最多可以有 组相邻且不同的数对
  • 最后，做 次反转最多可以有几组数对就能通过简单的判断得到了 
#include <bits/stdc++.h>

using namespace std;


int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (int i = 0; i < n; ++i) cin >> v[i];
    for (int i = 0; i < n; ++i) --v[i];
    vector<int> cnt(n, 0);
    int ans = 0;
    for (int i = 1; i < n; ++i) if (v[i - 1] == v[i]) ++cnt[v[i]]; else ++ans;
    multiset<int> st(cnt.begin(), cnt.end());
    st.erase(0);

    while (st.size() > 1u && k > 0) {
        int x = *st.begin();
        st.erase(st.begin());
        int y = *prev(st.end());
        st.erase(prev(st.end()));
        --x, --y, --k, ans += 2;
        if (x) st.insert(x);
        if (y) st.insert(y);
    }

    if (st.size() && k) {
        int z = min(*st.begin(), k);
        ans += z;
        k -= z;
    }

    cnt = vector<int>(n, 0);
    for (int i = 0; i < n; ++i) ++cnt[v[i]];
    sort(cnt.rbegin(), cnt.rend());
    ans = min(min(ans, n - 1), (n - cnt[0]) * 2);
    cout << ans << endl;
}

E - 排列

  • 排序 个东西需要 次比较，但是数列的比较需要 吗？
  • 显然我们无法存下所有的排列，就像字符串比较，我们可以通过 得到 的数比较
  • 但是 也需要 的空间，并没有解决另外一个问题
  • 注意到相邻的两个数列只差一丢丢
  • 可持久化 ，交换两个数字相当于两个单点修改， 查询是前缀查询
  • 可以用可持久化线段树/BIT， 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0)
#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define F first
#define S second
#define REP(i, n) for(int i=0;i<((int)n);i++)
#define pb push_back
#define MP(a, b) make_pair(a,b)

template<typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> P) {
    out << '(' << P.F << ',' << P.S << ')';
    return out;
}

template<typename T>
ostream &operator<<(ostream &out, vector<T> V) {
    REP(i, SZ(V)) out << V[i] << ((i != SZ(V) - 1) ? " " : "");
    return out;
}

const ll maxn = 100005;
const ll MOD = ll(1e9 + 7);
const ll pp = 880301;
const ll P = 31;

ll mypow(ll a, ll b) {
    ll res = 1LL;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

pll operator+(pll A, pll B) {
    return MP((A.F + B.F >= MOD) ? (A.F + B.F - MOD) : (A.F + B.F),
              (A.S + B.S >= MOD) ? (A.S + B.S - MOD) : (A.S + B.S));
}

pll operator-(pll A, pll B) {
    return MP((A.F >= B.F) ? (A.F - B.F) : (A.F - B.F + MOD), (A.S >= B.S) ? (A.S - B.S) : (A.S - B.S + MOD));
}

pll operator*(pll A, pll B) {
    return MP(A.F * B.F % MOD, A.S * B.S % MOD);
}

pll operator*(ll A, pll B) {
    return MP(A * B.F % MOD, A * B.S % MOD);
}

pll operator*(pll A, ll B) {
    return B * A;
}

pll ex[maxn];
pll invex[maxn];

struct node {
    pll val;
    node *lc, *rc;

    node(pll _val, node *_lc, node *_rc) : val(_val), lc(_lc), rc(_rc) {}

    node(pll _val) : val(_val), lc(0), rc(0) {}
};

int n, m;
ll a[maxn];
int x[maxn], y[maxn];

node *build(int l, int r) {
    if (r - l == 1) {
        return new node(ex[l] * a[l]);
    }
    int mid = (l + r) / 2;
    node *ret = new node(MP(0LL, 0LL), build(l, mid), build(mid, r));
    ret->val = ret->lc->val + ret->rc->val;
    return ret;
}

node *mdf(node *root, int l, int r, int p, pll val) {
    if (p < l or r <= p) return root;
    if (r - l == 1) {
        return new node(root->val + val);
    }
    int mid = (l + r) / 2;
    node *ret = new node(MP(0LL, 0LL), mdf(root->lc, l, mid, p, val), mdf(root->rc, mid, r, p, val));
    ret->val = ret->lc->val + ret->rc->val;
    return ret;
}

node *root[maxn * 2];

bool cmp(int s, int t) {
    if (root[s + s]->val == root[t + t]->val) {
        return s < t;
    }
    int l = 0, r = n;
    node *ss = root[s + s], *tt = root[t + t];
    while (l < r - 1) {
        int mid = (l + r) / 2;
        if (ss->lc->val == tt->lc->val) {
            ss = ss->rc;
            tt = tt->rc;
            l = mid;
        } else {
            ss = ss->lc;
            tt = tt->lc;
            r = mid;
        }
    }
    return ss->val * invex[l] < tt->val * invex[l];
}

int main() {
    IOS;
    cin >> n >> m;
    ex[0] = MP(1, 1);
    for (int i = 1; i < maxn; i++) ex[i] = ex[i - 1] * MP(pp, P);
    invex[0] = MP(1, 1);
    invex[1] = MP(mypow(pp, MOD - 2), mypow(P, MOD - 2));
    for (int i = 2; i < maxn; i++) invex[i] = invex[i - 1] * invex[1];

    for (int i = 0; i < n; i++) cin >> a[i];
    REP(i, m - 1) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }

    root[0] = build(0, n);
    for (int i = 1; i < m; i++) {
        root[i * 2 - 1] = mdf(root[i * 2 - 2], 0, n, x[i - 1], (a[y[i - 1]] - a[x[i - 1]] + MOD) % MOD * ex[x[i - 1]]);
        root[i * 2] = mdf(root[i * 2 - 1], 0, n, y[i - 1], (a[x[i - 1]] - a[y[i - 1]] + MOD) % MOD * ex[y[i - 1]]);
        swap(a[x[i - 1]], a[y[i - 1]]);
    }
    vector<int> ans;
    REP(i, m) ans.pb(i);
    sort(ALL(ans), cmp);
    REP(i, m) cout << ans[i] << " \n"[i == m - 1];
    return 0;
}

F - 字符删除

  • 考虑字符 ，若 被保留在最后的答案中，代表 之后的字符是用 删除的
  • 如果一个段 可以用 删除，那么 也可以用 删除
  • 所以，对于每个位置 ，就必须找到使 可以删除的最大长度
  • 这个计算长度部分可以dp也可以用栈，我用的栈
  • 然后问题就转变为将字符串 转化为 段，每段都可以用 删除
  • 我们不在 存答案，存 ，就是答案的第二个字符形成的索引
  • 那么 的链接形成一棵悬浮的树，每个 都是由顶点 到根的路径
  • 在这棵树上，可以计算二元提升，并为每个二元提升计算hash并做字典序比较，找到它们的最大匹配前缀，然后比较下一个字符 
#include <cstdio> 
#include <string>
#include <vector>
using namespace std;
const int L = 20;
const int N = (int) 1e6 + 10;
const int M = 26;
const int H = 2;
const int MOD = (int) 1e9 + 7;
const int P[] = {17239, 23917};
int n, m, best[N], go[L][N], ppow[H][N];
bool can[M][M];
char ch, s[N];

struct data {
    int len, h[H];
    data() {}
    data(char c): len(1) {
        for (int ih = 0; ih < H; ++ih) {
            h[ih] = c;
        }
    }
} str[L][N];

data operator+(const data& a, const data& b) {
    data c;
    c.len = a.len + b.len;
    for (int ih = 0; ih < H; ++ih) {
        c.h[ih] = (a.h[ih] * 1LL * ppow[ih][b.len] + b.h[ih]) % MOD;
    }
    return c;
}

bool operator==(const data& a, const data& b) {
    if (a.len != b.len) return false;
    for (int ih = 0; ih < H; ++ih) {
        if (a.h[ih] != b.h[ih]) return false;
    }
    return true;
}

int compare_lex(int si, int sj) {
    int i = si, j = sj;
    for (int k = L - 1; k >= 0; --k) {
        if (str[k][i] == str[k][j]) {
            i = go[k][i];
            j = go[k][j];
        }
    }
    if ((i == n) || (j == n)) return (i == n) ? si : sj;
    return (s[i] < s[j]) ? si : sj;
}

int main() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf(" %c", &ch), can[i][j] = (ch == '1');
        }
    }
    scanf("%s", s);
    for (int ih = 0; ih < H; ++ih) {
        ppow[ih][0] = 1;
        for (int i = 0; i < n; ++i) {
            ppow[ih][i + 1] = (ppow[ih][i] * 1LL * P[ih]) % MOD;
        }
    }
    vector<int> cur;
    go[0][n] = n;
    for (int i = n - 1; i >= 0; --i) {
        best[i] = i + 1;
        while (!cur.empty() && can[s[i] - 'a'][s[cur.back()] - 'a']) {
            best[i] = compare_lex(best[cur.back()], best[i]);
            cur.pop_back();
        }
        cur.push_back(i);
        go[0][i] = best[i];
        str[0][i] = data(s[i]);
        for (int j = 1; j < L; ++j) {
            go[j][i] = go[j - 1][go[j - 1][i]];
            str[j][i] = str[j - 1][i] + str[j - 1][go[j - 1][i]];
        }
    }
    for (int i = 0; i < n; i = best[i])  printf("%c", s[i]);
    return 0;
}
2024最新求职资料大礼包领取
真题
历年笔试真题附答案
搜狗2020校招【研究】笔试（第二场）
iHandy2019校招-大数据开发工程师笔试题
英雄游戏校招数据分析岗
全部 >
面经
面试常考问题整理
0928携程笔试题解
硬件/IC/嵌入式高薪--你应该看看这些公司和岗位
23届联想面经分享： 秋招上岸
全部 >
内推
员工内推码获取
【美团】校招社招内推，所有岗位，进度可查，消息必回
拼多多内推实习&校招
体验中心实习生招募 - 淘天集团
全部 >
大家都在关注
校招日程表 笔试日历 ai模拟面试 面试宝典 剑指offer 知识点专项练习

全部评论

(5) 回帖
加载中...
话题 回帖
返回全部帖子

本文相关内容

等你来战

查看全部

热门推荐

牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”