_kikyou--CSDN博客

原创 F. ATM and Students （双指针 / 二分+rmq）

传送门给定序列，求出最长的子段，满足其每个前缀和+s都大于等于0,s是给定的常数。双指针：对于每个l，求出其满足条件的最远的r，用于更新答案，此时sum+a[r+1] +s < 0.我们再把l右移一格，继续求最远的r。这样是不会损失最优解的，原因如下：l移动前，如果a[l]小于等于0，那么r接下来继续右移并更新答案即可；如果a[l]大于0，移动后一定有[l+1，r+1]+s<0,所以r不会右移，l会继续右移，而这个l贡献的答案一定小于移动前贡献的答案，所以不会损失最优解。#inc

2022-01-03 19:50:44 506

原创 Codeforces Round #757 C. Divan and bitwise operations(组合数学)

传送门有一个隐藏的序列，每个数位于[0,2^30)，给出m条信息形如l,r,x，表示[l,r]区间元素按位或的结果，保证每个位置都会涉及到。问这个序列所有子序列的异或结果之和。首先想到是二进制下每一位单独考虑贡献，假设第i位有k个1，那么一个子序列能够产生贡献当且仅当里面选了奇数个1，所以第i位的贡献为:2^i * v * 2^(n-k)其中v=每一项的含义：2^i ：二进制第i位，v：组合数，2 ^(n-k)：每个0都有选和不选两种情况。而v可以根据二项式定理推出来就等于2^(k-

2021-12-06 21:15:13 345

原创 Codeforces Round #757 E. Divan and a Cottage（非递减权值线段树+标记永久化）

传送门给出了n天的室外温度t[i]，同时规定，如果第i天早上的室内温度为P，那么当t[i]>P,第i+1的室温变为P+1,如果小于，则变为P-1,等于则仍然是P。按照样例解释一下输入的信息：首先输入n，代表有n天，接下来是n组信息，代表每天的室外温度以及询问每组信息由室外温度t、询问个数k、k个询问组成。对于第i组信息，首先给出室外温度t[i],然后给出k，接下来是k个询问，每个询问是一个非负数x[j]，表示如果第一天早上的室温是x[j],那么第i天结束后，室温是多少？比如第三组信息，首

2021-12-06 20:48:22 685

原创 2020ccpc威海 G.Caesar Cipher （hash+线段树）

传送门给定了一个长度不超过5e5的序列，0<=a[i]<65 536,q次操作，q不超过5e5。操作1：[l,r]区间每个数加1，并且对65536取模操作2：给出x,y,L,询问[x,x+l-1] ,[y,y+l-1]两个区间的序列是否相等。这题区间修改是每次加1，一共最多加nq，所以我们取模可以写成单点修改，最多取模(n*q)/65536 次，（通过维护区间最大值剪枝实现这个暴力的单点修改。）我们不考虑取模，发现这题是可以用hash+线段树写的。假设hash进制为base，令p

2021-11-20 21:57:15 546

原创 Educational Codeforces Round 64 D. 0-1-Tree （组合数学+并查集）

传送门给定无根树(undirected connected acyclic graph)，边权都是0或者1,问有多少条简单路径满足，在经过1边后不再经过0边。(即：00011… , 1111… , 0000… 三种路径数量之和)。如果我们把通过0边连起来的点染色(记作集合0)，那么0000…这种路径很好求，就是单独对每个连通块里取2个点。比如我们得到了4个连通块，每个连通块内的点都是靠0边连起来的，size分别是s1,s2,s3,s4,那么这4个连通块贡献的000…路径数量就是 (s12)\bino

2021-11-20 16:35:42 287

原创 D. Dogeforces (贪心构造+并查集维护生成树)

传送门有一个有根树，带点权，最多500个叶节点，满足根到叶子单条链上的点权严格递减同时告诉了每对叶节点(i,j)的lca的点权，构建一棵符合条件的树。首先这个题肯定是从叶子节点往上去构建一棵树的过程，想到可以用并查集来维护，fa[u]就表示u往上走目前到达的点，我们把(i,j,lca(i,j))三元组按点权升序排序，点权相同则按顶点编号排序。枚举排好序的三元组，对于(u,v,w),有两种情况。先求出u v的根节点r1 r2 ,如果小于w 说明u v的lca的点权就是w，n+=1表示新建一个节

2021-11-19 21:45:26 332

原创 P2398 GCD SUM (欧拉函数)

传送门我们可以从1开始枚举最大公约数，枚举到n，求出满足gcd(x,y)==i，1<=x,y<=n，的x,y对数m，i*m累加起来就是答案。问题是如何求满足gcd(x,y)==i，1<=x,y<=n，的x,y对数呢？我们知道满足gcd(x,y)==1，1<=x,y<=n，的x,y对数是...

2021-11-18 13:54:02 243

原创 Educational Codeforces Round 81 D. Same GCDs （欧拉函数）

传送门由于a,m都是给定的，所以记d=gcd(a,m) .由辗转相除法得 gcd(a+x,m)=gcd((a+x)%m , m)由于0<=x<m,a>=1所以(a+x)%m的范围是[0,m-1]记t=(a+x)%m,0<=t<=m-1,我们要求的东西就是满足gcd(t,m)==d,0<=t<m的t的个数。我们令t=ad,m=bd,那么就等价于求满足gcd(a,b)==1,0<=a<b)的a的个数，这个值就等于b的欧拉函数值。

