fork()==0世界线变动

正在加载今日诗词....

0%

发表于 分类于 ，

    给定一棵 $n$ 个点的无根树，要求给每条边分配一个正整数权值，使得任意两个叶子节点之间路径上的边权异或值为 $0$。求最少要多少种不同权值，以及最多可以使用多少种不同权值。

    这里，填入的边权值可以为任意大。

    $3 \le n\le 10^5$

阅读全文 »

发表于 分类于 ，

    题目描述

    有 $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)$ 互不相同。

阅读全文 »

发表于 分类于 ，

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

阅读全文 »

发表于 分类于 ，

    你有一个初始长度为 $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)$，表示数据组数。

    对于每一组数据：

    • 第一行一个正整数 $n(1 < n \le 10^5)$，表示 $a$ 数组的初始长度

    • 第二行 $n$ 个整数 $a_i(0 \le a_i \le 5\times10^5)$，表示 $a$ 数组。

阅读全文 »