20150814 常州培训扫坑

tonyfang posted @ 2015年8月15日 11:25 in 随笔 with tags c++ , 316 阅读

20140814:

第一题:有一个微波炉(雾?)然后目前温度是0度,有$n$个控制温度的按钮,按第$i$个按钮一下就可以加$a_i$度,问能否达到设定温度$t$及以上,如果可以的话,输出可以达到的离设定温度$t$最近的一个与$t$的差及要调到这个温度最少要按几次按钮,否则输出$-1$。

很明显的一个完全背包,但是我写烂了$TAT$

闫神教我,他说这题目经常可以用最短路来做。

每个温度与能通过按按钮到达的温度连边,跑一遍$spfa$或$dijkstra$即可。

第二题

有$m$个$n$位01串,给出这些01串与未加密的串的匹配成功的数字个数,求有多少个解,如果只有1个,输出这个01串。$n \leq 30$

折半搜索 $O(2^{\frac{n}{2}})$即可。

第三题

有$n$个人,要选第$i$个人的先决条件是选了第$x_i$个人,选的人不超过$k$,问最多选几个。

CSU的题好像。

先连边,然后$tarjan$缩环,然后跑一遍背包就行了。

听说暴力有96!!!听说不缩点能AC!!!

坑坑坑。

这天$ZZQ$成功$AK$(竟然还要求我改),$WYH$成功$AK$

我解锁成就:$\frac{8AK}{15}$.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter