题解：AtCoder AT_abc468_b Corridor Watch

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderCorridor Watch【题目描述】You are given integersM , D M,DM,Dand a stringS SSof lengthM MMconsisting ofGand..There areM MMcells arranged in a row from left to right, numbered1 11throughM MMfrom the left.Some of the cells have a guardman standing on them. Specifically, a guardman stands on celli iiifS i S_iSi​G, and no one stands on celli iiifS i S_iSi​..A cell whose distance from a cell with a guardman is at mostD DDis watched by that guardman. That is, a cellx xxis watched by a guardman if there exists a celli iisuch thatS i S_iSi​Gand∣ x − i ∣ ≤ D |x-i|\le D∣x−i∣≤D.Among theM MMcells, find the number of cells that arenotwatched.给定整数M , D M, DM,D和一个长度为M MM、由G和.组成的字符串S SS。有M MM个格子排成一排从左到右编号为1 11到M MM。部分格子上站着守卫。具体地如果S i S_i Si​G则第i ii个格子上站着守卫如果S i S_i Si​.则第i ii个格子上没有人。与有守卫的格子的距离不超过D DD的格子会被该守卫监视。也就是说如果存在某个格子i ii满足S i S_i Si​G且∣ x − i ∣ ≤ D |x - i| \leq D∣x−i∣≤D则格子x xx被守卫监视。求M MM个格子中未被监视的格子数量。【输入】The input is given from Standard Input in the following format:M MMD DDS SS【输出】Output the answer.【输入样例】7 1 .G...GG【输出样例】1【核心思想】问题分析给定M MM个格子和守卫位置每个守卫监视距离不超过D DD的区间。求未被任何守卫监视的格子数量。这是一个差分数组 区间标记问题核心在于高效处理多个区间的覆盖避免对每个守卫的监视范围逐格遍历。算法选择差分数组Difference Array将每个守卫的监视区间[ l , r ] [l, r][l,r]转化为差分数组的两个单点更新最后通过前缀和还原每个格子的监视状态关键步骤读入数据读取M , D M, DM,D和字符串S SS字符串索引调整KaTeX parse error: Double superscript at position 7: S ̲ S使下标从1 11开始差分标记遍历i ii从1 11到M MM若 $S_i $Gl max ⁡ ( 1 , i − D ) l \max(1, i - D)lmax(1,i−D)r min ⁡ ( M , i D ) r \min(M, i D)rmin(M,iD)d i f f [ l ] ← d i f f [ l ] 1 diff[l] \leftarrow diff[l] 1diff[l]←diff[l]1d i f f [ r 1 ] ← d i f f [ r 1 ] − 1 diff[r 1] \leftarrow diff[r 1] - 1diff[r1]←diff[r1]−1前缀和还原i ii从1 11到M MMd i f f [ i ] ← d i f f [ i ] d i f f [ i − 1 ] diff[i] \leftarrow diff[i] diff[i - 1]diff[i]←diff[i]diff[i−1]若d i f f [ i ] 0 diff[i] 0diff[i]0a n s ← a n s 1 ans \leftarrow ans 1ans←ans1输出结果a n s ansans时间/空间复杂度时间复杂度O ( M ) O(M)O(M)遍历字符串一次标记一次前缀和还原空间复杂度O ( M ) O(M)O(M)差分数组差分数组与区间覆盖的核心思想区间操作降维差分数组将区间[ l , r ] [l, r][l,r]的加1 11操作转化为d i f f [ l ] 1 diff[l] 1diff[l]1和d i f f [ r 1 ] − 1 diff[r1] - 1diff[r1]−1两个O ( 1 ) O(1)O(1)操作避免O ( D ) O(D)O(D)的逐格遍历前缀和还原通过一次前缀和遍历将差分数组还原为每个位置的实际覆盖次数。d i f f [ i ] 0 diff[i] 0diff[i]0表示被监视d i f f [ i ] 0 diff[i] 0diff[i]0表示未被监视边界处理l ll和r rr需要限制在[ 1 , M ] [1, M][1,M]范围内防止数组越界多守卫叠加差分数组天然支持多个区间的叠加每个守卫的贡献在前缀和后自动累加适用于区间覆盖、批量标记类基础问题【算法标签】#差分【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将int定义为long long避免数据范围溢出constintN105;// 定义数组最大容量为105intm,d,ans;// m为格子总数d为守卫监视半径ans记录未被监视的格子数量string s;// 存储M个格子的状态G表示有守卫.表示空intdiff[N];// 差分数组用于高效标记每个守卫的监视区间signedmain()// 使用signed main配合#define int long long{cinmd;// 读入格子总数M和监视半径Dcins;// 读入格子状态字符串s s;// 在字符串前添加一个空格使下标从1开始方便处理for(inti1;im;i)// 遍历每个格子{if(s[i]G)// 如果第i个格子有守卫{intlmax(0LL,i-d);// 计算该守卫监视区间的左端点不能小于0intrmin(m,id);// 计算该守卫监视区间的右端点不能超过mdiff[l]1;// 在差分数组的左端点位置加1标记区间开始diff[r1]-1;// 在差分数组右端点的下一个位置减1标记区间结束}}for(inti1;im;i)// 遍历每个格子通过前缀和还原实际监视次数{diff[i]diff[i-1];// 累加差分数组得到第i个格子被多少个守卫监视if(diff[i]0)// 如果第i个格子未被任何守卫监视ans;// 未被监视的格子数量加1}coutansendl;// 输出未被监视的格子总数return0;}【运行结果】7 1 .G...GG 1