训练记录
3月
实时场比赛记录
ABC 396 赛时 AC 4题
CF Round 1008 赛时AC 3题 +79
CF Round 1009 Div.3 赛时AC 5题 +102， CF rating 达到1600分
Edu 场 B Wa8 掉大分
一部分些题解分享:
用BFS搜出所有的联通块， 然后用位运算简化墙壁的判断
题目给出的优先级需要处理，调整枚举顺序就不需要特判优按照哪个方位先输出
Floyd
按照时间戳更新每个节点的联通情况，然后每次更新针对新增的边跑Floyd
很水的一道F
给你一个树根1和q个操作
操作1： 一个数 在某个节点后增加一个节点
操作2： 两个数 把某棵树和它的子树的值都增加x
问q次操作之后每个节点的值分别是多少
dfn序 + 树状数组维护
先建立整棵树，假设所有的节点都存在
记录每个节点遍历到的时间戳和它的子树大小， 之后连续的一段大小必然都是它的子树
然后增加操作就直接把子树范围用树状数组增加， 如果到某个节点了，之前的操作要清空，加上相反数即可清空整棵子树。
这里用BIT add先构建一个差分数组，最后直接O(1)复杂度查询前缀和即是当前点的值
题意:
给一个数组a有n个数，q次询问，每次询问都是独立的。
每次询问输入一个数x
从数组的最右边开始，如果x 比ai大，那么吃掉这个数,x变成x^ai，然后往左走。
如果x比ai小，停止，输出吃掉数的个数。
发现一个性质：
x最高位如果比ai大，则一定可以吃掉，并且最高位保持不变
如果最高位比ai小，停止
最高位与ai一样，那么有两个可能，停止，或者吃掉然后最高位减小
用一个数组prei,j记录第i个数之前最高位大于等于j的数的最大下标
这样x就可以不断往前跳，时间复杂度n*logW
CF 2000 D. Game With Triangles
题意两条线上分别有n, m个点， 两条线之间的距离为2。
有操作f : 取得一条线上选2个点， 另一条线上选1个点所围成的三角形的面积。
记最多能操作k次
输出：
两行
第一行 k
第二行 k个整数 第i个表示 操作i次取得的面积总和的最大值
反悔贪
如果两边都能取， 取最大
有一边点的数量为0时， 而另一边至少有3个点, 如果能回退就回退
这个题目在实现的时候因为一个指针某个地方忘记自减调了好几个个小时，最后对拍找到样例才发现qwq
树状数组 单点修改+区间查询
关键是将查询离线后按照右端点排序
如果一个元素出现多次， 就之按照它最右边出现的位置统计一次贡献
用一个数组维护某个值最后出现的位置
立方差公式然后不等式放缩，得到一个式子，发现是一个对称轴<0的二次函数求整数零点，
二分答案即可，二分的时候有一边是三次项会爆long long, 可以移项放到右边。
很巧妙的贪心
暴力BFS，当时想法建立两个queue，那这样几乎不可做
用一个queue+结构体好写很多
线段树二分 简单的区间修改，用树状数组更优
位运算，图论
每一位都是独立的，因此可以拆位。
对于每一位，由于异或边的限制，只要确定其中一个位，其他的位都定了
所以可以对于每个未访问的联通块，假定某位为0跑一遍BFS即可,如果不如为1的个数少，则反转所有位
逆序对处理三
数位DP
dp[i][j] 表示第i位开头为j的符合条件的数的数目
收集区间答案的时候要仔细