8.22 后记

ABFSB一个长\(n(n\le1e5)\)的字符串\(S\)，长\(m(m\le30)\)的字符串\(T\)，\(S\)的每个位置有权值\(a_i\)。\(q(q\le1e5)\)次询问\(l,r\)，求\(T\)作为一个子序列出现在\(S(l,r)\)中的所有方案中，\(T\)出现的位置的权值和。先考虑\(a_i=1\)。显然有\(f_{i,j}=......

#include<bits/stdc++.h>usingnamespacestd;usingpii=pair<int,int>;constexprintN=3e5+5,S=2e3+5,K=1e2+5,INF=0x3f3f3f3f;intn,m,T,poi[N];inthed[N],nxt[N<<2],rch[N<<2],val[N<<2],idx;vo......

模拟3分数：期望100+100+20+20,实际90+90+15+0总体上：思路还是不错的，但是细节地方没有处理到，详情见后面T1/T2/T3/T4的反思。多多少少总是有点毛病。个体上：第一题：连续三个已经想到了，但是我选择了修改最后一个而不是中间。当时贪心的想法是：如果能通过改变最后一个让后面的不合......

有点超模了。签完到跑路。记下做法。T2有字符串\(S\)，\(T\)，且\(|S|=n\)，\(|T|=m\)，均由小写字母构成。一个匹配指\(T\)作为子序列在\(S\)中出现，记匹配位置为\(pos_1,pos_2,\dots,pos_m\)，该匹配的权值为\(\displaystyle\sum_{i=1}^{m}A_{pos_i}\).每次问\(S[l:r]\)与\(......

上午简单排序P5143攀爬者点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=5e4+10;structT{intx,y,z;}a[N];boolcmp(Ta,Tb){returna.z<b.z;//返回是否合法，或者说是否不需要交换}doubledis(inti,intj){returnsq......

关于时间复杂度原来这么麻烦有5种符号：\(Θ：Θ(......

T1令\(DP_{i,k}\)表示当前颜料为\(i\)，前两个盘子状态为\(k\)的最大收益，\(O(16\timesn)\)的DPT2签到题，但数据结构为空时pop应不出东西，若pop出来东西就不属于三种数据结构T3DP，修改的时候往右找覆盖到哪，扫完到下一层继续往右找，图长这样：T4点分治......

T1dp注意赋初值每个点记前&k&大的和，暴力转移T2放到一个序列上双指针，覆盖所有国家T3T4狠狠的DFS......

T1原来组合数有通项公式（大雾）线性求逆元：显然，\(1^{-1}\equiv1(\operatorname{mod}p)\)令\(k=\lfloor\frac{p}{i}\rfloor,j=p\operatorname{mod}i\)，则\(p=i\timesk+j\)则\(0\equivi\timesk+j(\operatorname{mod}p)\)两边同时乘\(i^{-1}\timesj^{-1}\)得\(0......

T1简单题，预处理每段线路要走的次数\(cnt_i\)，如果\(c_i+b_i\timescnt_i\lea_i\timescnt_i\)则买票T2原题，考虑逆向思考倒叙枚举操作，将待查询的点还原到原序列上T3好题对于每个点\((i,j)\)，考虑以这个点为左上角/右下角正方形边长最多为\(l_i/r_i\)对于每一条对角......