2019.7.26 多校一 1002 Operation（线性基+二维动态规划） [BJWC2011]元素(线性基+贪心) 推荐模板题线性基模板这题的题解写的挺好的大家可以康康 线性基呢就是从几个数里选出任意个数使得它们异或起来得到的数最大 反正那个题解写的真挺好。。我就不多讲具体原理 operation 这题讲的是一个在线的修改求线性基里面还要decode一下。。。 那我们就用动态规划的思想二维dp线性基尽量取右边的数然后运用pos数组检查是否在l到r之间二维dp维护线性基很巧妙 题解叫这个是上三角形态/线性基前缀和 #include using namespace std; co...

vacation vacation题解 题目意思就是你现在在一条单行道上然后你前边有n辆车已知所有车距离红绿灯的距离s，速度v，车长l假设大家车技都很好距离可以保持为0那么问你需要多久才能到红绿灯那 上面的博写的是O(n)的复杂度从末态起手很精妙 然后看懂了题解的小根堆维护如果用O(nlogn)就像是常规的动态规划了 7.26更新 首先我们把各辆车与前一辆车相距为0的时间求出来用这个来不断让我们自己的车逼近前一辆车然后其他的车也都会逼近前一辆车并且用并查集来联通已经逼近的车这个情况下又会产生新的状态我们有t数组和d数组来维护当前时间的当前距离接着所有的车不断接近前一辆车知道所有车连在一起或者说...

现在假设受众已有 求图的所有最短路径 的前置知识 推荐阅读：白书P209 看懂最大流&最小割 今天没时间重构代码了。。。 就随便注释一下 题目呢是签到题 意思是给一个有向图 一个人要从1点走到n点 我们要阻碍他走最短路 而你堵塞一条边的代价就是这条边的长度 问最小代价 要是看懂了最小割就知道这题几乎就是板子题 先用优先队列优化最短路，求所有最短路径的所有边题解的方法可以学一手 采用的方法是先更新好所有点的最短距离 （题中的sp数组）然后遍历所有边接着如果说两个点的最短距离之差刚好是边的长度那么这条边就是在最短路上 就是题解那个蜜汁公式的意思 for(int pos=1;pos&...

前置知识：欧拉函数 φ函数的值  通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数(小于等于1)就是1本身）。 (注意：每种质因数只一个。比如12=223那么φ（12）=12（1-1/2）(1-1/3)=4) ----摘自百度 接下来怎么求欧拉函数呢 L...

小a的轰炸游戏具体意思看题面 这题也太巧妙了让我情不自禁想把它解释清楚用图吧 这是一种想法，直接使用一维前缀和的思想，强行计算前缀和 但是想想，如果l是1000，5e5乘1000接受不了的哦 所以我们就想到用二维动态差分 只需要做8个操作，就是5e5乘8完全可以 我们只标记8处 再用动态更新的方法，就可以达到第一张图的前缀和效果 具体怎么实现的呢 自己从代码里理解吧 for(int i=0;i<n+2*L;i++) { int ans=0; for(int j=0;j<m+2*L;j++) { ...