TDOG集训
define
\(|s|: 字符串s的长度\)
\(fac_x:x的因数个数\)
Day 1
T1.乘积累加和 已完成
Question：
求C(n,0)*C(n,0)+C(n,1)*C(n,1)…+C(n,n)*C(n,n)，对\(10^9+7\)取模
Analysis：数学
原式可通过二项式定理转化成求 \(C_{2n}^n \bmod 1e9+7\) 。
Solution：
预处理阶乘和逆元。剩余部分可打表。
或者找规律，一般来说有取模的都可以找规律。
T2.字符串操作 已完成
Question：
给定两个由小写字母组成的字符串 \(s,t\)，你可以对 \(s\) 进行以下四种 操作：
1.在任意位置添加任意一个字母，代价为 \(a\)。
2.删除任意一个字母，代价为 \(b\)。
3.替换任意一个字母，代价为 \(c\)。
4.交换相邻两个字母，代价为 \(d\)。
你需要求出将 \(s\) 变为 \(t\) 的最小代价。
Analysis：DP
设计转移方程：\(f_{i,j}\) 字符串 \(s\) 的前 \(i\) 个字符修改的与字符串 \(t\) 前 \(j\) 分字符一致的最低代价
最终目标：\(f_{|s|,|t|}\)
\[f_{i,j}= \begin{cases} f_{i,j-1}+a& \text{操作1}\\ f_{i-1,j}+b& \text{操作2}\\ f_{i-1,j-1}+c& \text{操作3}\\ \end{cases} \]数据范围的 \(a+b \leq 2*d\) ,因此，每个数最多交换一次，且不会再被替换。
操作4：
令 \(pres : s 上一个 t_j 的位置，pret : t 上一个 s_i 的位置\)
则 \(f_{i,j}=f_{pres-1,pret-1}+d+(i-pres-1)*b+(j-pret-1)*a\)
T3 回文自动机 已完成
Question：
给一个只包含小写字母的字符串，求出这个字符串下标为 \([l,r]\) 的子串的回文子串个数(相同的回文子串需重复计数)。
Solution：dp
\(is(i,j):i \to j 是否为回文串\)
设计状态：\(f_{i,j}：i \to j\) 的回文子串个数。
转移方程：\(f[i][j]=f[i+1][j]+f[i][j-1]-f[i+1][j-1]+is(i,j)\)
T4 区间加与区间和 已完成
Question：
给定数列 \(a\)，两种操作，第一种对数列 \(a\) 区间加，第二中求 \(f(a_i)\)的区间和。
其中 \(f(x)\) 表示斐波那契数列第 \(x\)项，\(f(1)=f(2)=1\)
由于询问的答案可能非常大，所以对 \(1e9+7\) 取模
Analysis：矩阵乘法+线段树
看到斐波那契数列和这么大的数据范围，首选矩阵快速幂加速。我们还需要进行，区间加，区间求和，首选线段树维护信息。（拿自己封装的 matrix 类真不错）
Day 2
T1 走迷宫 未完成
T2 最小生成树 已完成
Question：
小A有一张无向图\(G(x)\)，图中每条边的权值可以表达为\(ax+b\)，现在小A想知道对于在\([l,r]\)之间的每一个\(x\)，使得这张图的最小生成树最大的那一个\(x\)，所对应的最小生成树的权值是多少。
Analysis：三分求单峰函数最大值
感性理解，当 \(x\) 逐步上升后，最小生成树的权值之和会形成一个单峰函数。
Solution：
后使用三分去求该函数的最大值。精度要开的高一点。（SXJ开到1e-10才过）
T3 游戏 已完成
Question：
你会依次走过n个点，你有一个能力值，每个点是下面两种之一：
第一种可以选择得到\(a[i]∗p\)的收益，之后能力下降\(k\%\)，\(p\)是你下降之前的能力。
第二种可以选择花费\(a[i]∗p\)，之后能力提升修复\(c\%\)，\(p\)是你提升之前的能力。
你一开始的能力值是\(w\)，求最大收益。
Analysis：
初步发现，当我们做出一次决策时，我们的能力值会发生变化，对后面的继续决策会产生影响。所以考虑从后往前考虑。
Solution：
我们可以算出 \(i \to n\) 1点能力的最大收益。从后往前 \(dp\) 计算出 \(1 \to n\) 1点能力值的最大收益后 \(*w\) 即可。
T4 压位 未完成
Day 3
T1 数字比较 未完成
T2 操作字符串 已完成
Questions：
长度为 \(n\) 的只含有 \(ABC\) 的字符串，选择连续的三个位置 \(ABC\)，如果 \(A\)在目前串的奇数位置就删去 \(AC\)；否则删去 \(B\)，要求最大化可以执行的操作数。
Solution：
我们可以观察到，删除的影响分别如下：
删除B 可以改变 \(B\) 以后字符位置的奇偶性。
删除AC 不可改变后方字符位置的奇偶性。同时还会改变 \(B\) 位置的奇偶性
同时对于一组 \(ABC\) 删去 \(B\) 后，这一组相当于废掉了。所以我们的策略就是尽可能删 \(AC\) ，留着 \(B\) 最后删。
考虑 \(B\) 的位置。
令下标为 \(i\) 的 \(B\) 两边的 \(AC\) 个数为 \(cnt_i\) ，此次操作前删了 \(tot\) 次 \(B\) （改变了几次奇偶性）
若在奇数位置：删除 \(AC\) 后，\(B\) 一定会处于偶数位置，贡献为 \(\min(tot+1,cnt_i)\)。
若在偶数位置：贡献为 \(\min(cnt_i,tot+2)\) ，如果这个 \(B\) 周围只有 \(1\) 对 \(AC\) 且之前进行过奇偶变化，或者是有大于 \(1\) 对 \(AC\) 的。可以删除一对 \(AC\) 。这两种情况都可以使操作数最大化。
T3 权值之和 未完成
T4 三元组 已完成
Question：
给定 \(l,r\)，求 \(l\) 到 \(r\) 之间有多少有序三元组 \((i,j,k)\)，满足 \(l \le i<j<k \le r\) 使得 \(lcm(i,j,k)≥i+j+k\)
Analysis：组合数学+二维数点
正向考虑有解情况较困难，考虑无解情况，即考虑 \(lcm(i,j,k)<i+j+k\)。
对于 \(i < j < k\) 不妨考虑让 \(i = k,j = k\) 则 \(i+j+k<3k\)
又因为 \(lcm(i,j,k)\) 一定是 \(k\) 的倍数，所以只有
\[lcm(i,j,k)= \begin{cases} k\\ 2k\\ \end{cases} \]这两种无解的情况，分类考虑即可。
Solution：
1.\(lcm(i,j,k)=2k\)
暴力打表可发现这种情况只存在 \((3,4,6) (6,10,15)\) 或者其倍数情况。可直接组合数学求出。
2.\(lcm(i,j,k)=k\)
由于 \(l,r \le 2e5\) ,可预处理出每个数的因数。假设我们当前处理到 \(x\) 的第 \(i\) 个因数，则这个因数对答案的贡献为：
\(fac_x-i-1\)。
现在我们可以把一次询问转化为对于 \(l \le k \le r\) 时 \([l,r]\) 区间的答案个数，二维数点即可。
离线处理，按右端点排序，在建立一个树状数组，把约数的贡献插进去。（排序的目的就是保证插贡献时的正确性）
Day 4
T1 砌墙可行性 已完成
Question：
小A要建造一个长为 \(N\) 高为 \(M\) 的墙，现在每一列只有最下方有若干砖头。
小A只有 \(1∗2\) 一种形状的砖头（可以横着或者竖着），给出每一列下方的砖头数量。
问小A还能否建造出一个完整的墙。
以下均使用 \(|\) 代表竖着放，\(-\)代表横着放
Analysis：
可以发现
\(||\) 和 \(=\) 是没有区别的，所以我们尽可能每一列先用 \(|\) 来填满，填不满的就是剩余奇数个单位的地方。
Solution：
我们只考虑需要拼的地方。
如果这一列是奇数，则需要横铺 —，来到第二列，如果铺完一块后仍然还是奇数，则还需再铺 —
像这样，1是竖着放的，0是横着放的
8 1
88 11
888 100
8888 0000
所以我们只需要这样模拟下去直到我铺完横着的结果下一列需要铺的没这么高或者补下面的补出界限了都是无解。
T2 炸鸡 已完成
Question：
肯德基的网红产品炸鸡需要油锅进行生产，这个厨房内，每个锅可以花费 \(x\) 的时间产出一份炸鸡，之后花费 \(z\) 的时间洗锅换油并可以重新投入生产。每个炸鸡产出之后可以放置至多y的时间否则必须扔掉。
一共会有 \(n\) 个时刻。在第 \(t_i\) 个时刻厨房会得到一个订单，要求ai份炸鸡，给出所有的 \(a_i\)，请问厨房最少需要多少个锅才可以满足所有的订单。 \(n \le 5000; t_i,a_i \le 10^9; x,y,z \le 10^9\) 你可以在 \(0\) 时刻以前就开始准备炸鸡 同时保证 \(y<x\)，即每份炸鸡可保存时间不超过制作时间
Solution：二分/优先队列模拟
我是写的二分，不过要考虑太多东西了。（写一下就知道了）
讲讲正解优先队列模拟
先完成第一次炸鸡订单，在考虑后面的订单。当有一次订单完不成时，往前去加锅来满足这个订单。我们按直到某一刻使用这个锅的时间前后进行分类，按时间进行贪心即可。
T3 俱乐部 未完成
T4 边链替换 未完成
Day 5
T1 搭积木 已完成
Question：
小A想搭一个体积不超过 \(m\) 的塔，他有各种大小的立方积木，比如边长为 \(a\) 的积木，体积为 \(a^3\)，现在小A需要你给一个 \(X\)，每次小A会用一个体积不超过 \(X\) 的最大积木，依次到搭好为止，现在他想最大化积木的个数，同时在积木个数最大的情况下使 \(X\) 最大。
Analysis：口胡
每次找离 \(m\) 最近的立方数，则第一块积木大小要么为 \(a^3\) 或者 \((a-1)^3\)。
Solution：
每次都这样找下去，暴力搜索即可。
T3 字符串转换 已完成
Question：
给出两个字符串 \(S\) 和 \(T\) ，他们长度相等，都是由小写字母‘a’、‘b’、‘c组成。每次操作，你可以对字符串S进行如下操作之一：
1、选择S的一个字符‘a’,把该字符变成字符‘b’，费用是cost[0]。
2、选择S的一个字符‘b’,把该字符变成字符‘c’，费用是cost[1]。
3、选择S的一个字符‘c’,把该字符变成字符‘a’，费用是cost[2]。
你的目标是把字符串 \(S\) 变成 \(T\) ，但是总费用不能超过 \(C\)，有多少种不同的操作。
两个操作是不同的定义是：当且仅当他们的操作序列存在某次操作不一样。
Analysis：组合数学
可观察发现，一个字符可以通过三次操作变回自身。这里称之为“转一圈”。我们先让字符串 \(S\) 变成字符串 \(T\) （没有字符转一圈）。令此时还剩的钱数为 \(money\)。
接下来剩余的钱就可以通过不同的位置转一圈来增加操作方法的种类数。
Solution：
我们可以给 \(\lfloor \frac{money}{cost[1]+cost[2]+cost[3]} \rfloor\) 个字符转一圈。
把一种状态看做一个点，把字符串转化为图后，可以把原问题转化为：由原点走到终点，走的边数不超过 \(\lfloor \frac{money}{cost[1]+cost[2]+cost[3]} \rfloor\) 条边的情况个数。
优化状态数，可以让 \(x\) 个字符要变两次，\(y\) 个字符变一次，\(n-x-y\) 个字符不用变，直接矩阵乘法搞。
Day 6
T1 数列 已完成
Question：
已知无穷数列 \(\{ai\}\) 的前两项为 \(a_0\) 和 \(a_1\)，且满足 \(a_i=|a_{i−1}−a_{i−2}|\)。求该数列中出现了多少个不同的数？
Analysis：更相减损术
手动模拟可以看出这是一个更相减损术的过程，通过模拟辗转相除法求解即可。
T2 电梯 已完成
Question：
遥远的迪拜有一栋摩天大楼，这座楼共有 \(ab+1\) 层（\(a,b\) 为正整数），其中最低层为第 \(0\) 层，最高层为第 \(ab\) 层。这座大楼有一个电梯，有趣的是这座电梯只有三个按钮：A、B、0。
假设现在位于第 \(x\) 层，那么这三个按钮每按一次的功能如下：
-
A：如果 \(x+a \le ab\)，则上升至第 \(x+a\) 层，否则不上升；
-
B：如果 \(x+b \le ab\)，则上升至第 \(x+b\) 层，否则不上升；
-
0：回到第 \(0\) 层。
不难发现，这样的电梯不一定能到达所有楼层。这是由于一些楼层尚未完成装修，设计者通过这种电梯的设计来巧妙地避开这些未装修好的楼层。
现在想知道两个问题：
-
从第 \(0\) 层开始，通过电梯能到达多少个楼层；
-
对于任意给定的 \(x\)，从第 \(0\) 层到第 \(x\) 层至少需要按多少次按钮。
Analysis：数学（exgcd+裴蜀定理）
第一个问题：
\(ax+by=c \le ab\) 令 g=\(\gcd(a,b)\)
可得：\(\frac a gx+\frac b g y=\frac c g\)
令 \(A=\frac a g,B=\frac b g,A \perp B\)
即 \(\forall x,y \in \N\)，让\(z \neq ax+by\) 且 \(z < ab\) ，则有
\[\sum_{i=0}^{B-1}[\frac{Ax}{B}]=\frac{(A-1)(B-1)}{2} \]无法表示。
第二个问题：
\(ax+by=c\) \(Min_{x+y}=?\)
令 \(a>b\) ，用exgcd求一组解 \(x_0,y_0\) 使 \(x_0\) 尽可能大即可。
T3 快速傅里叶变换 已完成
Question：
设 \(f(i)\) 表示 \(i\) 的因数个数，求
\[\sum_{i=1}^n\sum_{d \mid i}f(d) \]Analysis：
题目要求我们枚举 \(n\) 以内所有数的因数的因数个数，相当于枚举有哪三个数乘积小于 \(n\)
Solution：
直接枚举三个数，保证递增即可。
T4 平方根 已完成
Question：
给定两个正整数 \(n,m\) 求有多少有序正整数数对 \(A,B\) 满足 \(1 \le A \le n,1 \le B \le m\) 且 \((\sqrt A+\sqrt B)^2\) 是正整数。
Analysis：线性筛+数学
\[(\sqrt A+\sqrt B)^2=A+B+2\sqrt {AB} \]首先，因为 \(A,B \in \Z\)，所以只要满足 \(\sqrt {AB} \in \Z\)，也就是 \(AB\) 是完全平方数。
Solution：
质因数分解可得：
\(A=p_1^{a_1} \times p_2^{a_2} \times…\times p_n^{a_n}\)
\(B=p_1^{b_1} \times p_2^{b_2} \times…\times p_n^{b_n}\)
\(AB=p_1^{a_1+b_1} \times p_2^{a_2+b_2} \times…\times p_n^{a_n+b_n}\)
即 \(A\) 奇数次质数的集合 = \(B\) 奇数次质数的集合，设其乘积为 \(tot\) ，则 \(B\) 就要满足 \(\frac B {tot}\) 为完全平方数，即有 \(\lfloor \sqrt{\frac m t} \rfloor\) 种可能。
线性筛求出每个数的因数，记录每个数的最小质因数。
Day 7
T1 课题选择 已完成
Question：
厦门某中学每个学期都有研学活动，一个月需要提交给 \(n\) 篇论文，论文的内容可以从 \(m\) 个课题中选择。由于课题数有限，可能不得不重复选择一些课题。完成不同课题的论文所花的时间不同。
具体地说，对于某个课题 \(i\)，若计划一共写 \(x\) 篇论文，则完成该课题的论文总共需要花费 \(A_i \times x^{B_i}\) 个单位时间（系数 \(A_i\) 和指数 \(B_i\) 均为正整数）。给定与每一个课题相对应的 \(A_i\) 和 \(B_i\) 的值，请计算出如何选择论文的课题使得可以花费最少的时间完成这 \(n\) 篇论文。
Analysis：优先队列
对于每个课题，一开始写一篇的代价为 \(A_i\)，思考如果还需要写的话，所需要的代价是多少？是\(A_i \times (x^{B_i}-(x-1)^{B_i})\) 。
Solution：
因此，我们可以把写这个课题所需要的代价放入优先队列，取出队头后进行更新代价 \(A_i \times (x^{B_i}-(x-1)^{B_i})\)
再放入队列中。计算答案即可。
Code：
struct tim{
ll a,b,now,x;
bool operator<(const tim& A)const{return now>A.now;}
}a[N];//a,b 两个系数 now 下一篇论文需要花的钱 x 已经写了的篇数
priority_queue<tim> task;
inline ll power(ll a,int b){
ll res=1;
while(b){
if(b&1) res=res*a;
a*=a;b>>=1;
}
return res;
}
int main(){
cin>>n>>m;
for(rint i=1;i<=m;i++){
ll x,y;scanf("%lld%lld",&x,&y);
a[i]={x,y,x,0};task.push(a[i]);
}
while(n--){
auto t=task.top();task.pop();
ans+=t.now;
t.x=t.x+1;//更新信息
t.now=t.a*power(1ll*(t.x+1),t.b)-t.a*power(1ll*(t.x),t.b);//更新下一篇论文的价格
task.push(t);
}
cout<<ans<<endl;
return 0;
}
T2 序列变换 已完成
Question：
你有一个长度为 \(n\) 的序列，初始时，这个序列为\(1,2,⋯,n\)。
你要支持 \(m\) 个操作，第 \(i\) 个操作给出一个正整数 \(q_i\)，要求:
-
将序列不断复制并连接到序列末尾,直到序列长度不小于 \(q_i\);
-
然后，截取序列的前 \(q_i\) 个数并删除剩余部分。
由于操作后的序列可能很长，为了检验你是否正确进行了这些操作,请在所有操作结束之后,输出 \(1,2,⋯,n\) 中的每个数在序列中各出现了多少次。
Analysis：
我们会发现，如果有一个 \(q_i >= q_{i+1}\) 那这次切割是没有任何作用的。所以这里的 \(q_i\) 是递增的，如果不是则可以忽略。
Solution：
我们从后往前考虑 \(q_i\) ，考虑 \(q_i\) 是 \(q_{i-1}\) 的多少倍，往前去查看这个位置应该放置为多少。
T3 摆棋子 已完成
Question：
有一个 \(n\) 行 \(m\) 列的棋盘，有些格子上有障碍。具体来说，第 \(i\) 行的前 \(a_i\) 个格子和后 \(b_i\) 个格子上均有障碍. 要求在棋盘中摆一些棋子（障碍的位置不能放棋子），使得任意两个棋子不在同一行或同一列，求最多能放多少个棋子。
Solution：贪心/set
把空白的部分看做一条条的区间，按左端点排序，每次都选择右端点最左的行进行放置。
T4 寻宝难题 未完成
Day 8
T1 集合与函数 已完成
Question：
小明有 \(n\) 个互不相同的正整数：\(p_1,p_2,⋯,p_n\) ，还有两个正整数 \(a, b\)。
他想把这些整数分到两个集合 \(A\) 和 \(B\) 里边，每个数只能属于一个集合。同时要符合下面条件：
定义函数 \(f(x)=a−x, g(x)=b−x\)， 则
-
如果 \(x\) 属于 \(A\)，那么 \(f(x)\) 也要属于 \(A\) 。
-
如果 \(x\) 属于 \(B\)，那么 \(g(x)\) 也要属于 \(B\) 。
判断一下是否存在一种方案来分配这些数字到集合 \(A\)，\(B\) 中。如果存在，输出 \(YES\)，否则输出 \(NO\)。
空集也是一种集合，所以如果一个集合为空集也是可以的。
Solution：建图
只要一个数 \(x\) 与另一个数 \(y\) 构成 \(f(x)=y\) \(g(x)=y\) \(f(y)=x\) \(g(y)=x\) 这样的函数关系都连边。
序列里只要有 \(2x=a\) 或者 \(2x=b\) 一定有解，或者链的大小为偶数的也有解。
T2 破损的键盘 已完成
Question：
输入包含多组数据。每组数据占一行，第 \(i\) 组数据中包含不超过 \(a_i（a_i≤100100）\)个字母、下划线、字符“[”或者字符“]”。其中字符 "[" 表示 Home 键，“]”表示 End 键。
Analysis：deque模拟/指针
我考场上选了 \(deque\)。毕竟能前面、后面都可以插入的我只想到 \(deque\)。好像 \(list\) 也行？官方题解使用指针做
Solution：
需要注意的是当我们从后往前（按了 \(home\)）输入文本时，一个一个按顺序插进去会导致顺序出问题。举个例子
\(1[12\) 如果一个个插会变成 \(211\) 而我们要的是 \(121\) 。所以我们要开一个字符串暂存一下插入的字符然后倒序插入。
T3 树 已完成
Question：
小 \(E\) 和小 \(C\) 是两个 \(OIer\)。他们经常一起玩和树有关的游戏。有一天，他们得到了一棵由 \(N\) 个节点，\(N−1\) 条边组成的无色的树。于是便玩起了给树染色的游戏。
一开始，整棵树都是无色的。小 \(E\)（先手）和小 \(C\)（后手）轮流给树染色。每次染色，小 \(E\) 可以选择一个未染色的节点并将其染成黑色。同样的，每次染色小 \(C\) 也可以选择一个未染色的节点并将其染成白色。如果最后存在一个黑色节点，不存在任意的一个白色节点与其相邻，则小 \(E\) 获胜。否则小 \(C\) 获胜。如果双方都采取最优策略，那么谁会获胜？
Solution：
注意大写 OrzE OrzC
我们玩一下这个游戏可以发现，我们染黑色染叶子结点，对方一定会染其父亲节点；反之，我们染父亲节点，若我们未染色的儿子大于1个，黑色就可以获胜。
我们的方法就是从叶子开始，一个儿子和一个父亲删，删到出现剩余的儿子则黑色赢；反之白色赢。
T4 神奇的矩阵 未完成
Day 9
T1 伐木工 已完成
Question：
有 \(n\) 棵树，初始时每棵树的高度为 \(H_i\)，第 \(i\) 棵树每月都会长高 \(A_i\)。现在有个木料长度总量为 \(S\) 的订单，客户要求每块木料的长度不能小于 \(L\)，而且木料必须是整棵树（即不能为树的一部分）。现在问你最少需要等多少个月才能满足订单。
Analysis：
我爱暴力。
Solution：
我们把每棵树生长到最低高度 \(L\) 的时间从小到大进行排序，令 \(time_i\) 表示 第 \(i\) 棵树需要长到大于等于 \(L\) 的时间。
前缀生长值：\(sumA_i\) 前缀基本高度：\(sumH_i\)
假设我们当前遍历到第 \(i\) 棵树，因为时间有排序，所以前 \(i\) 棵在此时高度都是合法的。
计算总高度：\(sumA_i \times time_i + sumH_i\)
如果大于 \(S\) 了就输出当前的 \(time_i\)
考虑极端情况：所有树都长得大于等于 \(L\) 时总高度仍未到 \(S\)
所需时间：\(\lceil (S-sumH_n)/sumA_n) \rceil\)
为什么 \(95\)
T2 填算式 已完成
Question：
填算式是一种简单的数学游戏，可以形式化描述如下：\(n\) 个数字 \(a_1,a_2,···,a_n\) 排成一排 \(（1 \le a_i \le 9）\)，相邻两个数字之间有一个空格。
你可以在每个空格内填入运算符 \(+,−,\times\) 之一，也可以不填，要求得到的算式的运算结果等于 \(k\)。
你的任务是计算有多少种不同的正确算式。比如 \(n=3\)，\(3\) 个数字为 \(2,2,2\)，\(k=24\) 时，有两种不同的正确算式：，\(22+2=24，2+22=24\)。
Analysis：搜索
就对于每一位，看你接下来是要 \(+,-,\times,合并\) ，计算最终结果即可。
Solution：
直接搜索，复杂度上界也就 \(O(4^{13})\) ，只不过为了方便，我们可以多传点参数方便我们计算。可以这样写。
void work(int pos,int sum,int a,int b){
if(pos==n){if(sum+a*b==k) ans++;return ;}
#define nxt (pos+1)
work(nxt,sum,a,b*10+num[nxt]);//合并
work(nxt,sum+a*b,1,num[nxt]);//加法
work(nxt,sum+a*b,-1,num[nxt]);//减法
work(nxt,sum,a*b,num[nxt]);//乘法
#undef nxt
return ;
}
T3 文本匹配 已完成
Question：
一般的文本编辑器都具有查找功能，即在文本文件中查找某个模式串的出现位置。形式化地，对于文本 \(s\) 和模式串 \(t\)，定义 \(s[l,r]\) 为 \(s\) 从第 \(l\) 个字符到第 \(r\) 个字符的子串，则文本编辑器可以找出 \(l,r\) 使得 \(t\) 匹配 $s[l,r]。
模式串可以包含通配符 * 和 ?，其中 * 代表匹配任意多个（可以是 0 个）字符，? 代表匹配 1 个（不可以是 0 个）字符。模式串 \(t\) 匹配文本 \(s\) 的条件是，能够将 \(t\) 中的通配符 * 替换成任意多个字符，? 替换成 1 个字符，使得替换后的模式串 \(t\) 与 \(s\) 相等。
现在，给定文本串 \(s\) 以及 n 个模式串 \(t_i\)，请你对于每个 \(t_i\) 找出它在 \(s\) 中的第一个匹配位置 \(s[l,r]\)（若有多个匹配，输出 \(l\) 最小的一个，若仍有多个，输出 \(r\) 最小的一个）。为了方便起见，\(s\) 中只含数字、大小写字母和下划线，\(t_i\) 中只含数字、大小写字母、下划线和通配符。
Analysis：字符串哈希
差一步想到正解的沙子。
就是字符串哈希，只不过要把模式串拆开来匹配。
Solution：
如果是 * ，就把 \(t\) 在 * 处拆成两段，把另一段往后匹配直到成功。
如果是 ？，就把 \(t\) 在 ? 处拆成两段，另一端往后一格继续匹配。注意，? 前如果是空串也需要记录
T4 简单计数 未完成
Day 10
T1 QQ空间的说说 已完成
Question：
不写了。
Analysis：DAG跑概率DP/暴力
不会DAG跑概率DP，直接暴力。（有点卡时间）
Solution：
\(ans_i\) ：第 \(i\) 个大写字母的概率。
\(val_i\) ：第 \(i\) 道题目被选到的概率
预处理出 \(1 \to 10^7\) 的逆元 \(inv_i\)
对于第 \(i\) 题选项是大写字母t，直接
\(ans_t=ans_t+val_i*inv_m\) 。
对于第 \(i\) 题选项是题目编号t，直接
\(val_t=val_t+val_i*inv_m\) 。
T2 乘与加 已完成
Question：
你有 \(n\) 个数字 \(x_1,x_2,⋯,x_n\) ，初始值均为 \(0\) 。
你可以进行若干轮操作，每轮操作你可以将某个 \(x_i\) 变为 \(x_i+1\) ，或者让所有 \(x_i\) 变为 \(2*x_i\) 。
求最少经过多少次操作能将其变成给定的目标状态。
Analysis：逆向思维+贪心
令目标状态为 \(S\)
直接考虑好像有些困难，我们可以把原问题转化为：有两种操作
- 把 \(S\) 中的一个元素 \(-1\)
- 把 \(S\) 都除以二（必须整除，也就是所有的元素均为偶数）
使 \(S\) 变为全 \(0\) 。
Solution：
解法显而易见，整体除以 \(2\) 显然比单单一个元素 \(-1\) 来得快，证明显然。所以我们如果有奇数就把这些奇数全部 \(-1\)，然后再一起除以 \(2\)。