如果是个明眼人，可以看出来选中位数一定是最优解，此时答案一定是后一半的和减去前一半的和，即∑i=1n/2(vn−i+1−vi)\sum_{i=1}^{{n}/{2}}(v_{n-i+1}-v_i)∑i=1n/2​(vn−i+1​−vi​)。 但是像我这样的大制杖就只能硬证。。。 我们求的是： min⁡f(x)=∑i=1n∣x−vi∣\min f(x)=\sum_{i=1}^n|x-v_i|minf(x)=∑i=1n​∣x−vi​∣ 这个最小的取值和下面这个式子一定是一样的： min⁡g(x)=∑i=1n(x−vi)2\min g(x)=\sum_{i=1}^n(x-v_i)^2ming(x)=...

一个朴素的想法是把大于bbb的数规约成111，小于bbb的数规约成−1-1−1，那么中位数为bbb就是区间的所有1,−1,01,-1,01,−1,0的和为000。 而给出的数列是一个排列，那么bbb只有唯一的位置，从这个位置向两边求和，就可以找出题目要求的区间。 于是整个区间的和就变成了suml+0+sumrsuml+0+sumrsuml+0+sumr，其中suml,sumrsuml,sumrsuml,sumr分别是bbb左端和右端的子串和。 把判断等式suml+sumr==0suml+sumr==0suml+sumr==0变成sumr==−sumlsumr==-sumlsumr==−suml...

