Weekly Recorded

· · 个人记录

补题。

abc345_d：暴搜，但是有一些 trick。

$Solution~2$ : 全排列每个方块，然后通过直接填左上角来判断该排列是否合法，不必要 $O(1)$ 判断，但是加上也可以。 对于 $n\le10$ 的题目应该跟位运算脱不了关系。 [abc345_e](https://atcoder.jp/contests/abc345/tasks/abc345_e)：一眼 $dp$ ，但是解法较为复杂。 $dp$ $O(n\times k^2)$ 显然，考虑优化。 感觉当前的转移应该不会和太前面的状态有太大关系，能不能只进行最大值和次大值不同颜色的球之间的转移呢？ 那么就尝试记录每一次 $dp[i][j][0/1]$ 的最后一个球的颜色 $c[i][j][0/1]$ 就可以进行转移了。 判断烦人，建议 $sort$。 [abc345_f](https://atcoder.jp/contests/abc345/tasks/abc345_f)：一个连通块一个连通块的去判断，搜出一棵生成树，每次去删最外围的点和边即可。感觉会比 $E$ 和 $D$ 的代码量简单一些。 当然题目中 $k$ 为奇数是无解的。 本场难度惊人。 关于题目是否可以倒序解，满足以下几点要求即可。 - 题目关系有顺序限制。“顺序”为决定题目答案的关键因素之一。 - 倒序方便 - 能从最后一个关系推到倒数第二个关系，直至第一个关系 3.30 本周记录： - 大%你调不会 - 二分判不会 - 逐渐唐氏 [abc346_f](https://atcoder.jp/contests/abc346/tasks/abc346_f): 凭自己能力做出来的 $f$ 题，首先数据范围大，$n \le 10^{12}

那么你要求出来 k ，肯定得二分。

二分的同时要记录第 i 个字符 c 字符出现的位置，前缀和即可。

md被hack了调半天才调出来

abc346_g:

令一个三元组 $(a,b,c)$ 为 $pos_{x_{i-1}},i,pos_{x_{i+1}}$ 。 每次更新的时候先添加当前的 $(i,x,y)$ 为 $[x ,y-1]+1$。 然后先删除当前的 $(x,i,y)$ 为 $[i ,y-1]-1$。 最后统计所有区间内所有出现次数大于等于 $1$ 的点。 ----- 如果 $dp$ 能写记忆化，那就写记忆化。 大写字母转小写字母异或 $32$。 线段树 $pair$ 维护区间出现次数最小的数和个数。