两道机考题题解整理题目一好看的串题目描述小华有一个好看的串A。对于一个串每次可以选择其中任意两个相邻且相同的字符然后删除其中一个。例如aabbbbaa可以一次操作变成abbbbaa aabbbaa aabbbba如果串X可以通过若干次删除操作得到串A则X也是好看的串。现在给定目标串A和字符串S需要计算S中有多少个子串是好看的串。位置不同的相同子串算不同子串。样例 1输入1 1 a b输出0解释S中只有一个子串b无法通过删除相邻相同字符得到a。样例 2输入3 6 aab aaabbb输出6解释目标串A aab压缩后为a:2, b:1所以合法子串必须是若干个连续的a后接若干个连续的b并且a至少 2 个b至少 1 个。合法子串为aaab aaabb aaabbb aab aabb aabbb共6个。题解思路删除相邻相同字符只会让某个连续段变短不会改变连续段的字符顺序也不会让某一段完全消失。所以先把目标串A按连续字符压缩。例如A aab压缩成字符段a b 长度 2 1一个子串合法当且仅当子串的连续字符段序列和A一样子串每一段长度都大于等于A对应段长度。然后枚举S的所有子串用indx表示当前匹配到目标串的第几段用cnt表示当前段长度。代码#includeiostream#includevector#includestringusingnamespacestd;string A,S;intn,m;intmain(){cinnmAS;vectorcharch;vectorintneed;// 压缩目标串 Afor(inti0;in;){intji;while(jnA[j]A[i])j;ch.push_back(A[i]);need.push_back(j-i);ij;}intkch.size();longlongans0;// 枚举子串左端点for(intl0;lm;l){intcnt0;intindx0;// 枚举子串右端点for(intrl;rm;r){if(S[r]ch[indx]){cnt;}else{// 上一段长度不够失败if(cntneed[indx])break;// 进入下一段indx;// 段数超过目标串失败if(indxk)break;// 新段字符不匹配失败if(S[r]!ch[indx])break;// 当前字符是新段的第一个字符cnt1;}// 已经匹配到最后一段并且长度够if(indxk-1cntneed[indx]){ans;}}}coutans\n;return0;}复杂度时间复杂度O(m^2) 空间复杂度O(n)题目二数据传输网络最小时延题目描述有N个数据交换节点编号为0到N - 1。数据包从节点0开始按编号顺序依次经过每个节点到达节点N - 1。每个节点i默认产生delay[i]单位处理时延。如果在节点i配置优先转发模式它会影响本节点和后续win_size[i]个节点。受影响节点j的处理时延会减少opt_delay[i]如果多个节点同时影响j则可以重复减少但最终时延不能小于0。最多选择K个节点配置优先转发模式求最小总处理时延。约束3 N 50 0 K 10 0 win_size[i] 3样例 1输入3 1 50 40 30 3 0 1 0 50 10输出80解释选择节点1最优节点1的处理时延从40降到0。总时延50 0 30 80样例 2输入5 2 10 20 30 40 50 1 0 1 3 2 15 20 0 30 35输出65解释选择节点0和节点3最优。节点0影响节点0和1节点 0: 10 - 0 节点 1: 20 - 5节点3影响节点3和4节点 3: 40 - 10 节点 4: 50 - 20总时延0 5 30 10 20 65题解思路不能贪心因为一个节点的收益会受到其他节点是否被选的影响。关键限制是win_size[i] 3所以处理节点i时最多只有这几个节点能影响它i - 3, i - 2, i - 1, i因此可以用状态压缩 DP只记录前面 3 个节点是否被选。定义dp[i][used][mask]表示已经处理完前 i 个节点也就是 0 ~ i - 1 已经选择了 used 个节点 最近 3 个节点的选择状态为 mask 此时的最小总时延其中mask的含义bit0i - 1 是否被选 bit1i - 2 是否被选 bit2i - 3 是否被选每次处理节点i枚举当前节点选或不选。代码三维 DP 写法#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN,K;cinNK;vectorlonglongdelay(N),opt_delay(N);vectorintwin_size(N);for(inti0;iN;i)cindelay[i];for(inti0;iN;i)cinwin_size[i];for(inti0;iN;i)cinopt_delay[i];constlonglongINF4e18;// dp[i][used][mask]vectorvectorvectorlonglongdp(N1,vectorvectorlonglong(K1,vectorlonglong(8,INF)));dp[0][0][0]0;for(inti0;iN;i){for(intused0;usedK;used){for(intmask0;mask8;mask){if(dp[i][used][mask]INF)continue;// take 0 表示不选 i// take 1 表示选择 ifor(inttake0;take1;take){if(usedtakeK)continue;longlongreduce0;// 当前节点 i 被选会影响自己if(take){reduceopt_delay[i];}// 检查 i - 1, i - 2, i - 3 是否能影响 ifor(intd1;d3;d){intpi-d;if(p0)continue;// mask 第 d - 1 位表示 i - d 是否被选if((mask(d-1))1){if(pwin_size[p]i){reduceopt_delay[p];}}}longlongcurDelaydelay[i]-reduce;if(curDelay0)curDelay0;// 下一轮处理 i 1// bit0 表示 i 是否被选// bit1 表示 i - 1 是否被选// bit2 表示 i - 2 是否被选intnewMask((mask1)7)|take;dp[i1][usedtake][newMask]min(dp[i1][usedtake][newMask],dp[i][used][mask]curDelay);}}}}longlongansINF;// 最多选 K 个所以 used 可以小于等于 Kfor(intused0;usedK;used){for(intmask0;mask8;mask){ansmin(ans,dp[N][used][mask]);}}coutans\n;return0;}复杂度时间复杂度O(N * K * 8 * 2 * 3) 空间复杂度O(N * K * 8)因为N 50K 10状态数量很小可以轻松通过。