[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

[JZOJ4765]Crisis

Problem

最近几年,一场新的金融危机爆发了,这场危机使得很多人陷入的经济问题的困境。一些X公司的员工试图通过要求加薪度过这一难关。
X公司有着严格的等级制度,除了公司所有者小H以外,其他人都有一个直属上司。没有下属的员工称为工人,其他人则称为领导者。
为了加薪,工人们都会向他们的上司提交请愿书。当然,每个领导者都希望自己的下属能够尽可能快乐的工作,所以当至少有T%的下属提交请愿书时,那么这个领导者就会向自己的上司提交请愿书。计算百分比时,领导者只会计算直属上司是他的下属,当然,他也只会提交一次请愿书。
如果最会小H收到了超过T%的请愿书,那么他将为所有工人们加薪。现在给出公司的构架和T的数值,你需要计算至少有多少工人提交请愿书才能使得小H给工人加薪。
\( 1≤N≤100000,1≤T≤100\)
继续阅读 [JZOJ4765]Crisis

0