二维前缀和与差分   对于一个二维数组a定义数组为数组a的前缀和数组，可以理解为一个左上矩阵的矩阵和   //为了避免数组越位，下标从1开始 for(int i=1;i<=n;++i) {     for(int j=1;j<=m;++j)//可以只用一个数组，这里为了看的清楚区分了s与a     {         s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i]...

前缀和与差分   对于一个数组a定义数组为a数组的前缀和数组。    //为了避免数组越位，下标从1开始用 for(int i=1;i<=n;++i) {     s[i]=s[i-1]+a[i]; }        定义数组为a数组的差分数组。   //为了避免数组越位，下标从1开始用 for(int i=n;i;--i) //倒着for的可以不借助两个数组，这里用d和a是为了看着清楚，实际可以用一个数组储存。 {     d[i]=a[i]-a[i-1]; }    前缀和与差分运算为...

数位DP   所谓数位DP，就是把一个数按照k进制数的每一个位展开，在把每一位的信息作为状态来推出答案。  比如：12345这个数在十进制下可拆为1、2、3、4、5，个位可以推十位，十位可以推百位，以此类推。 推状态的方法有很多，一般来说第一反应就是像普通dp一样从前往后推，但是由于思维难度较高而且写起来难度较大，所以推荐递归写法，也就是记忆话搜索的写法。  以HDU2089 不要62为例。   统计l,r区间内不含62,4的数字个数。   l~r区间符合条件的数字没有普遍的规律，状态数目过多不好做DP。但是1~x一段连续的区间在枚举数字时有大量重复状出现，利用记忆化搜索做DP。   一、首先...

