2022.8.8 心态爆炸记录


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

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/279672.html

(0)
上一篇 2022年8月9日
下一篇 2022年8月9日

相关推荐

发表回复

登录后才能评论