Skip to content

1122: 神奇储物箱

题目

题目描述

凡D有一个神奇的储物箱,在未来的 q 天里,每天会发生一次事件,事件有两种,格式如下:

  • 1 v w e 储物箱中存入一个体积为 $v$ 价值为 $w$ 的物品,并且这个物品会在第 $e$ 天结束后消失
  • 2 v 他的哥哥y哥会询问当天是否会存在一个物品集合,满足集合中物品的体积和为 $v$ ,如果存在,他想要知道这个集合中物品的价值和最大是多少

凡D当然会这个问题,可凡D最近沉迷其他科目的学习,他希望聪明的你来帮他解决这些事件,如果你做出来了,他会强迫y哥请你一杯奶茶,如果你做出来并且不使用任何STL,他会强迫y哥额外附赠你一个与奶茶等价的红包。

输入格式

第一行的输入是三个整数 $q$ ,$maxv$,$T$ ,$q$表示天数,$v$表示最大可能的物品体积 $v$ ,$T$表示是否强制在线.

接下来 $q$ 行每行描述一个操作:

设修正值 $d$ = $T * lastans$ ,这里 $lastans$ 表示上次的第 2 种事件的 两个答案的异或和 ,初始为0

第 $i$ 行中,第一个整数 op 表示操作类型

  • op 为 1 ,接下来三个整数 $v'_i$ , $w'_i$ , $e'_i$ ,表示储物箱中存入体积为 $v_i$ = $v'_i - d$ , $w_i$ = $w'_i - d$ , $e_i$ = $e'_i - d$ 的物品;
  • op 为 2 ,接下来一个整数 $v'_i$ ,表示y哥询问的物品集合的物品体积和为 $v_i$ = $v'_i - d$ 。

输出格式

对于每个 op 为 2 的事件,输出一行两个整数 $e$ 和 $maxw$ ,用空格分隔

若这样的物品集合不存在,则 $e$ 和 $maxw$ 均为0;否则 $e$ 为 1 ,$maxw$ 为满足体积和条件的物品集合里面可以取到的最大的价值和

样例输入

样例输入 1

text 12 10 0 1 1 1 12 1 6 0 12 1 10 7 8 1 3 8 7 2 6 2 9 2 10 2 10 2 10 1 3 2 11 2 4 2 4

样例输入 2

text 19 20 1 1 2 19 11 2 2 1 27 27 22 1 20 34 36 2 29 1 9 8 9 1 5 19 8 1 1 15 19 2 3 1 36 40 54 1 37 50 52 2 40 2 62 1 1 17 16 1 1 7 16 1 13 16 18 1 9 11 19 2 10 2 34

样例输出

样例输出 1

text 1 0 1 8 1 9 1 7 0 0 1 3 0 0

样例输出 2

text 1 19 0 0 1 34 1 46 0 0 1 26 0 0

数据范围

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!