Codeforces 656 Div3 E. Directing Edges 链接：https://codeforces.com/problemset/problem/1385/E 提示：拓扑排序 看到有向无环图可以想到的性质吧 Codeforces 656 Div3 F. Directing Edges 链接：https://codeforces.com/problemset/problem/1385/F 提示：贪心的去删节点数大于k的就可以了 Codeforces 656 Div3 G. Columns Swaps 链接：https://codeforces.com/proble...

题目描述 Rinne 喜欢 OI。在 9102 年的 PION 中，她在初赛遇到了这样一道题目：阅读下列代码，然后回答问题。补充：建树过程中会更新lc和rc，这实质上是一个二叉查找树的插入过程。定义一个玄学节点叫做 R，每次操作读入 val ，执行 Insert(R,val)。问题：每次 Insert 操作结束之后，输出当前节点的深度和。这里我们定义 R 节点的深度为 0。 输入描述: 第一行一个整数 N，表示操作次数。接下来 N 行，第 i 行有一个值 ，表示第 i 次操作的 。 输出描述: N 行，每行输出该次操作完后的答案。 题解 题目中代码所建出来的二叉树一个节点的左子树上的值...

题目描述 小 Bo 有 n 个正整数 a1..an，以及一个权值序列 w1…wn，现在他定义 。现在他想知道 的值，需要你来帮帮他。你只需要输出答案对 109+7 取模后的值 输入描述: 第一行一个正整数 n第二行 n 个正整数 a1..an第三行 n 个正整数 w1..wn 输出描述: 输出答案对 109+7 取模后的值 题解 这种题我们就把式子展开找规律就好了我以n=6为例仔细观察会发现w1和w6，w2和w5，w3和w4的系数是相同的，并且对于每个系数之间都是加上一段连续的区间和（或者减去一段连续的区间和）而得到的。然后我们就可以根据推出来的规律写代码啦 代码 /* * C...

题目描述 有n个木块排成一行，从左到右依次编号为1~n。你有k种颜色的油漆，其中第i种颜色的油漆足够涂ci个木块。 所有油漆刚好足够涂满所有木块，即c1+c2+...+ck=n。相邻两个木块涂相同色显得很难看，所以你希望统计任意两个相邻木块颜色不同的着色方案。 输入描述: 第一行为一个正整数k，第二行包含k个整数c1, c2, ... , ck。 输出描述: 输出一个整数，即方案总数模1,000,000,007的结果 题解 一共有15种颜色，如果直接从颜色入手会比较麻烦， 我们考虑存储剩余能涂x个木块的油漆有多少种。 设置dp[a][b][c][d][e][last]为还剩a种可以...

题目描述 小H有n个碗需要放进橱柜，她希望将他们叠起来放置。你知道每个碗都是规则的圆柱体，并且都是上宽下窄，你已经测量出了每个碗的两个半径及高，请你帮小H找出一种叠放顺序，使得叠放出来的碗堆的高度尽量小，比如：100%数据满足n < = 9。所有输入的数绝对值不超过1000。 输入描述: 第一行一个整数n，表示碗的数目。以下n行，每行三个整数h，r1，r2。分别表示碗高及两个半径。其中r1<r2 输出描述: 仅一个数，表示最小的高度。答案四舍五入取整 题解 几何题是我头秃 我们首先分情况讨论一下两个碗放在一起时的状态：（以下讨论的均为放进去的碗的下碗底距离外面的碗的上碗...

题目描述 给你一棵树，最开始点权为0，每次将与一个点x树上距离<=1的所有点点权+1，之后询问这些点修改后的点权和. 输入描述: 第一行两个数n和m第二行n-1个数，第i个数fa[i + 1]表示i + 1点的父亲编号，保证fa[i + 1]<i + 1第三行m个数，每个数x依次表示这次操作的点是x 输出描述: 输出一个数，即这m次操作的答案的hash值如果是第i次操作，这次操作结果为ans,则这个hash值加上i * ans,输出hash值对19260817取模的结果 题解 对于本题，数据范围太大，没办法进行暴力，我们考虑谁对当前点有贡献。 对于一个点，对他有贡献的点...

题目描述 windy的生日到了，为了庆祝生日，他的朋友们帮他买了一个边长分别为 X 和 Y 的矩形蛋糕。现在包括windy ，一共有 N 个人来分这块大蛋糕，要求每个人必须获得相同面积的蛋糕。windy主刀，每一切只能平行于一块蛋糕 的一边（任意一边），并且必须把这块蛋糕切成两块。这样，要切成 N 块蛋糕，windy必须切 N-1 次。为了使得每块蛋糕看起来漂亮，我们要求 N块蛋糕的长边与短边的比值的最大值最小。你能帮助windy求出这个比值么？ 输入描述: 包含三个整数，X Y N。1 ≤ X,Y ≤ 10000 ； 1 ≤ N ≤ 10 输出描述: 包含一个浮点数，保留6位小数。...

题目描述 给一个由小写字母组成的字符串，我们可以用一种简单的方法来压缩其中的重复信息。压缩后的字符串除了小 写字母外还可以（但不必）包含大写字母R与M，其中M标记重复串的开始，R重复从上一个M（如果当前位置左边没 有M，则从串的开始算起）开始的解压结果（称为缓冲串）。bcdcdcdcd可以压缩为bMcdRR，另一个例子是abcabcdabcabcdxyxyz可以被压缩为abcRdRMxyRz。 输入描述: 输入仅一行，包含待压缩字符串，仅包含小写字母，长度为n。 输出描述: 输出仅一行，即压缩后字符串的最短长度。 题解 由于每次压缩的都是连续的一段，就像一个个小区间一样，所以考虑区...

题目描述 Island 发生了一场***！现在 Rinne 要和 Setsuna 立马到地上世界去。众所周知：Island 是有一些奇怪的城镇和道路构成的（题目需要，游戏党勿喷），有些城镇之间用双向道路连接起来了，且每条道路有它自己的距离。但是有一些城镇已经被派兵***，虽然主角可以逆天改命强闯，但是为了体验该游戏的平衡性，他们只能穿过不超过 K 次被***的城镇。定义“穿过”：从一个***的点出发到达任意一个点，都会使得次数加1现在他们想从 1 号城镇最快的走到 n 号城镇（即出口），现在他们想让你告诉他们最短需要走多少路。 输入描述: 第一行三个整数 n,m,k，分别表示城镇数量，边...

题目描述 X王国有n位官员，编号从1到n。国王是1号官员。除了国王以外，每个官员都有一个上司。我们称这个官员是这个上司的下属。上司的编号总比下属小。我们定义一个官员的影响力为他所有下属的影响力之和再加1。例如，一个没有下属的官员的影响力是1。国王的影响力总是n。任何一位有下属的官员总是选择他的下属中影响力最高的作为他的心腹（有若干下属影响力相同的话则会选择编号最小的）。一位官员得到一条消息后，他就要把消息传达给国王。我们定义一位官员的花费为他将消息传达给国王的花费。国王自己的花费为0。如果一位官员是他上司的心腹，则他的花费等于他上司的花费，否则他的花费为他上司的花费加1。由于时代和平，消息并...

题目描述 小雨所在的城市一共有 mmm 条地铁线，分别标号为 1 号线，2 号线，……，m 号线。整个城市一共有 nnn 个车站，编号为 1∼n1 \sim n1∼n 。其中坐 i 号线需要花费 aia_iai​ 的价格，每坐一站就需要多花费 bib_ibi​ 的价格。i 号线有 cic_ici​ 个车站，而且这 cic_ici​ 个车站都已知，如果某一站有多条地铁线经过，则可以在这一站换乘到另一条地铁线，并且能多次换乘。现在小雨想从第 sss 个车站坐地铁到第 ttt 个车站，地铁等待时间忽略不计，求最少花费的价格，若不能到达输出 -1 。（地铁是双向的，所以 sss 可能大于 ttt） ...

题目描述 又到暑假了，住在城市A的Car想和朋友一起去城市B旅游。她知道每个城市都有四个飞机场，分别位于一个矩形的四个顶点上，同一个城市中两个机场之间有一条笔直的高速铁路，第I个城市中高速铁路了的单位里程价格为Ti，任意两个不同城市的机场之间均有航线，所有航线单位里程的价格均为t。图例（从上而下）机场高速铁路飞机航线注意：图中并没有标出所有的铁路与航线。那么Car应如何安排到城市B的路线才能尽可能的节省花费呢?她发现这并不是一个简单的问题，于是她来向你请教。任务：找出一条从城市A到B的旅游路线，出发和到达城市中的机场可以任意选取，要求总的花费最少。 输入描述: 第一行为一个正整数n( 0...

题目描述 给一个没有重边的二分图, 要求给边染色. 有公共点的边不能同色. 问最少用多少种颜色, 并任意构造一组方案. 输入描述: 第一行两个数n和m表示图的点数和边数(0<n<1001,0<m<2001).之后m行每行2个数表示一条边的两个端点. 点从1编号到n.保证给的是二分图. 输出描述: 第一行一个数k表示需要多少种颜***r>接下来m行每行一个数表示输入的边的颜色. 按照输入的顺序输出, 颜色从1编号到k. 题解 用公共点的边不同色，即从一个点出来的边颜色不同。二分图里有一个定理，二分图边着色所需最小颜色数，等于图中点的最大度数。现在的问题...

题目描述 帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个元素aij均为非负整数。游戏规则如下：1.每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；2.每次取走的各个元素只能是该元素所在行的行首或行尾；3.每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分 = 被取走的元素值 * 2i，其中i表示第i次取数（从1开始编号）；4.游戏结束总得分为m次取数得分之和。帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。 输入描述: 第1行为两个用空格隔开的整数n和m。第2~n+1行为n*m矩阵，其中每行有m个用单个空格隔开的非...