BearChild's Blog

Melancholy Time Limit: 10 Sec Memory Limit: 256 MB Description DX3906星系，Melancholy星上，我在勘测这里的地质情况。 　　我把这些天来已探测到的区域分为N组，并用二元组(D,V)对每一组进行标记：其中D为区域的相对距离，V为内部地质元素的相对丰富程度 　　在我的日程安排表上有Q项指派的计划。 　　每项计划的形式是类似的，都是“对相对距离D在[L,R]之间的区域进行进一步的勘测，并在其中有次序地挑出K块区域的样本进行研究。”采集这K块的样品 后，接下来在实验中，它们的研究价值即为这K块区域地质相对丰富程度V的乘积。 　　我对这Q项计划都进行了评估：一项计划的评估值P为所有可能选取情况的研究价值之和。 　　但是由于仪器的原因，在一次勘测中，这其中V最小的区域永远不会被选取。 　　现在我只想知道这Q项计划的评估值对2^32取模后的值，特殊地，如果没有K块区域可供选择， 评估值为0。 Input 第一行给出两个整数，区域数N与计划数Q。 　　第二行给出N个整数，代表每一块区域的相对距离D。 　　第三行给出N个整数，代 ...

Weed Time Limit: 20 Sec Memory Limit: 512 MB Description 从前有个栈，一开始是空的。 　　你写下了 m 个操作，每个操作形如 k v : 　　　　若 k = 0，代表往栈顶加入一个数 v 　　　　若 k = 1，则代表从栈顶弹出 v 个数，如果栈中的元素少于 v 个，则全部弹出。 　　接着你又进行了 q 次修改，每次你会选择一个操作，并且修改它的两个参数。 　　在每次修改后，你都要求出如果依次执行这些操作，最后栈中剩下的元素之和。 Input 第一行两个正整数 m,q，分别表示操作数和修改次数。 　　接下来 m 行，每行两个整数 k,v，代表一个操作。 　　接下来 q 行，每行三个正整数 c,k,v，表示将第 c 个操作的参数修改为 k 和 v。 Output 输出 q 行，每行一个整数，代表依次执行所有操作后栈中剩下的元素之和。 Sample Input 5 2 　　0 3 　　0 2 　　0 3 　　1 1 　　0 5 　　1 0 3 　　1 0 1 Sample Output 10 　　8 HINT m,q ≤ 2×1e5, ...

Wide Swap Time Limit: 50 Sec Memory Limit: 512 MB Description Input Output Sample Input 8 3 　　4 5 7 8 3 1 2 6 Sample Output 1 　　2 　　6 　　7 　　5 　　3 　　4 　　8 HINT Solution 首先，直接做难度系数较高，假设原序列为a，我们考虑设一个p，p[a_i] = i，即将题目中的权值与下标调换。 那么显然，要令a字典序最小，只要让p字典序最小即可。因为**“权值小的尽量前”与“前面的权值尽量小”**是一个意思。 现在操作转化为：相邻元素且权值差>=k的可以换顺序。 考虑一个暴力怎么做，显然是 i 与后面的所有 j 比，如果 abs(p_i - p_j) < k，则 i 和 j 的相对顺序就确定了， 连一条 p_i -> p_j 的边。 连边之后跑一边拓扑即可。 显然复杂度在于连边，因为这样暴力会有很多无用边。比如A->B, B->C, A->C，这条A->C显然无用。 我们考虑如何删掉 A ...

划分序列 Time Limit: 20 Sec Memory Limit: 256 MB Description 给定一个长度为n的序列A;，现在要求把这个序列分成恰好K段(每一段是一个连续子序列，且每个元素恰好属于一段)，并且每段至少有一个元素，使得和最大的那一段的和最小。 请你求出这个最小值。 Input 第一行两个正整数n,K，意义见题目描述。接下来一行n个整数表示序列Ai Output 仅一行一个整数表示答案。 Sample Input 9 4 　　1 1 1 3 2 2 1 3 1 Sample Output 5 HINT Main idea 将序列分为若干段，使得和最大的那一段最小，值可以为负。 Source 首先，显然都想到了二分答案。 我们先把都为正数或负数的情况写了：Ai>=0的时候求出最小的划分段数x，若x<=K则表示当前答案可行；Ai<=0的时候求出最大的划分段数x，若x>=K则表示当前答案可行。然后再打了暴力，接着我们对拍一下，惊讶地发现了一个规律：若最小划分段数为L，最大划分段数为R，当L<=K<=R时则可以更新。 然后我 ...

阅读 Time Limit: 10 Sec Memory Limit: 256 MB Description A君喜欢阅读，现在他准备读一本书，他会从第K页开始看，然后看到第M页。 书中的内容并不一定都让A君愉悦，或者说，A君更喜欢看书中的精华。更具体地，书中有N页能让A君感到愉悦，阅读第T页可以获得B;的愉悦度。 由于书的页数实在太多，因此A君会选择跳着看，但是他一次最多跳D页(两页页码差不大于D)，然后阅读跳到的那一页的内容，每次翻页他将会丧失A的愉悦度。 现在A君想知道他阅读完这本书，能得到的愉悦度之和最大能是多少。 Input Output Sample Input 0 10 4 10 2 　　3 10 　　8 5 Sample Output -20 HINT Main idea 从K走向M，路上有n个收益点，表示到了pos位置可以增加val的收益，每次最多可以走D步，走一次损耗A。求最大收益。 Solution 这题必然是一道DP，我们层层深入来思考。 先从20%考虑：首先我们一下子就想到了暴力DP，令f[i]表示到了第i个收益点的最大收益，显然对于每个收益点我们可以O ...

乒乓游戏 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: 40 Sec Memory Limit: 512 MB Description Informatikverbindetdichundmich. 信息将你我连结。B君希望以维护一个长度为n的数组，这个数组的下标为从1到n的正整数。一共有m个操作，可以 分为两种：0 l r表示将第l个到第r个数（al,al+1,…,ar）中的每一个数ai替换为c^ai，即c的ai次方，其中c是 输入的一个常数，也就是执行赋值ai=c^ai1 l r求第l个到第r个数的和，也就是输出：sigma(ai),l<=i<=rai因为 这个结果可能会很大，所以你只需要输出结果mod p的值即可。 Input 第一行有三个整数n,m,p,c，所有整数含义见问题描述。 接下来一行n个整数，表示a数组的初始值。 接下来m行，每行三个整数，其中第一个整数表示了操作的类型。 如果是0的话，表示这是一个修改操作，操作的参数为l,r。 如果是1的话，表示这是一个询问操作，操作的参数为l,r。 Output 对于每个询问操作，输出一行，包括一个整数表示答案mod p的值。 Sampl ...

交错和查询 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: 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 ...