Description Farmer John went to cut some wood and left N (2 ≤ N ≤ 100,000) cows eating the grass, as usual. When he returned, he found to his horror that the cluster of cows was in his garden eating his beautiful flowers. Wanting to minimize the subsequent damage, FJ decided to take immediate action...

Description 给出1~n的一个排列，统计该排列有多少个长度为奇数的连续子序列的中位数是b。中位数是指把所有元素从小到大排列后，位于中间的数。 Solution 经典中位数计数问题，记得以前百度之星也出过类似的题，这道题有一个限定范围是要奇数区间的我们很容易想到，奇数下标到偶数下标或者偶数下标到奇数下标的长度一定是奇数的对于每个数字，只可能大于，等于，小于b，于是可以重新分别赋值为1，0，-1那么维护两个前缀和和一个now，如果当前在奇数下标，查询偶数的前缀和的cnt2[now]，否则查询奇数的前缀和cnt1[now]now 是 1到i 的前缀和，因为如果有两个位置比如 2 和 5 的...

Description 小sun最近为了应付考试，正在复习图论，他现在学到了图的遍历，觉得太简单了，于是他想到了一个更加复杂的问题： 无向图有n个点，从点1开始遍历，但是规定：按照每次“走两步”的方式来遍历整个图。可以发现按照每次走两步的方法，不一定能够遍历整个图，所以现在小sun想问你，最少加几条边，可以完整的遍历整个图。 Solution 首先考虑要完整遍历整个图，需要联通，先 dfs 找到连通块数量 ， 然后把连通块连接起来需要加 条边其次，这道题他的遍历方式有所不同，他是两步两步走，那么如果存在一个奇数环，我们可以通过走这个环来调节使得我们总能到达每个点，那么我们可以先找下是否存在奇数...

Description 牛客幼儿园的小朋友课间操时间需要按照学号从小到大排队，但是他们太小了只能站成一列顺序却不对，现在幼儿园的阿姨需要帮忙交换小朋友的位置让他们最终有序，阿姨希望能尽快完成交换操作，问最少需要交换多少次，才能使得小朋友们从小到大排好。注意：每个小朋友的学号不同，但是未必连续，因为可能有小朋友请假了没有来。 Solution 这道题有点意思, 一开始以为是求逆序数, 但是仔细一看他跟我们之前求的最小交换数的条件有所不同简单的说，这道题不限定交换的是相邻两个，因此我们可以自由交换我们可以推断出有一个循环节，就可以少交换一次，因为n个元素的循环节，只需交换n-1次即可有序。那么对于...

Description 你在打比赛，这场比赛总共有12个题 对于第i个题，你的队伍有a[i]的几率解决她 如果解决不了她呢？ 由于所有人讨论的都很大声 所以你有b[i]的概率从左边那个队那里听会这个题的做法 有c[i]的概率从右边那个队那里听会这个题的做法 请问最终你们队伍解出0-12题的概率分别是多少 Solution1 首先我们可以计算出每道题做不出来的概率 然后因为只有 12 道题, 每道题要么做对要么做错, 我们可以做 当前做对的题数小于 的时候, 我们可以往对和不对的方向搜索如果做对的题数等于 , 那么我们只能往不对的方向搜索 Code1 #include<bits/stdc+...

只会ABC, 但是第一题好像数据出锅了rejudge后wa的全过了, 卡了半个小时?(雾)实际做题时间大概40分钟 A. 怪盗-1412 Solution 贪心的放, 怎么放最贪呢? 4 和 2 可以不用管直接放一起, 重点在两个1因为最终答案是 要把 n 拆分成 和 , 比如 5 拆成 1 和 4 或者 2 和 3肯定是拆成 和 最优啦 Code #include<bits/stdc++.h> typedef long long ll; using namespace std; int main() { ios::sync_with_stdio(false), cin.tie(n...

用户端的使用手册 快速入门 在右上角点击 ,按照要求注册好账号,点击 ,开始你的做题之旅吧! Problem 这里可以看到管理员设置的题目以及题目的难度(前提是管理员设置了),点击题目可以进入并做题。 Status 这里看到自己和其他人交题的情况,包括判题结果和所提交代码内存/运行时间等信息。 Contest 这里可以进入比赛界面,可以显示比赛的举行时间和持续时间，并进入比赛。 Rank 可以看到累计做题数和 的排行。 其他功能 暂未开放 管理员的使用手册 添加题目 根据提示, 填写题目的题面,输入输出样例和时间内存限制,可以设定是否公开(可以造完题目再公开)。同时需要上传数据文件压缩包,输入...

