fork()==0世界线变动

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

0%

发表于 分类于 ，

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

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

    3≤n≤105

阅读全文 »

发表于 分类于 ，

    题目描述

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

    对于第 i 种菜类，共有 ni 种供选择。开胃菜、主菜、饮品和甜点价格分别为 ai、bi、ci、di。

    有些菜品不能搭配。对于开胃菜和主菜来说，有 m1 对不能搭配。对于主菜和饮品、饮品和甜点分别有 m2，m3 对。

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

    输入

    第一行有 n1、n2、n3、n4；

    接下来四行分别为 ai，bi，ci，di；

    接下来一行为 m1，接下来 m1 行中，每一行有 xi，yi，表示第 xi 道开胃菜和第 yi 道主菜不能搭配。

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

    输出

    如果不存在，输出 -1；

    否则，输出最小花费。

    数据规模

    1≤ni≤150000，0≤mi≤200000，1≤ai,bi,ci,di≤108。

    保证 1≤xi≤nt，1≤yi≤nt+1，且对于相同的 t，(xi,yi) 互不相同。

阅读全文 »

发表于 分类于 ，

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

阅读全文 »

发表于 分类于 ，

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

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

    输入包含多组数据，第一行一个正整数 t(0<t≤104)，表示数据组数。

    对于每一组数据：

    • 第一行一个正整数 n(1<n≤105)，表示 a 数组的初始长度

    • 第二行 n 个整数 ai(0≤ai≤5×105)，表示 a 数组。

阅读全文 »