静态维护区间加等差数列的求和问题   维护一个数组，先进行m次操作，然后查询每个位置的值，每个操作给定四个参数l,r,a,k表示从l到r依次加上一个首项为a，公差为k的等差数列。   维护数组，表示原数组的二阶差分。   修改操作   void add(int l,int r,int a,int k) {     d2[l]+=a;     d2[l+1]+=k-a;     d2[r+1]-=(r-l+1)*k+a; &nb...

知识预备   多项式差分   对于一个多项式函数,定义它在x的一阶向前差分为,定义它在x的一阶向后差分为。      定义k阶向前差分：，   定义k阶向后差分：，   定义0阶差分：   多项式差分的性质   (C为常数)；         若,为最高次项系数为的n次多项式，则   若,为n次多项式，则   若，则表示f(x)是一个次数小于等于r的代数多项式(为恒等号，表示全为0)   摘自百度百科：https://baike.baidu.com/item/%E4%B8%80%E9%98%B6%E5%B7%AE%E5%88%86/3937421?fr=aladdin   数组的前缀和以及差分...

The 2019 Ningbo Institute of Technology, ZJU Programming Contest  Super easy: A/K     Easy: B/C/I/J      Medium: D/E/H      Hard: F/G       D. 雷顿女士与分队(hard version)     动态规划    显然先将所有人按能力值大小排序。    表示从1分到第i个位置，矛盾因数的最小值    转移方程：           E. 雷顿女士与平衡树     首先题目显然可以将最大值和最小值分为两部分分别计算。 求最大值的方法：从小到大将每个点与相连的...

T1从NOIP到CSP   tag，字符串模拟，签到题   10pts  输入什么，直接输出。  100pts  按题意模拟即可…  T2可持久化变量   tag，思维，数组，模拟，定位：第二签到题，题意题   30pts  *暴力模拟（一个一个back）  100pts  做一个真正的“可持久化变量”，什么是可持久化，可持久化就是保留所有的历史版本，所以可持久化变量就是数组。然后对于back操作就可以O(1)回退了。  T3doge的取数博弈   tag，博弈，区间DP，定位：中等偏简单题   20pts  if,else判一下  30pts  暴搜一下，或者胡乱贪心都可以。  40pts ...

T1仓鼠的石子游戏    定位：签到题，tag：博弈，思维     题意：n个石圈，两个人轮流对石子进行染色，相邻不能同色，不能操作的人输，问谁赢。   10pts   白送，测试点6主要作用是引导选手发现堆大小为1时后手必败。   40pts   暴力dfs或者状压dp都可以。实际上拿40分不需要打代码，在纸上左右互博一下，然后把答案打个表直接输出即可。   60pts   如果大胆猜想，每一堆的胜负状态其实不随两个人的决策而改变，就会发现输赢其实之和必败堆的奇偶数目有关，所以只要统计必败堆的个数，用必败堆的奇偶数目判断即可。   100pts   无论是通过暴力还是纸上自己推一下画画，都不...

T1   题意：问从1到n有多少个数字在二进制表示下是“反对称01串”，反对称意为对称相反。   10pts   能过样例就是10pts   30pts   写了个大暴力，每次输入n都暴力求   60pts   暴力打了一张1~100000的表，预处理输入直接输出   100pts   显然的是，如果一个数字二进制表示的字符串长度为奇数，一定不符合条件。   我们观察一下前几个符合条件的数字，既然题目与二进制有关，不妨换个视角   10   1010   1100   100110   101010   110100   111000   看出来了嘛？没看出来，没关系，我们把这些数字切一半  ...

T1:手术等级？？？   定位：本场签到题。   题意：给你一个数组，你需要将其切成两部分，每部分的权值等于各自从1开始的下标乘以相应的数组元素。求最小权值和。   0pts   数组越界RE，或者写的错的非常离谱....不然一般会不0分。   10-20pts   看了一眼，100000，好像可以nlog，然后盲狙一个单调写了个二分/三分。如果写了个二分那么一般是10分，运气好一点20分。如果写了个三分就是20分。      50pts   写了n方暴力或者，爆int了，就是50分。   实际上本场比赛有不少人爆了int。   100pts   仔细思考一下   对于第一部分的数组，永远都是...

树上启发式合并(dsu on tree)，也叫静态树链分治模板题,预处理dfn可以节省一个dfs，改写成for循环，常数更小。  #include<bits/stdc++.h> using namespace std; const int MAXN=100005; int n; int g[MAXN],tot,col[MAXN],dfn,u,v; int sz[MAXN],deep[MAXN],fa[MAXN],son[MAXN],L[MAXN],R[MAXN],index[MAXN],skp; long long sum,ans[MAXN]; int cnt[MAXN],nowm...

题目大意：给一颗无根带边权树。支持两种操作：   1、修改某条边的边权。   2、查询当前直径。   点分树模板题，全局开一个multiset维护直径，对于每个重心开一颗线段树和一个局部multiset，用欧拉序线段树维护每一个子树中的最值，然后将其放入局部multiset。接下来取局部multiset中前两大的路径合并扔到全局multiset中，每次直接输出全局multiset的最大值即可。  #include<bits/stdc++.h> using namespace std; const int MAXN=200005,MAXM=400005,MAXBIT=19; stru...

同南昌网络赛，贴过来改改直接过了。   因为不单调，所以不能直接尺取，分治的话可以拿脚写。放宽了时限所以可以接受nlogn的复杂度。   本来直接for是不单调的，但是如果规定分治中点mid，那么过mid往两侧延伸的最小值单调递减，过mid往两侧延伸的前缀和的前缀最大值与前缀最小值也是单调的。   凭空造了两个单调出来，所以可以划窗尺取。分成两种情况，即假设最小值由左侧提供，假设最小值由右侧提供。   最大值只要么由当前对面可结合的前缀和中最大的提供，要么就是最小的提供，所以两种都和当前答案取max即可。    #include <bits/stdc++.h> using name...

同NOIP2004合唱队形，原题DP部分可以直接贴。   题意：求一个最长严格先上升后下降子序列，有两问，输出字典序最小解和字典序最大解。   从后往前DP，使用线段树维护，过程中使用后继数组记录转移过程。然后顺着模拟一遍取出来就行了。思路很简单。  #include<bits/stdc++.h> using namespace std; const int MAXN=300005; long long A[MAXN]; struct tnode {     int dpval;     int maxpos;     i...