题目描述  珂朵莉给了你一个序列，有个子区间，求出她们各自的逆序对个数，然后加起来输出  输入描述:  第一行一个数 n 表示这个序列 a 的长度之后一行 n 个数，第i个数表示ai  输出描述:  输出一行一个数表示答案  题解 直接搞肯定不行了，那我们就考虑每一对逆序数对于答案的贡献吧。假如a[i]和a[j]组成一对逆序对，那么这对逆序对对于所有区间左界在[1,i]的范围，区间右界在[j,n]的范围的区间都有贡献，即它对答案贡献是。那我们就好搞了，用权值树状数组维护每个数字对应的坐标和，然后枚举j，在区间里面找大于的数字的坐标和，然后算出他的贡献加到答案里就好啦。最后注意答案爆long l...

题目描述  树国是一个有n个城市的国家，城市编号为1∼n。连接这些城市的道路网络形如一棵树，即任意两个城市之间有恰好一条路径。城市中有k个帮派，编号为1∼k。每个帮派会占据一些城市，以进行非法交易。有时帮派之间会结盟，这就使得城市更加不安全了。同一座城市中可能有多个帮派。当一些帮派结成联盟时，他们会更加强大，同时也更加危险。他们所控制的城市数会显著增加。具体地，一个联盟控制的城市是联盟中所有帮派所占据的城市，再加上这些城市两两之间路径上的所有城市。shy是树国的市长，他想要选择一个城市作为首都。在决定之前，他要先做一些调研。为此，他找来你帮他回答一些询问，你能做到吗？在每个询问中，shy会选择...

题目描述  小z放假了，准备到RRR城市旅行，其中这个城市有N个旅游景点。小z时间有限，只能在三个旅行景点进行游玩。小明租了辆车，司机很善良，说咱不计路程，只要你一次性缴费足够，我就带你走遍RRR城。小z很开心，直接就把钱一次性缴足了。然而小z心机很重，他想选择的路程尽量长。然而司机也很聪明，他每次从一个点走到另外一个点的时候都走最短路径。你能帮帮小z吗？需要保证这三个旅行景点一个作为起点，一个作为中转点一个作为终点。（一共三个景点，并且需要保证这三个景点不能重复）.  输入描述:  本题包含多组输入，第一行输入一个整数t，表示测试数据的组数每组测试数据第一行输入两个数N,M表示RRR城一共有...

题目描述  牛牛为了减（吃）肥（好），希望对他的零食序列有更深刻的了解，所以他把他的零食排成一列，然后对每一个零食的美味程度都打了分，现在他有可能执行两种操作：eat k：吃掉当前的第k个零食。右边的零食全部往左移动一位（编号减一）。query i j：查询当前第i个零食到第j个零食里面美味度最高的和最低的零食的美味度。  输入描述:  第一行包含两个数n, m，表示原始数组的元素个数和操作的个数。第二行包括n个数，表示原始数组。以下m行，每行格式为1 k或者2 i j，其中第一个数为1表示吃掉，为2表示询问。  输出描述:  对每个询问操作输出一行，包括两个数，表示该范围内的最小值和最大值。...

题目描述  小明是个大厨，早上起来他开始一天的工作。他所在的餐厅每天早上都会买好n件食材（每种食材的数量可以视为无限），小明从到达餐厅开始就连续工作T时间。每道菜肴的制作需要特定的一种食材以及一段时间，但是食材一旦放久就不新鲜了，菜的美味值会降低。第i道菜肴有三个属性ai，bi，ci，ai是该菜肴的美味值，bi是该菜肴所选食材不新鲜的速率，如果在第t时刻完成第i道菜则美味值为：ai-t*bi，完成这道菜需要ci的时间。小明希望在这T时间内能做出菜肴使得总美味值最大，所以小明求助于你。  输入描述:  第1行输入三个整数n，m，T，分别代表食材种类，菜肴种类和工作时间。第2行输入n个整数bi，代...

