2022陕西省赛

比赛链接：https://ac.nowcoder.com/acm/contest/44007

J. Make it Equal

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
const int N = 1e6 + 10;

void solve()
{
    int n;
    cin >> n;
    map<int, int> mp;
    int x;

    for (int i = 0; i < n; i++)
    {
        cin >> x;
        mp[x]++;
    }
    cout << (mp[x] != n ? n - 1 : n) << endl;
}

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

D. 2D-Lake

#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define endl '\n'
#define int ll
const int N = 1e6 + 10;

void solve()
{
    int n, m;
    cin >> n >> m;
    auto find = [&](ll n)
    {
        ll num;
        if (n % 2 != 0)
        {
            ll h = (n - 1) / 2;
            num = h * h;
        }
        else
        {
            ll h = (n - 2) / 2;
            num = h * (h + 1);
        }
        return num;
    };
    int res = find(n);
    if (res >= m)
    {
        cout << res << endl;
    }
    else
    {
        ll l = 2, r = 1e13;
        while (l <= r)
        {
            ll mid = (l + r) / 2;
            if (find(mid) >= m)
            {
                r = mid - 1;
            }
            else
                l = mid + 1;
        }
        cout << l;
    }
}

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

B. Card

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
int n, q, k;

const int N = 1e6 + 10;
int tr[N];
int idx[N], s[N];
int lowbit(int x) { return x & -x; }
void add(int x, int c)
{
    for (; x <= n; x += lowbit(x))
        tr[x] += c;
}
ll getsum(int x)
{
    ll ans = 0;
    for (; x; x -= lowbit(x))
        ans += tr[x];
    return ans;
}

void solve()
{
    cin >> n >> k;
    vector<int> a(n + 1), b(n + 1);
    vector<pair<int, int>> c(n + 1);
    int sum = 0;
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum += a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    for (int i = 1; i <= n; i++)
        c[i].first = b[i] - a[i], c[i].second = i;
    sort(c.begin() + 1, c.begin() + 1 + n, greater<pair<int, int>>());

    for (int i = 1; i <= n; i++)
    {
        idx[c[i].second] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        add(i, 1);
        s[i] = s[i - 1] + c[i].first;
    }

    int ans;
    cin >> q;
    while (q--)
    {
        int m;
        cin >> m;
        vector<int> id(m);
        for (int &x : id)
            cin >> x, add(idx[x], -1);
        int l = 1, r = n;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (getsum(mid) < k)
                l = mid + 1;
            else
                r = mid;
        }
        ll res = sum + s[r];
        for (int x : id)
        {
            if (idx[x] <= r)
                res -= c[idx[x]].first;
            add(idx[x], 1);
        }
        cout << res << '\n';
    }
}

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

H. Cute Rabbit

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define int ll
int n, ans;
const int N = 1e6 + 10;
int a[N];

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    int minn = a[1], maxn = a[n];
    int mod1 = maxn % minn;
    ans = 0;
    int pos = 1e7, f = 1;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] == a[1])
            ans++;
        if (maxn % a[i] != mod1)
        {
            pos = min(pos, i);
            if (a[i] % minn != mod1)
                f = 0;
            break;
        }
        else
        {
            if (i > pos)
            {
                f = 0;
                break;
            }
        }
    }
    if (pos == 1e7)
    {
        cout << n - 1;
        return;
    }
    if (f)
    {
        cout << max(pos - 1, n - ans);
    }
    else
        cout << n - ans;
}

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

C. Type The String

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 110;
ll n, m, k;
char s[N][N];
int dp[N][N], cost[N][N], l[N], fa[N];
struct A
{
    int u, v, w;
    bool operator<(const A &a) const
    {
        return w < a.w;
    }
} G[N * N];
int lcs(int u, int v)
{
    for (int i = 0; i <= 100; i++)
    {
        for (int j = 0; j <= 100; j++)
            dp[i][j] = 0;
    }
    int len1 = l[u];
    int len2 = l[v];

    for (int i = 1; i <= len1; i++)
    {
        for (int j = 1; j <= len2; j++)
        {
            if (s[u][i] == s[v][j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
            {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return len1 + len2 - 2 * dp[len1][len2] + k;
}
int find(int x)
{
    if (x == fa[x])
        return x;
    else
        return fa[x] = find(fa[x]);
}
void solve()
{
    cin >> n >> k;
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> l[i];
        cin >> s[i] + 1;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (i == j)
                continue;
            G[++cnt] = {i, j, lcs(i, j)};
        }
    }

    for (int i = 1; i <= n; i++)
    {
        G[++cnt] = {0, i, l[i]};
    }

    sort(G + 1, G + cnt + 1);

    for (int i = 1; i <= n; i++)
    {
        fa[i] = i;
    }
    int ans = 0, num = n + 1;
    for (int i = 1; i <= cnt; i++)
    {
        auto [u, v, w] = G[i];
        u = find(u), v = find(v);
        if (u == v)
            continue;
        ans += w;
        if (--num == 0)
            break;
        fa[u] = v;
    }
    cout << ans << '\n';
}

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

D.Hash

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'

long long mod = 5999993;
long long gethas(string s)
{
    long long ret = 0;
    for (char c : s)
        ret = (ret * 29 + (c - 'a' + 1)) % mod;
    return ret;
}

void solve()
{
    string s;
    cin >> s;
    ll x = gethas(s);
    vector<int> a(50);
    int tmp = x, res;
    for (int i = 1; i <= 50; i++)
    {
        tmp = (tmp * 29 + 1) % mod;
        res = (x - tmp + mod) % mod;
        bool flag = 1;
        for (int j = 1; j <= i; j++)
        {
            a[j] = res % 29;
            res /= 29;
            if (a[j] > 25)
            {
                flag = 0;
                break;
            }
        }
        if (flag == 0 || res)
            continue;
        cout << s;
        for (int j = i; j >= 1; j--)
            cout << char(a[j] + 'a');
        cout << endl;
        return;
    }
}

signed main()
{
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

F.Cross Fire

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 2e5 + 10;
const int M = 20;
int a[N], d[N], ne[N][20], dp[N][20], ma[N][20];
//dp[i][j]:以下标i开始，恰好参加2^j场比赛能获得的最大分数
//ma[i][j]:以下标i开始，最多参加2^j场比赛能获得的最大分数
//ne[i][j]:参加i场比赛后，应该参加的比赛是ne[2^j]场
void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> d[i];
        dp[i][0] = d[i];
        ma[i][0] = max(0, d[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        int x = lower_bound(a + 1, a + 1 + n, a[i] + k + 1) - a;
        ne[i][0] = x;
    }
    for (int i = 1; i < 20; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            ne[j][i] = ne[ne[j][i - 1]][i - 1];
            dp[j][i] = dp[j][i - 1] + dp[ne[j][i - 1]][i - 1];
            ma[j][i] = max(ma[j][i - 1], ma[ne[j][i - 1]][i - 1] + dp[j][i - 1]);
        }
    }
    function<int(int, int)> dfs = [&](int u, int m)
    {
        if (m == 0)
            return 0;
        int i = 0;
        while ((1 << i) <= m)
            i++;
        i--;
        return max(ma[u][i], dfs(ne[u][i], m - (1 << i)) + dp[u][i]);
    };
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dfs(i, m));
    cout << ans << endl;
}

signed main()
{
#ifdef LOCAL
    freopen("in.in", "r", stdin);
    freopen("out.out", "w", stdout);
#endif
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}