牛客周赛 Round 119 题解

A ICPC Rank

先比题数，如果题数相同比罚时。

void solve() {
    int x, y, p1, p2;
    cin >> x >> y >> p1 >> p2;

    if (x != y) {
        if (x > y) cout << "A" << "\n";
        else cout << "B" << "\n";
    } else {
        if (p1 < p2) cout << "A" << "\n";
        else if (p1 > p2) cout << "B" << "\n";
        else cout << "C" << "\n";
    }
}

B 小苯的序列极值

每个二元组都被覆盖到了，所以值最大的就是序列的最大值 $-$ 序列的最小值。

void solve() {
    int n, mx = 0, mn = inf;
    cin >> n;
    for (int i = 0, x; i < n; ++i) cin >> x, mx = max(mx, x), mn = min(mn, x);
    cout << mx - mn << "\n";
}

C 小苯的平方数

打表发现只有 $1$ 和 $9$ 符合。

$Tips$ ：不需要打完 $10^9$ 的表，只需要打到 $10^5$ 发现只有 $1$ 和 $9$ 符合就可以猜只有这两个数符合了。

void solve() {
    int l, r;
    cin >> l >> r;
    if (l <= 1 && r >= 9) cout << 2 << "\n";
    else if (r >= 9 && l <= 9) cout << 1 << "\n";
    else if (l <= 1 && r >= 1) cout << 1 << "\n";
    else cout << 0 << "\n";
}

D 小苯的左右移动

用 $ofs$ 统计移动的指针，向右移动时需要考虑有没有位被抹掉了，模拟即可。

void solve() {
    int n;
    ll k;
    Z ans = 0;
    cin >> n >> k;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<ll> pos;
    for (int b = 0; b < 64; ++b) {
        if ((k >> b) & 1ll) pos.pb(b);
    }

    ll ofs = 0;
    for (int i = 0; i < n; ++i) {
        if ((i + 1) % 2 == 1) {
            ofs += a[i];
        } else {
            ofs -= a[i];
            if (!pos.empty()) {
                vector<ll> np;
                for (ll p : pos) {
                    if (p + ofs >= 0) np.pb(p);
                }
                pos.swap(np);
            }
        }
        if (pos.empty()) break;
    }

    if (pos.empty()) {
        cout << 0 << "\n";
        return;
    }

    for (ll p : pos) {
        ll e = p + ofs;
        if (e < 0) continue;
        ans += ksm(Z(2), e);
    }
    cout << ans << "\n";
}

E 小苯的三角计数

分三类：

等边三角形：出现次数 $\geq 3$ 就有一次贡献。
等腰三角形：枚举两个边长，合法就 $+1$ 。
一般三角形：枚举两个边长，检查第三边。

void solve() {
    int n;
    cin >> n;
    vector<PLL> v(n);
    for (int i = 0; i < n; i++) cin >> v[i].fi >> v[i].se;
    sort(all(v));

    ll ans = 0;

    for (int i = 0; i < n; i++) {
        if (v[i].se >= 3) ans++;
    }

    for (int i = 0; i < n; i++) {
        if (v[i].se >= 2) {
            ll a = v[i].fi;
            for (int j = 0; j < n; j++) if (j != i) {
                    if (2 * a > v[j].fi) ans++;
                }
        }
    }

    for (int i = 0; i < n; i++) {
        int k = i + 2;
        for (int j = i + 1; j < n; j++) {
            while (k < n && v[i].fi + v[j].fi > v[k].fi) k++;
            ans += max(0, k - j - 1);
        }
    }

    cout << ans << "\n";
}

F 小苯的极大支配

法1：

枚举可能出现的频率，为了让序列最长（删掉元素最少），我们需要选择这个出现的频率下最大的那个元素。对于比它大的元素，全部删掉，比它小的元素，出现次数小于它即可。

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

    vector<int> cnt(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    vector<ll> pre(n + 1);
    vector<vector<int>> groups(n + 1);
    vector<int> freq;

    for (int i = 1; i <= n; ++i) {
        pre[i] = pre[i - 1] + cnt[i];
        if (cnt[i]) {
            if (groups[cnt[i]].empty()) {
                freq.pb(cnt[i]);
            }
            groups[cnt[i]].pb(i);
        }
    }

    ll mx = 0;

    for (int c : freq) {
        int x = groups[c].back();

        ll cur = c + pre[x - 1];

        ll ex = 0;

        for (int f : freq) {
            if (f < c) continue;

            auto grp = groups[f];
            int count = 0;

            if (f == c) {
                count = grp.size() - 1;
            } else {
                auto it = lower_bound(all(grp), x);
                count = distance(grp.begin(), it);
            }

            if (count > 0) {
                ex += (ll)count * (f - c + 1);
            }
        }

        cur -= ex;
        mx = max(mx, cur);
    }

    cout << n - mx << "\n";
}

法2：