题目描述  给定两个长度为n的整数列A和B，每次你可以从A数列的左端或右端取走一个数。假设第i次取走的数为ax，则第i次取走的数的价值vi=bi⋅ax，现在希望你求出∑vi的最大值。  输入描述:  第一行一个数T，表示有T组数据。对于每组数据，第一行一个整数n，接下来两行分别给出A数列与B数列。  输出描述:  每一组数据输出一行，最大的∑vi。  题解 这道题还是很好想的，我们每次做的决策就是是选最左端的还是选择最右端的。我们可以设置dp[i][j]表示剩下的区间是从i到j的，也就是我们选了1~i-1和j+1到n。那么很明显，dp[i][j]=max(dp[i-1][j]+a[i]b[k]...

题目描述  给一个连通图，每次询问两点间最短路。每条边的长度都是1。  输入描述:  第一行两个整数n和m，表示图的点数和边数（1≤ n≤ 100000, 1≤ m≤ n+100）。接下来m行每行两个整数a和b，表示一条边（1≤ a, b≤ n）。保证没有自环和重边。保证图连通。接下来一个整数q表示询问的个数（1≤ q≤ 100000）。接下来q行每行两个整数a和b表示询问a和b之间的最短路。  输出描述:  每个询问输出一行表示答案。  题解 这道题我本来是不会的，通过阅读别人的题解才会，呜呜我好菜啊这道题边的范围很好玩，。我们先假设恰好是即图为一棵树，那么我们可以通过最近公共祖先求得两点的...

题目描述  平衡二叉树，顾名思义就是一棵“平衡”的二叉树。在这道题中，“平衡”的定义为，对于树中任意一个节点，都满足左右子树的高度差不超过 d. 空树的高度定义为0，单个节点的高度为1，其他情况下树的高度定义为根节点左右子树高度最大值 + 1. 一棵在高度上平衡的树，节点数可能不平衡，因此再定义一棵树的不平衡度为这棵树中所有节点的左右子树的节点数之差的最大值。给定平衡的定义参数d, 你需要求出所有高度为 n 的平衡树中不平衡度的最大值。  输入描述:  两个整数，n, d.  输出描述:  一个整数：所有高度为 n 的平衡树中不平衡度的最大值。  题解 对于这道题，我们最后要求的是高度为n的平...

题目描述  在大学期间，经常需要租借教室。大到院系举办活动，小到学习小组自习讨论，都需要向学校申请借教室。教室的大小功能不同，借教室人的身份不同，借教室的手续也不一样。面对海量租借教室的信息，我们自然希望编程解决这个问题。我们需要处理接下来n天的借教室信息，其中第i天学校有ri个教室可供租借。共有m份订单，每份订单用三个正整数描述，分别为dj, sj, tj，表示某租借者需要从第sj天到第tj天租借教室（包括第sj天和第tj天），每天需要租借dj个教室。我们假定，租借者对教室的大小、地点没有要求。即对于每份订单，我们只需要每天提供dj个教室，而它们具体是哪些教室，每天是否是相同的教室则不用考虑...

题目描述  旅行完了的牛牛又胖了，于是他终于下决心要戒掉零食，所以他带着他最爱的土豆回到了牛星，开始了在牛星种土豆和只吃土豆减肥的日子。（吃土豆能减肥么？）经过了辛勤的劳作，牛牛种的土豆奇迹般的收获了，于是他得到了很多很多很多很多的土豆（实在太多，数不过来了，你可以认为是无穷个）。他将这很多很多个土豆按照重量从小到大进行了排序，每个土豆的编号依次为1、2、3……N，然后他就惊奇地发现：由于牛星球的土壤很奇特，第i个土豆的重量正好是3^(i-1) 。现在牛牛饿了要吃掉其中的若干个土豆。他每次拿的土豆的数目是任意的，选的土豆也是任意的。选中的土豆的总重量即每个土豆重量之和。例如：牛牛这一次拿了第一...

题目描述  栗酱有一个长度为n的数列A，一个长度为m的数列B，现在询问A中有多少个长度为m的连续子序列A'，满足(a'1+b1)%k = (a'2+b2)%k = …… = (a'm + bm)%k。  输入描述:  第一行一个数T，表示有T组数据。对于每组数据，第一行三个整数，n, m, k。第一行输入n个数, a1,a2,…,an, 表示A数列中的数，第二行输入m个数, b1,b2,…,bm, 表示B数列中的数。  输出描述:  每一组数据输出一行，满足条件的连续子序列数量。  题解 对于这道题拿到手的第一感觉是暴力匹配吧，但复杂度太高。然后我们可以仔细想一想暴力的过程跟字符串匹配的暴力过...

题目描述  萌学姐在玩大型手游《futa go》，他现在准备进入作战环节，所以他准备安排自己的队伍。队伍配置里，可供玩家选择的作战人物被称作“从者”，玩家可以对每个“从者”可以装备至多1件的“概念礼装”，玩家具有一个cost上限值。详细定义如下：1、每个从者和概念礼装都具有攻击值ATK。2、每个从者和概念礼装都会占据一定的cost值。3、每个从者和概念礼装只能上场一次，不能重复使用。4、概念礼装只能装备在从者上，不能单独存在。5、选择的从者和概念礼装的cost值之和不能超过玩家的cost上限值。6、最多可以选择5名从者（在cost值限制下）。现在给出玩家仓库的每个从者和每件概念礼装的ATK值和...

题目描述  小A与小B这次两个人都被困在了迷宫里面的两个不同的位置，而他们希望能够迅速找到对方，然后再考虑如何逃离迷宫的事情。小A每次可以移动一个位置，而小B每次可以移动两次位置，小A移动的方向是上下左右左上左下右上右下8个方向，小B移动的方向是上下左右4个方向，请问他们最早什么时候能够找到对方，如果他们最终无法相遇，那么就输出”NO"。  输入描述:  第一行两个整数N，M分别表示迷宫的行和列。接下来一个N×M的矩阵其中"C"表示小A的位置,"D"表示小B的的位置，"＃"表示不可通过的障碍，"."则是可以正常通过的位置。字符用空格隔开第一行两个整数N，M分别表示迷宫的行和列。接下来一个N×M...

题目描述  小明现在在玩一个游戏，游戏来到了教学关卡，迷宫是一个N*M的矩阵。小明的起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。障碍物不能通过。小明如果现在在点（x，y）处，那么下一步只能走到相邻的四个格子中的某一个：（x+1，y），（x-1，y），（x，y+1），（x，y-1）；小明想要知道，现在他能否从起点走到终点。  输入描述:  本题包含多组数据。每组数据先输入两个数字N,M接下来N行，每行M个字符，表示地图的状态。数据范围：2<=N,M<=500保证有一个起点S，同时保证有一个终点E.  输出描述:  每组数据输出一行，如果小...