Description 帕秋莉掌握了一种土属性魔法  这种魔法可以在一片k×k大小的一个正方形区域内产生地震 但是如果某片即将产生地震的区域内有建筑物，帕秋莉会停止施法 整个地图大小为n×m，其中一些地方有建筑 请问有多少种可能的情况，使得帕秋莉会停止施法 Solution 题意就是要找每一个 的小正方形里至少有一个1的数量显然我们可以通过二维前缀和处理出(1, 1) 到 (n, m) 的数量然后通过枚举处理出答案，具体思想是容斥令 为 (1, 1) 到 (n, m) 的1的数量有递推式子 这个式子可以看成以下图形减去上下两个矩形的1的数量，然后蓝色的区域会被减两次，要加回来一次最后我们枚举所...

这题数据好多细节，气死本萌妹了 Description  一个数轴，每一个储物点会有一些东西，同时它们之间存在距离。每次给个区间 ,查询把这个区间内所有储物点的东西运到另外一个储物点的代价是多少？比如储物点 有 个东西，要运到储物点 ，代价为 就是储物点间的距离。  Solution 对于一个区间 , 总的代价为 对于最终点 , 我们可以分三种情况:   , 那么上面式子里的绝对值去掉得到  , 那么上面式子里的绝对值去掉得到  , 那么对区间 分别做上述的操作即可  观察发现可以维护两个前缀和, 和 , 那么上述每次查询操作就能够 注意到数据好大, 前缀和都要注意取模，然后负数取模也要注意。...

Description 小明来到一个由n x m个格子组成的迷宫，有些格子是陷阱，用'#'表示，小明进入陷阱就会死亡，'.'表示没有陷阱。小明所在的位置用'S'表示，目的地用'T'表示。 小明只能向上下左右相邻的格子移动，每移动一次花费1秒。 有q个单向传送阵，每个传送阵各有一个入口和一个出口，入口和出口都在迷宫的格子里，当走到或被传送到一个有传送阵入口的格子时，小明可以选择是否开启传送阵。如果开启传送阵,小明就会被传送到出口对应的格子里，这个过程会花费3秒；如果不开启传送阵，将不会发生任何事情，小明可以继续向上下左右四个方向移动。 一个格子可能既有多个入口，又有多个出口，小明可以选择任意一个...

Description  一个n个节点的二叉树tree的中序遍历为（l,2,3,…,n），其中数字1,2,3,…,n为节点编号。每个节点都有一个分数（均为正整数），记第j个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下：  subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数  若某个子树为主，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1,2,3,…,n）且加分最高的二叉树tree。要求输出： （1）tree的最高加分 （2）tree的前序...

心态炸了 不小心关掉 又要重新写 Description 一共有 个数，第 个数是 可以取 中任意的一个值。设 ，求 S 种类数。 Solution 这个问题的难点在于如何统计出所有和可能出现的情况，并且不能重复。很容易想到用桶去存储每一个数，即某个和能够组合出来则为1，否则为0不妨令 表示为第 次选择时，和为 的情况是否出现过但是内存方面需要 的 内存，显然是不可接受的那么我们考虑用 优化一下，有递推方程 代表第 次选择的时候是否能从当前状态转移到和为 的状态 Code #include<bits/stdc++.h> typedef long long ll; using nam...

早上起来找几道有意思点的题(过的人少)来写一写吧, 太简单就不写了 B. k-size字符串 Solution 赛后发现自己通过 90%, 先去上课, 回来写update 没想到过了五六天了这题一看数据范围 k 好大, 组合数怎么做啊然后显然 的时候是无解的那么对 的讨论降到的 级别既然一定要k个, 考虑先放足k个满足条件的情况即ababab 这样放, 这样要考虑一下当 为奇数的时候 a, b的个数相差1，偶数的时候相等同理我们考虑bababa，当偶数时这两种情况的数量是一样的乘 2 就行，奇数的话就两者的种类相加那么我们只需要考虑放了 abababab... 后对于剩下的 a, b的分配方案...