Preface

又是颓废的一天！

Content

[CF1251E2]Voting(Hard Version)

一共有 \(n\) 个选民，你可以付出 \(p_i\)​ 的代价让第 \(i\) 个选民为你投票，或者，在为你投票的人数达到 \(m_i\)​ 时，他会主动为你投票而不用你付出任何代价。

问得到所有选民投票的最小代价。

\(1\le n \le 2\times 10^5,1\le p_i\le 10^9,0\le m_i\lt n\)。

神仙贪心，思路难想，代码也难理解。

这道题里肯定就不能延续 Easy Version 的 DP 了，那这个问题大概率就是贪心。

首先要发现若干个性质：

1. 如果已经确定要花钱收买一些人，那么肯定是在一开始就收买他们。（这点一定要记牢，我们接下来贿赂的人并不是按处理顺序，而是一开始就先贿赂好）

2. 基于 Easy Version 的思路，把 \(m\) 升序排序，那么处理 \(m_i=x\) 时，\(m=1\sim x-1\) 的人一定都已经投了票，否则一定更劣。至于是收买还是跟风我们不知道，也不需要知道。

性质 1 不难理解，至于性质 2，我的理解是：这是基于性质 1 的推断。

当我们处理到 \(m_i=x\) 的时候，肯定是希望这些人尽可能地跟风，减少花费。

那这就要求已经投过的人尽量地多。

如果 \(m_i\) 的人无法跟风，那 \(m\gt m_i=x\) 的人肯定更没法跟风。

所以只能考虑 \(m\lt m_i=x\) 的人，先让他们都投了，如果此时还没法让 \(m_i\) 跟风，那就只能在 \(m_i\ge x\) 的人里选一些贿赂。

还是要记住，我们贿赂的这些人是在一开始就贿赂了的。

综上，设计出一个贪心算法：

用 std::vector 存储 \(m_i\) 每种取值对应的 \(p_i\)。

倒序遍历 \(0\sim n-1\)，如果后面买的人加上前面所有人的数量仍然小于当前的 \(m\)，就从后面没买的人里选择若干个贿赂。

时间复杂度 \(O(N\log N)\)，描述得很乱，建议参考代码。

Code

// Problem: CF1251E2 Voting (Hard Version)
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1251E2
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;
int n;
vector<ll> G[maxn];
multiset<ll> s;
void work() {
    scanf("%d",&n);
    for(int i = 0;i < n;++ i)G[i].clear();
    s.clear();
    for(int i = 1;i <= n;++ i) {
        int x;
        ll y;
        scanf("%d %lld",&x,&y);
        G[x].pb(y);
    }
    int tot = n,cur = 0;
    //cur:当前买了多少个
    //tot:前面已经有多少人投了
    ll ans = 0;
    for(int i = n - 1;~ i;-- i) {
        if(G[i].empty())continue ;
        tot -= G[i].size();
        for(auto& v : G[i]) {
            s.insert(v);
        }
        for(;cur < i - tot;++ cur) {
            ans += *s.begin();
            s.erase(s.begin());
        }
    }
    printf("%lld\n",ans);
    return ;
}
int main() {
    int T;
    scanf("%d",&T);
    while(T --)work();
    return 0;
}

[CF853C]Boredom

调了 \(\infin\) 年调不出来，心态爆炸，于是直接对着 7KByte 大佬的题解写，虽然有些地方无法理解，但我不管，摆烂了，不写题解，有兴趣可以看看 7KByte 大佬的题解。只放代码。

Code

// Problem: CF853C Boredom
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF853C
// Memory Limit: 500 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
struct query {
    int x,y,l,r,id,v;
    query() {
        x = y = l = r = id = v = 0;
    }
    query(int x,int l,int r,int id,int v):x(x),l(l),r(r),id(id),v(v){}
}Q[maxn];
typedef long long ll;
ll ans[maxn];
int c[maxn],a[maxn];
int n,m;
int lowbit(int x) {
    return x & -x;
}
void add(int x,int y) {
    for(;x <= n;x += lowbit(x))c[x] += y;
    return ;
}
int Query(int x) {
    int ans = 0;
    for(;x;x -= lowbit(x))ans += c[x];
    return ans;
}
int b[maxn];
void rev() {
    for(int i = 1;i <= n;++ i)b[a[i]] = i;
    for(int i = 1;i <= n;++ i)a[i] = b[i];
    for(int i = 1;i <= m;++ i) {
        int x = Q[i].x,y = Q[i].y;
        Q[i].x = n + 1 - Q[i].r;
        Q[i].y = n + 1 - Q[i].l;
        Q[i].l = x;
        Q[i].r = y;
    }
    return ;
}
void calc() {
    sort(Q + 1 , Q + 1 + m , [&](const query& p,const query& q) {
        return p.l < q.l;
    });
    memset(c , 0 , sizeof(c));
    for(int i = 1,j = 1;i <= m;++ i) {
        for(;j < Q[i].l;++ j) {
            add(a[j] , 1);
        }
        int cur = Query(Q[i].x - 1);
        ans[Q[i].id] -= 1ll * (j - 1) * (j - 2) / 2 - 1ll * cur * (cur - 1) / 2ll; 
    }
    return ;
}
int main() {
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= n;++ i)scanf("%d",&a[i]);
    for(int i = 1;i <= m;++ i) {
        scanf("%d %d %d %d",&Q[i].l,&Q[i].x,&Q[i].r,&Q[i].y);
        Q[i].id = i;
        ans[i] = 1ll * n * (n - 1) / 2ll;
    }
    calc();
    rev();
    calc();
    rev();
    calc();
    rev();
    calc();
    for(int i = 1;i <= m;++ i)printf("%lld\n",ans[i]);
    return 0;
}

[CF768D]Jon and Orbs

无数个物品，种类有 \(N\) 种，每天可以随机取其中一个。

\(Q\) 次询问，询问将 \(N\) 种物品都取到的概率不小于 \(\frac{p}{2000}\) 的最小天数。

\(1 \le N,Q,p \le 10^3\)。

简单题，就是洛谷翻译的题面让我晕了好久。

设 \(f(i,j)\) 表示 \(i\) 天取到 \(j\) 种物品的概率。

初始状态：\(f(0,0)=1\)。

状态转移方程：\(f(i,j)=f(i-1,j)\times \frac{j}{n}+f(i-1,j-1)\times \frac{n-j+1}{n}\)。

在 \(N,p\) 均取极值的情况下，实测得出约为 \(7500\)，数组开 \(10^4\times 10^3\) 即可。

每次询问直接暴力查找就行。

Code