[Codeforces 1003D]Coins and Queries – 贪心

Description

给你\(n\)个硬币,每个硬币的面值都为\(2\)的幂次方。先有\(q\)个询问,每个询问给出一个数\(b\),问你至少用多少个硬币才能使得他们的面值凑成\(b\)。若不能凑出,则输出\(-1\)。

Solution


1+

1101总结

T1

共有\( n \)种竞赛,对于其中任意\( i \)种竞赛,\(1≤i≤n\),有\(a_i\)个人同时参加,问有多
少个人参加了至少一门竞赛?

傻逼容斥。系数即为组合数。加个大模数。没了

T2

有一棵\( n \)个点的树,每个叶子节点上都有一个人,他们按照每秒钟走一条边的
速度向树根(节点\( 1\))前进。
你可以运用\( k \)次瞬移,让某一个节点(除了根节点)上的所有人瞬间(耗时为\( 0\))
转移到这个节点的父亲上。
你想知道最少需要多少时间,所有人可以到达根节点。

\( k \leq 5 \times 10^5\)
贪心,搞个优先队列

T3

有一个\( n \)面的骰子,第\( i \)面的数是\( v_i\),朝上的概率是\( p_i\)。
不停地抛这个骰子,直到某一面朝上了两次,就停止抛骰子,求所有朝上的面
的数字的和的期望\( E \)是多少. \( n \leq 500\)

想了一个\(n^2\)做法
看pdf

0

[JZOJ4882]多段线性函数

Problem

有\( n\)个变量\(x_1,x_2,\cdots,x_n \in \mathbb{R} \),对于每个变量都有一个限制\(x_i \in [l_i, r_i]\),任意两个变量的取值不想和影响。

给一个多段线性函数

\[ f(y)=\sum_{i=1}^n |y-x_i|\]

定义这个函数的局部最小值\( f_{\text{min}}(y_0)\)为,当\( y\)取某个值\(y_0\)时,存在一种\( x_i\)的取值方案使得函数值为\( f_{\text{min}}(y_0)\),且对于所有的\(x_i\)的取值方案,都有\(f(y_0) \geq f_{\text{min}}(y_0)\)

定义这个函数的全局最小值\( f_{\text{min}} \):存在某个\( y=y_0\),使得\(f_{\text{min}}(y_0)=f_{\text{min}}\),且对于所有的\(y\),都有\( f_{\text{min}}(y)\geq f_{\text{min}}\)。

任务是求出\( y\)的取值范围\( [L, R]\),使得都有\( f_{\text{min}}(y)=f_{\text{min}}\)

可以证明\( [L, R]\)是答案的一般形式,也就是不存在多段的\( y\)满足题意。如果\(y\) 仅能取一个值\(z\),令\(L=R=z\)
继续阅读 [JZOJ4882]多段线性函数

0