10.14 模拟考试 题解报告
目录扯
水题模拟赛
T2 的数据真的...
显然没有什么需要整理的
考试过程
读完题发现好像不是特别难的亚子...
然后 T1
写 写完过不了样例 然后就调 写过了样例之后写暴力 然后写对拍
然后就拍 然后就挂了 然后再调 再拍 再挂...
然后一个小时就没了
理了一下思路 重构代码 然后把对拍挂上 开 T2
想法比较暴力 直接把所有串丢到 Trie 树里面 然后 dfs 大力迭代
半个小时过样例直接跑路
T3 的部分分可以直接暴力 dp
dp 数组是一个 01 的形式 然后尝试构造矩阵 发现确实可以
然后就大力线段树维护矩阵乘
码 调 写了个对拍拍上
又回头自己卡了一下 T2 差不多就三个小时多了
虽然最后 T2 还是没过
T2 最后一个点被构造的数据卡掉了 当时看到这数据的时候蛮惊讶的
大概是这么个情况
看到后面那个 0 KB 大概就知道事情不大对...
读入大概是这样的
然后就被那一个 b 卡没了 dfs 迭代的时候接近跑满...
后来又试了一下 好像把那个 b 删了也跑不过去 但那就是数据的问题了
再然后就是这组输入是没有输出的... 所以如果在 dfs 的时候卡一下时也能过
得分情况
100 + 90 + 100 = 290
差了亿点点...
题解
钟神的题当然没有题解
T1 加加减减
手玩一下数据的话 大概可以发现如果将数组从小到大的话 存在一个分界线 左边全是加 右边全是减 当然这个分界线有可能在两端
全加和全减没什么区别 答案都是原数组最大减最小
再枚举分界线的位置 看一下两边是否分别成为最大值或最小值 更新答案即可
T2 英文分词
_ 的字典序是比字母小的 所以能插的尽量插
把所以串丢到 Trie 里面 然后通过 dfs 进行匹配 贪心的匹配即可
然后这个方法会被最后一个构造的数据卡掉...
卡掉的原因是因为超时 而最后一个点的数据又没有输出
这就启示了对算法的优化:
直接面向数据进行卡时 TLE 之前退出这个点就可以过啦 反正这个点也没有输出(雾
其实个人感觉这样做是没什么问题的
因为原题中有这样的一句话
匹配的代码是这样的
void dfs(int x) {
if(x == m + 1)
{
if(!top) return ;
int l = 0;
for(int i = 1; i < top; ++i)
{
for(int j = l + 1; j <= st[i]; ++j)
putchar(s[j]);
putchar('_'); l = st[i];
}
for(int j = l + 1; j <= st[top]; ++j) putchar(s[j]); pn;
return ;
}
for(int p = 0, i = x; ; ++i)
{
int k = s[i] - 96;
if(!t[p][k]) return ;
p = t[p][k];
if(ed[p])
{
st[++top] = i;
dfs(i + 1);
--top;
}
}
}
贪心的匹配 匹配成功之后标记这个位置 继续匹配下一个位置
卡掉的原因从上面那组数据中也能看出来 几乎每个字符都可以进行匹配 迭代次数太多
复杂度差不多能到 \(O(2^{|T|})\) 这里的 \(T\) 是文本串
那为什么直接卡时不输出呢 因为这个数据如果有输出的话 仅输出就会超时 可行的情况实在太多了
所以能够正常输出的量级卡不掉这个迭代 能卡掉的就没有输出了
当然不排除有这里没想到的数据 但是就算有的话应该也比较难构造
T3 内需消费
首先有一个比较显然的 \(dp\)
设 \(f_{i, 0/1}\) 表示到 \(i\) 位置 手中是否有物品的最大价值
转移考虑买入或卖出
\[f_{i, 0} = \max(f_{i - 1, 0}, f_{i - 1, 1} + a_i)\\ f_{i, 1} = \max(f_{i - 1, 0} - a_i, f_{i - 1, 1}) \]暴力的话直接每次询问 \(dp\) 一遍 \(l \leq r\) 的时候从左向右进行 \(dp\) 否则从右向左进行 \(dp\)
然后这个是需要带修的 考虑能不能通过矩阵乘法进行转移 矩阵也不难构造
定义矩阵运算符 \(\oplus\) :
\[C_{i, j} = \min_{k = 1}^n\left(A_{i, k} + B_{k, j}\right) \]有:
\[\begin{vmatrix} f_{i - 1, 0} & f_{i - 1, 1}\end{vmatrix} \oplus \begin{vmatrix} 0 & -a_i\\a_i & 0 \end{vmatrix} = \begin{vmatrix} f_{i, 0} & f_{i, 1} \end{vmatrix} \]直接上线段树 维护广义矩阵乘
修改就是单点修改 查询就是区间求和
正反各维护一遍即可