题目：4.# 工作规划## 题目描述n*n* 台机器人正在完成任务。其中，第 i*i* 台机器人需要工作 ti*ti* 分钟才能完成任务。这些机器人之间有一些前后约束，其中约束关系共有m*m*条，每一条约束表示机器人 b*b* 要在机器人 a*a* 完成任务后才能开始工作。请问，所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的，所有机器人一定在有限时间内完成工作。## 输入格式第一行：两个整数 n*n* 和 m*m*• 第二行到第 n+1*n*+1 行：每个机器人需要的时间 ti*ti*​• 接下来 m*m* 行：每行有两个整数 a*a* 和 b*b*，表示第 b*b* 台机器人必须要等第 a*a* 台机器人任务完成之后才能开始工作。## 输出格式单个整数，表示所有机器人任务完成最少需要花多少时间。## 输入样例10 932913518228294123 24 81 76 57 108 110 92 45 3## 输出样例161## 说明提示1≤n≤1041≤*n*≤1041≤m≤50,0001≤*m*≤50,0001≤ti≤1051≤*ti*​≤1051≤ai,bi≤n1≤*ai*​,*bi*​≤*n*## 限制时间限制：1000ms内存限制：512MiB

题目：3.# 联盟## 题目描述在国际会议上，共有 n*n* 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况，请计算存在多少种合法的联盟分配方案。## 输入格式· 第一行：单个整数 n*n* 表示国家数量· 第二行到第 n*n* 行：在第 i+1*i*+1 行有 n−i*n*−*i* 个整数 ci,i+1,ci,i+2,…,ci,n*ci*,*i*+1,*ci*,*i*+2,…,*ci*,*n*，其中· ci,j=0*ci*,*j*=0 表示 i*i* 号国家与 j*j* 号国家不接壤· ci,j=1*ci*,*j*=1 表示 i*i* 号国家与 j*j* 号国家接壤## 输出格式单个整数：表示合法的联盟分配方案总数。## 输入样例#131 11## 输出样例#16## 输入样例#241 1 11 11## 输出样例#20## 说明提示数据范围· 对于 50%50% 的数据，1≤n≤121≤*n*≤12· 对于 100%100% 的数据，1≤n≤201≤*n*≤20样例1说明三国两两接壤，形成三角形。三个联盟的排列方案为 3!=63!=6 种。## 限制时间限制：1000ms内存限制：512MiB

题目：2.# 逻辑表达式## 题目描述给定一个逻辑表达式，以运算符做前缀的形式给出。它包含三种运算符：&、|、^：· & 表示逻辑与运算· | 表示逻辑或运算· ^ 表示逻辑异或运算表达式还包含三种基本逻辑值：0、1、?。每个 ? 必须赋值成为 0 或 1 中的一种，请问有多少种不同的赋值方式，可以让整个逻辑表达式的值为 0？由于答案可能很大，请输出方案数模 1,000,000,0071,000,000,007 的余数。前缀表达式的定义如下：· 0、1、? 都是前缀表达式；· 如果 x，y 都是前缀表达式，则 &xy、｜xy、^xy 都是前缀表达式；· 不满足以上两条规则的表达式都不是前缀表达式。## 输入格式单个字符串表示输入的前缀表达式## 输出格式单个整数：表示答案模 1,000,000,0071,000,000,007 的余数。## 输入样例#1&??## 输出样例#13## 输入样例#2||??|||?^?|0|1&???|??## 输出样例#24## 输入样例#3|?^?|0|&??||?^?|1??## 输出样例#364## 说明提示设 ∣s∣∣*s*∣ 表示输入字符串的长度· 50%50%的数据，1≤∣s∣<1,0001≤∣*s*∣<1,000· 100%100%的数据，1≤∣s∣<200,0001≤∣*s*∣<200,000## 限制时间限制：1000ms内存限制：512MiB

题目：1.# 子序列## 题目描述给定两个整数序列，第一个序列长度为 n*n*，第二个序列长度为 m*m*。请问，这两个序列有多少种公共的子序列？输出数量模 998244353998244353 的余数。所谓子序列，是指从原序列中选择部分或全部元素组成新序列，这些元素在原序列中不必连续，但要保持在原序列中的顺序。只要下标不同，哪怕数字相同，也要算成不同的子序列。## 输入格式· 第一行：两个整数表示 n*n* 与 m*m*；· 第二行： n*n* 个数字 a1,a2,⋯ ,an*a*1,*a*2,⋯,*an*；· 第三行：m*m* 个数字 b1,b2,⋯ ,bm*b*1,*b*2,⋯,*bm*；## 输出格式单个整数表示答案。## 输入样例4 33 4 6 23 3 2## 输出样例6## 说明提示· 1≤n,m≤20001≤*n*,*m*≤2000· 1≤ai,bj≤100,0001≤*ai*,*bj*≤100,000## 限制时间限制：1000ms内存限制：512MiB

