BearChild's Blog

区间 Time Limit: 60 Sec Memory Limit: 256 MB Description 在数轴上有 n个闭区间 [l1,r1],[l2,r2],…,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。 对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。 求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。 Input 第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n 接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。 Output 只有一行，包含一个正整数，即最小花费。 Sample Input 6 3 　3 5 　1 2 　3 4 　2 2 　1 5 　1 4 Sample Output 2 HINT N<=500000,M<=2000 ...

排序 Time Limit: 60 Sec Memory Limit: 256 MB Description 在2016年，佳媛姐姐喜欢上了数字序列。 因而他经常研究关于序列的一些奇奇怪怪的问题，现在他在研究一个难题，需要你来帮助他。 这个难题是这样子的： 给出一个1到n的全排列，现在对这个全排列序列进行m次局部排序，排序分为两种： 1: (0,l,r)表示将区间[l,r]的数字升序排序 2: (1,l,r)表示将区间[l,r]的数字降序排序 最后询问第q位置上的数字。 Input 输入数据的第一行为两个整数n和m。 n表示序列的长度，m表示局部排序的次数。 第二行为n个整数，表示1到n的一个全排列。 接下来输入m行，每一行有三个整数op, l, r, op为0代表升序排序，op为1代表降序排序, l, r 表示排序的区间。 最后输入一个整数q，q表示排序完之后询问的位置。 Output 输出数据仅有一行，一个整数，表示按照顺序将全部的部分排序结束后第q位置上的数字。 Sample Input 6 3 　1 6 2 5 3 4 　0 1 4 　1 3 6 　0 2 4 　3 Sampl ...

我也不知道题目名字是什么 Time Limit: 10 Sec Memory Limit: 512 MB Description 给定一个序列A[i]，每次询问l,r，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串 Input 第一行n，表示A数组有多少元素 　接下来一行为n个整数A[i] 　接下来一个整数Q，表示询问数量 　接下来Q行，每行2个整数l，r Output 对于每个询问，求[l,r]内最长子串，使得该子串为不上升子串或不下降子串 Sample Input 9 　1 2 3 4 5 6 5 4 3 　5 　1 6 　1 7 　2 7 　1 9 　5 9 Sample Output 6 　6 　5 　6 　4 HINT N,Q<=50000 Solution 直接上线段树，记录一下一个区间内：左边最长，右边最长，整体最优。再分一下不下降和不上升即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545 ...

数据结构C Time Limit: 20 Sec Memory Limit: 512 MB Description Input Output Sample Input Sample Output HINT Solution 首先，D操作为删除操作显然不可做，又发现这道题可以离线处理，那么我们考虑倒着来，维护加入操作。 那么这时候，D操作就变为了合并操作，那么这时候我们只需要维护一个：可以支持单点修改、查询第 k 大、信息可合并的数据结构即可。 显然构建若干棵权值线段树即可！对于每个联通块维护一棵线段树，用并查集判断两点是否在一个块内。 这时候，D操作显然判断一下两点是否在一个联通块内，不在则合并两棵线段树；Q操作就是查询第 k 大，在树上二分即可；C操作就是原来值个数-1，新加入值个数+1。 Code 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737 ...

相关分析 Time Limit: 10 Sec Memory Limit: 128 MB Description Frank对天文学非常感兴趣，他经常用望远镜看星星，同时记录下它们的信息，比如亮度、颜色等等，进而估算出星星的距离，半径等等。 Frank不仅喜欢观测，还喜欢分析观测到的数据。他经常分析两个参数之间（比如亮度和半径）是否存在某种关系。 现在Frank要分析参数X与Y之间的关系。 他有n组观测数据，第i组观测数据记录了x_i和y_i。 他需要一下几种操作 1 L,R：用直线拟合第L组到底R组观测数据。 用xx表示这些观测数据中x的平均数，用yy表示这些观测数据中y的平均数，即 xx=Σx_i/(R-L+1)(L<=i<=R) yy=Σy_i/(R-L+1)(L<=i<=R) 如果直线方程是y=ax+b，那么a应当这样计算： a=(Σ(x_i-xx)(y_i-yy))/(Σ(x_i-xx)(x_i-xx)) (L<=i<=R) 你需要帮助Frank计算a。 2 L,R,S,T： Frank发现测量数据第L组到底R组数据有误差，对每个i满足L ...

魔法 Time Limit: 10 Sec Memory Limit: 256 MB Description Input Output 仅一行一个整数表示答案。 Sample Input 4 10 　　7 2 8 5 Sample Output 2 HINT Solution 我们找一下规律，显然发现是就是Σa[i]*C(n-1,i-1)。然后问题主要就转化为了怎么快速求组合数C(n,i)在模一个非质数情况下的值。 首先我们先确定一个式子： 然后我们立马想到了一个暴力分解质因数的方法。就是记录所有的(n-i+1)和(i)的质因数，然后用上面的质因数个数减去下面的质因数个数，剩下的乘起来，就不用求取模了。 但是我们发现，这样显然会TLE，我们考虑如何优化。优化的话显然就是要找到一个办法不把多的质因数都彻底分解出来。我们来继续思考： 我们可以先求出模数的质因数，再对于(n-i+1)和(i)分解质因数。这时候如果质因数和模数的质因数一样，由于不互质没有逆元，就把它记录下来，等下用快速幂乘起来就行了。那么这时候其余的质因数就可以直接求逆元了，由于模数不是质数，我们运用这个公式：（phi ...