2021-11-17 21:14:44 242

原创 2019西安邀请赛 J And And And (树上启发式合并+组合数)

传送门题意：给定一个带边权的有根树，定义E(U , V)表示u到v简单路径上经过节点构成的点集，X(U , V)表示u到v简单路径上的边权异或的结果。然后让我们求这个东西：这个式子看上去特别复杂，实际上也确实很复杂但其实就是，如果(u,v)的简单路径上存在一个点对i,j满足X(i,j)==0，那么(u,v)情况下的(i,j)可以给答案贡献1 。首先X(i,j)==0可以转化成X(1,i) xor X(1,j) == 0 ,当我们找到一个点对i，j满足X(1,i) xor X(1,j)

2021-11-16 20:57:03 140

原创 codeforces 939E - Maximize （三分 / 双指针）

传送门题意：给定一个空集合S，操作1是每次加入一个数，保证不会小于当前集合的最大数，操作2是询问，从该集合选出一个子集，满足子集最大值减去元素平均值最大，输出这个最大值。1<=q<=5e5首先可以感性地想到选出来的子集的2个性质，①选出来的最大元素一定是集合S的最大值，即：每次都选最新加入的元素。②其余的元素是集合S的一个连续的前缀(按升序排列之后) .为什么呢？①：②：如果我们选的是s[1],s[2],s[4],s[5]，那么如果我们用s[3]去代替s[4]，总和一定会减小，

2021-11-15 22:27:18 587

原创 Atcoder 4142 Xor Sum (双指针)

传送门题意：(1<=n<=1e6)a^b == a+b成立当且仅当对于每一位，a，b中最多只有1个数是1.大胆推广到[l,r],a[l]+a[l+1]...+a[r]==a[l] xor a[l+1] xor ...a[r]成立当且仅当，对于每一位，这些数最多只有1个是1 。可以推出，如果区间[l,r]满足条件，那么该区间任何一个子区间都满足条件所以,[l,r]区间满足条件，那么[l+1,r]区间也满足条件，我们可以枚举左端点L，分别计算其能贡献多少个满足条件的区

2021-11-15 16:44:30 508

原创【HDU - 4348】To the moon （主席树标记永久化区间更新）

传送门主席树的修改一般是只涉及单点修改的，因为区间操作如果我们pushdown的话，相当于又涉及了两个孩子节点的修改，一直递归下去，这样空间要去就和建n棵线段树差不多一个量级了。我们可以把懒标记永久打在节点上，不下传，只在pushup和查询的时候用上。具体来说，pushup的时候除了合并左右子节点，再考虑一下根节点区间的懒标记的影响。查询的时候，查询路径上经过节点的懒标记都要合并起来，一路记录下去，最终在查询区间进行计算。#include<bits/stdc++.h>using na

2021-11-13 20:25:09 404

原创 D. Persistent Bookcase （可持久化线段树维护bitset）

传送门给定一个n*m的矩阵，每个元素都是0或1，一共4种操作，操作q次。1、把(i,j)改成12、把(i,j)改成03、翻转第i行4.回溯变成第k次操作时的矩阵每次操作完后输出矩阵所有元素之和。(1<=n,m<=1000,q<=1e5)涉及回溯历史版本，可持久化线段树。我们把每行看成一个整体，单独一行涉及的操作是单点修改，区间反转，查询区间和，如果我们对每行都建线段树，即：用线段树维护n棵线段树之和，那么肯定会爆空间的。单点修改，区间反转，查询区间和我们可以用一个空间位

2021-11-13 16:20:20 340

