题解：AtCoder AT_awc0098_c Highway Discount Pass

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderC - Highway Discount Pass【题目描述】Takahashi is about to drive along a long highway. This highway hasN NNtoll gates lined up in a row, numbered from1 11toN NN, and each toll gatei iiis assigned an identification code consisting of a single lowercase alphabet letter. When the identification codes of theN NNtoll gates are arranged in order of their numbers, a stringS SSof lengthN NNis obtained. That is, thei ii-th character ofS SSis the identification code of toll gatei ii.Takahashi must pass through all toll gates from toll gate1 11to toll gateN NNin ascending order of their numbers. Normally, passing through each toll gate takes a travel time of1 11, so without any optimization, the total travel time isN NN.However, Takahashi has a discount pass. The discount pass is represented by a stringT TTof lengthM MM. By using this discount pass, it may be possible to pass through exactlyM MMconsecutive toll gates together with a travel time of1 11. The discount pass can be used any number of times, but the intervals to which it is applied must not overlap.Specifically, the conditions for applying the discount pass are as follows. For an interval consisting ofM MMconsecutive toll gates, namely toll gatesl , l 1 , … , l M − 1 l, l1, \ldots, lM-1l,l1,…,lM−1(1 ≤ l ≤ N − M 1 1 \leq l \leq N-M11≤l≤N−M1), if the string formed by arranging their identification codes in order (the substring ofS SSfrom thel ll-th character to the( l M − 1 ) (lM-1)(lM−1)-th character) matchesT TT, then the discount pass can be applied to that interval. When applied, thoseM MMtoll gates can be passed together with a travel time of1 11(instead of the usual travel time ofM MM).Takahashi can choose0 00or more intervals to apply the discount pass, but no two chosen intervals may share a common toll gate. It is fine for the last toll gate of one interval and the first toll gate of another interval to have consecutive numbers (i.e., be adjacent).Toll gates not included in any interval where the discount pass is applied are passed individually, each taking a travel time of1 11. If the number of intervals where the discount pass is applied isk kk, the total travel time isk ( N − k M ) N − k ( M − 1 ) k (N - kM) N - k(M - 1)k(N−kM)N−k(M−1).Find the minimum total travel time for Takahashi to pass through all toll gates.高橋即将驾车行驶一条长高速公路。这条高速公路上有N NN个收费站排成一排编号从1 11到N NN每个收费站i ii被分配了一个由单个小写英文字母组成的识别码。当将N NN个收费站的识别码按编号顺序排列时得到一个长度为N NN的字符串S SS。也就是说S SS的第i ii个字符是收费站i ii的识别码。高橋必须按编号升序从收费站1 11通过到收费站N NN。正常情况下通过每个收费站需要1 11的通行时间因此没有任何优化时总通行时间为N NN。然而高橋有一张折扣通行证。该折扣通行证由长度为M MM的字符串T TT表示。通过使用这张折扣通行证可能可以将恰好M MM个连续的收费站一起通过且通行时间仅为1 11。折扣通行证可以使用任意多次但应用的区间不能重叠。具体地应用折扣通行证的条件如下。对于由M MM个连续收费站组成的区间即收费站l , l 1 , … , l M − 1 l, l1, \ldots, lM-1l,l1,…,lM−11 ≤ l ≤ N − M 1 1 \leq l \leq N-M11≤l≤N−M1如果按顺序排列它们的识别码所形成的字符串即S SS从第l ll个字符到第( l M − 1 ) (lM-1)(lM−1)个字符的子串与T TT匹配则可以将折扣通行证应用于该区间。应用时这M MM个收费站可以一起通过通行时间为1 11而不是通常的通行时间M MM。高橋可以选择0 00个或多个区间应用折扣通行证但任意两个选中的区间不能共享同一个收费站。一个区间的最后一个收费站与另一个区间的第一个收费站编号连续即相邻是允许的。未被包含在任何折扣通行证应用区间中的收费站需逐个通过每个通行时间为1 11。如果应用折扣通行证的区间数量为k kk则总通行时间为k ( N − k M ) N − k ( M − 1 ) k (N - kM) N - k(M - 1)k(N−kM)N−k(M−1)。求高橋通过所有收费站的最小总通行时间。【输入】N NNM MMS SST TTThe first line contains an integerN NNrepresenting the number of toll gates and an integerM MMrepresenting the length of the discount pass, separated by a space.The second line contains a stringS SSof lengthN NN, which is the identification codes of the toll gates arranged in order of their numbers.The third line contains a stringT TTof lengthM MM, representing the discount pass.【输出】Output in one line the minimum total travel time for Takahashi to pass through all toll gates.【输入样例】8 3 abcxxabc abc【输出样例】4【算法标签】#KMP【代码详解】#includebits/stdc.husingnamespacestd;constintN1000005;// 最大字符串长度intn,m,cnt;// n: S串长度, m: T串长度, cnt: 选中的匹配区间数量chars[N],p[N];// s: 收费站识别码字符串下标从1开始, p: 折扣通行证字符串intne[N];// KMP的next数组前缀函数ne[i]表示p[1..i]的最长相等前后缀长度vectorintmatches;// 存储所有T在S中匹配的起始位置intmain(){cinnm;// 读入N和M// 读入S串下标从1开始for(inti1;in;i)cins[i];// 读入T串下标从1开始for(inti1;im;i)cinp[i];// KMP预处理求T串的next数组 // ne[i] p[1..i] 的最长相等真前缀和真后缀的长度for(inti2,j0;im;i){while(jp[i]!p[j1])// 不匹配时回退到next[j]jne[j];if(p[i]p[j1])// 匹配成功jj;ne[i]j;// 记录p[1..i]的最长相等前后缀长度}// KMP匹配在S中查找所有T的出现位置 for(inti1,j0;in;i){while(js[i]!p[j1])// 不匹配时回退到next[j]jne[j];if(s[i]p[j1])// 匹配成功jj;if(jm)// 完整匹配了一个T{// 记录匹配起始位置当前位置i减去T的长度再加1matches.push_back(i-m1);jne[j];// 继续匹配回退到next[j]允许重叠匹配}}// 贪心选择不重叠的匹配区间最大化区间数量 // 策略按起始位置排序每次选择最早结束且不与上一个重叠的区间intlast-1;// 上一个选中区间的结束位置for(intpos:matches){intendposm-1;// 当前匹配区间的结束位置if(poslast)// 当前区间起始位置在上一个区间结束之后不重叠{cnt;// 选中该区间lastend;// 更新last为当前区间的结束位置}}// 输出最小总通行时间// 总时间 N - cnt * (M - 1)// 解释每个选中的区间节省 (M-1) 的时间M个收费站一起通过只需1而不是Mcoutn-cnt*(m-1)endl;return0;}【运行结果】8 3 abcxxabc abc 4