显然，最大保留数为 $freq[x] + \sum\limits_{i<x}min(freq[x]-1,freq[i])$ ，所以我们按 $x$ 从小到大遍历，维护「 $<x$ 中每个频次出现的数量」的树状数组，快速计算 $\sum\limits_{i<x} min(freq[i], freq[x]-1)$ 。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<int> freq(n + 1, 0);
    for (int v : a) freq[v]++;
    int mx = 0;
    for (int v = 1; v <= n; v++) if (freq[v] > mx) mx = freq[v];
    BIT<int> cnt(mx), sum(mx);
    int pref = 0;
    ll kp = 0;
    for (int x = 1; x <= n; x++) {
        int fx = freq[x];
        if (fx > 0) {
            int t = fx - 1;
            ll mn = 0;
            if (t > 0) {
                mn = sum.ask(t - 1) + t * (pref - cnt.ask(t - 1));
            } else {
                mn = 0;
            }
            ll kept = fx + mn;
            kp = max(kp, fx + mn);
        }
        if (fx > 0) {
            cnt.add(fx, 1);
            sum.add(fx, fx);
            pref++;
        }
    }
    ll ans = n - kp;
    cout << ans << "\n";
}

头文件

//Another
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef tuple<ll, ll, ll> TLLL;
typedef __gnu_pbds::tree<PLL, __gnu_pbds::null_type, less<PLL>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;
// typedef __gnu_pbds::tree<ll, __gnu_pbds::null_type, less<ll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> Tree;

constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld PI = acos(-1.0);
constexpr ld eps = 1e-10;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}

void init() {

}

void solve() {
    
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    init();

    int t = 1;
    cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    return 0;
}

自动取模

template<class T>
constexpr T ksm(T a, ll b) {
	T res = 1;
	while (b) {
		if (b & 1) res *= a;
		b >>= 1;
		a *= a;
	}
	return res;
}

template<int P>
struct MInt {
	int x;
	constexpr MInt(): x() {}
	constexpr MInt(ll x) : x{norm(x % getMod())} {}
	static int Mod;
	constexpr static int getMod() {
		if (P > 0) {
			return P;
		} else {
			return Mod;
		}
	}
	constexpr static void setMod(int Mod_) {
		Mod = Mod_;
	}
	constexpr int norm(int x) const {
		if (x < 0) {
			x += getMod();
		}
		if (x >= getMod()) {
			x -= getMod();
		}
		return x;
	}
	constexpr int val() const {
		return x;
	}
	explicit constexpr operator int() const {
		return x;
	}
	constexpr MInt operator-() const {
		MInt res;
		res.x = norm(getMod() - x);
		return res;
	}
	constexpr MInt inv() const {
		assert(x != 0);
		return ksm(*this, getMod() - 2);
	}
	constexpr MInt &operator*=(MInt rhs) & {
		x = 1LL * x * rhs.x % getMod();
		return *this;
	}
	constexpr MInt &operator+=(MInt rhs) & {
		x = norm(x + rhs.x);
		return *this;
	}
	constexpr MInt &operator-=(MInt rhs) & {
		x = norm(x - rhs.x);
		return *this;
	}
	constexpr MInt &operator/=(MInt rhs) & {
		return *this *= rhs.inv();
	}
	friend constexpr MInt operator*(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res *= rhs;
		return res;
	}
	friend constexpr MInt operator+(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res += rhs;
		return res;
	}
	friend constexpr MInt operator-(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res -= rhs;
		return res;
	}
	friend constexpr MInt operator/(MInt lhs, MInt rhs) {
		MInt res = lhs;
		res /= rhs;
		return res;
	}
	friend constexpr istream &operator>>(istream &is, MInt &a) {
		ll v;
		is >> v;
		a = MInt(v);
		return is;
	}
	friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
		return os << a.val();
	}
	friend constexpr bool operator==(MInt lhs, MInt rhs) {
		return lhs.val() == rhs.val();
	}
	friend constexpr bool operator!=(MInt lhs, MInt rhs) {
		return lhs.val() != rhs.val();
	}
};

template<>
int MInt<0>::Mod = 998244353;

using Z = MInt<MOD>;

树状数组

template<class Int>
struct BIT {
    vector<Int> a;
    int n;

    BIT() {}
    BIT(int n) {
        init(n);
    }

    void init(int n) {
        this->n = n;
        a.resize(n + 1);
    }

    void add(int x, int k) {
        for (; x <= n; x += x & -x) {
            a[x] += k;
        }
    }

    void add(int x, int y, Int k) {
        add(x, k), add(y + 1, -k);
    }

    Int ask(int x) {
        Int ans = 0;
        for (; x; x -= x & -x) {
            ans += a[x];
        }
        return ans;
    }

    Int ask(int x, int y) {
        return ask(y) - ask(x - 1);
    }

    Int kth(int k) {
        Int ans = 0;
        for (int i = __lg(n); i >= 0; i--) {
            Int val = ans + (1 << i);
            if (val < n && a[val] < k) {
                k -= a[val];
                ans = val;
            }
        }
        return ans + 1;
    }
};

题解 | 牛客周赛 Round 119