fork()==0世界线变动

Cheap Dinner

发表于 2024-02-28 分类于 codeforces ， practice

题目描述

有 $4$ 种菜类——开胃菜，主菜，饮品和甜点。一顿晚饭由 $4$ 种菜类各一道组成。

对于第 $i$ 种菜类，共有 $n_i$ 种供选择。开胃菜、主菜、饮品和甜点价格分别为 $a_i$、$b_i$、$c_i$、$d_i$。

有些菜品不能搭配。对于开胃菜和主菜来说，有 $m_1$ 对不能搭配。对于主菜和饮品、饮品和甜点分别有 $m_2$，$m_3$ 对。

试问总价格最小的晚饭需要多少钱？

输入

第一行有 $n_1$、$n_2$、$n_3$、$n_4$；

接下来四行分别为 $a_i$，$b_i$，$c_i$，$d_i$；

接下来一行为 $m_1$，接下来 $m_1$ 行中，每一行有 $x_i$，$y_i$，表示第 $x_i$ 道开胃菜和第 $y_i$ 道主菜不能搭配。

主菜和饮品，饮品和甜点的搭配需求也以相同的方式输入。

输出

如果不存在，输出 -1；

否则，输出最小花费。

数据规模

$1\le n_i\le 150000$，$0\le m_i\le 200000$，$1\le a_i,b_i,c_i,d_i\le 10^8$。

保证 $1\le x_i\le n_t$，$1\le y_i\le n_{t+1}$，且对于相同的 $t$，$(x_i,y_i)$ 互不相同。

阅读全文 »

505

发表于 2024-02-26 分类于 codeforces ， practice

给出一个 $n \times m$ 的 $01$ 矩阵，如果每个长宽都为偶数的正方形子矩阵内 $1$ 的个数都为奇数，则这是一个“好的”矩阵。如果能把矩阵改成“好的”，问最少改多少个数。如果不能，输出 $-1$。

阅读全文 »

Difference Array

发表于 2024-02-26 分类于 codeforces ， practice

你有一个初始长度为 $n$ 的有序数组 $a$（从小到大）。设 $a$ 当前长度为 $l$，你要对 $a$ 作差分，即令 $b_i = a_{i+1} - a_i(1\le i < l)$，然后将 $b$ 数组从小到大排序，接着让 $a_i = b_i(1 \le i < l)$，并继续执行上述操作。

显然，每一次操作后 $a$ 数组的长度都会减少 $1$；执行 $n - 1$ 次操作之后，$a$ 中只会剩下一个元素，请你输出这个剩下的元素。

输入包含多组数据，第一行一个正整数 $t(0 < t \le 10^4)$，表示数据组数。

对于每一组数据：