BearChild's Blog

最大割 Time Limit: 15 Sec Memory Limit: 256 MB Description 考虑一张n个点的边带权无向图，点从1~ n编号。 对于图中的任意一个点集(可以为空集或是全集)，称所有那些恰好有一个端点在这个点集中的边所组成的边集为割。 我们再定义一个割的权值为:这个割中所含的所有边边权的异或和。 现在初始时给定一张n个点的空图，接下来会有若干次加(无向)边操作，每次加边后请你求出当前图中权值最大的割的权值。 Input Output Sample Input 3 6 　　1 2 1 　　1 2 1 　　3 3 111 　　1 3 101101 　　1 2 1011 　　2 3 111011 Sample Output 1 　　0 　　0 　　101101 　　101101 　　110000 HINT l = log2(w) Solution 首先我们发现，由于XOR满足消去律，那么我们定义一个新点的点权为该点所有连边的XOR和，那么任意点XOR起来得到的值正是割的值，所以这样操作之后问题就转化为了：任取几个点，求XOR出的最大值，支持点权修改。 那 ...

Vladik and Entertaining Flags Time Limit: 20 Sec Memory Limit: 512 MB Description n * m的矩形，每个格子上有一个数字代表颜色。 q次询问，询问[l, r]有几个连通块，若颜色相同并且连通则属于同一个连通块。 Input 输入第一行n,m,q。 　　然后一个n*m的矩形。 　　之后q行，每行两个整数l，r。 Output 输出q行，对于每个询问输出答案。 Sample Input 4 5 4 　　1 1 1 1 1 　　1 2 2 3 3 　　1 1 1 2 5 　　4 4 5 5 5 　　1 5 　　2 5 　　1 2 　　4 5 Sample Output 6 　　7 　　3 　　4 HINT 1 ≤ n ≤ 10, 1 ≤ m, q ≤ 1e5， 1 ≤ l ≤ r ≤ m Solution 我们运用线段树，线段树一个节点i维护这个点表示的**[L, R]**。 具体维护Li列~Ri列的连通块个数，Li列连通信息，Ri列连通信息，Li列编号，Ri列编号。 连通信息指的是n个点的连通关系，用一个** ...

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。 　　若第 ...