签到题，输出 \(m \mod{2^n}\)，m%pow(2.0,n) 居然hack不了。

签到题，判断一棵有根树是否满足所有的非叶子节点都有至少3个叶子节点与它直接相连。

题目大意：

有\(n\le30\)种不同的物品，第\(i\)种物品的价值为\(2^{i-1}\)，花费为\(1\le c_i\le10^9\)。每种物品的数量可以认为是无穷的。问要得到价值和至少为\(1\le L\le10^9\)的物品，最小的花费是多少？

题解：

令\(f[i]\)表示得到少价值和至为\(2^i\)的物品所需要的最小花费，则有\(f[i] = \min(2\times f[i-1],c[i+1])\)。

做完之后再用\(f[i] = \min(f[i], f[i-1])\)更新一次。

之后就递归计算最小花费\(G(L)\):

如果\(L\ge 2^{n-1}\)，则\(G(L) = f[n-1]\times \lfloor \frac{L}{2^{n-1}} \rfloor + G(L \mod{2^{n-1}})\)
如果 \(L = 2^{k}, 0\le k \le n-2\)，则 \(G(L) = f[k]\)
如果以上两条都不满足， \(2^k< L < 2^{k+1}\)，则 \(G(L) = \min(f[k+1],f[k] + G(L - 2^k))\)

时间复杂度 \(O(n)\)

题目大意：

一场考试有\(1\le n\le2\times10^5\)道题目，总时间为\(1\le T\le10^9\)。

做第\(i\)道题目需要\(1\le t_i\le40000\)的时间，并且如果这场考试一共做完了\(k\)道（包括此题）题目，那么第\(i\)道题目对总分贡献一分，当且仅当\(k\le a_i\)。

问这场考试最多能得多少分？并输出任意一种使得分最多的做题方案。

题解：

显然可以二分答案，然后判定的时候将所有 \(a_i\) 大于等于当前二分的答案的题都拿出来，按 \(t_i\) 从小到大做，看最多能做多少道，如果大于当前二分的答案，就可以接受当前的答案。

时间复杂度\(O(n\log{n}+\max t_i \log{n})\)

题目大意：

\(1\le n\le 10000\)组询问，每组给出逻辑真值函数\(f(x,y,z)\)的真值表，要求输出\(f\)的长度最短的表达式，在长度相同时，取字典序最小的。

题解：

用\(dp[set][a]\)表示真值表为 \(set\)，优先级为 \(a\) 的最优表达式。

然后用spfa去做dp，三个原子公式\(x\)，\(y\)，\(z\)是起点。

松弛的方法大致有三种，在当前表达式前面加 NOT，用 AND 连接当前表达式与另一表达式，以及用 OR 连接当前表达式与另一表达式。

时间复杂度\(O(\text{跑挺快的})\)

ShinriiTin/contest/CF_Hello_2018

Hello 2018