【题解】牛客练习赛53

A:
dp[i][0]表示长度为 i 且最后一个字符是‘c’的情况数,dp[i][1]
表 示 长 度 为 i 且 最 后 一 个 字 符 是 ‘ y ’ 的 情 况 数 。
dp[i+1][0]=dp[i][1],dp[i+1][1]=dp[i][0]+dp[i][1]。
B:
交换一下顺序得: ，对于每个j,第二重循环可以分为 块，每一块可以暴力计算。 可以根据上一次循环递推。总时间复杂度: 。
C:
设三个二进制串a,tag,q。若询问的第i位为’_’,则q[i]=0,tag[i]=0。若第i位为0,则q[i]=1,tag[i]=0。若第i位为1，则q[i]=1,tag[i]=1。对于一个确定的文本串，若第i位为0,a[i]=0,否则a[i]=1。对于每一位，若a[i]&q[i]==tag[i]，则询问的串和这个文本串匹配。然后bitset优化一下，或按位压缩成long long。
D:
骰子归类一下只有 C(9,6)种，对于给定的数字，每个字符出现的顺
序不影响结果，只需统计每个字符出现了多少次。对于每种骰子，与
它六个面上的数字连边，跑网络流即可。
E:
每一个i找到 i左边离i最近的j使得a[j]^a[j+1]...^a[i]=0，
令 对于d[i]=j。b 数组初始化为无穷大。询问离线处理，按照询问的 R 从小到大排序。从 1~n 处理每一个位置 ，设当前处理到i, 令
b[d[i]]=min(b[d[i]],i-d[i]+1), 对于R==i的询问，求
min(b[L],b[L+1],...,b[R])即可。

F:
令
原式=




现在问题转化为求
分段考虑，



+
+...
+

=
=

同理求得

预处理一下前缀和，前缀和的前缀和，前缀和平方的前缀和，每次询问可以O(1)处理。
std:
A:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41391429
B:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41391433
C:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41391437
D:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41391453
E:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41391459
F:
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41391456