魔法森林是一个 $ N $ 个节点 $ M $ 条边的无向图,节点标号为 $ 1 \ldots N $,边标号为 $ 1 \ldots M $。初始时小 E 同学在号节点 $ 1 $,隐士在节点 $ N $。

无向图中的每一条边 $ E_i $ 包含两个权值 $ A_i $ 与 $ B_i $。若身上携带的 A 型守护精灵个数不少于 $ A_i $,且 B 型守护精灵个数不少于 $ B_i $,这条边上的妖怪就发起攻击。

小 E 想要知道,要能够成功拜访到隐士,最少需要携带守护精灵的总个数。

阅读全文

对于字符串 $ S $ 的前 $ i $ 个字符构成的子串,既是它的后缀同时又是它的前缀,并且该后缀与该前缀不重叠,将这种字符串的数量记作 $ \mathrm {num}(i) $,求

$$ \prod\limits_{i = 1} ^ n (\mathrm{num}(i) + 1) \pmod {1000000007} $$

阅读全文

JOI 君有 $ N $ 个装在手机上的挂饰,编号为 $ 1 \to N $。 JOI君可以将其中的一些装在手机上。

一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上,要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有 $ 1 $ 个。此外,每个挂件有一个安装时会获得的喜悦值,用一个整数(可以为负)来表示。

JOI 君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰,而且一个都不挂也是可以的。

阅读全文

有 $ n $ 个玩偶,每个玩偶有对应的价值、价钱,每个玩偶都可以被买有限次,在携带的价钱 $ m $ 固定的情况下,如何选择买哪些玩偶以及每个玩偶买多少个,才能使得选择的玩偶总价钱不超过 $ m $,且价值和最大。

多次询问,每次询问都将给出新的总价钱,并且会去掉某个玩偶(即这个玩偶不能被选择),再问此时的多重背包的答案。

阅读全文

windy 有 $ N $ 条木板需要被粉刷。每条木板被分为 $ M $ 个格子。 每个格子要被刷成红色或蓝色。 windy 每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色。每个格子最多只能被粉刷一次。如果 windy 只能粉刷 $ T $ 次,他最多能正确粉刷多少格子?

一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷。

阅读全文

$ N $ 个政党要组成一个联合内阁,每个党都有自己的席位数。现在希望你找出一种方案,你选中的党的席位数要大于总数的一半,并且联合内阁的席位数越多越好。对于一个联合内阁,如果某个政党退出后,其它党的席位仍大于总数的一半,则这个政党被称为是多余的,这是不允许的。

阅读全文

合唱队的排队方式为:

  1. 第一个人直接插入空的队形中;
  2. 对于第二个人开始的每一个人,如果他比上一个人高,则站到最右边,否则站到最左边。

求对于某一个排好的序列,可以被多少种初始序列构建出,答案对任意数取模。

阅读全文

折叠的定义如下:

  1. 一个字符串可以看成它自身的折叠。
  2. $ X(S) $ 是 $ X(X > 1) $ 个 $ S $ 连接在一起的串的折叠。
  3. 如果 $ A $ 是 $ A’ $ 的折叠,$ B $ 是 $ B’ $ 的折叠,则 $ AB $ 是 $ A’B’ $ 的折叠。

给一个字符串,求它的最短折叠。

阅读全文

Menci

眉眼如初,岁月如故

OI / Linux / C++

Linyi, Shandong