MiniumCutDescription 从前有张图。图里 n 个顶点两两之间有 $n^2$ 种最小割。告诉你这 $n^2$ 个最小割。还原出这张图。 Input 第一行一个正整数 n, 表示图的顶点数。接下来 n 行每行 n 个非负整数, 第 i 行第 j 列的数表示第 i 个点与第 j 个点的最小割。点的编号从 1 开始。$v_{ij}$ ≤ $10^5$ 。保证 $v_{ii}$ = ...

塔- 问题描述 有一个塔,他的名字叫做粽粑,粽粑的每一层都有一个颜色 .粽粑非常厉害,它在吸收天地精华之后会长高.粽粑的长高方式有两种:1.在塔顶长出一层.2.在塔底长出一层,即原来的第一层变成第二层,第二层变成第三层,以此类推,新长出来的是第一层.粽粑有可能在某个时刻不是很开心,这个时候它会撤销它的前若干次长高.你现在想知道粽粑长高的奥秘,于是找到了粽粑,发现它的入口上写着这么一句话:要进入粽 ...

[CODE+]白金元首与莫斯科题面 如果说障碍格子已经确定，那么可以用一个简单的插头dp算出方案数。那么可以暴力枚举障碍格子，但这样是$O(n^2m^22^m)$的。 注意到由于不确定的状态格子只有一个，因此可以从左上到右下dp一次，再从右下到左上dp一次，令两次的dp数组分别为$F1[i][j][S]$和$F2[i][j][S]$，那么当$(x,y)$为障碍时，答案就是$\sum F1[i][ ...

[CODE+]博弈论与概率统计问题描述 样例输入 3 5001 12 34 4 样例输出 500000004200000002728571435 提示 首先，容易得到题目中的p是没有用的，因为Alice每一种输赢序列的出现概率是相等的，因此只需要算出每种排列的得分之和再除以$C_{n+m}^{n}$即可。 然后将赢记作1，输记作-1，那么得到一个序列$a_i$，对其求前缀和得 ...

P4028[HZOI 2015]疯狂的机器人问题描述 现在在二维平面内原点上有一只机器人 他每次操作可以选择向右走，向左走，向下走，向上走和不走(每次如果走只能走一格） 但是由于本蒟蒻施展的大魔法，机器人不能走到横坐标是负数或者纵坐标是负数的点上 否则他就会big bang 给定操作次数n，求有多少种不同的操作序列使得机器人在操作后会回到原点 输出答案模998244353后的 ...

Tree Description 从前有棵树。找出 k 个点 A 1 , A 2 , · · · , A k 。∑ k−1使得 i=1 dis(A i A i+1 ) 最小。 Input 第一行两个正整数 n, k, 表示数的顶点数和需要选出的点个数。接下来 n − 1 行每行 3 个非负整数 x, y, z, 表示从存在一条从 x 到 y 权值为 z 的边。1 ≤ k ≤ n。1 ≤ x ...

P4022 [HEOI2015]最短不公共子串问题描述 在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。 一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。 一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。 下面，给两个小写字母串A，B，请你计算： (1) A的一个最短的子串，它不 ...

C-问题描述 样例输入 40 0 R0 1 B1 1 R1 0 B 样例输出 2 提示 先考虑如果平行线恰好平行于y轴的情况，那么只需要按照x轴排序后求出最长连续R串即可。注意到如果有点在直线上，那么是可以通过微小扰动来解决的，因此一定合法。 然后考虑一般情况，我们考虑平行线来旋转，等价于坐标系旋转，那么两个点的位置位置关系发生改变当且仅当当前的平行线与两点确定的直线平行，因 ...

B问题描述 样例输入3 10ATTTAAAAA3 10ATTTTAAAAA 样例输出 NoYes 提示 构造一个串不含某些给定串，考虑将给定串构造AC自动机，并将其改造成有限状态自动机（每个点不存在的转移改成fail树上第一个该转移），将串结尾的标记沿着fail树传上去，然后如果自动机的转移中存在环，那么一定有解，否则该图为DAG，求出从根节点出发的最长路（不能经过串结尾），最长 ...

P3984[WC2010]重建计划问题描述 输入格式 第一行包含一个正整数N，表示X国的城市个数.第二行包含两个正整数L和U，表示政策要求的第一期重建方案中修建道路数的上下限接下来的N-1行描述重建小组的原有方案，每行三个正整数Ai,Bi,Vi分别表示道路(Ai,Bi),其价值为Vi 其中城市由1..N进行标号 输出格式 输出最大平均估值，保留三位小数 样例输入 1 42 31 2 ...