BearChild · Blog

交错和查询 Time Limit: 10 Sec Memory Limit: 256 MB Description 无限循环数字串S由长度为n的循环节s构成。设s为12345(n=5)，则数字串S为123451234512345… 　　设Si为S的第i位数字，在上面的例子中，S1=1，S2=2，S6=1。 　　设S的一个子串S[l,r]的交错和为sum(l,r)： 　　sum(l,r) = Sl - S1+1 + Sl+2- Sl+3 + … + (-1)r-lSr 　　如sum(2,7) = 2 - 3 + 4 - 5 + 1 - 2 = -3 　　现给定循环节s，要求支持两种操作： 　　1 pos digit：修改循环节s上的某一位，即将spos改为digit。 　　2 l r：求S[l,r]内所有子串的交错和的和，即输出ans对10^9+7的模。 Input 第一行一个整数n，表示循环节s的长度。 　　第二行一个长度为n的数字串，表示循环节s。 　　第三行一个整数m，表示操作次数。 　　以下m行，每行3个整数。 　　若第一个数为1，表示是修改操作1 pos digit。 　　若第 ...

乒乓游戏 Time Limit: 10 Sec Memory Limit: 256 MB Description Input Output Sample Input 5 　　1 1 5 　　1 5 11 　　2 1 2 　　1 2 9 　　2 1 2 Sample Output NO 　　YES HINT Main idea 如果一个区间的端点在区间内，则这个区间可以走到那个区间，询问一个区间能否到另一个区间。 Source 首先我们立马想到了：如果两个区间严格有交集，那么这两个区间所能到达的区间集合是一样的。那么如果两个区间严格有交集的话我们就可以把它们合并起来，这里运用并查集。 这样处理完之后，剩下的区间只有两种情况：包含或者相离。那么查询的时候显然只要判断两个区间指向的大区间的情况即可。 我们要怎么合并呢？显然就是在线段树上进行操作，对于线段树上的每个节点开个vector，存下严格包含这个节点表示的[l,r]的区间的编号，那么我们加入新区间的时候，只要把左右端点在线段树上往下走，如果遇到这个线段树上的节点上的vector有东西，就记录几个区间的最小左端点以及最大右端点，把 ...

排序 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: 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: 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: 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 ...

看电影 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。（注意，这里要求将答案化为既约分 ...

魔法 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 ...