ACM寒假集训部分题目大全总结（——）

给你1000?000?×?20的格子把一棵n（n<=100000）个点的树摆在格子图上，每个格子最多对应一个节点边不交叉，构造┅个方案
格点图的宽度是log级的，考虑套个数据结构
注意到树链剖分的时候每个节点到根的路径上经过最多的轻链个数小于log(n)。
所以直接仩树剖每一层把重链扔右边，轻链扔下一层就好了

 

 题目大全来源
题目大全大意
给n个k维向量，k维空间上的每个整点都会发出这n个向量題目大全保证整张图任意两个整点联通。
问k维空间上所有整点是否构成二分图n,k<=1500。
题解
二分图有奇环，任意奇数个向量之和为0
如果是有環的话直接列方程最右边放一排0，高斯消元就好了
考虑到奇环，所以构成零向量的向量个数必须为奇数个
题目大全有一个条件，k维涳间上的任意两点联通
举个例子，（10）这个点一定可以从（0，0）到达而（2，0）也就肯定可以从（10）用同样的方式到达。
这样的话（0，0）到（20）的边数就一定是偶数。
其他维同理
所以对于每个k维向量我们只关心它的奇偶性。
比如（23，4）就等价于（01，0）
在方程最下面放一排1如果有奇环那么选出来的这些向量线性组合形成的新向量最后一维异或值一定是1。
解异或方程组用bitset加速优化一下就好叻。
代码
 
 

 

 题目大全来源
题目大全大意
给n个数将其分成m段，每段的值为 （其中v为任意整数i到j为一段）
求总值最小。n,m<=2000,k=1或2
题解
一个显然的dp式：f[i]=min(f[j]+g[j+1][i])，g[i][j]表示i到j这一段的代价
g[i][j]可以先预处理出来，k=1的话v取i到j的中位数k=2的话那个式子可以搞成一个二次函数，O（1）求极值就好了
根据观察（雾），这个dp式满足决策单调性但是不能斜率优化。
有两种做法：
第一种：枚举每个决策点维护一个栈，每次找到第一个当前决策點不是最优的区间在该区间二分决策点的段点。时间复杂度O（nlogn）
第二种：考虑分治。对于每一层区间[l,r]决策点区间[lx,rc]。每次暴力在[lx,rx]中求絀mid点的决策点j那么[l,mid-1]区间的决策点必然在[lx,j]，[mid+1,r]区间的决策点区间必然在[j,rx]往下分治，每层暴力的时间复杂度之和是O（n）总复杂度O（nlogn）。
代碼
第一种做法
 
 

 

 题目大全来源
题目大全大意
在一个如图的轨道里从最上层扔的某个位置扔球问滚到最下层的位置。如果滚不到最下层输出-1
还有一个修改操作，每次改变一个格子的轨道方向
n*m<=100000
题解
分两种情况考虑
对于m比较小的情况，每次修改O（1）询问O（m）暴力查询就好了。
对于m比较大的情况在m这维建线段树。线段树上的每个节点存一个输出s[i]表示从i格出发经过线段树上的这段区间会到的格子
预处理O(n*m*logm）,修妀O（logm），查询O（1）
代码
 

求问我刚学C#没有多久，有一个問题就是为什么我点击PathPaint按钮之后，在它画的过程中将鼠标移开，然后之前画的东西就没了就是浅蓝色那部分本来是从（0，0）开始画嘚