首页 > 其他分享 >CF1612E(概率,独立贡献计算+枚举)

CF1612E(概率,独立贡献计算+枚举)

时间:2022-10-25 22:44:19浏览次数:96  
标签:概率 20 CF1612E int tot 枚举 ans include define

CF1612E(概率,独立贡献计算+枚举)

Problem - 1612E - Codeforces

题目

Monocarp 是 \(n\) 个学生的导师。现在有很多条消息,Monocarp 希望第 \(i\) 个学生阅读编号为 \(m_i\) 的消息。他需要把一些消息置顶,因为学生只会阅读置顶的消息。

学生 \(i\) 有一个属性 \(k_i\)。如果你置顶了 \(t\) 条消息,若 \(t\le k_i\), 该学生会阅读所有置顶消息;否则,该学生会从置顶的 \(t\) 条消息中随机选 \(k_i\) 条阅读。

你需要求出在使得第 \(i\) 名学生阅读到第 \(k_i\) 条消息的 \(i\) 的数量的期望值最大时,你应该置顶哪些消息。如果有多个答案,输出任意一种。

\(k_i \le 20\)

思路

由于 \(k_i\) 非常小,可以猜测总的置顶数应该也不大,也就是可以枚举的。于是记 \(tot\) 为总的置顶数。

对每个信息考虑,可以写出每个信息 \(m\) 的贡献是 \(\sum_i^n \frac{min(k[i], tot)}{tot},where~~ \exist c_j,c_j=m\) 这里 \(c_j\) 是答案序列中的某一项。

可以发现,它只和自己有关,不同信息之间彼此独立。

于是我们就可以分别计算每个信息的单点贡献,之后取最大的作为答案。

最后,试着证明一下总置顶数不会太大的正确性。我们设 \(w\) 为 \(tot=20\) 时每个人的贡献序列。\(w_i = \frac{min(k[i],tot)}{tot}=\frac{k[i]}{tot}\) 。所以当 \(tot > 20\) 时, \(w\) 不再发生变化。

我们设 \(ans_{20}\) 是 \(tot = 20\) 时的答案,并让 \(w\) 按降序排序,考虑 \(ans_{21}\)。有

\(ans_{20} = \sum_{i=1}^{20}w_i/20\)

\(ans_{21}=\sum_{i=1}^{21}w_i/21\)

作差后易得, \(ans_{20} \ge ans_{21}\)。同理可证其他 \(tot > 20\) 的情况。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<bitset>
#include<queue>
#include<map>
#include<stack>
#include<string>
#include<random>
#include<cassert>
#include<functional>
#include<iomanip>
#define inf 0x3f3f3f3f
#define linf 0x3f3f3f3f3f3f3f3fll
#define endl '\n'
#define ll long long
// #define int long long
#define SZ(x) (int)x.size()
#define rep(i,a,n) for(int i = (a);i <= (n);i++)
#define dec(i,n,a) for(int i = (n);i >= (a);i--)
using namespace std;
using PII = pair<int,int>;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x;}
const int N =10 + 2e5 ,mod=1e9 + 7;
const int MAX = 2e5;
int k[N], m[N], n;
PII w[N];
void solve()
{    
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> m[i] >> k[i];

    double mx = 0;
    vector<int> Ans;
    for(int tot = 1;tot <= min(20, n);tot ++) {
        memset(w, 0, sizeof w);
        for(int i = 1;i <= n;i ++) {
            w[m[i]].first += min(k[i], tot);
            w[m[i]].second = m[i];
        }
        
        nth_element(w + 1, w + tot, w + MAX + 1, greater<PII>());

        int res = 0;
        vector<int> ans;
        for(int i = 1;i <= tot;i ++) {
            res += w[i].first;
            ans.emplace_back(w[i].second);
        }

        if(1. * res / tot > mx) {
            mx = 1. * res / tot;
            Ans = ans;
        }
    }

    cout << SZ(Ans) << endl;
    for(auto x : Ans) cout << x << " ";
    cout << endl;
}
signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    //int T;cin>>T;
    //while(T--)
        solve();

    return 0;
}

标签:概率,20,CF1612E,int,tot,枚举,ans,include,define
From: https://www.cnblogs.com/Mxrush/p/16826669.html

相关文章

  • 背包问题的倒序枚举与正序枚举
    这可能是困扰很多人很长时间的问题吧。先把各个变量列出来体积为的背包,有个物品,每个物品的体积为,价值为,每个物品装一次,求最大价值来这看的肯定都是学习过基础背包的人,如果没......
  • c#枚举enum用法
    转载:https://www.cnblogs.com/eliauk-L/p/16185682.html1.定义枚举类型publicenumTest{男=0,女=1}publicenumTest{男,女}2.获......
  • CF 287A(IQ Test-枚举3个字符相等的矩阵)
    A.IQTesttimelimitpertestmemorylimitpertestinputoutputInthecity......
  • 枚举、单例模式
    一、枚举Enum1.1简介1.概念:枚举就是表示一些固定的值(常量)使用枚举项表示这些固定的值每一个枚举项都是一个对象2.定义枚举类的语法:访问修饰符enum枚举类的......
  • c枚举类型enum用法(java 枚举类型enum用法)
    C中的枚举类型有什么特点呢?我们利用C中的枚举类型定义了在扫描程序中的记号;为了避免涉及到特定实现语言(C)中表示记号的细节,就使用了正则表达式本身来表示记号如何使用java......
  • Codeforces Round #829 (Div. 2) E // 概率dp
    题目来源:CodeforcesRound#829(Div.2)E-WishIKnewHowtoSort题目链接:Problem-E-Codeforces题意给定大小为\(n\)的仅包含\(0\)、\(1\)的数组\(a\),每......
  • 鸭子圆形湖概率
    鸭子圆形湖概率一个圆形,湖中随机分布了\(n\)个点,求存在一个圆心角为\(\theta\)而且包含了这\(n\)个点的扇形的概率。其中\(n\)为大于2的整数,\(0\lt\theta\lt2\pi\)。为了......
  • C语言——自定义类型(结构体+枚举+联合)
    结构体基础知识结构是一些值的集合,这些值被称为成员变量;结构体可以存储不同类型的数据项,而数组中是存储相同类型数据项声明structtag{//struct是关键字,tag是结构体标签名......
  • 02 随机变量及其分布 | 概率论与数理统计
    1.随机变量随机变量:设随机变量的样本空间为\(S={e}\).\(X=X(e)\)是定义在样本空间\(S\)上的实值单值函数,则称\(X=X(e)\)为随机变量2.离散型随机变量及其分布律1.......
  • [SHOI2014] 概率充电器
    首先因为每个点的贡献都是\(1\),所以求的就是概率。每个点都有三种来电的原因:自己发电由儿子那边来电由父亲那边来电前两种好办,只要树形DP一次就够了。第三种的......