题目：4.是不是堆二叉堆可以用一棵完全二叉树来实现，但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。时间限制：1000内存限制：65536输入输入在一行中给出两个正整数：m（≤ 100）是将要测试的完全二叉树的数量；n（1 < n ≤ 1000）是完全二叉树中的结点数。 随后 m 行，每行给出 n 个互不相同的键值（均在整型范围内），为完全二叉树的层序遍历序列。输出对输入的每棵完全二叉树，如果它是最大堆（大顶堆），就在一行中输出 `Max Heap`；如果是最小堆（小顶堆），则输出 `Min Heap`；如果根本不是堆，则输出 `Not Heap`。然后在下一行输出这棵树的后序遍历序列。同行数字间以 1 个空格分隔，行首尾不得有多余空格。样例输入3 898 72 86 60 65 12 23 508 38 25 58 52 82 70 6010 28 15 12 34 9 8 56样例输出Max Heap50 60 65 72 12 23 86 98Min Heap60 58 52 38 82 70 25 8Not Heap56 12 34 28 9 8 15 10

题目：3.树的偏斜度对于一棵二叉树，令 nL 表示仅有左孩子的结点的个数，令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题就请你计算任一棵给定二叉树的 Ds。时间限制：1000内存限制：65536输入输入在第一行给出正整数 n (≤ 103)，为二叉树中结点个数。随后两行先后给出这棵树的后序遍历和中序遍历序列，键值为 1 到 n 的整数。同行数字间以空格分隔。输出在一行中按以下格式输出树的偏斜度： Ds = nL - nR样例输入71 2 7 5 4 3 61 2 3 4 7 5 6样例输出2 = 3 - 1

题目：2.网红点打卡攻略一个旅游景点，如果被带火了的话，就被称为“网红点”。大家来网红点游玩，俗称“打卡”。在各个网红点打卡的快（省）乐（钱）方法称为“攻略”。你的任务就是从一大堆攻略中，找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。时间限制：1000内存限制：65536输入首先第一行给出两个正整数：网红点的个数 N（1 < N ≤ 200）和网红点之间通路的条数 M。随后 M 行，每行给出有通路的两个网红点、以及这条路上的旅行花费（为正整数），格式为“网红点1 网红点2 费用”，其中网红点从 1 到 N 编号；同时也给出你家到某些网红点的花费，格式相同，其中你家的编号固定为 0。 再下一行给出一个正整数 K，是待检验的攻略的数量。随后 K 行，每行给出一条待检攻略，格式为： n V1 V2 … Vn 其中 n (≤ 200) 是攻略中的网红点数，Vi 是路径上的网红点编号。这里假设你从家里出发，从 V1 开始打卡，最后从 Vn 回家。输出在第一行输出满足要求的攻略的个数。 在第二行中，首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号（从 1 开始），然后输出这个攻略的总路费，其间以一个空格分隔。如果这样的攻略不唯一，则输出序号最小的那个。 题目保证至少存在一个有效攻略，并且总路费不超过 109。样例输入6 130 5 26 2 26 0 13 4 21 5 22 5 13 1 14 1 21 6 16 3 21 2 14 5 32 0 276 5 1 4 3 6 26 5 2 1 6 3 48 6 2 1 6 3 4 5 23 2 1 56 6 1 3 4 5 27 6 2 1 3 4 5 26 5 2 1 4 3 6样例输出35 11提示样例说明： 第 2、3、4、6 条都不满足攻略的基本要求，即不能做到从家里出发，在每个网红点打卡仅一次，且能回到家里。所以满足条件的攻略有 3 条。 第 1 条攻略的总路费是：(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 + (3->6) 2 + (6->2) 2 + (2->0) 2 = 14； 第 5 条攻略的总路费同理可算得：1 + 1 + 1 + 2 + 3 + 1 + 2 = 11，是一条更省钱的攻略； 第 7 条攻略的总路费同理可算得：2 + 1 + 1 + 2 + 2 + 2 + 1 = 11，与第 5 条花费相同，但序号较大，所以不输出。

题目：1.树的同构给定两棵树 T1 和 T2。如果 T1 可以通过若干次左右孩子互换就变成 T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。图2现给定两棵树，请你判断它们是否是同构的。时间限制：1000内存限制：65536输入输入给出2棵二叉树的信息。对于每棵树，首先在一行中给出一个非负整数 n(≤ 10)，即该树的结点数（此时假设结点从 0 到 n -1 编号）；随后 n 行，第 i 行对应编号第 i 个结点，给出该结点中存储的 1 个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出 “-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。输出如果两棵树是同构的，输出“Yes”，否则输出“No”。样例输入样例#1（对应图1）：8A 1 2B 3 4C 5 -D - -E 6 -G 7 -F - -H - -8G - 4B 7 6F - -A 5 1H - -C 0 -D - -E 2 -样例#2（对应图2）：8B 5 7F - -A 0 3C 6 -H - -D - -G 4 -E 1 -8D 6 -B 5 -E - -H - -C 0 2G - 3F - -A 1 4样例输出样例#1：Yes样例#2：No

题目：4.

题目：3.