祝馀宫

题面大秦为你打开题目传送门 题目描述给你一个环形跑道，一开始你只能走 $0$ 公里（如果你选择了从第 $i$ 个节点开始的话，那就是 $p_i$ 公里），第 $i$ 个节点可以让你多走 $p_i$ 公里，第 $i$ 个节点距离下一个节点有 $d_i$ 公里。对于每一个节点，如果能从他出发顺时针或逆时针走遍所有空间站，输出 TAK 否则输出 NIE 。 思路那么遇到这种环上的问题，第一步就是破环为链。这样的话可以免去这个跳一圈算来算去的事情。 然后再看看题目，如果起始点一样的话顺时针和逆时针其实就是反过来算的关系，所以说我们就考虑一个方向，然后到时候反过来做一遍就可以了。那么方便起见先考虑顺时针。 那么根据上面我稍微缩减了的题面，从某一个节点加完油出来，到达下一个节点的这个过程，其实就是 $p_i - d_i$ 这样的过程。正的 $p_i$ 是加的油量，负的 $d_i$ 表示走这么一段路我们会花掉那么多的油量。 也就是说，这个点的贡献我们可以认为就是 $p_i - d_i$ 。那么我们一开始的油量是 $0$ 这样一个一个经过节点的过程，其实就是求前缀和的过程，如果某一刻前缀和小于等于 ...

模板：单调队列首先给出自己封装好的模板吧。 12345678910111213141516template<typename T, unsigned int N, bool (*func)(T, T)>class MQueue {private : pair<T , int >q[N]; int hd, tl, len;public : inline void clear(int len) { this->len = len; hd = 0, tl = -1; } inline int size() { return tl - hd + 1; } inline bool empty() { return hd > tl; } inline void push(pair<T, int> ele) { while(!empty() && (*func)(ele.first, q[tl].first) ...

题面大秦为你打开题目传送门 题目描述某大学有 $n$ 个职员，编号为 $1\ldots n$。 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。 所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。 输入格式输入的第一行是一个整数 $n$。 第 $2$ 到第 $(n + 1)$ 行，每行一个整数，第 $(i+1)$ 行的整数表示 $i$ 号职员的快乐指数 $r_i$。 第 $(n + 2)$ 到第 $2n$ 行，每行输入一对整数 $l, k$，代表 $k$ 是 $l$ 的直接上司。 输出格式输出一行一个整数代表最大的快乐指数。 样例 #1样例输入 #11234567891011121314711111111 32 36 47 44 53 5 样例输出 #115 提示数据规模与约定对于 $100\%$ 的数据，保证 $1\leq n \leq 6 \times 10 ...

题面大秦为你打开题目传送门 题目描述在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？ 输入格式第一行有两个整数 $N$ , $M$ 用空格隔开。( $1 \leq N \leq 300$ , $1 \leq M \leq 300$ ) 接下来的 $N$ 行,第 $I+1$ 行包含两个整数 $k_i $和 $s_i$, $k_i$ 表示第I门课的直接先修课，$s_i$ 表示第I门课的学分。若 $k_i=0$ 表示没有直接先修课（$1 \leq {k_i} \leq N$ , $1 \leq {s_i} \leq 20$）。 输出格式只有一行，选 $M$ 门课程的最大得分。 样例 #1样例输入 #1123456787 42 20 10 42 17 17 62 ...

题面大秦为你打开题目传送门 题目描述有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点） 这棵树共有 $N$ 个结点（叶子点或者树枝分叉点），编号为 $1 \sim N$，树根编号一定是 $1$。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 $4$ 个树枝的树： 123452 5 \ / 3 4 \ / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量，求出最多能留住多少苹果。 输入格式第一行 $2$ 个整数 $N$ 和 $Q$，分别表示表示树的结点数，和要保留的树枝数量。 接下来 $N-1$ 行，每行 $3$ 个整数，描述一根树枝的信息：前 $2$ 个数是它连接的结点的编号，第 $3$ 个数是这根树枝上苹果的数量。 输出格式一个数，最多能留住的苹果的数量。 样例 #1样例输入 #1123455 21 3 11 4 102 3 203 5 20 样例输出 #1121 提示$1 \leqslant Q < N \leqslant 100$，每根树枝上的苹果 $\leqslan ...

题面大秦为你打开题目传送门 题目描述帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的 $n \times m$ 的矩阵，矩阵中的每个元素 $a_{i,j}$ 均为非负整数。游戏规则如下： 每次取数时须从每行各取走一个元素，共 $n$ 个。经过 $m$ 次后取完矩阵内所有元素； 每次取走的各个元素只能是该元素所在行的行首或行尾； 每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 $\times 2^i$，其中 $i$ 表示第 $i$ 次取数（从 $1$ 开始编号）； 游戏结束总得分为 $m$ 次取数得分之和。 帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。 输入格式输入文件包括 $n+1$ 行： 第一行为两个用空格隔开的整数 $n$ 和 $m$。 第 $2\sim n+1$ 行为 $n \times m$ 矩阵，其中每行有 $m$ 个用单个空格隔开的非负整数。 输出格式输出文件仅包含 $1$ 行，为一个整数，即输入矩阵取数后的最大得分。 样例 #1样例输入 #11232 31 2 33 4 2 样例输出 #1182 提示【数据范围 ...

题面大秦为你打开题目传送门 题目描述在 Mars 星球上，每个 Mars 人都随身佩带着一串能量项链。在项链上有 $N$ 颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是 Mars 人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为 $m$，尾标记为 $r$，后一颗能量珠的头标记为 $r$，尾标记为 $n$，则聚合后释放的能量为 $m \times r \times n$（Mars 单位），新产生的珠子的头标记为 $m$，尾标记为 $n$。 需要时，Mars 人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。 例如：设 $N=4$，$4$ 颗珠子的头标记与尾标记依次为 $(2,3)(3,5)(5,10)(10,2)$。我们用记号 $\oplus$ 表示两颗珠子的聚合操作，$ ...