P2654【SDOI2011第2轮DAY2】消耗战问题描述 在一场战争中，战场由n个岛屿和n-1个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为1的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他k个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸 ...

P4343最小流:有源汇上下界问题描述 n 个点，m 条边，每条边 e有一个流量下界 lower(e) 和流量上界 upper(e)，给定源点 s 与汇点 t，求源点到汇点的最小流。 输入格式 第一行两个正整数 n、m、s、t。之后的 m行，每行四个整数 s、t、lower、upper 。 输出格式 如果无解，输出一行 please go home to sleep。否则输出最小流。 ...

P2284【L1 SOLO 第九场 HN11 day1】贪吃蛇问题描述 一些蛇覆盖了一个网格。每个格子要么是一个障碍物，要么是蛇的一部分。每条蛇占据了一条折线（拐角处只能水平和竖直连接），且至少占据两个格子。蛇与蛇之间不重叠，蛇也不会与自己重叠。每条蛇还必须满足以下两个条件中的一个： 两个端点所在的格子在网格的边界。 蛇构成一个环，即两个端点相邻（垂直或水平，不能斜着），至少要占据4个格子（否 ...

P2041【CQOI2011】动态逆序对问题描述 对于序列A，它的逆序对数定义为满足i < j，且Ai > Aj的数对(i,j)的个数。给1到n的一个排列，按照某种顺序依次删除m个元素，你的任务是在每次删除一个元素之前统计整个序列的逆序对数。 输入格式 输入第一行包含两个整数n和m，即初始元素的个数和删除的元素个数。以下n行每行包含一个1到n之间的正整数，即初始排列。以下m行每行 ...

P2266【HNOI2013 DAY2】游走问题描述 一个无向连通图，顶点从1 编号到N，边从1 编号到M。小Z 在该图上进行随机游走，初始时小Z 在1 号顶点，每一步小Z 以相等的概率随机选择当前顶点的某条边，沿着这条边走到下一个顶点，获得等于这条边的编号的分数。当小Z到达N 号顶点时游走结束，总分为所有获得的分数之和。现在，请你对这M 条边进行编号，使得小Z 获得的总分的期望值最小。 输入 ...

P2895 万径人踪灭题目描述 如果机房马上要关门了，或者你急着要和MM 约会，请直接跳到第六个自然段。VFleaKing注意到了这条上山下山的土路，有些地方能欣赏到美景，有些地方则不能。把上山的道路每10cm分为一小段，则对于每一小段，用a 表示能欣赏到美景，用b表示不能欣赏到美景，就能得到一个只含a,b的字符串s。当然由于下山和上山是一条路，所以下山的道路的字符串就是将上山的道路的字符串反过 ...

P4087【SDOI2017】硬币游戏问题描述 输入格式 输出格式 样例输入 3 3THTTTHHTT 样例输出 0.33333333330.25000000000.4166666667 提示 这题显然的想到高斯消元，关键是如何建立方程。不妨设每个人赢的概率分别为$P_1,P_2…P_n$,那么显然我们需要寻找他们之间的关系。此题的关键在于假设一个状态$N$，他表 ...

P4350生成魔咒问题描述 魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 1、2 拼凑起来形成一个魔咒串 [1,2]。 一个魔咒串 S 的非空字串被称为魔咒串 S 的生成魔咒。 例如 S=[1,2,1] 时，它的生成魔咒有 [1]、[2]、[1,2]、[2,1]、[1,2,1] 五种。S=[1,1,1] 时，它的生成魔咒有 [1]、[1,1]、[1,1,1] 三种 ...

P2663【ZJOI 2009 Day2】对称的正方形问题描述 Orez很喜欢搜集一些神秘的数据，并经常把它们排成一个矩阵进行研究。最近，Orez又得到了一些数据，并已经把它们排成了一个n行m列的矩阵。通过观察，Orez发现这些数据蕴涵了一个奇特的数，就是矩阵中上下对称且左右对称的正方形子矩阵的个数。 Orez自然很想知道这个数是多少，可是矩阵太大，无法去数。只能请你编个程序来计算出这 ...

P4000 [Ahoi2013]差异问题描述 输入格式 一行，一个字符串S 输出格式 一行，一个整数，表示所求值 样例输入 cacao 样例输出 54 提示 2<=N<=500000,S由小写英文字母组成 还是先说优美的自动机做法，将字符串反过来建立后缀自动机，那么后缀的前缀变成前缀的后缀，那么变成在后缀自动机parent树上求LCA 考虑到所有的LCP要求和， ...