昨天训练时有一道并不难的dp题 http://codeforces.com/gym/103202/problem/H
大意是有n种卡，每种卡有d,k,c三个属性，表示有效时间，使用次数和价格，每张卡可以买任意次，也可以不用卡。再给出m天，用$p_i,q_i$表示一个人要在$p_i$天买$q_i$次东西，问最小代价。
阅读全文
MorphLing
9月 30, 2021
LGV引理给出网格图上两个起点$a_1,a_2$和两个终点$b_1,b_2$，每次只能往右或往上走一步，问$a_1\rightarrow b_1$和$a_2\rightarrow b_2$的所有路径方案中，两条路径没有相交点的方案数
用$e(a,b)$表示从a走到b的方案总数，则$ans=e(a_1,b_1)e(a_2,b_2)-e(a_1,b_2)e(a_2,b_1)$
理解：利用容斥，从$e(a_1,b_1)e(a_2,b_2)$中减去那些存在相交的方案。已知$e(a_1,b_2)e(a_2,b_1)$中每种方案的路径一定相交，对于每个交点，两条路径交点要么在交点处交换位置，要么像是“在交点处反弹了”一样没有交换位置（如下图）
阅读全文
MorphLing
8月 15, 2021
03. Forgiving Matching题意：给出长度为n的原串S和模式串T，串由’1’,’2’,…,’9’和通配符’*’构成，问对于$k\in[0,n-1]$，S的子串中满足失配位置小于等于k的子串个数
用FFT/NTT卷积计算字符匹配数。单独考虑每个字符，如字符’1’，将S和T串根据位置上是否为’1’转化为一个0/1串，若$s[i]=t[j]=1$，则开始位置在$i-j+1$的子串匹配数+1，用数组$cnt[i]$记录开始位置在$i$的子串的匹配数，有$cnt[i]=\sum\limits_{j=1}^ns[j]t[j-i+1]$。
将T串反置为T’，即$t[j-i+1]=t’[n-(j-i+1)+1]=t’[n-j+i]$，就有$cnt[i]=\sum\limits_{j=1}^ns[j]t’[n-j+i]$，发现这个东西就可以用卷积计算了。$cnt[i]$的结果在卷积之后$n+i$的位置。
还需要注意的是通配符的处理，可以用一个容斥计算通配符的影响，将每个位置的结果直接加上两个串同通配符的总数，然后减去两个通配符相匹配的情况，两个通配符相匹配的情况计算方法同上。
阅读全文
MorphLing
7月 30, 2021
B. Sample Game题意：有一个随机数生成器，每个数生成的概率为$p_i$，不断生成直到最后一个数小于先前的任意一个数时停止，共生成x个数，问$x^2$的期望
首先可以把$x^2$分解为$1+3+\cdots+(2x+1)$，即从每一步的增量考虑转移方法，若当前长度为x，则增量为2x+1，考虑增量的期望$E(2x+1)=2E(x)+1$，于是只要借助$E(x)$就能进行转移了
因此可以先处理出$f[i]$表示第一个数为$i$时的期望长度$E(x)$，$f[i]=(\sum\limits_{j=i+1}^nf[j]p_j+p_if[i]+\sum\limits_{j=1}^{i-1}p_j)+1$
再通过$f[i]$计算$f2[i]$，表示第一个数为$i$时长度平方的期望$E(x^2)$，$f2[i]=\sum\limits_{j=i+1}^n p_j(f2[j]+2f[j]+1)+p_i(f2[i]+2f[i]+1)+4\sum\limits_{j=1}^{i-1}p_j$
答案为$ans=\sum\limits_{i=1}^nf2[i]p_i$
阅读全文
MorphLing
7月 28, 2021
自闭场，题都没读几道
B. Black and white题意：给定一个n*m的棋盘，起初全白，将一个格子染黑需要代价$a[i][j]$，若某个矩形的四个角里有三个已经是黑色，则将第四个角染黑不需要任何代价，问将整个棋盘染黑的最小代价
转化为一个联通性问题，点1~n代表1~n行，点n+1~n+m代表1~m列，i和j+n之间连一条边权为$a[i][j]$用的边。$(i,j+n)$联通代表$(i,j)$这个格子已被染黑，于是将整个棋盘染黑等价于整张图联通，即求该图的最小生成树
为啥问题等价呢，考虑$(i,j)$联通的两种可能性：
$(i,j+n)$连了一条边，说明直接染黑
$(i_1,j_2)$通过一些中间边如$(i_1,j_1),(i_2,j_1),(i_2,j_2)$联通，意味着$(i_1,j_1),(i_2,j_1),(i_2,j_2)$已被染黑，显然这四个点构成矩形的四个角，$(i_1,j_2)$可以不花费代价染黑
阅读全文
MorphLing
7月 25, 2021
I love tree题意：给一棵树，每次操作选择一条链，从起点到终点点权依次增加$1^2,2^2,…n^2$，单点询问当前点权
容易想到树剖，然后考虑在线段树上维护这个问题
发现可以转化成选择一段区间$[l,r]$，对于每个点$x$，该位置增加的值为$(x-h)^2$，把平方项展开后得到$x^2+h^2-2xh$，对这三项分别线段树维护即可（分别维护$x^2,-2x$出现的次数和$h^2$的和）
有时候dfs序和修改顺序是反的，就是对于区间$[l,r]$，每个点增加量分别是$n^2,(n-1)^2,…,1^2$，实际上就是每个位置增加量变为$(h-x)^2$，h为r+1，而显然$(x-h)^2=(h-x)^2$，因此这种情况下线段树不需要进行任何修改，只要调整传入的h参数即可
树剖时还需要稍微注意的是，这里对链的修改存在先后顺序，常规的树剖对于两个端点x,y是一起往上跳的，那么这里只在x往上跳时修改，y往上跳时先用vector记录哪些点需要修改，等x修改完再去修改y
阅读全文
MorphLing
7月 24, 2021
06. Xor sum07. Pass!09. KD-Graph10. zoto题意：给出一个序列，离线查询m个区间$[l_i,r_i]$中，在数值区间$[d_i,u_i]$中有多少个不同的数，n=1e5
首先考虑在数值区间上维护问题，也就是维护一个支持单点修改和区间查询的数据结构，很容易想到用线段树之类的方法实现$O(\log n)$的修改和查询
离线查询若干个区间，可以再想到莫队算法，每次修改复杂度$O(\sqrt n)$，查询$O(1)$，将上述两种结构合并后发现，修改复杂度达到了$O(\sqrt n\log n)$，显然超时
于是为了使总复杂度限制在$O(n\sqrt n)$，需要在数值区间上维护一个$O(1)$修改，$O(\sqrt n)$查询的做法，这个方法就是分块，维护$num[i]$记录数i出现的次数，$sum[i]$记录第i个块中不同数的个数，两者合并起来刚好是$O(n\sqrt n)$
阅读全文
MorphLing
7月 20, 2021
B. CannonG. League of Legends题意：给定n个区间，要求将它们分成k组，每组之间有交，最大化每组交长度之和
简化问题，对于如果一个大区间能够完整包含某个小区间，则该大区间只有两种最优决策：
单独归为一组，贡献r-l
与任意一个其包含的小区间归为一组，不对结果产生影响
可以用反证法证明结论，假如大区间和其他区间归为一组，那么将该大区间移出该组，该组的交一定不下降，再放入其包含的小区间组中，小区间所在的组的交也不下降，即大小区间在同一组的决策一定最优
于是可以把所有大区间取出来，单独讨论所有小区间，可以发现，若将剩下的区间按照左端点从小到大排序，其右端点也一定是有序的，接着考虑dp，$f[i][j]$表示考虑前i个区间，分成j组的最优答案，而一组的贡献只与最左和最右两个区间相关，显然有转移$f[k][j+1]=\max\limits_{r[i+1]-l[k]>0} \{f[i][j]+r[i+1]-l[k]\}$
阅读全文
MorphLing
7月 20, 2021