原创 P3509 [POI2010]ZAB-Frog （尺取+倍增）

传送门数轴上有n个点按点权大小升序排列，每个点上有一只青蛙，各自独立行动。每一步都会跳到距离他第k近的点(,距离等于点权之差的绝对值，如果存在两个这样的点，就跳到下标较小的那个), 问每只青蛙跳m步之后到达的位置。(1<=n<=1e6,1<=m<=1e18)首先我们通过尺取法预处理出每只青蛙跳一步到达的位置。然后倍增即可。to[i][j]=to[to[i][j-1]][j-1]枚举m的二进制的每一位，每次跳2^i步。#include<bits/stdc++.h&g

2021-11-12 21:22:24 426

原创 2019 ICPC 南昌 Regional K. Tree（树上启发式+动态开点线段树）

传送门给定了一棵带点权的有根树，求出节点对(i,j)的个数，满足a[i]+a[j]=2*a[lca]

2021-11-12 20:55:19 152

原创 E. Minimal Segment Cover （贪心+倍增）

传送门给定一个数轴，给定n条线段，每条线段可以覆盖[li,ri]的位置，q次询问，每次问如果要覆盖[l,r]，最少要选多少条线段。先考虑一个贪心的暴力解法：对于询问[L,R],假设当前位置为l，我们要从左端点小于等于l的线段中找到一个最大的右端点r，并让当前位置更新为r，直到R==r 。尽管我们可以预处理得到a[i]表示从i位置只选一个线段能到达右边最远的位置是哪里，暴力解法时间复杂度仍为 O（nq）.既然i位置能够选一条线段最远到达a[i],同时a[i]位置能选一条线段最远到达a[a[i]

2021-11-11 21:58:52 597 1

原创 Codeforces Round #373 C. Sasha and Array（斐波那契数列矩阵形式+矩阵快速幂+线段树）

传送门题意，给定一个序列，定义f(a)表示斐波那契数列的第a项，序列涉及两种操作，一是区间每个数加x二是对于询问[l,r]，输出 Σf(a[i]) (l<=i<=r)，对1e9+7取模。看到斐波那契数列容易联想到其矩阵形式：[f(3)(f2)]=[f(2)f(1)]∗[1110]\begin{bmatrix}f(3)&(f2)\end{bmatrix}=\begin{bmatrix}f(2)&f(1)\end{bmatrix}*\begin{bmatrix}1&a

2021-11-09 20:47:28 1027

原创 CF319B Psychos in a Line （单调栈+dp）

传送门给定一个序列，如果第i个数比第i+1个数大，那么就会吃掉第i+1个数，吃与被吃同时发生，每一次吃看作一轮，问多少轮后可以稳定下来。dp[i]表示i位置被吃的时候是第几轮，(0表示不会被吃，初始记为1)对于i,我们从i-1的位置往前遍历，假设遍历到位置j，如果a[j]<=a[i],那么dp[i]=max(dp[i],dp[j]+1)否则当a[j]>a[i], 直接退出循环不需要更新此外，如果a[i]是前i个里面最大的，dp[i]=0转移过程可以用单调栈，不断

2021-11-09 15:44:55 193

原创 D. Bash and a Tough Math Puzzle （线段树+dfs剪枝）

传送门给定序列，单点修改，区间询问[l,r]中，能否最多修改一个数使得区间GCD等于x。（询问时的修改只是想象中的修改，不会改变序列的元素）线段树维护区间gcd这个很显然了，问题是询问如何处理呢？刚开始的方向是找满足条件的序列，有什么规律性质，但是在纸上画了很久也没有结果。可以说方向完全错了。...

2021-11-08 23:34:54 112

原创 Lawn of the Dead （线段树）

传送门给定一个n*m的网格，有k个地雷，不能踩到地雷所在格子，从（1，1）出发，只能往左或者往下走，问最多可以到达多少个格子。由于n，m都是1e5级别，所以我们不能模拟。我们先观察一个结论，对于第i行，假设有y1,y2两个雷，[y1+1,y2-1]这个区间格子如何能被到达呢？只能从上面下来，所以我们在第i-1行中找打[y1+1,y2-1]这个区间内最左端的可到达的位置idx,那么第i行的[idx,y2-1]这个区间都是可到达的了。如果我们用1代表可到达，0代表不可到达，上面的操作实质

2021-11-06 17:25:01 444

原创 Codeforces Round #200 D. Water Tree（树剖+线段树 / 线段树+思维）

传送门给定有根树，初始点权为0，有三种操作：1、u为根的子树全部节点赋值为12、u到根节点1的路径上，所有的点赋值为03、查询u的点权带点权的树上路径修改问题，可直接树剖暴力写完。同时，树剖还可以解决这个问题的拓展：点权并非只有1，0两种，可以是任意值，同样是区间修改+区间查询。时间复杂度O(N logN log N)#include<bits/stdc++.h>using namespace std;//#pragma GCC optimize(2)#define ul

2021-11-05 15:56:46 147

原创 D. Integers Have Friends (思维+区间gcd)

传送门给定正整数序列，每个数都不一样，求最长的子段[l,r]，满足a[l] % m = a[l+1] % m ... = a[r] % m , m>=2从这个式子观察得到一个性质，如果[l,r]区间满足条件，那么a[l+1]-a[l],a[l+2]-a[l+1]一定是m的倍数，即：差分数组一定是k1 * m,k2 * m…的形式，ki是整数，这个性质等价为[L,R]区间对应的差分数组的GCD大于等于2 。而且我们发现，符合条件的区间长度是具有单调性的，我们可以二分这个长度，然后枚举+验

2021-11-04 23:29:46 209

原创 Codeforces Round #312 E. A Simple Task （桶排序思想+线段树维护桶）

传送门给定一个只包含小写字母的字符串，长度为n，m次操作，每次指定 [L,R] K K=0,让[L,R]区间降序排列，否则升序排列。输出最终字符串。由于每个数都相当于是[0,25]区间内，我们试试能不能开26个桶，第i个桶记录有多少个i，利用桶排序来求解。我们开n个桶，每个桶大小都是26，记录第i位的26个数分布情况。线段树维护桶序列，每个节点表示：当前区间内，桶合并后的情况，即：【0，25】这些数各有多少个。于是每次操作就可以这样处理：先区间查询出当前询问区间[L,R]里面，【0，25

2021-11-04 19:38:34 150

原创 Codeforces Round #737 (Div. 2)D. Ezzat and Grid (dp+线段树)

传送门给了n个01串，每个串都是1e9的长度。一个01串集合是优美的当且仅当相邻的任意两个串中，至少存在一列，满足在这两个串里面都是1。问最少删去多少个串，才能使得剩下的串构成一个优美集合。题目等价于可以从中挑出多少个串，使得任意相邻的两个串都满足条件。我们先思考一个暴力解法：dp[i]表示前i个串中，最多可以挑出多少个串构成优美集合。求解dp[i]:先枚举串i的每一个1的位置j，然后枚举dp[k],(1<=k<=i-1)，对于j位置上也是1的串k，我们取dp[i]=max(d

2021-11-03 23:40:01 166

原创 Educational Codeforces Round 112 E. Boring Segments(双指针+线段树)

传送门给定一个[1,m]区间的坐标轴n条线段，每个覆盖[li,ri]的区间并有一个价值w[i]，我们可以从点u 到达点v 当且仅当u v在同一个线段中，现在要选取一个代价最小的线段集合，使得我们可以从1到达m。线段长度大于1。代价指：所选取线段集合中w[i]最大值与最小值之差。保证一定有解。线段覆盖区间的问题，我们可以让右端点-1，然后区间加1，那么最终区间不为0的连续段，就可以任意跳了。比如 [1,7] [8,9] 这两个线段是不相交的，右端点-1，变成[1,6] [8,8] ，做完区间加

2021-11-03 21:30:31 134

原创欧拉序的几点性质

参考第一种欧拉序写法下：对于u，v两个点之间的简单路径。如果u，v存在祖先关系，那么u->v简单路径上的点就是在欧拉序的[in[x],in[y]]中恰好出现一次的点。(画图理解)如果不存在祖先关系，那么u->v简单路径上的点就是在欧拉序的[out[x],in[y]]中恰好出现一次的点,再加上他们的LCA。这样就把路径问题转化成了一个特殊的区间问题。应用(树上莫队)...

2021-10-27 15:55:30 405

原创 Codeforces Round #746 (Div. 2)D. Hemose in ICPC ? （交互二分+dfs序）

题目链接给定带边权的无根树，定义dis(u,v)等于u到v简单路径上所有边的GCD，每次可以询问一个点集，会返回点集中所有点对的dis最大值，最后输出这棵树中，使得dis(u,v)最大的u,v 。(2<=n<=1e3 ,最多询问12次)首先GCD具有只减不增的性质，最后答案就等价于输出边权最大的边的两个顶点。看到询问次数，12，点只有1000个，说明主体算法肯定是二分了。我们首先可以询问所有的点，返回的一定是最大边权W。我们想到，能不能把所有的边分成两部分，左边右边各询问一次，看看

2021-10-27 15:53:55 179

原创 Educational Codeforces Round 81 E. Permutation Separation(dp+线段树优化)

传送门题意：给定一个排列p，每个位置有一个花费a[i]，先可以在任意位置把p切开成头尾两部分，非空，然后从两个部分中选几个数放到另一个部分，使得左边集合的每个数都小于右边集合的最小值(某个集合为空也符合要求)。移动第i个数花费为a[i],求最小花费。(1<=n<=2e5)我们观察发现，最终两个集合的答案只能是这样 1 2...m ; m+1,m+2..n于是，我们可以枚举分割点t(t在左边)，再枚举左边集合的最大值m，[1,t]中找到大于m的元素给他们移到右边去，[t+1,n

2021-10-26 20:15:59 158

原创 HDU 4757 Tree（可持久化01trie+LCA）

传送门给定无根树，带点权，m次询问，每次询问给出x,y,z，问x到y的简单路径上的点，与z进行异或运算，结果最大是多少。求与给定常数的异或最大值，妥妥的01字典树。我们可以把x,y的简单路径拆分成两条链x->lca(x,y);y->lca(x,y);分别在两条链上找答案然后取最大值。如何找答案呢，先假设根节点是1，我们可以对每个节点建一个01trie，表示其到1的路径上的点建成的01trie，由于该节点与其父节点相比只多了一条链，所以可以建可持久化01trie。查询：在root

2021-10-24 23:37:39 179

原创 HDU 6959 zoto (莫队+树状数组)

传送门题意本质就是，给定序列，m次询问，每次问[x1,x2]这个区间内的数中，大小位于[y1,y2]这个区间的不同的数有多少个。求区间不同的数的加强版。求区间不同的数的时候，我们只需要维护1个桶，记录每个数出现多少次即可，用一个变量ret保存答案，这里我们需要对每个数都分别保存答案，可以用权值线段树或树状数组维护。单点修改，区间查询。时间复杂度是O(Nsqrt（N）logN) 但是跑不满，因为不一定每次都要修改。1900ms。注意我们把y的坐标都加了1，保证树状数组维护的定义域是从1开始。

2021-10-24 21:03:02 142

原创 P4735 最大异或和（可持久化01trie）

传送门用pre[i]保存前缀异或值，询问操作就转化为了:求x ^ pre[n] ^ pre[p-1]的最大值,其中l-1<=p-1<=r-1而x^pre[n]是常数，所以问题实质就是在给定区间中询问区间元素与一个常数异或的最大值。01字典树的经典老活的区间询问版本。对pre数组每个前缀建01字典树，每个节点保存有多少个1，由于每次只更新一条链，所以用线段树合并的思想利用上一个版本的树去建树，这和主席树的思想如出一辙。询问[l,r]区间就用root[r]版本减去root[l-1]版本，

2021-10-23 18:55:22 381

原创 Codeforces Round #748 (Div. 3) F. Red-Black Number （dp）

传送门给定一串长度为n的数字，可以把每一位涂上红色或黑色，要求每种颜色至少有一位，每位都必须涂色，最终红色位构成的数可以整除A，黑色位构成的数可以整除B.输出红黑数相差最小的一种涂法，如果不存在，输出-1.本来有2^40个状态，我们需要合并某些状态以减少状态数目。这种涉及整除，且除数比较小的情况，我们可以拿模数当成一维状态。dp[pos][mod_a][mod_b][na]表示当前枚举到第pos位，红色数对A的模数为mod_a,黑色对B的模数为mod_b，总共有na个红色，状态下的涂色答案。

2021-10-15 10:29:52 273

原创 CF741D Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths（利用二进制处理回文串+dsu on tree）

传送门每条边是一个字母，且最多22种，我们可以转化成一个二进制数，那么一条简单路径如果能重排得到回文串就等价为边权异或结果为2的幂数。（二进制下最多含有1个1）带边权路径问题，我们除了点分治之外可以枚举LCA，然后在LCA的子树中求解，再利用dsu on tree优化时间复杂度。最终把问题转化成:dis[i]表示根节点(1)到节点i的路径上边的异或结果，dep[i]表示i的深度，求满足dis[i] XOR dis[j] ==(2的幂数)的情况下dep[i]+dep[j]-2*dep[LCA]的最大值

2021-10-13 21:11:21 458

空空如也

空空如也