String Problem Time Limit: 10 Sec Memory Limit: 64 MB Description Input Output Sample Input 1 　　3 　　135 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　1 2 　　0 0 3 　　1 0 0 　　4 0 0 Sample Output 3 HINT Solution 官方题解： 首先将点分为3类 第一类：Pij 表示第i个点和第j个点组合的点，那么Pij的权值等于w[i][j]+w[j][i]（表示得到的价值） 第二类：原串中的n个点每个点拆出一个点，第i个点权值为 –a[s[i]] （表示需要的花费） **第三类：**对于10种字符拆出10个点，每个点的权值为 -(b[x]-a[x]) 那么我们可以得到一个关系图 ，对于第一类中的点Pij，如果想要选择Pij，你就必须要选中第二类中的点i和j，对于第二类中的点如果你想选中第i个点，其对应的字符s[i]，那么就必须选中第三类中s[i] 对应的点，因为每个种类的点 ...

看电影 Time Limit: 10 Sec Memory Limit: 259 MB Description 到了难得的假期，小白班上组织大家去看电影。但由于假期里看电影的人太多，很难做到让全班看上同一场电影，最后大家在一个偏僻的小胡同里找到了一家电影院。但这家电影院分配座位的方式很特殊，具体方式如下： 1. 电影院的座位共有K个，并被标号为1…K，每个人买完票后会被随机指定一个座位，具体来说是从1…K中等可能的随机选取一个正整数，设其为L。 2. 如果编号L的座位是空位，则这个座位就分配给此人，否则将L加一，继续前面的步骤。 3. 如果在第二步中不存在编号L的座位，则该人只能站着看电影，即所谓的站票。小白班上共有N人（包括小白自己），作为数学爱好者，小白想知道全班都能够有座位的概率是多少。 Input 输入文件第一行有且只有一个正整数T，表示测试数据的组数。 第2～T+1行，每行两个正整数N,K，用单个空格隔开，其含义同题目描述。 Output 输出文件共包含T行。第i行应包含两个用空格隔开的整数A,B，表示输入文件中的第i组数据的答案为A/B。（注意，这里要求将答案化为既约分 ...

tower Time Limit: 10 Sec Memory Limit: 256 MB Description Nick近在玩一款很好玩的游戏，游戏规则是这样的： 有一个n*m的地图，地图上的每一个位置要么是空地，要么是炮塔，要么是一些BETA狗，Nick需要操纵炮塔攻击BETA狗们。 攻击方法是：对于每个炮塔，游戏系统已经给出它可以瞄准的方向(上下左右其中一个），Nick需要选择它的攻击位置，每一个炮塔只能够攻击一个位置，炮塔只能够向着它的瞄准方向上的某个位置发动攻击，当然炮塔也可以不进行攻击。炮塔威力强大，它可以且仅可以消灭目标位置上所有的BETA狗。出于安全考虑，游戏系统已经保证不存在一个炮塔能够瞄准另外一个炮塔，即对于任意一个炮塔，它所有可能的攻击位置上不存在另外一个炮塔。而且，如果把炮塔的起点和终点称为炮弹的运行轨迹，那么系统不允许两条轨迹相交f包括起点和终点）。现在，选定目标位置以后，每一个炮塔同时开炮，你要告诉Nick，他最多可以干掉多少BETA狗。 Input Output 一行一个整数表示答案。 Sample Input 4 5 　　0 0 -2 0 0 　　- ...

算术天才⑨与等差数列 Time Limit: 10 Sec Memory Limit: 128 MB Description 算术天才⑨非常喜欢和等差数列玩耍。 　有一天，他给了你一个长度为n的序列，其中第i个数为a[i]。 　他想考考你，每次他会给出询问l,r,k，问区间[l,r]内的数从小到大排序后能否形成公差为k的等差数列。 　当然，他还会不断修改其中的某一项。 　为了不被他鄙视，你必须要快速并正确地回答完所有问题。 　注意：只有一个数的数列也是等差数列。 Input 第一行包含两个正整数n,m，分别表示序列的长度和操作的次数。 　第二行包含n个整数，依次表示序列中的每个数a[i]。 　接下来m行，每行一开始为一个数op， 　若op=1，则接下来两个整数x,y，表示把a[x]修改为y。 　若op=2，则接下来三个整数l,r,k，表示一个询问。 　在本题中，x,y,l,r,k都是经过加密的，都需要异或你之前输出的Yes的个数来进行解密。 Output 输出若干行，对于每个询问，如果可以形成等差数列，那么输出Yes，否则输出No。 Sample Input 5 3 　1 3 2 5 ...