牛客练习赛86题解

A - 取因数

偶数先手必胜，奇数后手必胜
奇数取完之后一定会变成偶数，偶数的话拿掉 $\texttt{1}$ 就会变成奇数
这样回来还是偶数，总有一次会拿到 $\texttt{2}$ ，然后就游戏结束了

#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 - 翻转数列

如果我们每次反转都多制造出两组要求的数对，效率就是最高的，当两组两组翻到无法再多制造出两组后，就不断多翻出一组直到不能再多为止
假设 $x$ 是出现最多的数字出现的次数，若 $x > \left \lceil \frac{N}{2} \right \rceil$ ，则最多可以有 $2 \times (N - x)$ 组，否则最多可以有 $N-1$ 组
问题回到如何在一次反转多制造出两组？
找到类似这样的区间 $aa...bb$ ，反转中间就可以得到 $ab...ab$
因此我们可以对一开始的序列统计每种数字相邻且相同的数对个数
之后问题就转化为了：给定一正整数序列，你每次可以挑两个大于零的数字同时减一，问最多可以进行几次操作？
每次找最大的数字和随意的数字同时减一，就可以得到答案
做完以上繁琐的操作之后，我们可以知道：
原本有 $a$ 组相邻且不同的数对，两组两组增加最多可以执行 $b$ 次，最终最多可以有 $c$ 组相邻且不同的数对
最后，做 $K$ 次反转最多可以有几组数对就能通过简单的判断得到了

#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 - 排列

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

#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 - 字符删除

考虑字符 $c$ ，若 $c$ 被保留在最后的答案中，代表 $c$ 之后的字符是用 $c$ 删除的
如果一个段 $s[l+1,...,r]$ 可以用 $s[l]$ 删除，那么 $s[l+1,...,r-1]$ 也可以用 $s[l]$ 删除
所以，对于每个位置 $s[l]$ ，就必须找到使 $s[l]$ 可以删除的最大长度
这个计算长度部分可以dp也可以用栈，我用的栈
然后问题就转变为将字符串 $s$ 转化为 $a_1,a_2,...,a_k$ 段，每段都可以用 $a_i[0]$ 删除
我们不在 $ans[i]$ 存答案，存 $next[i]$ ，就是答案的第二个字符形成的索引
那么 $ans[i]=s[i]+s[next[i]]+s[next[next[...]]]$ 的链接形成一棵悬浮的树，每个 $ans[i]$ 都是由顶点 $i$ 到根的路径
在这棵树上，可以计算二元提升，并为每个二元提升计算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;
}