题意 维护一个数列，支持区间加，以及区间斐波那契数列数列求和，即∑i=lrf(ai)\sum_{i=l}^rf(a_i)∑i=lr​f(ai​)。 解法 首先把f(ai)f(a_i)f(ai​)拆成矩阵的幂次形式： f(ai)=[f(0),f(1)]×[0111](ai−1)f(a_i)=[f(0),f(1)]\times \left[\begin{matrix}0&1\\1&1\end{matrix}\right]^{(a_i-1)}f(ai​)=[f(0),f(1)]×[01​11​](ai​−1) 然后用线段树维护右边的矩阵就好。 区间加xxx就是区间的和直接乘[0111...

树上路径与子树最大异或和问题。。。 想都不想一个树链剖分上去，变成序列问题。 区间最大异或和。。。这不板子么？ 又是一个可持久化TrieTrieTrie丢上去。 这个题就搞完了。 复杂度O(32×n2(n))O(32\times n\log_2(n))O(32×nlog2​(n))，稳的不行。 （按理说我把TrieTrieTrie树深度搞成323232也没啥问题，但样例过不去。。。可能是符号位的问题吧） 附代码： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 1000...

2022 BUAA Winter Training 1 A − Interesting Subarray\Large{A\ -\ Interesting\ Subarray}A − Interesting Subarray [ CodeForces − 1270B ]{\scriptstyle [\ CodeForces\ -\ 1270B\ ]}[ CodeForces − 1270B ] 题意 给定一个数组，要找出一个子数组使得数组中最大值与最小值的差...

题意 有nnn个怪物，每只怪物的出现时间是kik_iki​，血量是hih_ihi​。魔法师可以从111点伤害开始施加魔法，每次伤害之后可以增加一点伤害，但如果不施法，下一次施法伤害会重新从111点伤害开始累计。问最少需要的魔法值总和。 解法 水题一发。 把每只怪物当成线段，需要开始从111开始施法累积的时间点为左端点，出现时间为右端点，然后当成线段覆盖做就好。 记得多组数据。 附代码： #include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #define...

看到题目中一个求和我人就蒙了。。。 这啥啊这是？？ 裸的暴力O(qn2)O(qn^2)O(qn2)，铁定TLETLETLE。。。 得，照惯例先把里面的玩意拽出来搞事。 首先要解决的是怎么在线计算F(l,r)F(l,r)F(l,r)，显然这个题我们不能用莫队了对吧。。。 于是拿出主席树来维护。 对于每一个数val[i]val[i]val[i]，找到上一次出现的位置pos[val[i]]pos[val[i]]pos[val[i]]，记为last[i]last[i]last[i]，如果第一次出现就是000，然后把这个值放进主席树里维护就好，那么F(l,r)F(l,r)F(l,r)就是区间[l,r][...

首先看一道题：洛谷 P3812 【模板】线性基 题目名称已经说明了算法是什么，毕竟是一道模板题对吧。。。 线性基是什么？ 哈？学过线性代数或者高斯消元的都应该知道吧。。。 不知道的左转出门自行百度。。。 或者参考这两篇博客： P3812 【【模板】线性基】 线性基学习笔记 在竞赛中，提到线性基，一般是指异或线性基。 实际上上面两篇博客已经把该奖的都差不多讲完了。 其实线性基还可以合并。 两个线性基合并就是暴力把某个线性基强行插入另外一个线性基。 代码的话，可以写成结构体重载加法： struct Linear_Basis{ long long base[MAXN]={0}; ...

真真正正的线性基。。。 上过大一线代的都应该知道，没上过的学过高斯消元或者异或线性基也应该知道。。。 第一反应高斯消元，消到最后就是秩。 但是那个最优解有点难搞。 于是从小到大排个序，依次加入线性基中，还没插满并且插不进去的就是选中的答案。 所以为什么我的代码要开才能过啊。。。 算了，过了就行 附代码： #include<iostream> #include<algorithm> #include<cstdio> #include<cmath> #include<cstring> #define MAXN 510 #define ep...

如果没有修改，这个题就是个线性基板子题对吧。 再看加上修改之后怎么整。 我们发现，对于任意一种已经确定数字的情况，只要线性基建好了，答案可以搞出来。 那么问题就是怎么动态维护线性基。 啥？动态维护？？不存在的！我才不告诉你我不会写那玩意 因为只有删除操作，所以顺序颠倒就是一个一个加入数字。 也就是离线然后一个一个插入线性基。 这样就搞定了，复杂度也就。 再看那个区间怎么整。 由于区间具有连续性，所以我们可以考虑用并查集来搞事。 每次假如一个数，如果这个数左或者右边有存在的区间，那就合并并查集，并且暴力合并线性基。 答案就是前一个询问的答案与当前数字对应答案取最大值。 附代码： #include...

先看原来的游戏先手必胜条件：所有值的异或和不为零。 带回到本体，也就是两个回合之后，所有值的异或和不为零。 那么我们就不能让对方从我方已经取完的情况下还能把情况变成异或和为零。 怎么做？ 等会儿，这不就是一线性基么？ 只要线性基插满了，或者有个值插不下就行（进不去，怎么想都进不去。。。） 先把线性基板子打上。。。 然后看题：让第一回合拿的火柴总数尽量小。。。 如果线性基中某个位置既能是小数字，又能是大数字，那不妨就让大数字占着，把小数字留下来。 这样的贪心能保证最后答案是最优解。 至于那个。。。好像没啥用。。。 聪明的人一定能找到一种方法对吧。。。 附代码： #include<iostr...

题目要求的式子： 两边同时异或得： 这个式子就是线性基的检查操作，直接写上即可。 附代码： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 40 using namespace std; int n,m,max_val=MAXN; long long val[MAXN]; bool flag_zero=false; char tp[100000],*p1=tp,*p2=tp; inline char get_char(){ return p1==p2&&...

很直接的一个想法就是把的作为断点，将整个链切分为两段。 那么只有三种情况： 在买卖 在买卖 在买，在卖 求就交给了倍增，因为树剖后面还要写数据结构维护，比较麻烦。。。 （当然离线也可做） 维护四个值： 前两个很显然的维护方式，跟着倍增一起跳就好。 后面两个维护是和求解方式差不多的思路，也就是把拆成，仍然是上述三种情况。 这样维护的式子就出来了：（） 最终答案的式子同理。 防止溢出建议开。 附代码： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 50010 #...

题意 给你一个有向图，问能否选择一个起点，使得每个点和每条边都走且只走过一次。 解法 其实就是让你判断这个图是不是一条链。 首先链的条件有一条：。 这样约束起来就是树和环的组合（可能是一棵树加一个环）。 再把入度和出度约束在之间，这样就是。 然后通过入度为零的点就是起点，把整条链扫一遍，计算通过的节点个数，判断是否有环即可。 附代码： #include<iostream> #include<algorithm> #include<cstdio> #define MAXN 100010 using namespace std; int n,m,root,v[M...